Branch-and-Price-and-Cut for the Vehicle Routing and Truck Driver Scheduling Problem

Christian Tilk ()
Additional contact information
Christian Tilk: Johannes Gutenberg-University Mainz, Germany

No 1616, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: Many governments worldwide have imposed hours of service regulations for truck drivers to ensure that break and rest periods are regularly taken. Transport companies have to take these into account and plan the routes and schedules of their truck drivers simultaneously. This problem is called vehicle routing and truck driver scheduling problem (VRTDSP). With their paper “An exact method for vehicle routing and truck driver scheduling problems” [Technical Report No. 33, Jacobs University, School of Engineering and Science, Bremen, Germany] Goel and Irnich presented the ?rst exact approach to the VRTDSP.They include hours of service regulations in a vehicle routing problem with time windows and use a branch-and-price algorithm to solve it. The main contribution of the paper at hand is to present a sophisticated branch-and-price-and-cut algorithm for the VRTDSP that is based on the parameter-free auxiliary network and the resource extension functions (REFs) de?ned in the work of Goel and Irnich. Their labeling algorithm is extended by means of de?ning backward REFs in order to build a bidirectional labeling. Feasible routes are constructed by a non-trivial merge procedure. Di?erent acceleration techniques are used to speed up the solution process of the pricing problem. In addition, several classes of known valid inequalities are used to further strengthen the LP-relaxation of the master program. We present a detailed computational study to analyze the impact of the di?erent techniques. The resulting algorithm is able to solve all VRTDSP benchmark instances with 25 customers and 44 out of 56 instances with 50 customers in two hours of computation time to proven optimality.

Keywords: truck driver; routing and scheduling; branch-and-price-and-cut (search for similar items in EconPapers)
Pages: 20 pages
Date: 2016-08-04
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1616.pdf First version, 2016 (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:jgu:wpaper:1616

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().