IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v99y2017icp1-29.html
   My bibliography  Save this article

A decomposition algorithm to solve the multi-hop Peer-to-Peer ride-matching problem

Author

Listed:
  • Masoud, Neda
  • Jayakrishnan, R.

Abstract

In this paper, we mathematically model the multi-hop Peer-to-Peer (P2P) ride-matching problem as a binary program. We formulate this problem as a many-to-many problem in which a rider can travel my transferring between multiple drivers, and a driver can carry multiple riders. We propose a pre-processing procedure to reduce the size of the problem, and devise a decomposition algorithm to solve the original ride-matching problem to optimality by means of solving multiple smaller problems. We conduct extensive numerical experiments to demonstrate the computational efficiency of the proposed algorithm and show its practical applicability to reasonably-sized dynamic ride-matching contexts. Finally, in the interest of even lower solution times, we propose heuristic solution methods, and investigate the trade-offs between solution time and accuracy.

Suggested Citation

  • Masoud, Neda & Jayakrishnan, R., 2017. "A decomposition algorithm to solve the multi-hop Peer-to-Peer ride-matching problem," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 1-29.
    • Handle: RePEc:eee:transb:v:99:y:2017:i:c:p:1-29
    DOI: 10.1016/j.trb.2017.01.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S019126151730019X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2017.01.004?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. Timothy A. Carnes & Shane G. Henderson & David B. Shmoys & Mahvareh Ahghari & Russell D. MacDonald, 2013. "Mathematical Programming Guides Air-Ambulance Routing at Ornge," Interfaces, INFORMS, vol. 43(3), pages 232-239, May-June.
    2. Agatz, Niels A.H. & Erera, Alan L. & Savelsbergh, Martin W.P. & Wang, Xing, 2011. "Dynamic ride-sharing: A simulation study in metro Atlanta," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1450-1464.
    3. Agatz, N.A.H. & Erera, A. & Savelsbergh, M.W.P. & Wang, X., 2010. "Sustainable Passenger Transportation: Dynamic Ride-Sharing," ERIM Report Series Research in Management ERS-2010-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    4. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    5. David M. Stein, 1978. "Scheduling Dial-a-Ride Transportation Systems," Transportation Science, INFORMS, vol. 12(3), pages 232-249, August.
    6. 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.
    7. Jaw, Jang-Jei & Odoni, Amedeo R. & Psaraftis, Harilaos N. & Wilson, Nigel H. M., 1986. "A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 243-257, June.
    8. Stiglic, Mitja & Agatz, Niels & Savelsbergh, Martin & Gradisar, Mirko, 2015. "The benefits of meeting points in ride-sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 36-53.
    9. Furuhata, Masabumi & Dessouky, Maged & Ordóñez, Fernando & Brunet, Marc-Etienne & Wang, Xiaoqing & Koenig, Sven, 2013. "Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 28-46.
    10. Roberto Baldacci & Vittorio Maniezzo & Aristide Mingozzi, 2004. "An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation," Operations Research, INFORMS, vol. 52(3), pages 422-439, June.
    11. 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.
    12. Agatz, Niels & Erera, Alan & Savelsbergh, Martin & Wang, Xing, 2012. "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, Elsevier, vol. 223(2), pages 295-303.
    13. Stiglic, M. & Agatz, N.A.H. & Savelsbergh, M.W.P. & Gradisar, M., 2015. "The Benefits of Meeting Points in Ride-sharing Systems," ERIM Report Series Research in Management ERS-2015-003-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    14. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    15. Harilaos N. Psaraftis, 1983. "An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows," Transportation Science, INFORMS, vol. 17(3), pages 351-357, August.
    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. Masoud, Neda & Jayakrishnan, R., 2017. "A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 218-236.
    2. Amirmahdi Tafreshian & Neda Masoud & Yafeng Yin, 2020. "Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions," Service Science, INFORMS, vol. 12(2-3), pages 44-60, June.
    3. Sun, Yanshuo & Chen, Zhi-Long & Zhang, Lei, 2020. "Nonprofit peer-to-peer ridesharing optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    4. Mourad, Abood & Puchinger, Jakob & Chu, Chengbin, 2019. "A survey of models and algorithms for optimizing shared mobility," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 323-346.
    5. Hua, Shijia & Zeng, Wenjia & Liu, Xinglu & Qi, Mingyao, 2022. "Optimality-guaranteed algorithms on the dynamic shared-taxi problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    6. Stumpe, Miriam & Dieter, Peter & Schryen, Guido & Müller, Oliver & Beverungen, Daniel, 2024. "Designing taxi ridesharing systems with shared pick-up and drop-off locations: Insights from a computational study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 183(C).
    7. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem & Yacine Rekik, 2022. "Environmental and social implications of incorporating carpooling service on a customized bus system," Post-Print hal-03598768, HAL.
    8. Inayatullah Shah & Mohammed El Affendi & Basit Qureshi, 2020. "SRide: An Online System for Multi-Hop Ridesharing," Sustainability, MDPI, vol. 12(22), pages 1-29, November.
    9. Dai, Rongjian & Ding, Chuan & Gao, Jian & Wu, Xinkai & Yu, Bin, 2022. "Optimization and evaluation for autonomous taxi ride-sharing schedule and depot location from the perspective of energy consumption," Applied Energy, Elsevier, vol. 308(C).
    10. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    11. Peng, Zixuan & Shan, Wenxuan & Zhu, Xiaoning & Yu, Bin, 2022. "Many-to-one stable matching for taxi-sharing service with selfish players," Transportation Research Part A: Policy and Practice, Elsevier, vol. 160(C), pages 255-279.
    12. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    13. Zhang, Ruolin & Masoud, Neda, 2021. "A distributed algorithm for operating large-scale ridesourcing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    14. Kishore Bhoopalam, A. & Agatz, N.A.H. & Zuidwijk, R.A., 2017. "Planning of Truck Platoons: a Literature Review and Directions for Future Research," ERIM Report Series Research in Management ERS-2017-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    15. Wang, Jing-Peng & Ban, Xuegang (Jeff) & Huang, Hai-Jun, 2019. "Dynamic ridesharing with variable-ratio charging-compensation scheme for morning commute," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 390-415.
    16. Naoum-Sawaya, Joe & Cogill, Randy & Ghaddar, Bissan & Sajja, Shravan & Shorten, Robert & Taheri, Nicole & Tommasi, Pierpaolo & Verago, Rudi & Wirth, Fabian, 2015. "Stochastic optimization approach for the car placement problem in ridesharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 173-184.
    17. Qian, Xinwu & Zhang, Wenbo & Ukkusuri, Satish V. & Yang, Chao, 2017. "Optimal assignment and incentive design in the taxi group ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 208-226.
    18. Stiglic, Mitja & Agatz, Niels & Savelsbergh, Martin & Gradisar, Mirko, 2016. "Making dynamic ride-sharing work: The impact of driver and rider flexibility," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 91(C), pages 190-207.
    19. Omer Faruk Aydin & Ilgin Gokasar & Onur Kalan, 2020. "Matching algorithm for improving ride-sharing by incorporating route splits and social factors," PLOS ONE, Public Library of Science, vol. 15(3), pages 1-23, March.
    20. 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.

    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:transb:v:99:y:2017:i:c:p:1-29. 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.

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