Large Neighborhood Search for the Electric Dial-A-Ride Problem Integrated with Timetabled Transit

FANG, Yumeng; MA, Tai-Yu; VITI, Francesco

doi:10.1109/MT-ITS68460.2025.11223580

Request a copy

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Large Neighborhood Search for the Electric Dial-A-Ride Problem Integrated with Timetabled Transit

FANG, Yumeng; MA, Tai-Yu; VITI, Francesco

2025 • In 2025 9th International Conference on Models and Technologies for Intelligent Transportation Systems, MT-ITS 2025

Peer reviewed

Permalink
https://hdl.handle.net/10993/67274

DOI
10.1109/MT-ITS68460.2025.11223580

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

[My Submission] MT-ITS2025_paper_118.pdf

Author preprint (527.07 kB)

Request a copy

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

capacitated charging station; electric vehicles; metaheuristics; Capacitated charging station; Dial-a-ride problem; Hybrid metaheuristics; Computer Science Applications

Abstract :

[en] Integrating demand-responsive mobility services with transit systems is recognized as a practical and effective strategy to mitigate their impact on traffic congestion and the environment. This paper develops an efficient hybrid metaheuristic to solve the corresponding integrated dial-a-ride problem utilizing electric vehicles to minimize both operational costs and customer travel time. The system aims to improve customer convenience by limiting a maximum intermodal transfer time to synchronize demand-responsive buses' arrival and transit departures. The proposed metaheuristic addresses the challenges of optimizing the integrated demand-responsive vehicle routing and charging operations with fixed-route transit systems with capacitated charging stations and partial recharge. The algorithm is tested on instances with up to 50 customers, outperforming an 8-hour state-of-the-art solver by 23% in solution quality, with an average runtime of 136 seconds.

Disciplines :

Computer science

Author, co-author :

FANG, Yumeng ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Engineering (DoE) ; Luxembourg Institute of Socio-Economic Research, Department of Urban Development and Mobility, Esch-sur-Alzette, Luxembourg

MA, Tai-Yu ; University of Luxembourg ; Luxembourg Institute of Socio-Economic Research, Department of Urban Development and Mobility, Esch-sur-Alzette, Luxembourg

VITI, Francesco ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Engineering (DoE)

External co-authors :

yes

Language :

English

Title :

Large Neighborhood Search for the Electric Dial-A-Ride Problem Integrated with Timetabled Transit

Publication date :

2025

Event name :

2025 9th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS)

Event place :

Luxembourg, Lux

Event date :

08-09-2025

Audience :

International

Main work title :

2025 9th International Conference on Models and Technologies for Intelligent Transportation Systems, MT-ITS 2025

Publisher :

Institute of Electrical and Electronics Engineers Inc.

ISBN/EAN :

9798331580636

Peer reviewed :

Peer reviewed

Additional URL :

http://xplorestaging.ieee.org/ielx8/11223286/11223517/11223580.pdf?arnumber=11223580

Available on ORBilu :

since 13 January 2026

Statistics

Number of views

16 (0 by Unilu)

Number of downloads

0 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

B. Schaller, "Can sharing a ride make for less traffic? Evidence from Uber and Lyft and implications for cities," Transp Policy (Oxf), vol. 102, pp. 1-10, Mar. 2021, doi: 10.1016/J.TRANPOL.2020.12.015.
A. Henao and W. E. Marshall, "The impact of ride-hailing on vehicle miles traveled," Transportation (Amst), vol. 46, no. 6, pp. 2173-2194, Dec. 2019, doi: 10.1007/S11116-018-9923-2/TABLES/6.
A. Tirachini and A. Gomez-Lobo, "Does ride-hailing increase or decrease vehicle kilometers traveled (VKT)? A simulation approach for Santiago de Chile," Int J Sustain Transp, vol. 14, no. 3, pp. 187-204, Jan. 2020, doi: 10.1080/15568318.2018.1539146.
M. Behroozi, "Understanding the Impact of Ridesharing Services on Traffic Congestion," Reengineering the Sharing Economy, pp. 119-145, Mar. 2023, doi: 10.1017/9781108865630.011.
L. Zha, Y. Yin, and Y. Du, "Surge pricing and labor supply in the ride-sourcing market," Transportation Research Part B: Methodological, vol. 117, pp. 708-722, Nov. 2018, doi: 10.1016/J.TRB.2017.09.010.
T. Y. Ma, S. Rasulkhani, J. Y. J. Chow, and S. Klein, "A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers," Transp Res E Logist Transp Rev, vol. 128, pp. 417-442, Aug. 2019, doi: 10.1016/J.TRE.2019.07.002.
C. H. Häll, H. Andersson, J. T. Lundgren, and P. Värbrand, "The Integrated Dial-A-Ride Problem," Public Transport, vol. 1, no. 1, pp. 39-54, May 2009, doi: 10.1007/S12469-008-0006-1/METRICS.
M. Posada, H. Andersson, and C. H. Häll, "The integrated dial-A-ride problem with timetabled fixed route service," Public Transport, vol. 9, no. 1-2, pp. 217-241, Jul. 2017, doi: 10.1007/S12469-016-0128-9/TABLES/2.
M. Posada and C. H. Häll, "A metaheuristic for evaluation of an integrated special transport service," International Journal of Urban Sciences, vol. 24, no. 3, pp. 316-338, 2020, doi: 10.1080/12265934.2019.1709533.
Y. Molenbruch, K. Braekers, P. Hirsch, and M. Oberscheider, "Analyzing the benefits of an integrated mobility system using a matheuristic routing algorithm," Eur J Oper Res, vol. 290, no. 1, pp. 81-98, Apr. 2021, doi: 10.1016/J.EJOR.2020.07.060.
Y. Su, N. Dupin, S. N. Parragh, and J. Puchinger, "A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem," Transportation Research Part B: Methodological, vol. 186, p. 103011, Aug. 2024, doi: 10.1016/J.TRB.2024.103011.
M. Aldaihani and M. M. Dessouky, "Hybrid scheduling methods for paratransit operations," Comput Ind Eng, vol. 45, no. 1, pp. 75-96, Jun. 2003, doi: 10.1016/S0360-8352(03)00032-9.
T. Y. Ma and Y. Fang, "Survey of charging management and infrastructure planning for electrified demand-responsive transport systems: Methodologies and recent developments," European Transport Research Review, vol. 14, no. 1, pp. 1-19, Dec. 2022, doi: 10.1186/S12544-022-00560-3/TABLES/5.
Y. Fang, T.-Y. Ma, and F. Viti, "Electric integrated dial-A-ride services with capacitated charging stations, multiple depots, and customer rejections," Nov. 2024. hal.science/hal-04765441.
S. N. Parragh, "Introducing heterogeneous users and vehicles into models and algorithms for the dial-A-ride problem," Transp Res Part C Emerg Technol, vol. 19, no. 5, pp. 912-930, 2011, doi: 10.1016/j.trc.2010.06.002.
S. T. Windras Mara, R. Norcahyo, P. Jodiawan, L. Lusiantoro, and A. P. Rifai, "A survey of adaptive large neighborhood search algorithms and applications," Comput Oper Res, vol. 146, p. 105903, Oct. 2022, doi: 10.1016/J.COR.2022.105903.
J. F. Cordeau and G. Laporte, "A tabu search heuristic for the static multi-vehicle dial-A-ride problem," Transportation Research Part B: Methodological, vol. 37, no. 6, pp. 579-594, Jul. 2003, doi: 10.1016/S0191-2615(02)00045-0.