EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A route-based algorithm for the electric vehicle routing problem with multiple technologies

Dario Bezzi, Alberto Ceselli, Giovanni Righini

Transportation Research Part C: Emerging Technologies · 2023-12 · 157 · 104374

DOI: 10.1016/j.trc.2023.104374 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Transportation Research Part C: Emerging Technologies, 2023-12. Verfasst von Dario Bezzi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 42-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Università degli Studi di Milano, Regione Lombardia.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

: Electric vehicles are seen as a pragmatic way of reducing emissions. In freight transportation, they prove to be appealing also in terms of costs, if proper planning algorithms are designed. We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers of given demand. Vehicles have limited batteries and limited time: they need to stop en-route to recharge stations. Our variant has two distinguishing features: recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates. We propose a novel exact algorithm. It relies on an extended formulation, having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We optimize it by branch-and-price. We design ad-hoc pricing algorithms, which exploit a special encoding of recharge plans, allowing for efficient bi-directional dynamic programming techniques. Extensive computational results show our approach to clearly outperform previous ones from the literature. Abstract Electric vehicles are seen as a pragmatic way of reducing emissions. In freight transportation, they prove to be appealing also in terms of costs, if proper planning algorithms are designed. We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers of given demand. Vehicles have limited batteries and limited time: they need to stop en-route to recharge stations. Our variant has two distinguishing features: recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates. We propose a novel exact algorithm. It relies on an extended formulation, having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We optimize it by branch-and-price. We design ad-hoc pricing algorithms, which exploit a special encoding of recharge plans, allowing for efficient bi-directional dynamic programming techniques. Extensive computational results show our approach to clearly outperform previous ones from the literature.

Förderung

  • Università degli Studi di Milano
  • Regione Lombardia

Zitieren

APA

Bezzi, D., Ceselli, A., & Righini, G. (2023). A route-based algorithm for the electric vehicle routing problem with multiple technologies. Transportation Research Part C: Emerging Technologies, 157, 104374. https://doi.org/10.1016/j.trc.2023.104374

Vancouver

Bezzi D, Ceselli A, Righini G. A route-based algorithm for the electric vehicle routing problem with multiple technologies. Transportation Research Part C: Emerging Technologies. 2023;157:104374. doi:10.1016/j.trc.2023.104374

BibTeX
@article{Bezzi2023,
  author = {Bezzi, Dario and Ceselli, Alberto and Righini, Giovanni},
  title = {A route-based algorithm for the electric vehicle routing problem with multiple technologies},
  journal = {Transportation Research Part C: Emerging Technologies},
  year = {2023},
  volume = {157},
  pages = {104374},
  doi = {10.1016/j.trc.2023.104374}
}
Kostenlos starten →