Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts

Said Dabia (), Stefan Ropke () and Tom van Woensel ()
Additional contact information
Said Dabia: School of Business and Economics, VU University Amsterdam, 1081 HV Amsterdam, Netherlands; Eyefreight B.V., 3981 AJ Bunnik, Netherlands;
Stefan Ropke: Department of Management Engineering, Technical University of Denmark, 2800 Copenhagen, Denmark;
Tom van Woensel: School of Industrial Engineering, Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands

Transportation Science, 2019, vol. 53, issue 5, 1354-1371

Abstract: This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a limited loading capacity. We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing subproblem is solved by a label-setting algorithm. Shift capacity constraints define knapsack inequalities; hence we use valid inequalities inspired from knapsack inequalities to strengthen the linear programming relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover inequalities and a family of new nonrobust cover inequalities. Numerical results show that nonrobust cover inequalities significantly improve the algorithm.

Keywords: vehicle routing problem; column generation; shift capacity; branch-and-cut-and-price algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0885 (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:5:p:1354-1371

Access Statistics for this article

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