Cover inequalities for a vehicle routing problem with time windows and shifts

S. Dabia, S. Röpke, T. van Woensel

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)1354-1371
Aantal pagina's18
TijdschriftTransportation Science
Volume53
Nummer van het tijdschrift5
DOI's
StatusGepubliceerd - 1 sep 2019

Vingerafdruk Duik in de onderzoeksthema's van 'Cover inequalities for a vehicle routing problem with time windows and shifts'. Samen vormen ze een unieke vingerafdruk.

Citeer dit