A Column Generation Algorithm for a Rich Vehicle-Routing Problem

Alberto Ceselli (), Giovanni Righini () and Matteo Salani ()
Additional contact information
Alberto Ceselli: Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy
Giovanni Righini: Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy
Matteo Salani: Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy, and EPFL ENAC INTER TRANSP-OR, CH-105 Lausanne, Switzerland

Transportation Science, 2009, vol. 43, issue 1, 56-69

Abstract: We present an optimization algorithm developed for a provider of software-planning tools for distribution logistics companies. The algorithm computes a daily plan for a heterogeneous fleet of vehicles that depart from different depots and must visit a set of customers for delivery operations. In this rich vehicle-routing problem (VRP), we consider multiple capacities; time windows associated with depots and customers; incompatibility constraints between goods, depots, vehicles, and customers; maximum route length and duration; upper limits on the number of consecutive driving hours and compulsory drivers' rest periods; the possibility of skipping some customers and using express courier services instead of the given fleet to fulfill some orders; the option of splitting up the orders; and the possibility of open routes that do not terminate at depots. Moreover, the cost of each vehicle route is computed through a system of fees depending on the locations visited by the vehicle, the distance traveled, the vehicle load, and the number of stops along the route. We developed a column generation algorithm where the pricing problem is a particular resource-constrained elementary shortest-path problem, solved through a bounded bidirectional dynamic programming algorithm. We describe how to encode the cost function and the complicating constraints by an appropriate use of resources, and we present computational results on real instances obtained from the software company.

Keywords: vehicle routing; column generation (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1080.0256 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:43:y:2009:i:1:p:56-69

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().