IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v318y2024i2p486-499.html
   My bibliography  Save this article

The rail-road Dial-a-Ride problem

Author

Listed:
  • Jodeau, Jean
  • Absi, Nabil
  • Chevrier, Rémy
  • Feillet, Dominique

Abstract

This paper addresses an original static Dial-A-Ride service designed for sparsely populated areas. The service relies on vehicles capable of switching between the road and an existing vacant railway network, which induces railway scheduling constraints that must be integrated into the solution algorithm. In the context of the static Dial-A-Ride Problem (DARP), a set of known users must be picked up and dropped off to desired locations while adhering to time windows at nodes and maximal riding time constraints. In our problem, there are additional constraints related to the vehicles when they operate on the rail, creating interdependencies between trips.

Suggested Citation

  • Jodeau, Jean & Absi, Nabil & Chevrier, Rémy & Feillet, Dominique, 2024. "The rail-road Dial-a-Ride problem," European Journal of Operational Research, Elsevier, vol. 318(2), pages 486-499.
    • Handle: RePEc:eee:ejores:v:318:y:2024:i:2:p:486-499
    DOI: 10.1016/j.ejor.2024.05.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724003953
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.05.036?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    2. 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).
    3. 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.
    4. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    5. Dorfman, M. J. & Medanic, J., 2004. "Scheduling trains on a railway network using a discrete event model of railway traffic," Transportation Research Part B: Methodological, Elsevier, vol. 38(1), pages 81-98, January.
    6. Xiaoming Xu & Keping Li & Lixing Yang & Ziyou Gao, 2019. "An efficient train scheduling algorithm on a single-track railway system," Journal of Scheduling, Springer, vol. 22(1), pages 85-105, February.
    7. 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.
    8. 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.
    9. Christian Pfeiffer & Arne Schulz, 2022. "An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(1), pages 87-119, March.
    10. 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.
    11. 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.
    12. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    13. Molenbruch, Yves & Braekers, Kris & Hirsch, Patrick & Oberscheider, Marco, 2021. "Analyzing the benefits of an integrated mobility system using a matheuristic routing algorithm," European Journal of Operational Research, Elsevier, vol. 290(1), pages 81-98.
    14. 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.
    15. Philippe Grangier & Michel Gendreau & Fabien Lehuédé & Louis-Martin Rousseau, 2021. "The vehicle routing problem with cross-docking and resource constraints," Journal of Heuristics, Springer, vol. 27(1), pages 31-61, April.
    16. 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.
    Full references (including those not matched with items on IDEAS)

    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.
    1. 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.
    2. 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).
    3. 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.
    4. Molenbruch, Yves & Braekers, Kris & Hirsch, Patrick & Oberscheider, Marco, 2021. "Analyzing the benefits of an integrated mobility system using a matheuristic routing algorithm," European Journal of Operational Research, Elsevier, vol. 290(1), pages 81-98.
    5. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.
    6. 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.
    7. Su, Yue & Dupin, Nicolas & Puchinger, Jakob, 2023. "A deterministic annealing local search for the electric autonomous dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1091-1111.
    8. 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.
    9. Christian Pfeiffer & Arne Schulz, 2022. "An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(1), pages 87-119, March.
    10. 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.
    11. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    12. Bongiovanni, Claudia & Kaspi, Mor & Cordeau, Jean-François & Geroliminis, Nikolas, 2022. "A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    13. Mohamed Amine Masmoudi & Manar Hosny & Emrah Demir & Erwin Pesch, 2020. "Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem," Journal of Heuristics, Springer, vol. 26(1), pages 83-118, February.
    14. 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.
    15. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. 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.
    17. Molenbruch, Yves & Braekers, Kris & Caris, An, 2017. "Benefits of horizontal cooperation in dial-a-ride services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 107(C), pages 97-119.
    18. Chane-Haï Timothée & Vercraene Samuel & Monteiro Thibaud, 2023. "The assignment-dial-a-ride-problem," Health Care Management Science, Springer, vol. 26(4), pages 770-784, December.
    19. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    20. Guo, Jiaqi & Long, Jiancheng & Xu, Xiaoming & Yu, Miao & Yuan, Kai, 2022. "The vehicle routing problem of intercity ride-sharing between two cities," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 113-139.

    Corrections

    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:ejores:v:318:y:2024:i:2:p:486-499. 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/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.