IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v193y2025ics1366554524004381.html

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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Hai Wang, 2019. "Routing and Scheduling for a Last-Mile Transportation System," Service Science, INFORMS, vol. 53(1), pages 131-147, February.
    10. 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).
    11. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. repec:osf:socarx:q86sd_v1 is not listed on IDEAS
    20. 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.
    21. 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.
    22. 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.
    23. 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.
    24. 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.
    25. 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.
    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. He, Qingying & Liu, Wei & Xi, Haoning, 2025. "Dynamic electric vehicle fleets management problem for multi-service platforms with integrated ride-hailing, on-time delivery, and vehicle-to-grid services," Transportation Research Part B: Methodological, Elsevier, vol. 199(C).
    2. Sun, Bo & Yu, Bin & Liu, Zhiyuan & Zhang, Li, 2025. "Integrating freight transport into first-and-last-mile ridesharing services with modular autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 202(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. Sun, Bo & Yu, Bin & Liu, Zhiyuan & Zhang, Li, 2025. "Integrating freight transport into first-and-last-mile ridesharing services with modular autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 202(C).
    2. 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.
    3. 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.
    4. Lu, Jiawei & Ye, Tinghan & Chen, Wenbo & Van Hentenryck, Pascal, 2025. "Boosting column generation with graph neural networks for joint rider trip planning and crew shift scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 202(C).
    5. Shariat, Negin & Yang, Dingtong & Jayakrishnan, R., 2025. "Partnering with transportation network companies (TNCs) for low-demand service: is it viable and beneficial for transit agencies?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 201(C).
    6. 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).
    7. 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.
    8. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    9. Fang, Yumeng & Ma, Tai-Yu, 2026. "A hybrid large neighborhood search algorithm for the integrated dial-a-ride problem using electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 206(C).
    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. 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.
    12. 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.
    13. 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).
    14. 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).
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Guo, Shuocheng & Dayarian, Iman & Li, Jian & Qian, Xinwu, 2025. "Solving the equity-aware dial-a-ride problem using an exact branch-cut-and-price algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    20. 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).

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.