IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v150y2021ics1366554520307729.html
   My bibliography  Save this article

A modified artificial bee colony algorithm for the dynamic ride-hailing sharing problem

Author

Listed:
  • Zhan, Xingbin
  • Szeto, W.Y.
  • Shui, C.S.
  • Chen, Xiqun (Michael)

Abstract

Ride-hailing sharing involves grouping ride-hailing customers with similar trips and time schedules to share the same ride-hailing vehicle to reduce their total travel cost. With the current information and communication technology, ride-hailing customers and drivers can be matched in real-time via a ride-hailing platform. This paper formulates a dynamic ride-hailing sharing problem that simultaneously maximizes the number of served customers, minimizes the travel cost and travel time ratios, and considers the capacity, time window, and travel cost constraints. The travel cost ratio is the ratio of actual passengers’ fare to the passengers’ fare without ride-hailing sharing, whereas the travel time ratio is defined as the actual travel time (including waiting time) over the maximum allowable travel time. To solve the dynamic problem, it is divided into many small and continuous static subproblems with an equal time interval. Each subproblem is solved by a modified artificial bee colony (MABC) algorithm with path relinking, while the contraction hierarchies and vantage point tree are used to determine the shortest path and accelerate the algorithm, respectively. Problem properties and the performance of the proposed solution method are demonstrated using large-scale real-time data from Didi that is the largest ride-hailing company in China. The proposed method is shown to outperform the benchmark, i.e., greedy randomized adaptive search procedure (GRASP) with path relinking. The proposed method also performs better when the length of each time interval is longer, and the tolerance for the incremental travel time caused by detours is higher. We also demonstrate that (a) considering both travel cost and travel time ratios in the objective can achieve a better sharing percentage, and balance the increase in the travel time ratio and the decrease in the travel cost ratio compared with the objective that misses either travel time or the travel cost ratio; and (b) the passengers can gain a large out-of-pocket cost saving in the case of ride-hailing sharing while enduring a relatively small increase in travel time compared with the case without ride-hailing sharing.

Suggested Citation

  • Zhan, Xingbin & Szeto, W.Y. & Shui, C.S. & Chen, Xiqun (Michael), 2021. "A modified artificial bee colony algorithm for the dynamic ride-hailing sharing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    • Handle: RePEc:eee:transe:v:150:y:2021:i:c:s1366554520307729
    DOI: 10.1016/j.tre.2020.102124
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554520307729
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.102124?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. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. 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.
    3. Szeto, W.Y. & Shui, C.S., 2018. "Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 176-211.
    4. 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.
    5. Szeto, W.Y. & Jiang, Y., 2014. "Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 235-263.
    6. 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.
    7. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun, 2014. "A bi-objective turning restriction design problem in urban road networks," European Journal of Operational Research, Elsevier, vol. 237(2), pages 426-439.
    8. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    9. Pascale Scapecchi, 2005. "Children's Environmental Health Indicators: A Survey," OECD Papers, OECD Publishing, vol. 5(9), pages 1-50.
    10. Robert Geisberger & Peter Sanders & Dominik Schultes & Christian Vetter, 2012. "Exact Routing in Large Road Networks Using Contraction Hierarchies," Transportation Science, INFORMS, vol. 46(3), pages 388-404, August.
    11. Sayarshad, Hamid R. & Chow, Joseph Y.J., 2015. "A scalable non-myopic dynamic dial-a-ride and pricing problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 539-554.
    12. 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.
    13. Michael Z. Spivey & Warren B. Powell, 2004. "The Dynamic Assignment Problem," Transportation Science, INFORMS, vol. 38(4), pages 399-419, November.
    14. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    15. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    16. Miguel Andres Figliozzi & Hani S. Mahmassani & Patrick Jaillet, 2007. "Pricing in Dynamic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 41(3), pages 302-318, August.
    17. 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.
    18. Coslovich, Luca & Pesenti, Raffaele & Ukovich, Walter, 2006. "A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1605-1615, December.
    19. Sayarshad, Hamid R. & Gao, H. Oliver, 2020. "Optimizing dynamic switching between fixed and flexible transit services with an idle-vehicle relocation strategy and reductions in emissions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 135(C), pages 198-214.
    20. Szeto, W.Y. & Wu, Yongzhong & Ho, Sin C., 2011. "An artificial bee colony algorithm for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 126-135, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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).
    2. 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).
    3. Zhan, Xingbin & Szeto, W.Y. & Wang, Yue, 2023. "The ride-hailing sharing problem with parcel transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    4. Zhan, Xingbin & Szeto, W.Y. & (Michael) Chen, Xiqun, 2022. "A simulation–optimization framework for a dynamic electric ride-hailing sharing problem with a novel charging strategy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    5. 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).
    6. Liu, Yang & Wu, Fanyou & Lyu, Cheng & Li, Shen & Ye, Jieping & Qu, Xiaobo, 2022. "Deep dispatching: A deep reinforcement learning approach for vehicle dispatching on online ride-hailing platform," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    7. Zhan, Xingbin & Szeto, W.Y. & (Michael) Chen, Xiqun, 2022. "The dynamic ride-hailing sharing problem with multiple vehicle types and user classes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).

    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. Sayarshad, Hamid R. & Chow, Joseph Y.J., 2015. "A scalable non-myopic dynamic dial-a-ride and pricing problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 539-554.
    2. 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.
    3. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    4. 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.
    5. Häme, Lauri, 2011. "An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows," European Journal of Operational Research, Elsevier, vol. 209(1), pages 11-22, February.
    6. 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).
    7. 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.
    8. Tafreshian, Amirmahdi & Abdolmaleki, Mojtaba & Masoud, Neda & Wang, Huizhu, 2021. "Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 227-259.
    9. 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).
    10. Dessouky, Maged M & Hu, Shichun, 2021. "Dynamic Routing for Ride-Sharing," Institute of Transportation Studies, Working Paper Series qt6qq8r7hz, Institute of Transportation Studies, UC Davis.
    11. 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.
    12. 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.
    13. 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.
    14. Aslaksen, Ingvild Eide & Svanberg, Elisabeth & Fagerholt, Kjetil & Johnsen, Lennart C. & Meisel, Frank, 2021. "A combined dial-a-ride and fixed schedule ferry service for coastal cities," Transportation Research Part A: Policy and Practice, Elsevier, vol. 153(C), pages 306-325.
    15. Xue, Li & Luo, Zhixing & Lim, Andrew, 2016. "Exact approaches for the pickup and delivery problem with loading cost," Omega, Elsevier, vol. 59(PB), pages 131-145.
    16. Joseph Y. J. Chow & Hamid R. Sayarshad, 2016. "Reference Policies for Non-myopic Sequential Network Design and Timing Problems," Networks and Spatial Economics, Springer, vol. 16(4), pages 1183-1209, December.
    17. 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).
    18. Zhan, Xingbin & Szeto, W.Y. & (Michael) Chen, Xiqun, 2022. "The dynamic ride-hailing sharing problem with multiple vehicle types and user classes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    19. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    20. Kergosien, Y. & Lenté, Ch. & Piton, D. & Billaut, J.-C., 2011. "A tabu search heuristic for the dynamic transportation of patients between care units," European Journal of Operational Research, Elsevier, vol. 214(2), pages 442-452, October.

    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:transe:v:150:y:2021:i:c:s1366554520307729. 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/600244/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.