Pickup and delivery problems with autonomous and electric vehicles

Problèmes de collecte et livraison avec véhicules autonomes et électriques Cette thèse étudie de nouveaux problèmes de Pickup et Delivery dans lesquels des véhicules autonomes et électriques sont utilisés. Les problèmes de Pickup et Delivery sont des problèmes d'optimisation définis sur des structures de graphes. Dans ce type de problèmes, il y a une flotte de véhicules qui desservent des demandes de transport parmi différents nœuds du graphe. Chaque demande de transport exige le transport d'une charge d'un nœud d'enlèvement à un nœud de livraison. Des fenêtres de temps sont associées aux demandes. L'objectif de ces problèmes est de desservir toutes les demandes de transport dans leurs fenêtres de temps respectives en minimisant une fonction objective donnée, comme par exemple la distance totale parcourue par les véhicules. La principale contribution de cette thèse est l'introduction de nouveaux problèmes de Pickup et Delivery motivés par les nouveaux systèmes de mobilité qui émergent avec les véhicules autonomes et électriques. En particulier, la première partie de la thèse introduit une nouvelle classe de problèmes de Pickup et Delivery définis sur des graphes circulaires. Chacun des problèmes de cette classe diffère par la composition de la flotte, la présence de fenêtres temporelles et la fonction objectif à optimiser. Ces problèmes trouvent une application dans le contexte des véhicules autonomes. En effet, l'exploitation de véhicules autonomes sur des infrastructures distinctes telles que des rails, des voies de guidage ou des voies surélevées, réduit les interactions avec les piétons, les véhicules à conduite humaine et d'autres obstacles. De telles infrastructures ont souvent des topologies particulières telles que des circuits. La deuxième partie de la thèse présente un nouveau problème de Pickup et Delivery où la flotte est composée de véhicules électriques à batterie (BEV) qui remplacent leurs batteries usagées dans des stations d'échange de batteries (BSS) alimentées par l'énergie solaire. L'aspect innovant de ce problème est la gestion optimale de l'énergie utilisée par les véhicules. En effet, l'énergie en surplus est vendue, et l'objectif est de desservir toutes les demandes de transport en maximisant le profit réalisé par la vente de l'énergie en surplus. Dans le chapitre 1, un contexte important et introductif sur les concepts utilisés dans cette thèse est fourni. Dans le chapitre 2, les problèmes de Pickup et Delivery sur des anneaux sont introduits. Un système de classification est proposé, ainsi que des études de complexité et des formulations de programmation linéaire en nombres entiers (PLNE). Le chapitre 3 contient la preuve de la NP-durété du problème V, 1|sd, u|CLT (introduit dans le chapitre 2) car la preuve est trop longue. Le chapitre 4 se focalise sur les problèmes de Pickup et Delivery sur des anneaux avec une fonction objectif de temps total de complétion. La complexité de toutes les variantes du problème dans cette classe est étudiée et une formulation ILP est proposée. Dans le chapitre 5, les problèmes de Pickup et Delivery sur des anneaux sont étudiés lorsque les véhicules peuvent circuler dans le sens des aiguilles d'une montre ou dans le sens inverse sur l'anneau. Un nouvel algorithme est proposé pour la variante la plus simple de cette classe de problèmes. Le chapitre 6 présente le problème de Pickup et Delivery de véhicules électriques avec gestion de l'énergie. Les principales caractéristiques de ce problème sont au nombre de trois :1. Des véhicules électriques sont utilisés pour desservir les demandes de transport;2. L'énergie utilisée pour recharger les batteries des véhicules électriques est produite dans une centrale photo-voltaïque qui est adjacente au dépôt de véhicules;3. L'énergie peut être soit utilisée pour recharger les batteries, soit vendue au réseau électrique. Si l'énergie produite n'est pas suffisante pour recharger les batteries, elle peut également être achetée. (...)