Models and Algorithms for Last Mile Delivery ...
Document type :
Thèse
Title :
Models and Algorithms for Last Mile Delivery Problems with Multiple Shipping Options
English title :
Modèles et Algorithmes pour les Problèmes de Livraison du Dernier Kilomètre avec Plusieurs Options d'Expédition
Author(s) :
Yuan, Yuan [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Integrated Optimization with Complex Structure [INOCS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Integrated Optimization with Complex Structure [INOCS]
Thesis director(s) :
Frédéric Semet
Defence date :
2019-10-14
Jury president :
Dominique Feillet [Président]
Yves Crama [Rapporteur]
Guido Perboli [Rapporteur]
Claudia Archetti
Martine Labbé
Caroline Prodhon
Yves Crama [Rapporteur]
Guido Perboli [Rapporteur]
Claudia Archetti
Martine Labbé
Caroline Prodhon
Jury member(s) :
Dominique Feillet [Président]
Yves Crama [Rapporteur]
Guido Perboli [Rapporteur]
Claudia Archetti
Martine Labbé
Caroline Prodhon
Yves Crama [Rapporteur]
Guido Perboli [Rapporteur]
Claudia Archetti
Martine Labbé
Caroline Prodhon
Accredited body :
Ecole Centrale de Lille
Doctoral school :
École doctorale Sciences pour l'ingénieur (Lille)
NNT :
2019ECLI0011
Keyword(s) :
Livraison du dernier kilomètre
Livraison dans le coffre / dans la voiture
Problème du voyageur de commerce généralisé
Problème de tournées de véhicules généralisé
Fenêtres de temps
Branch-and-cut
Livraison dans le coffre / dans la voiture
Problème du voyageur de commerce généralisé
Problème de tournées de véhicules généralisé
Fenêtres de temps
Branch-and-cut
English keyword(s) :
Last mile delivery
Trunk/in-car delivery
Generalized traveling salesman problem
Generalized vehicle routing problem
Time windows
Branch-and-cut
Trunk/in-car delivery
Generalized traveling salesman problem
Generalized vehicle routing problem
Time windows
Branch-and-cut
HAL domain(s) :
Informatique [cs]/Autre [cs.OH]
French abstract :
Dans cette thèse, nous étudions les problèmes de tournées de véhicules dans le contexte de la livraison du dernier kilomètre lorsque plusieurs options de livraisons sont proposées aux clients. Le mode de livraison le plus ...
Show more >Dans cette thèse, nous étudions les problèmes de tournées de véhicules dans le contexte de la livraison du dernier kilomètre lorsque plusieurs options de livraisons sont proposées aux clients. Le mode de livraison le plus commun est la livraison à domicile ou au travail. La livraison peut également être effectuée dans des points de collecte tels que des consignes ou des magasins. Ces dernières années, un nouveau concept appelé livraison dans le coffre / dans la voiture a été proposé. Avec ce mode de livraison, les colis des clients peuvent être livrés directement dans les coffres des voitures. Notre objectif est de modéliser et de développer des approches de résolution efficaces pour les problèmes de routage dans ce contexte, dans lequel chaque client peut disposer de plusieurs lieux potentiels de livraison. Premièrement, nous proposons un état de l'art sur les problèmes de routage non-Hamiltoniens. Ensuite, nous étudions le cas avec un seul véhicule, qui est modélisé comme un problème du voyageur de commerce généralisé avec fenêtres de temps (GTSPTW). Quatre formulations en programme linéaire à variables mixtes et un algorithme efficace de branch-and-cut sont proposés. Ensuite, nous étudions le cas multi-véhicules, dénommé problème de tournées de véhicules généralisé avec fenêtres de temps (GVRPTW). Une heuristique efficace basée sur la génération de colonnes est proposée pour le résoudreShow less >
Show more >Dans cette thèse, nous étudions les problèmes de tournées de véhicules dans le contexte de la livraison du dernier kilomètre lorsque plusieurs options de livraisons sont proposées aux clients. Le mode de livraison le plus commun est la livraison à domicile ou au travail. La livraison peut également être effectuée dans des points de collecte tels que des consignes ou des magasins. Ces dernières années, un nouveau concept appelé livraison dans le coffre / dans la voiture a été proposé. Avec ce mode de livraison, les colis des clients peuvent être livrés directement dans les coffres des voitures. Notre objectif est de modéliser et de développer des approches de résolution efficaces pour les problèmes de routage dans ce contexte, dans lequel chaque client peut disposer de plusieurs lieux potentiels de livraison. Premièrement, nous proposons un état de l'art sur les problèmes de routage non-Hamiltoniens. Ensuite, nous étudions le cas avec un seul véhicule, qui est modélisé comme un problème du voyageur de commerce généralisé avec fenêtres de temps (GTSPTW). Quatre formulations en programme linéaire à variables mixtes et un algorithme efficace de branch-and-cut sont proposés. Ensuite, nous étudions le cas multi-véhicules, dénommé problème de tournées de véhicules généralisé avec fenêtres de temps (GVRPTW). Une heuristique efficace basée sur la génération de colonnes est proposée pour le résoudreShow less >
English abstract : [en]
In this thesis, we study routing problems that arise in the context of last mile delivery when multiple delivery options are proposed to the customers. The most common option to deliver packages is home/workplace delivery. ...
Show more >In this thesis, we study routing problems that arise in the context of last mile delivery when multiple delivery options are proposed to the customers. The most common option to deliver packages is home/workplace delivery. Besides, the delivery can be made to pick-up points such as dedicated lockers or stores. In recent years, a new concept called trunk/in-car delivery has been proposed. Here, customers' packages can be delivered to the trunks of cars. Our goal is to model and develop efficient solution approaches for routing problems in this context, in which each customer can have multiple shipping locations. First, we survey non-Hamiltonian routing problems. Then, we study the single-vehicle case in the considered context, which is modeled as a Generalized Traveling Salesman Problem with Time Windows (GTSPTW). Four mixed integer linear programming formulations and an efficient branch-and-cut algorithm are proposed. Finally, we study the multi-vehicle case which is denoted Generalized Vehicle Routing Problem with Time Windows (GVRPTW). An efficient column generation based heuristic is proposed to solve itShow less >
Show more >In this thesis, we study routing problems that arise in the context of last mile delivery when multiple delivery options are proposed to the customers. The most common option to deliver packages is home/workplace delivery. Besides, the delivery can be made to pick-up points such as dedicated lockers or stores. In recent years, a new concept called trunk/in-car delivery has been proposed. Here, customers' packages can be delivered to the trunks of cars. Our goal is to model and develop efficient solution approaches for routing problems in this context, in which each customer can have multiple shipping locations. First, we survey non-Hamiltonian routing problems. Then, we study the single-vehicle case in the considered context, which is modeled as a Generalized Traveling Salesman Problem with Time Windows (GTSPTW). Four mixed integer linear programming formulations and an efficient branch-and-cut algorithm are proposed. Finally, we study the multi-vehicle case which is denoted Generalized Vehicle Routing Problem with Time Windows (GVRPTW). An efficient column generation based heuristic is proposed to solve itShow less >
Language :
Anglais
Collections :
Source :
Files
- https://tel.archives-ouvertes.fr/tel-03229424/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-03229424/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-03229424/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-03229424/document
- Open access
- Access the document
- document
- Open access
- Access the document
- Yuan_Yuan_DLE.pdf
- Open access
- Access the document