{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T14:02:15Z","timestamp":1782741735406,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T00:00:00Z","timestamp":1782691200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>We address the electric autonomous dial-a-ride problem (E-ADARP), a challenging extension of the dial-a-ride problem with the goal of finding minimum-cost routes serving given transportation requests with a fleet of electric and autonomous vehicles (EAVs). Special emphasis lies on the minimization of user excess ride time under consideration of the charging requirements of the EAVs, while operational constraints have to be satisfied. We propose a novel large neighborhood search (LNS) approach for the E-ADARP together with two alternatives for handling the charging of the EAVs, the scheduling, and route evaluation. One deals with these challenges separately using dedicated LNS operators and a forward labeling algorithm, and the other provides a combined approach with on-the-fly charging stop insertion during route evaluation. The performance of the algorithms is evaluated on various configurations of two common benchmark sets as well as some very large-scale instances. Results show that especially the approach with the on-the-fly insertion almost consistently outperforms former state-of-the-art techniques on the common benchmark instances, finding many new best known solutions. For this best performing approach, multiple variants of a more advanced destroy operator for the underlying LNS are investigated. This enhancement can yield significantly improved performance, especially on the very large instances, as illustrated by further empirical results.<\/jats:p>","DOI":"10.1145\/3779426","type":"journal-article","created":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T16:17:18Z","timestamp":1765297038000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Revisiting Large Neighborhood Search with On-the-Fly Charging Station Insertion for the Electric Autonomous Dial-a-Ride Problem"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8291-6765","authenticated-orcid":false,"given":"Maria","family":"Bresich","sequence":"first","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3293-177X","authenticated-orcid":false,"given":"G\u00fcnther R.","family":"Raidl","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2385-7886","authenticated-orcid":false,"given":"Steffen","family":"Limmer","sequence":"additional","affiliation":[{"name":"Honda Research Institute Europe GmbH, Offenbach, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,29]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2024.106588"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2022.102835"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2019.03.004"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2014.05.007"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2016.09.010"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3638529.3654057"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-82949-9_20"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0283"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0191-2615(02)00045-0"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.15837\/ijccc.2009.2.2420"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.06.044"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1535"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(91)90319-Q"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.12.014"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.05.010"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0531"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2018.02.001"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC65147.2025.11042942"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-94216-8_1"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602287"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113714"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2016.01.013"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trip.2023.100876"},{"issue":"54","key":"e_1_3_2_26_1","first-page":"1","article-title":"SMAC3: A versatile Bayesian optimization package for hyperparameter optimization","volume":"23","author":"Lindauer Marius","year":"2022","unstructured":"Marius Lindauer, Katharina Eggensperger, Matthias Feurer, Andr\u00e9 Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, Ren\u00e9 Sass, and Frank Hutter. 2022. SMAC3: A versatile Bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research 23, 54 (2022), 1\u20139. Retrieved from http:\/\/jmlr.org\/papers\/v23\/21-0888.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2021.107614"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2016.10.002"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2018.08.005"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2017.09.001"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-017-2525-0"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.07.020"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2019.12.008"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081068008717184"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2010.06.002"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-010-0229-9"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.10.003"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.08.004"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5_13"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0524"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2021.1044"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1090.0272"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20177"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1050.0135"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-815018-4.00003-6"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49481-2_30"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2024.103011"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.02.012"},{"key":"e_1_3_2_49_1","volume-title":"Proceedings of the 11th International Conference on Machine Learning, Optimization, and Data Science (LOD \u201925)","author":"Tomandl Laurenz","year":"2025","unstructured":"Laurenz Tomandl, Maria Bresich, G\u00fcnther R. Raidl, Yi Mei, Steffen Limmer, and Tobias Rodemann. 2025. A reinforcement learning guided large neighborhood search for the dynamic electric autonomous dial-a-ride problem. In Proceedings of the 11th International Conference on Machine Learning, Optimization, and Data Science (LOD \u201925). Springer, in press."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3779426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T13:33:17Z","timestamp":1782739997000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3779426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,29]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3779426"],"URL":"https:\/\/doi.org\/10.1145\/3779426","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,29]]},"assertion":[{"value":"2024-12-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}