A New Formulation for the Dial-a-Ride Problem

References

• Alyasiry AM, Forbes M, Bulmer M (2019) An exact algorithm for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Sci. 53(6):1695–1705.Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Google Scholar
• Braekers K, Caris A, Janssens GK (2014) Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Res. Part B: Methodological 67(2014):166–186.Google Scholar
• Chassaing M, Duhamel C, Lacomme P (2016) An ELS-based approach with dynamic probabilities management in local search for the dial-a-ride problem. Engrg. Appl. Artificial Intelligence 48(2016):119–133.Google Scholar
• Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573–586.Google Scholar
• Cordeau JF, Laporte G (2003) A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Res. Part B: Methodological 37(6):579–594.Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Detti P, Papalini F, de Lara GZM (2017) A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega 70(2017):1–14.Google Scholar
• Firat M, Woeginger GJ (2011) Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. Oper. Res. 39(1):32–35.Google Scholar
• Gschwind T (2015) A comparison of column-generation approaches to the synchronized pickup and delivery problem. Eur. J. Oper. Res. 247(1):60–71.Google Scholar
• Gschwind T, Drexl M (2019) Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transportation Sci. 53(2):480–491.Google Scholar
• Gschwind T, Irnich S (2015) Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Sci. 49(2):335–354.Google Scholar
• Haugland D, Ho SC (2010) Feasibility testing for dial-a-ride problems. Chen B, ed. Algorithmic Aspects in Information and Management. AAIM 2010, Lecture Notes in Computer Science, vol. 6124 (Springer, Berlin), 170–179.Google Scholar
• He E, Boland N, Nemhauser G, Savelsbergh M (2018) A dynamic discretization discovery algorithm for the minimum duration time-dependent shortest path problem. van Hoeve WJ, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018, Lecture Notes in Computer Science, vol. 10848 (Springer, Cham, Switzerland), 289–297.Crossref, Google Scholar
• Hunsaker B, Savelsbergh M (2002) Efficient feasibility testing for dial-a-ride problems. Oper. Res. Lett. 30(3):169–173.Google Scholar
• 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.Google Scholar
• Luo Z, Liu M, Lim A (2019) A two-phase branch-and-price-and-cut for a dial-a-ride problem in patient transportation. Transportation Sci. 53(1):113–130.Google Scholar
• Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J. ACM 7(4):326–329.Google Scholar
• Munari P, Dollevoet T, Spliet R (2017) A generalized formulation for vehicle routing problems. Preprint, submitted September, https://www.researchgate.net/publication/303840066_A_generalized_formulation_for_vehicle_routing_problems.Google Scholar
• Parragh SN, Schmid V (2013) Hybrid column generation and large neighborhood search for the dial-a-ride problem. Comput. Oper. Res. 40(1):490–497.Google Scholar
• Ropke S (2006) Heuristic and exact algorithms for vehicle routing problems. PhD thesis, University of Copenhagen, Copenhagen.Google Scholar
• Ropke S, Cordeau JF (2009) Branch and cut and price for the pickup and delivery problem with time windows. Transportation Sci. 43(3):267–286.Google Scholar
• Ropke S, Cordeau JF, Laporte G (2007) Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4):258–272.Google Scholar
• Savelsbergh MWP, Sol M (1995) The general pickup and delivery problem. Transportation Sci. 29(1):17–29.Google Scholar
• Sippel L (2019) An exact algorithm for the ER-DARP. Unpublished honours thesis, University of Queensland, Brisbane, Australia.Google Scholar
• Tang J, Kong Y, Lau H, Ip AW (2010) A note on “efficient feasibility testing for dial-a-ride problems.” Oper. Res. Lett. 38(5):405–407.Google Scholar
• Veenstra M, Cherkesly M, Desaulniers G, Laporte G (2017) The pickup and delivery problem with time windows and handling operations. Comput. Oper. Res. 77(2017):127–140.Google Scholar
• Zhang Z, Liu M, Lim A (2015) A memetic algorithm for the patient transportation problem. Omega 54(2015):60–71.Google Scholar