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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00342598
Contributor : François Vanderbeck <>
Submitted on : Thursday, November 27, 2008 - 5:20:34 PM
Last modification on : Friday, July 26, 2019 - 11:58:03 AM

Identifiers

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⟩

Share

Metrics

Record views

252