Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing

Timo Gschwind () and Stefan Irnich ()
Additional contact information
Timo Gschwind: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

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

Abstract: A dynamic time window relates to two operations that have to be executed within a given time meaning that the difference between the points in time when the two operations are performed is restricted. The most prevalent context of dynamic time windows is when precedences are given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedences is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points have to be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypical vehicle-routing problem with ordinary and dynamic time windows. For the first time, both ordinary and dynamic time windows are handled in the column-generation subproblem. For its solution, an effective column-generation pricing procedure is derived that allows fast shortest-path computations due to new dominance rules. The new approach is compared with alternative column-generation algorithms that handle dynamic time windows either as constraints of the master program or with less effective labeling procedures. Computational experiments indicate the superiority of the new approach.

Keywords: Dynamic time windows; dial-a-ride problem; labeling algorithm; ride-time constraints; time synchronization; branch-and-price (search for similar items in EconPapers)
Pages: 32 page
Date: 2012-10-04
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1211.pdf First version, 2012 (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:1211

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 ().