Exact and Heuristic Solution of the Consistent Vehicle-Routing Problem

Dominik Goeke (), Roberto Roberti () and Michael Schneider ()
Additional contact information
Dominik Goeke: School of Business and Economics, RWTH Aachen University, 52062 Aachen, Germany
Roberto Roberti: Department of Information, Logistics and Innovation, VU Amsterdam, 1081 HV Amsterdam, Netherlands
Michael Schneider: School of Business and Economics, RWTH Aachen University, 52062 Aachen, Germany

Transportation Science, 2019, vol. 53, issue 4, 1023–1042

Abstract: Providing consistent service by satisfying customer demands with the same driver (driver consistency) at approximately the same time (arrival-time consistency) allows companies in last-mile distribution to stand out among competitors. The consistent vehicle-routing problem (ConVRP) is a multiday problem addressing such consistency requirements along with traditional constraints on vehicle capacity and route duration. The literature offers several heuristics but no exact method for this problem. The state-of-the-art exact technique to solve VRPs—column generation (CG) applied to route-based formulations in which columns are generated via dynamic programming—cannot be successfully extended to the ConVRP because the linear relaxation of route-based formulations is weak. We propose the first exact method for the ConVRP, which can solve medium-sized instances with five days and 30 customers. The method solves, via CG, a formulation in which each variable represents the set of routes assigned to a vehicle over the planning horizon. As an upper bounding procedure, we develop a large neighborhood search (LNS) featuring a repair procedure specifically designed to improve the arrival-time consistency of solutions. Used as stand-alone heuristic, the LNS is able to significantly improve the solution quality on benchmark instances from the literature compared with state-of-the-art heuristics.

Keywords: customer service; column generation; large neighborhood search; consistent vehicle routing problems (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0864 (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:53:y:2019:i:4:p:1023-1042

Access Statistics for this article

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