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

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 v...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2007-12, Vol.183 (3), p.1028-1041
Main Authors: Mourgaya, M., Vanderbeck, F.
Format: Article
Language:English
Subjects:
Branch and bound
Combinatorial optimization
Heuristic
Heuristics
Integer programming
Mathematical programming
Optimization
OR in strategic planning
Routing
Studies
Vehicles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2006.02.030