Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem

Timo Gschwind () and Stefan Irnich ()
Additional contact information
Timo Gschwind: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany
Stefan Irnich: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany

Transportation Science, 2015, vol. 49, issue 2, 335-354

Abstract: A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is 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 precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must 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 (to our knowledge), both ordinary and dynamic time windows are handled in the column-generation subproblem. For the 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: transportation; vehicle routing; dynamic time windows; dial-a-ride problem; labeling algorithm; ride-time constraints; time synchronization; branch-and-price (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0531 (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:49:y:2015:i:2:p:335-354

Access Statistics for this article

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