The electric vehicle shortest path problem with time windows and prize collection

• Autorzy: Cassia Antonio , Jabali Ola , Malucelli Federico , Pascoal Marta

Identyfikatory

DOI

10.15439/2022F186

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

The Electric Vehicle Shortest Path Problem (EVSPP) aims at finding the shortest path for an electric vehicle (EV) from a given origin to a given destination. During long trips, the limited autonomy of the EV may imply several stops for recharging its battery. We consider combining such stops with visiting points of interest near charging stations (CSs). Specifically, we address a version of the EVSPP in which the charging decisions are harmonized driver's preferences. The goal is to maximize the total gained score (assigned by the driver to the CSs), while respecting the time windows and the EV autonomy constraints. We define the problem as a MILP and develop a A* search heuristic to solve it. We evaluate the method by means of extensive computational experiments on realistic instances.

Słowa kluczowe

EN

shortest path problem; computer science; heuristic algorithm; charging station; electric vehicle; search problems; battery

PL

problem najkrótszej ścieżki; informatyka; algorytm heurystyczny; stacja ładowania; pojazd elektryczny; problemy wyszukiwawcze; akumulator

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 313--322
• Opis fizyczny: Bibliogr. 14 poz., il., tab., wz.

Twórcy

autor

Cassia Antonio

• Politecnico di Milano, Italy

autor

Jabali Ola

• Politecnico di Milano, Italy

autor

Malucelli Federico

• Politecnico di Milano, Italy

autor

Pascoal Marta

• University of Coimbra, CMUC, INESC-Coimbra, Portugal
• Politecnico di Milano, Italy

Bibliografia

• 1. M. Baum, J. Dibbelt, A. Gemsa, D. Wagner, and T. Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. In Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems, pages 1–10, 2015. https://doi.org/10.1145/2820783.2820826.
• 2. M. Baum, J. Dibbelt, T. Pajor, J. Sauer, D. Wagner, and T. Zündorf. Energy-optimal routes for battery electric vehicles. Algorithmica, 82:1490–1546, 2020. https://doi.org/10.1007/s00453-019-00655-9.
• 3. API ChargePrice.com. Open EV Data, Chargeprice.app API. https://github.com/chargeprice/open-ev-data. Accessed: 18-03-2022.
• 4. S. Erdoğan and E. Miller-Hooks. A green vehicle routing problem. Transportation research part E: logistics and transportation review, 48:100–114, 2012. https://doi.org/10.1016/j.tre.2011.08.001.
• 5. E. Fadda, D. Manerba, G. Cabodi, P. Camurati, and R. Tadei. Kpis for optimal location of charging stations for electric vehicles: the biella case-study. In 2019 Federated Conference on Computer Science and Information Systems (FedCSIS), pages 123–126. IEEE, 2019. http://dx.doi.org/10.15439/2019F171.
• 6. A. Froger, J. E. Mendoza, O. Jabali, and G. Laporte. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions. Computers & Operations Research, 104:256–294, 2019. https://doi.org/10.1016/j.cor.2018.12.013.
• 7. P. Kaeding. MapCustomizer. https://www.mapcustomizer.com. Accessed: 12-03-2022.
• 8. D. Luxen and C. Vetter. Real-time routing with openstreetmap data. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’11, pages 513–516, New York, NY, USA, 2011. ACM. https://doi.org/10.1145/2093973. 2094062.
• 9. A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas. A multi-space sampling heuristic for the green vehicle routing problem. Transportation Research Part C: Emerging Technologies, 70:113–128, 2016. https://doi.org/10.1016/j.trc.2015.09.009.
• 10. A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas. The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103:87–110, 2017. https://doi.org/10.1016/j.trb.2017.02.004.
• 11. M. Schiffer, S. Stütz, and G. Walther. Electric commercial vehicles in mid-haul logistics networks. In Behaviour of Lithium-Ion Batteries in Electric Vehicles, pages 153–173. Springer, 2018. https://doi.org/10.1007/978-3-319-69950-9_7.
• 12. M. Schneider, A. Stenger, and D. Goeke. The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48:500–520, 2014. https://doi.org/10.1287/trsc.2013.0490.
• 13. T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins. Heuristics for multi-attribute vehicle routing problems: A survey and synthe sis. European Journal of Operational Research, 231:1–21, 2013. https://doi.org/10.1016/j.ejor.2013.02.053.
• 14. T. Zündorf. Electric vehicle routing with realistic recharging models. Unpublished Master’s thesis, Karlsruhe Institute of Technology, Karlsruhe, Germany, 2014.

Uwagi

1. Track 6: 15th International Workshop on Computational Optimization

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).