A branch-and-price algorithm for a vehicle ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
A branch-and-price algorithm for a vehicle routing with demand allocation problem
Auteur(s) :
Titre de la revue :
European Journal of Operational Research
Pagination :
523-538
Éditeur :
Elsevier
Date de publication :
2019-01-16
ISSN :
0377-2217
Mot(s)-clé(s) en anglais :
Routing
Vehicle routing-allocation problem
Logistics and distribution
Branch-and-price
Dynamic programming
Vehicle routing-allocation problem
Logistics and distribution
Branch-and-price
Dynamic programming
Discipline(s) HAL :
Sciences de l'Homme et Société/Gestion et management
Résumé en anglais : [en]
We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the ...
Lire la suite >We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.Lire moins >
Lire la suite >We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :