Demand responsive transport; Electric vehicle; Meeting point; Metaheuristic; Synchronization constraint mixed integer linear programming; Feeder service; First mile; Hybrid metaheuristics; Integer Linear Programming; Mixed integer linear; Synchronization constraints; Business and International Management; Civil and Structural Engineering; Transportation; Synchronization constraint mixed integer; linear programming
Abstract :
[en] This paper addresses the on-demand meeting-point-based feeder electric bus routing and charging scheduling problem under charging synchronization constraints. The problem considered exhibits the structure of the location routing problem, which is more difficult to solve than many electric vehicle routing problems with capacitated charging stations. We propose to model the problem using a mixed-integer linear programming approach based on a layered graph structure. An efficient hybrid metaheuristic solution algorithm is proposed. A mixture of random and greedy partial charging scheduling strategies is used to find feasible charging schedules under the synchronization constraints. The algorithm is tested on instances with up to 100 customers and 49 bus stops/meeting points. The results show that the proposed algorithm provides near-optimal solutions within less one minute on average compared with the best solutions found by a mixed-integer linear programming solver set with a 4-hour computation time limit. A case study on a larger sized case with 1000 customers and 111 meeting points shows the proposed method is applicable to real-world situations.
Disciplines :
Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
MA, Tai-Yu ; University of Luxembourg ; Luxembourg Institute of Socio-Economic Research (LISER), Esch-sur-Alzette, Luxembourg
FANG, Yumeng ; University of Luxembourg ; Luxembourg Institute of Socio-Economic Research (LISER), Esch-sur-Alzette, Luxembourg
CONNORS, Richard ; University of Luxembourg > Faculty of Science, Technology and Medicine > Department of Engineering > Team Francesco VITI
VITI, Francesco ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Engineering (DoE)
NAKAO, Haruko ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Engineering (DoE)
External co-authors :
no
Language :
English
Title :
A hybrid metaheuristic to optimize electric first-mile feeder services with charging synchronization constraints and customer rejections
Publication date :
May 2024
Journal title :
Transportation Research. Part E, Logistics and Transportation Review
Aïvodji, U.M., Gambs, S., Huguet, M.-J., Killijian, M.-O., Meeting points in ridesharing: a privacy-preserving approach. Transp. Res. Part C Emerg. Technol. 72 (2016), 239–253, 10.1016/j.trc.2016.09.017.
Alonso-González, M.J., Liu, T., Cats, O., Van Oort, N., Hoogendoorn, S., The potential of demand-responsive transport as a complement to public transport: an assessment framework and an empirical evaluation. Transp. Res. Rec., 2672, 2018, 10.1177/0361198118790842.
Arnold, F., Sörensen, K., Knowledge-guided local search for the vehicle routing problem. Comput. Oper. Res. 105 (2019), 32–46, 10.1016/j.cor.2019.01.002.
Belenguer, J.M., Benavent, E., Prins, C., Prodhon, C., Wolfler Calvo, R., A branch-and-cut method for the capacitated location-routing problem. Comput. Oper. Res. 38 (2011), 931–941, 10.1016/J.COR.2010.09.019.
Bian, Z., Liu, X., Mechanism design for first-mile ridesharing based on personalized requirements part I: theoretical analysis in generalized scenarios. Transp. Res. Part B Methodol. 120 (2019), 147–171, 10.1016/j.trb.2018.12.009.
Bongiovanni, C., Kaspi, M., Geroliminis, N., The electric autonomous dial-a-ride problem. Transp. Res. Part B Methodol. 122 (2019), 436–456, 10.1016/j.trb.2019.03.004.
Braekers, K., Caris, A., Janssens, G.K., Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transp. Res. Part B Methodol. 67 (2014), 166–186, 10.1016/j.trb.2014.05.007.
Bruglieri, M., Mancini, S., Pisacane, O., The green vehicle routing problem with capacitated alternative fuel stations. Comput. Oper. Res., 112, 2019, 10.1016/j.cor.2019.07.017.
Bruglieri, M., Mancini, S., Pisacane, O., A more efficient cutting planes approach for the green vehicle routing problem with capacitated alternative fuel stations. Optim. Lett. 15 (2021), 2813–2829, 10.1007/S11590-021-01714-3/FIGURES/3.
Chen, P.W., Nie, Y.M., Analysis of an idealized system of demand adaptive paired-line hybrid transit. Transp. Res. Part B Methodol. 102 (2017), 38–54, 10.1016/j.trb.2017.05.004.
Cordeau, J.F., Laporte, G., A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B Methodol. 37 (2003), 579–594, 10.1016/S0191-2615(02)00045-0.
Czioska, P., Kutadinata, R., Trifunović, A., Winter, S., Sester, M., Friedrich, B., Real-World Meeting Points for Shared Demand-Responsive Transportation Systems, Public Transport. 2019, Springer, Berlin, Heidelberg doi: 10.1007/s12469-019-00207-y.
Desaulniers, G., Errico, F., Irnich, S., Schneider, M., Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64 (2016), 1388–1405, 10.1287/opre.2016.1535.
Dueck, G., Scheuer, T., Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J. Comput. Phys. 90:1 (1990), 161–175.
Erdoğan, S., Miller-Hooks, E., A green vehicle routing problem. Transp. Res. Part E Logist. Transp. Rev. 48 (2012), 100–114, 10.1016/j.tre.2011.08.001.
Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G., A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transp. Res. Part E Logist. Transp. Rev. 71 (2014), 111–128, 10.1016/j.tre.2014.09.003.
Froger, A., Mendoza, J.E., Jabali, O., Laporte, G., 2017. A Matheuristic for the Electric Vehicle Routing Problem with Capacitated Charging Stations. Working paper. CIRRELT-2017-31.
Froger, A., Jabali, O., Mendoza, J.E., Laporte, G., The electric vehicle routing problem with capacitated charging stations. Transp. Sci. 56 (2021), 460–482, 10.1287/TRSC.2021.1111.
Goeke, D., Schneider, M., Routing a mixed fleet of electric and conventional vehicles. Eur. J. Oper. Res. 245 (2015), 81–99, 10.1016/j.ejor.2015.01.049.
Haglund, N., Mladenović, M.N., Kujala, R., Weckström, C., Saramäki, J., Where did Kutsuplus drive us? Ex post evaluation of on-demand micro-transit pilot in the Helsinki capital region. Res. Transp. Bus. Manag., 32, 2019, 10.1016/j.rtbm.2019.100390.
Jenn, A., Electrifying Ride-Sharing: Transitioning to a Cleaner Future. 2019, National Center for Sustainable Transportation, UC Davis Retrieved from https://escholarship.org/uc/item/12s554kd.
Keskin, M., Çatay, B., Partial recharge strategies for the electric vehicle routing problem with time windows. Transp. Res. Part C Emerg. Technol. 65 (2016), 111–127, 10.1016/j.trc.2016.01.013.
Keskin, M., Laporte, G., Çatay, B., Electric vehicle routing problem with time-dependent waiting times at recharging stations. Comput. Oper. Res. 107 (2019), 77–94, 10.1016/j.cor.2019.02.014.
Kucukoglu, I., Dewil, R., Cattrysse, D., The electric vehicle routing problem and its variations: a literature review. Comput. Ind. Eng., 161, 2021, 107650, 10.1016/j.cie.2021.107650.
Lam, E., Desaulniers, G., Stuckey, P.J., Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations. Comput. Oper. Res., 145, 2022, 105870, 10.1016/J.COR.2022.105870.
Lambotte, J. M., Marbehant, S., Rouchet, H., 2021. Distribution spatiale de l'emploi et des modes de transport des travailleurs actifs au Grand-Duché de Luxembourg–Analyse des données de l'enquête Luxmobil 2017. UniGR-CBS Working Paper, 11.
Lee, A., Savelsbergh, M., An extended demand responsive connector. EURO J. Transp. Logist. 6 (2017), 25–50, 10.1007/s13676-014-0060-6.
Lutz, R. 2004. Adaptive Large Neighborhood Search. Bachelor thesis at Ulm University.
Ma, T.Y., Chow, J.Y.J., Klein, S., Ma, Z., A user-operator assignment game with heterogeneous user groups for empirical evaluation of a microtransit service in Luxembourg. Transp. A Transp. Sci. 17 (2021), 946–973, 10.1080/23249935.2020.1820625.
Ma, T.-Y., Rasulkhani, S., Chow, J.Y.J., Klein, S., A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers. Transp. Res. Part E Logist. Transp. Rev. 128 (2019), 417–442, 10.1016/j.tre.2019.07.002.
Macrina, G., Di Puglia Pugliese, L., Guerriero, F., Laporte, G., The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Comput. Oper. Res. 101 (2019), 183–199, 10.1016/j.cor.2018.07.012.
Melis, L., Queiroz, M., Sörensen, K., The integrated on-demand bus routing problem. Working Papers 2021004. 2021, University of Antwerp, Faculty of Business and Economics.
Melis, L., Sörensen, K., The static on-demand bus routing problem: large neighborhood search for a dial-a-ride problem with bus station assignment. Int. Trans. Oper. Res. 29 (2022), 1417–1453, 10.1111/itor.13058.
Montenegro, B.D.G., Sörensen, K., Vansteenwegen, P., A large neighborhood search algorithm to optimize a demand-responsive feeder service. Transp. Res. Part C Emerg. Technol., 127, 2021, 103102, 10.1016/j.trc.2021.103102.
Montenegro, B.D.G., Sörensen, K., Vansteenwegen, P., A column generation algorithm for the demand-responsive feeder service with mandatory and optional, clustered bus-stops. Networks 80 (2022), 274–296, 10.1002/net.22095.
Park, J., Kim, B.-I., The school bus routing problem: a review. Eur. J. Oper. Res. 202 (2010), 311–319, 10.1016/j.ejor.2009.05.017.
Parragh, S.N., Doerner, K.F., Hartl, R.F., Variable neighborhood search for the dial-a-ride problem. Comput. Oper. Res. 37 (2010), 1129–1138, 10.1016/j.cor.2009.10.003.
Pimenta, V., Quilliot, A., Toussaint, H., Vigo, D., Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles. Eur. J. Oper. Res. 257 (2017), 601–613, 10.1016/j.ejor.2016.07.037.
Ropke, S., Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40 (2006), 455–472, 10.1287/trsc.1050.0135.
Schittekat, P., Kinable, J., Sörensen, K., Sevaux, M., Spieksma, F., Springael, J., A metaheuristic for the school bus routing problem with bus stop selection. Eur. J. Oper. Res. 229 (2013), 518–528, 10.1016/j.ejor.2013.02.025.
Schneider, M., Stenger, A., Goeke, D., The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci. 48 (2014), 500–520, 10.1287/trsc.2013.0490.
Stiglic, M., Agatz, N., Savelsbergh, M., Gradisar, M., The benefits of meeting points in ride-sharing systems. Transp. Res. Part B Methodol. 82 (2015), 36–53, 10.1016/j.trb.2015.07.025.
Vansteenwegen, P., Melis, L., Aktaş, D., Montenegro, B.D.G., Sartori Vieira, F., Sörensen, K., A survey on demand-responsive public bus systems. Transp. Res. Part C Emerg. Technol., 137, 2022, 103573, 10.1016/j.trc.2022.103573.
Wang, F., Ross, C.L., New potential for multimodal connection: exploring the relationship between taxi and transit in New York City (NYC). Transportation (Amst). 46 (2019), 1051–1072, 10.1007/s11116-017-9787-x.
Zheng, Y., Li, W., Qiu, F., Wei, H., The benefits of introducing meeting points into flex-route transit services. Transp. Res. Part C Emerg. Technol. 106 (2019), 98–112, 10.1016/j.trc.2019.07.012.
