Solving the equity-aware dial-a-ride problem using an exact branch-cut-and-price algorithm
Author
Abstract
Suggested Citation
DOI: 10.1016/j.trb.2024.103149
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
- Timo Gschwind & Stefan Irnich, 2015. "Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 49(2), pages 335-354, May.
- Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
- Liu, Yining & Ouyang, Yanfeng, 2023. "Planning ride-pooling services with detour restrictions for spatially heterogeneous demand: A multi-zone queuing network approach," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
- Nathalie Perrier & André Langevin & Ciro-Alberto Amaya, 2008. "Vehicle Routing for Urban Snow Plowing Operations," Transportation Science, INFORMS, vol. 42(1), pages 44-56, February.
- Schulz, Arne & Pfeiffer, Christian, 2024. "A Branch-and-Cut algorithm for the dial-a-ride problem with incompatible customer types," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
- Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
- George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
- Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2015. "A column generation approach for a multi-attribute vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 888-906.
- Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "The bi-objective Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 464-478.
- Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.
- Ann Melissa Campbell & Dieter Vandenbussche & William Hermann, 2008. "Routing for Relief Efforts," Transportation Science, INFORMS, vol. 42(2), pages 127-145, May.
- Hosni, Hadi & Naoum-Sawaya, Joe & Artail, Hassan, 2014. "The shared-taxi problem: Formulation and solution methods," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 303-318.
- Bonner, Taylor & Miller-Hooks, Elise, 2023. "Achieving equitable outcomes through optimal design in the development of microtransit zones," Journal of Transport Geography, Elsevier, vol. 112(C).
- Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
- Huang, Michael & Smilowitz, Karen & Balcik, Burcu, 2012. "Models for relief routing: Equity, efficiency and efficacy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 2-18.
- Foth, Nicole & Manaugh, Kevin & El-Geneidy, Ahmed M., 2013. "Towards equitable transit: examining transit accessibility and social need in Toronto, Canada, 1996–2006," Journal of Transport Geography, Elsevier, vol. 29(C), pages 1-10.
- G. Dikas & I. Minis, 2018. "Scheduled Paratransit Transport Enhanced by Accessible Taxis," Transportation Science, INFORMS, vol. 52(5), pages 1122-1140, October.
- Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
- Nie, Qifan & Qian, Xinwu & Guo, Shuocheng & Jones, Steven & Doustmohammadi, Mehrnaz & Anderson, Michael D., 2022. "Impact of COVID-19 on paratransit operators and riders: A case study of central Alabama," Transportation Research Part A: Policy and Practice, Elsevier, vol. 161(C), pages 48-67.
- Faheng Deng & Hu Qin & Jiliu Li & Chun Cheng, 2023. "The Pickup and Delivery Problem with Time Windows and Incompatibility Constraints in Cold Chain Transportation," Transportation Science, INFORMS, vol. 57(2), pages 444-462, March.
- Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
- Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
- Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
- P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
- Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
- Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
- Zhixing Luo & Mengyang Liu & Andrew Lim, 2019. "A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation," Service Science, INFORMS, vol. 53(1), pages 113-130, February.
- Yining Liu & Yanfeng Ouyang, 2022. "Planning ride-pooling services with detour restrictions for spatially heterogeneous demand: A multi-zone queuing network approach," Papers 2208.02219, arXiv.org, revised Jun 2023.
- Gupta, Diwakar & Chen, Hao-Wei & Miller, Lisa A. & Surya, Fajarrani, 2010. "Improving the efficiency of demand-responsive paratransit services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 44(4), pages 201-217, May.
- Braekers, Kris & Caris, An & Janssens, Gerrit K., 2014. "Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 166-186.
- Paquette, Julie & Cordeau, Jean-François & Laporte, Gilbert & Pascoal, Marta M.B., 2013. "Combining multicriteria analysis and tabu search for dial-a-ride problems," Transportation Research Part B: Methodological, Elsevier, vol. 52(C), pages 1-16.
- Zahra Navidi & Nicole Ronald & Stephan Winter, 2018. "Comparison between ad-hoc demand responsive and conventional transit: a simulation study," Public Transport, Springer, vol. 10(1), pages 147-167, May.
- Yuan Qu & Jonathan F. Bard, 2015. "A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity," Transportation Science, INFORMS, vol. 49(2), pages 254-270, May.
- Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, October.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
- Gaul, Daniela & Klamroth, Kathrin & Stiglmayr, Michael, 2022. "Event-based MILP models for ridepooling applications," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1048-1063.
- Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
- Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
- Zhang, Li & Liu, Zhongshan & Yu, Lan & Fang, Ke & Yao, Baozhen & Yu, Bin, 2022. "Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
- Zhang, Li & Liu, Zhongshan & Yu, Bin & Long, Jiancheng, 2024. "A ridesharing routing problem for airport riders with electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
- Sharif Azadeh, Sh. & Atasoy, Bilge & Ben-Akiva, Moshe E. & Bierlaire, M. & Maknoon, M.Y., 2022. "Choice-driven dial-a-ride problem for demand responsive mobility service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 128-149.
- Rahman, Md Hishamur & Chen, Shijie & Sun, Yanshuo & Siddiqui, Muhammad Imran Younus & Mohebbi, Matthew & Marković, Nikola, 2023. "Integrating dial-a-ride with transportation network companies for cost efficiency: A Maryland case study," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
- Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
- Zhixing Luo & Mengyang Liu & Andrew Lim, 2019. "A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation," Service Science, INFORMS, vol. 53(1), pages 113-130, February.
- Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
- Johnsen, Lennart C. & Meisel, Frank, 2022. "Interrelated trips in the rural dial-a-ride problem with autonomous vehicles," European Journal of Operational Research, Elsevier, vol. 303(1), pages 201-219.
- Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
- Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
- Ertan Yakıcı & Robert F. Dell & Travis Hartman & Connor McLemore, 2018. "Daily aircraft routing for amphibious ready groups," Annals of Operations Research, Springer, vol. 264(1), pages 477-498, May.
- Braekers, Kris & Kovacs, Attila A., 2016. "A multi-period dial-a-ride problem with driver consistency," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 355-377.
- Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
- Timo Gschwind & Michael Drexl, 2019. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 53(2), pages 480-491, March.
- Detti, Paolo & Papalini, Francesco & Lara, Garazi Zabalo Manrique de, 2017. "A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare," Omega, Elsevier, vol. 70(C), pages 1-14.
- Daniel Y. Mo & H. Y. Lam & Weikun Xu & G. T. S. Ho, 2020. "Design of Flexible Vehicle Scheduling Systems for Sustainable Paratransit Services," Sustainability, MDPI, vol. 12(14), pages 1-18, July.
More about this item
Keywords
Dial-a-ride problem; Branch-cut-and-price; Column generation; Demand-responsive transit; Equity; Pareto front;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:192:y:2025:i:c:s019126152400273x. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.