article

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

Authors:

Stefan IrnichAuthors Info & Claims

Transportation Science, Volume 49, Issue 2

Pages 335 - 354

https://doi.org/10.1287/trsc.2014.0531

Published: 01 May 2015 Publication History

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.

References

[1]

Ascheuer N, Fischetti M, Grötschel M (2000) A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2):69-79.

[2]

Azi N, Gendreau M, Potvin J-Y (2010) An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. Eur. J. Oper. Res. 202(3):756-763.

[3]

Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120(2):347-380.

Digital Library

[4]

Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269-1283.

Digital Library

[5]

Borndörfer R, Klostermeier F, Grötschel M, Küttner C (1997) Telebus Berlin: Vehicle scheduling in a dial-a-ride system. Technical Report SC 97-23, Konrad-Zuse-Zentrum für Informationstechnik, Berlin.

[6]

Bredström D, Rönnqvist M (2008) Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur. J. Oper. Res. 191(1):19-29.

[7]

Ceselli A, Righini G, Salani M (2009) A column generation algorithm for a rich vehicle-routing problem. Transportation Sci. 43(1):56-69.

Digital Library

[8]

Cordeau J-F (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573-586.

Digital Library

[9]

Cordeau J-F, Laporte G (2003) A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Res. Part B 37(6):579-594.

[10]

Cordeau J-F, Laporte G (2007) The dial-a-ride problem: Models and algorithms. Ann. Oper. Res. 153(1):29-46.

[11]

Cordeau J-F, Laporte G, Ropke S (2008) Recent models and algorithms for one-to-one pickup and delivery problems. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, Boston), 327-357.

[12]

Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387-404.

Digital Library

[13]

Desaulniers G, Desrosiers J, Erdmann A, Solomon MM, Soumis F (2002) VRP with pickup and delivery. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 225-242.

[14]

Desaulniers G, Desroisiers J, Ioachim I, Solomon MM, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constraint vehicle routing and crew scheduling problems. Crainic TG, Laporte G, eds. Fleet Management and Logistics (Kluwer, Norwell, MA), 57-93.

[15]

Desrochers M, Soumis F (1988) A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26(3):191-212.

[16]

Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342-354.

[17]

Drexl M (2012) Synchronization in vehicle routing¿A survey of VRPs with multiple synchronization constraints. Transportation Sci. 46(3):297-316.

Digital Library

[18]

du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1-3):229-237.

Digital Library

[19]

Dumas Y, Desrosiers J, Soumis F (1991) The pickup and delivery problem with time windows. Eur. J. Oper. Res. 54(1):7-22.

[20]

Eveborn P, Flisberg P, Rönnqvist M (2006) Laps care¿An operational system for staff planning of home care. Eur. J. Oper. Res. 171(3):962-976.

[21]

Firat M, Woeginger GJ (2011) Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. Oper. Res. Lett. 39(1):32-35.

Digital Library

[22]

Haugland D, Ho SC (2010) Feasibility testing for dial-a-ride problems. Chen B, ed. Algorithmic Aspects in Information and Management, Lecture Notes Comput. Sci., Vol. 6124 (Springer, Berlin Heidelberg), 170-179.

[23]

Houck DJ, Picard JC, Queyranne M, Vemuganti RR (1980) The travelling salesman problem as a constrained shortest path problem: Theory and computational experience. OPSEARCH 17:93-109.

[24]

Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999) Fleet assignment and routing with schedule synchronization constraints. Eur. J. Oper. Res. 119(1):75-90.

[25]

Ioachim I, Gélinas S, Desrosiers J, Soumis F (1998) A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31(3):193-204.

[26]

Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33-65.

[27]

Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ¿ 3. INFORMS J. Comput. 18(3):391-406.

Digital Library

[28]

Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497-511.

Digital Library

[29]

Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007-1023.

Digital Library

[30]

Madsen O, Ravn H, Rygaard J (1995) A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Ann. Oper. Res. 60(1):193-208.

[31]

Naddef D, Rinaldi G (2002) Branch-and-cut algorithms for the capacitated VRP. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 53-84.

[32]

Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. J. für Betriebswirtschaft 58(2):81-117.

[33]

Parragh SN, Doerner KF, Hartl RF (2010) Variable neighborhood search for the dial-a-ride problem. Comps. Oper. Res. 37(6):1129-1138.

Digital Library

[34]

Ropke S, Cordeau J-F (2005) Branch and cut and price for the pickup and delivery problem with time windows. Unpublished doctoral dissertation, Heuristic and exact algorithms for vehicle routing problems, University of Copenhagen, Copenhagen.

[35]

Ropke S, Cordeau J-F (2009) Branch and cut and price for the pickup and delivery problem with time windows. Transportation Sci. 43(3):267-286.

Digital Library

[36]

Ropke S, Cordeau J-F, Laporte G (2007) Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4):258-272.

[37]

Russell RA, Morrel RB (1986) Routing special-education school buses. Interfaces 16(5):56-64.

[38]

Savelsbergh MWP (1992) The vehicle routing problem with time windows: Minimizing route duration. INFORMS J. Comput. 4(2):146-154.

[39]

Tang J, Kong Y, Lau H, Ip AWH (2010) A note on "efficient feasibility testing for dial-a-ride problems." Oper. Res. Lett. 38(5):405-407.

Digital Library

[40]

Toth P, Vigo D (1997) Heuristic algorithms for the handicapped persons transportation problem. Transportation Sci. 31(1):60-71.

Digital Library

Cited By

Boyer VCervantes–Mendieta EHernández-López OSalazar–Aguilar M(2025)The Dial-a-Tour ProblemComputers and Operations Research10.1016/j.cor.2024.106832173:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.cor.2024.106832
Bresich MRaidl GLimmer SLi XHandl J(2024)Letting a Large Neighborhood Search for an Electric Dial-A-Ride Problem Fly: On-The-Fly Charging Station InsertionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654057(142-150)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654057
Faldum SMachate SGschwind TIrnich S(2024)Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoffOR Spectrum10.1007/s00291-024-00766-y46:4(1063-1097)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00291-024-00766-y
Show More Cited By

Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization

Recommendations

A Branch-and-Cut Algorithm for the Dial-a-Ride Problem

In the dial-a-ride problem, users formulate requests for transportation from a specific origin to a specific destination. Transportation is carried out by vehicles providing a shared service. The problem consists of designing a set of minimum-cost ...
A New Formulation for the Dial-a-Ride Problem
This paper proposes a new mixed integer programming formulation and branch and cut (BC) algorithm to solve the dial-a-ride problem (DARP). The DARP is a route-planning problem where several vehicles must serve a set of customers, each of which has a ...
Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports

The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Transportation Science

Transportation Science Volume 49, Issue 2

May 2015

269 pages

ISSN:1526-5447

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2015

Accepted: 01 January 2014

Received: 01 April 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Boyer VCervantes–Mendieta EHernández-López OSalazar–Aguilar M(2025)The Dial-a-Tour ProblemComputers and Operations Research10.1016/j.cor.2024.106832173:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.cor.2024.106832
Bresich MRaidl GLimmer SLi XHandl J(2024)Letting a Large Neighborhood Search for an Electric Dial-A-Ride Problem Fly: On-The-Fly Charging Station InsertionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654057(142-150)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654057
Faldum SMachate SGschwind TIrnich S(2024)Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoffOR Spectrum10.1007/s00291-024-00766-y46:4(1063-1097)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00291-024-00766-y
Luo KFlorio ADas SGuo X(2023)A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride ProblemProceedings of the VLDB Endowment10.14778/3579075.357909116:5(1195-1207)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.14778/3579075.3579091
Vercraene SLehuédé FMonteiro TPéton O(2023)The Dial-a-Ride Problem with School Bell Time AdjustmentTransportation Science10.1287/trsc.2022.116057:1(156-173)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1287/trsc.2022.1160
Wang SBaldacci RYu YZhang YTang JLuo XSun W(2023)An Exact Method for a First-Mile Ridesharing ProblemTransportation Science10.1287/trsc.2022.013957:6(1581-1604)Online publication date: 29-Sep-2023
https://dl.acm.org/doi/10.1287/trsc.2022.0139
Heßler KIrnich S(2023)Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing ProblemINFORMS Journal on Computing10.1287/ijoc.2022.125535:1(50-65)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1287/ijoc.2022.1255
Wang JCheng PZheng LChen LZhang W(2022)Online Ridesharing with Meeting PointsProceedings of the VLDB Endowment10.14778/3565838.356584915:13(3963-3975)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3565838.3565849
Rist YForbes M(2022)A column generation and Combinatorial Benders Decomposition algorithm for the Selective Dial-A-Ride-ProblemComputers and Operations Research10.1016/j.cor.2021.105649140:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105649
Pfeiffer CSchulz A(2022)An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimizationOR Spectrum10.1007/s00291-021-00656-744:1(87-119)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s00291-021-00656-7
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents