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 with given demands. An upper limit is imposed on the duration of the routes. Vehicles have limited autonomy: they may need to stop en-route at recharge stations. Recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates.We present a new a branch-and-price algorithm, that relies on an extended formulation having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We design ad-hoc pricing algorithms, which exploit a novel 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, being able to solve instances with up to 30 customers, 5 stations, 7 vehicles and 3 technologies to proven optimality within some minutes on a standard PC.
A route-based algorithm for the electric vehicle routing problem with multiple technologies / D. Bezzi, A. Ceselli, G. Righini. - In: TRANSPORTATION RESEARCH. PART C, EMERGING TECHNOLOGIES. - ISSN 0968-090X. - 157:(2023), pp. 104374.1-104374.16. [10.1016/j.trc.2023.104374]
A route-based algorithm for the electric vehicle routing problem with multiple technologies
D. Bezzi;A. Ceselli
Secondo
;G. RighiniUltimo
2023
Abstract
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 with given demands. An upper limit is imposed on the duration of the routes. Vehicles have limited autonomy: they may need to stop en-route at recharge stations. Recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates.We present a new a branch-and-price algorithm, that relies on an extended formulation having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We design ad-hoc pricing algorithms, which exploit a novel 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, being able to solve instances with up to 30 customers, 5 stations, 7 vehicles and 3 technologies to proven optimality within some minutes on a standard PC.File | Dimensione | Formato | |
---|---|---|---|
53 - 2023 TRC - EVRP route based.pdf
accesso aperto
Descrizione: Article
Tipologia:
Publisher's version/PDF
Dimensione
625.58 kB
Formato
Adobe PDF
|
625.58 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.