A column generation based heuristic for ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
A column generation based heuristic for the generalized vehicle routing problem with time windows
Auteur(s) :
Yuan, Yuan [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
SEMET, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Vigo, Daniele [Auteur]
Alma Mater Studiorum Università di Bologna = University of Bologna [UNIBO]
Integrated Optimization with Complex Structure [INOCS]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
SEMET, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Vigo, Daniele [Auteur]
Alma Mater Studiorum Università di Bologna = University of Bologna [UNIBO]
Titre de la revue :
Transportation Research Part E: Logistics and Transportation Review
Pagination :
102391
Éditeur :
Elsevier
Date de publication :
2021
ISSN :
1366-5545
Mot(s)-clé(s) en anglais :
generalized vehicle routing problem
time windows
last mile delivery
delivery options
trunk/in-car delivery
time windows
last mile delivery
delivery options
trunk/in-car delivery
Discipline(s) HAL :
Informatique [cs]/Recherche opérationnelle [cs.RO]
Résumé en anglais : [en]
The generalized vehicle routing problem with time windows (GVRPTW) is defined on a directed graph G = (V, A) where the vertex set V is partitioned into clusters. One cluster contains only the depot, where is located a ...
Lire la suite >The generalized vehicle routing problem with time windows (GVRPTW) is defined on a directed graph G = (V, A) where the vertex set V is partitioned into clusters. One cluster contains only the depot, where is located a homogeneous fleet of vehicles, each with a limited capacity. The other clusters represent customers. A demand is associated with each cluster. Inside a cluster, the vertices represent the possible locations of the customer. A time window is associated with each vertex, during which the visit must take place if the vertex is visited. The objective is to find a set of routes such that the total traveling cost is minimized, exactly one vertex per cluster is visited, and all the capacity and time constraints are respected. This paper presents a set covering formulation for the GVRPTW which is used to provide a column generation based heuristic to solve it. The proposed solving method combines several components including a construction heuristic, a route optimization procedure, local search operators and the generation of negative reduced cost routes. Experimental results on benchmark instances show that the proposed algorithm is efficient and high-quality solutions for instances with up to 120 clusters are obtained within short computation times.Lire moins >
Lire la suite >The generalized vehicle routing problem with time windows (GVRPTW) is defined on a directed graph G = (V, A) where the vertex set V is partitioned into clusters. One cluster contains only the depot, where is located a homogeneous fleet of vehicles, each with a limited capacity. The other clusters represent customers. A demand is associated with each cluster. Inside a cluster, the vertices represent the possible locations of the customer. A time window is associated with each vertex, during which the visit must take place if the vertex is visited. The objective is to find a set of routes such that the total traveling cost is minimized, exactly one vertex per cluster is visited, and all the capacity and time constraints are respected. This paper presents a set covering formulation for the GVRPTW which is used to provide a column generation based heuristic to solve it. The proposed solving method combines several components including a construction heuristic, a route optimization procedure, local search operators and the generation of negative reduced cost routes. Experimental results on benchmark instances show that the proposed algorithm is efficient and high-quality solutions for instances with up to 120 clusters are obtained within short computation times.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03439212/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03439212/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 2021_A%20column%20generation%20heuristic%20for%20the%20GVRPTW.pdf
- Accès libre
- Accéder au document