Column generation based heuristic for tactical planning in multi-period vehicle routing

M. Mourgaya 1 François Vanderbeck 1, 2
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : The periodic vehicle routing problem (PVRP) consists in establishing a planning of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. The tactical planning model considered here restricts its attention to scheduling visits and assigning them to vehicles while leaving sequencing decisions for an underlying operational model. The objective is twofold: to optimize regional compactness of the routes in a desire to specialize routes to restricted geographical area and to balance the workload evenly between vehicles. Approximate solutions are constructed using a truncated column generation procedure followed by a rounding heuristic. This mathematical programming based procedure can deal with problems with 50–80 customers over five working days which is the range of size of most PVRP instances treated in the literature with meta-heuristics. The paper highlights the importance of alternative optimization criteria not accounted for in standard operational models and provides insights on the implementation of a column generation based rounding heuristic.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2007, 183 (3), pp.1028-1041. 〈10.1016/j.ejor.2006.02.030〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00342598
Contributeur : François Vanderbeck <>
Soumis le : jeudi 27 novembre 2008 - 17:20:34
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

Collections

Citation

M. Mourgaya, François Vanderbeck. Column generation based heuristic for tactical planning in multi-period vehicle routing. European Journal of Operational Research, Elsevier, 2007, 183 (3), pp.1028-1041. 〈10.1016/j.ejor.2006.02.030〉. 〈inria-00342598〉

Partager

Métriques

Consultations de la notice

186