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

Optimizing first-and-last-mile ridesharing services with a heterogeneous vehicle fleet and time-dependent travel times

Author

Listed:
  • Sun, Bo
  • Chen, Shukai
  • Meng, Qiang

Abstract

This study investigates an on-demand first-and-last-mile ridesharing service (FLRS) problem considering the time-dependent travel time for an operator who manage a heterogeneous vehicle fleet. The operator, aiming to minimize the total operational cost, needs to simultaneously serve both first-mile (FM) and last-mile (LM) trips around a public transportation hub, such as a metro station. To holistically address this problem, we formulate a time-discretized mixed integer linear programming (MILP) model by constructing a time-expanded network and then extend a route-based set partitioning model. To yield good-quality solutions in a short computational time, a rolling-horizon-based column generation (RHCG) method is developed to handle real-time requests. An exact branch-and-price (BP) algorithm and a customized adaptive large neighborhood search (ALNS) algorithm are utilized to assess the solution quality of the applied RHCG. We conduct extensive numerical experiments created from real-world instances in Singapore to demonstrate the effectiveness of the proposed research methodology. The results of large-scale cases indicate that the RHCG outperforms both the commercial solver and the BP, and significantly reduces computational time in comparison with the ALNS. The implemented FLRS solution can decrease system-wide costs by 21.38% and increase shared-ride efficiency by 1.47 times, compared with the FM and LM services that operate separately.

Suggested Citation

  • Sun, Bo & Chen, Shukai & Meng, Qiang, 2025. "Optimizing first-and-last-mile ridesharing services with a heterogeneous vehicle fleet and time-dependent travel times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    • Handle: RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004381
    DOI: 10.1016/j.tre.2024.103847
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554524004381
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2024.103847?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. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    2. 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.
    3. Hai Wang, 2019. "Routing and Scheduling for a Last-Mile Transportation System," Service Science, INFORMS, vol. 53(1), pages 131-147, February.
    4. Cai, Yutong & Ong, Ghim Ping & Meng, Qiang, 2022. "Dynamic bicycle relocation problem with broken bicycles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    5. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    6. Yu, Yang & Wang, Sihan & Wang, Junwei & Huang, Min, 2019. "A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 511-527.
    7. Shen, Yu & Zhang, Hongmou & Zhao, Jinhua, 2018. "Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore," Transportation Research Part A: Policy and Practice, Elsevier, vol. 113(C), pages 125-136.
    8. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    9. Ma, Tai-Yu & Rasulkhani, Saeid & Chow, Joseph Y.J. & Klein, Sylvain, 2019. "A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 417-442.
    10. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    11. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    12. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    13. Munise Kübra Şahin & Hande Yaman, 2022. "A Branch and Price Algorithm for the Heterogeneous Fleet Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 56(6), pages 1636-1657, November.
    14. Lucas Agussurja & Shih-Fen Cheng & Hoong Chuin Lau, 2019. "A State Aggregation Approach for Stochastic Multiperiod Last-Mile Ride-Sharing Problems," Service Science, INFORMS, vol. 53(1), pages 148-166, February.
    15. repec:osf:socarx:q86sd_v1 is not listed on IDEAS
    16. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.
    17. 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.
    18. Pessoa, Artur & Sadykov, Ruslan & Uchoa, Eduardo, 2018. "Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 270(2), pages 530-543.
    19. 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.
    20. A. Pessoa & R. Sadykov & E. Uchoa & F. Vanderbeck, 2018. "Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 339-360, May.
    21. Zhu, Zheng & Qin, Xiaoran & Ke, Jintao & Zheng, Zhengfei & Yang, Hai, 2020. "Analysis of multi-modal commute behavior with feeding and competing ridesplitting services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 132(C), pages 713-727.
    22. Liang, Xiao & Correia, Gonçalo Homem de Almeida & van Arem, Bart, 2016. "Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 115-129.
    23. Rick Grahn & Sean Qian & Chris Hendrickson, 2023. "Optimizing first- and last-mile public transit services leveraging transportation network companies (TNC)," Transportation, Springer, vol. 50(5), pages 2049-2076, October.
    24. 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.
    25. 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.
    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. 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.
    2. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    3. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2020. "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    4. 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.
    5. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    6. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    7. 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.
    8. 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).
    9. Rich, Jeppe & Seshadri, Ravi & Jomeh, Ali Jamal & Clausen, Sofus Rasmus, 2023. "Fixed routing or demand-responsive? Agent-based modelling of autonomous first and last mile services in light-rail systems," Transportation Research Part A: Policy and Practice, Elsevier, vol. 173(C).
    10. 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.
    11. 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.
    12. 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).
    13. Rick Grahn & Sean Qian & Chris Hendrickson, 2023. "Optimizing first- and last-mile public transit services leveraging transportation network companies (TNC)," Transportation, Springer, vol. 50(5), pages 2049-2076, October.
    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. 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.
    16. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    17. Wang, Yong & Wei, Zikai & Luo, Siyu & Zhou, Jingxin & Zhen, Lu, 2024. "Collaboration and resource sharing in the multidepot time-dependent vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    18. Su, Yue & Dupin, Nicolas & Parragh, Sophie N. & Puchinger, Jakob, 2024. "A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    19. Paul Czioska & Ronny Kutadinata & Aleksandar Trifunović & Stephan Winter & Monika Sester & Bernhard Friedrich, 2019. "Real-world meeting points for shared demand-responsive transportation systems," Public Transport, Springer, vol. 11(2), pages 341-377, August.
    20. He, Ping & Jin, Jian Gang & Trépanier, Martin & Schulte, Frederik, 2024. "A math-heuristic and exact algorithm for first-mile ridesharing problem with passenger service quality preferences," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).

    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:193:y:2025:i:c:s1366554524004381. 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.