Optimisation spatio-temporelle des routes pour les problèmes de livraison de colis par services postaux

Je souhaite tout d'abord remercier mes directeurs de recherche, Guy Desaulniers et Louis-Martin Rousseau, pour l'aide qu'ils m'ont apportée tout au long de ce doctorat, par leur soutien et leur bienveillance.Merci pour votre suivi, vos nombreux commentaires toujours pertinents et vos innombrables relectures (particulièrement Guy) qui ont dû, par période, monopoliser votre temps.Merci de me l'avoir accordé pendant toutes ces années et me permettre, enfin, de conclure ce chapitre enrichissant d'éducation académique.Merci à la compagnie Giro, et en particulier Charles Fleurent et son équipe avec laquelle j'ai eu la chance de travailler et d'échanger, de m'avoir permis de rendre plus concret mon travail dans le milieu industriel.Merci à eux, ainsi qu'au CRSNG pour leur soutien financier tout au long de mes études doctorales.J'aimerais aussi remercier Nicolas Zufferey, ainsi qu'Alain Hertz et Antoine Legrain d'avoir accepté d'évaluer mes travaux et d'être sur mon jury de thèse.Je remercie aussi Andrea Lodi qui a présidé le jury de mon oral de présentation de thèse et qui m'a donc permis de continuer mes recherches.Merci à François Lessard pour son aide capitale dans l'implémentation de nouvelles fonctionnalités dans GENCOL, sa disponibilité et ses retours positifs.Cela a été un plaisir de travailler avec toi.Merci à Adil Tahir qui m'a épaulé au cours du dernier chapitre et avec qui nous avons eu de nombreuses séances d'idéation très enrichissantes.Merci au personnel du CIRRELT et du GERAD, en particulier Serge Bisaillon pour son partage de connaissances en termes d'implémentation et Guillaume Michaud pour l'assistance technique et matérielle.Merci à l'équipe du tarot du GERAD, où on retrouve Guy, mais aussi les fidèles Serge, Alain, François, Matthieu, Sébastien, Carole, Frédéric, Hugues et les autres.Votre accessibilité m'a permis de passer des dîners très conviviaux tout en diminuant significativement mon aversion au risque : nous sommes rarement à bien plus qu'une belle garde-contre de la tête !Merci bien entendu à Coralie, celle avec qui je partage ma vie depuis bientôt quatre ans déjà, pour son soutien indéfectible dans les hauts et bas d'un doctorat.La vie est plus facile et motivante quand on se sent aimé, merci de me donner tout ça.Pour rester dans le thème, merci aussi à mes parents qui, malgré la distance et certaines difficultés à me laisser partir si loin d'eux, m'ont toujours encouragé et poussé dans mes v choix sans jamais les remettre en question.Merci à ma sœur, mon frère et aussi mes deux nièces pour les chaleureuses retrouvailles familiales à chacun de mes retours en France.Merci à mes colocataires, présents et passés, pour leur joie de vivre et les instants de légèreté que nous avons pu passer ensemble, avec une mention spéciale à Rémi, Anaïs et Valentin qui sont devenus bien plus que de simples colocataires.Merci à mes coéquipiers de basket, Sébastien, Charlotte, Dimitri, Juanma (European Dream Team), Louis, Ian, Alex, Johnny, et tant d'autres passionnés de la balle orange avec qui j'ai pu me vider la tête et épuiser mon corps, mais aussi à coach Richard qui m'a donné tant de confiance en moi.Merci à Tim', pour tous ces bons moments, notamment quelques longues séances de jeu nocturnes, entremêlées de fous rires et qui m'ont parfois peut-être couté un peu de productivité matinale... Merci à Florian, qui a traversé le doctorat avec moi et qui se retrouve dans pas mal des groupes sus-cités, qui m'a beaucoup aidé et inspiré par sa méthodologie mais aussi son ouverture au monde.vi RÉSUMÉ En raison d'une forte croissance du commerce en ligne, combinée à un recul significatif du courrier transactionnel, les services postaux ont dû, au cours des dix dernières années, s'adapter à un marché en métamorphose.En effet, le courrier traditionnel et la livraison de colis ne se gèrent pas de la même façon.Pour le courrier postal, les facteurs sont généralement assignés à des zones géographiques dans lesquelles ils doivent visiter toutes les adresses sur toutes les rues au cours de leur tournée.En ce qui concerne les colis, seulement quelques résidents ou commerçants doivent être visités, et l'encombrement des divers colis oblige les livraisons à s'effectuer par camion.Parmi les clients à visiter, certains présentent des contraintes horaires, appelées fenêtres de temps, période durant laquelle leur colis doit être livré.Cette contrainte provient généralement d'accords entre les services postaux et leurs clients (généralement des entreprises).Depuis quelques années, des contrats de livraison en moins de 24H ou 48H peuvent aussi être à l'origine de ces fenêtres de temps.Le problème de livraison de colis dans le milieu postal possède quelques caractéristiques qui lui sont propres.Le nombre de clients par route est relativement conséquent (traditionnellement entre 50 et 150 clients par route) et la capacité des camions n'est généralement pas limitante.En revanche, la durée des tournées est une mesure essentielle dans ce genre de problème, la durée des journées de travail des livreurs en dépendent.Il est bon de noter que le temps de service, comprenant entre autres stationnement du véhicule, récupération du colis dans le camion et livraison en mains propres, compte pour une part conséquente de la durée des routes et que ce temps est incompressible.Au cours des dernières années, les compagnies postales ont cherché à assigner à leurs livreurs des routes plus compactes pour diverses raisons.Cela permet notamment d'augmenter la connaissance du quartier des livreurs (travaux, embouteillages réguliers aux heures de pointe, etc.) et ainsi améliorer leurs performances.Dans certaines compagnies pour lesquelles les livreurs reçoivent une récompense pour chaque colis livré, cela peut aussi permettre un retour plus rapide chez un client absent.Dans cette thèse, nous présentons les outils mis en place pour optimiser les caractéristiques spatio-temporelles des routes dans ce contexte postal.Ce dernier étant très dynamique, puisque les clients peuvent changer d'un jour à l'autre, nous cherchons à développer des méthodes donnant les meilleurs résultats possibles en peu de temps, et ce malgré la taille conséquente des instances.L'intégralité des projets présentés par la suite a été réalisée en collaboration avec Giro Inc., la compagnie montréalaise ayant développé GeoRoute, un logiciel vii d'optimisation utilisé par de nombreuses compagnies postales à travers le monde.Dans la première partie de cette thèse, nous expliquons en quoi la durée des routes peut être un avantage aussi bien stratégique que purement économique.En effet, en nous intéressant au problème de voyageur de commerce avec fenêtres de temps, nous mettons en place des méthodes pour essayer de trouver le meilleur équilibre économique entre temps de parcours et durée de la tournée, le temps des livreurs étant une ressource précieuse et limitée.En plus de ceci, nous développons une méthode permettant de résoudre des instances postales de très grande taille (jusqu'à près de 500 clients) avec très peu de fenêtres de temps en mélangeant agrégations de clients, programmation par contraintes et programmation en nombres entiers.Nous observons que, dans un contexte où il existe des fenêtres de temps, le chemin le plus court n'est pas forcément le moins coûteux, car il faut prendre en considération les éventuels temps d'attente.Dans le deuxième projet, nous nous intéressons particulièrement à la notion de compacité.À partir d'une compacité géographique considérée comme exacte et calculée comme étant l'aire de l'enveloppe convexe des clients d'une route, nous proposons deux approximations de cette mesure.Par la suite, nous les testons, aussi bien sur des instances académiques que sur des instances dérivées de données du monde industriel, en ajustant un algorithme combinant recherche à voisinage large et génération de colonnes heuristique.Dans ce projet, nous nous limitons à des instances de taille moyenne, relativement à la nature du problème, c'est-à-dire ne dépassant pas les 500 clients.Nous pouvons analyser à travers les résultats obtenus sur les instances académiques que, lorsqu'il existe de nombreuses fenêtres de temps, la compacité des routes ne peut être améliorée qu'au détriment d'un temps de parcours plus long.En revanche, quand les fenêtres de temps sont moins nombreuses comme c'est le cas avec les données réelles, la prise en compte de la compacité peut avoir l'effet d'un guide pour notre méthode, permettant ainsi, en un temps limité, d'améliorer à la fois la compacité et le temps de parcours de chacune des routes.La troisième partie de cette thèse est une extension du projet précédent, appliqué à des instances industrielles de très grande taille (jusqu'à plus de 3000 clients).Gérer de telles instances amène de nouveaux défis.Nous présentons donc plusieurs techniques pour rendre les temps de calcul raisonnables sans impacter la qualité des solutions.Tout d'abord, nous limitons l'espace de recherche de façon dynamique autour de la solution courante afin de favoriser l'obtention de routes améliorantes.Ensuite, nous utilisons une méthode de décompositions successives du problème, à taille variable pour limiter les effets de bord, pour intensifier la recherche dans toutes les zones géographiques de l'instance.Nous montrons alors que notre heuristique permet d'obtenir des routes plus compactes sans dégrader la qualité de la solution viii par rapport à d'autres méthodes négligeant l'aspect compacité.ix

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.