Heuristics for an oil delivery vehicle routing problem

Companies distributing heating oil typically solve vehicle routing problems on a daily basis. Their problems may involve various features such as a heterogeneous vehicle fleet, multiple depots, intra-route replenishments, time windows, driver shifts and optional customers. In this paper, we consider...

Full description

Saved in:
Bibliographic Details
Published in:Flexible services and manufacturing journal 2014-12, Vol.26 (4), p.516-539
Main Authors: Prescott-Gagnon, Eric, Desaulniers, Guy, Rousseau, Louis-Martin
Format: Article
Language:English
Subjects:
Computation
Customers
Distributing
Distribution planning
Engineering
Fuels
Heuristic
Integer programming
Linear programming
Machines
Manufacturing
Motor vehicle fleets
Operations Management
Operations Research/Decision Theory
Processes
Production methods
Replenishment
Route optimization
Route selection
Studies
Vehicles
Windows (intervals)
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:Companies distributing heating oil typically solve vehicle routing problems on a daily basis. Their problems may involve various features such as a heterogeneous vehicle fleet, multiple depots, intra-route replenishments, time windows, driver shifts and optional customers. In this paper, we consider such a rich vehicle routing problem that arises in practice and develop three metaheuristics to address it, namely, a tabu search (TS) algorithm, a large neighborhood search (LNS) heuristic based on this TS heuristic and another LNS heuristic based on a column generation (CG) heuristic. Computational results obtained on instances derived from a real-world dataset indicate that the LNS methods outperform the TS heuristic. Furthermore, the LNS method based on CG tends to produce better quality results than the TS-based LNS heuristic, especially when sufficient computational time is available.
ISSN:1936-6582
1936-6590
DOI:10.1007/s10696-012-9169-9