The Electric Vehicle Routing Problem (EVRP) has been introduced by Erdogan and Miller-Hooks under the name of Green Vehicle Routing Problem. Several varia- tions have been studied, including problem with time windows, partial recharges, multiple technologies and both exact and heuristic algorithms have been developed. Examples of heuristic algorithms for the EVRP are given in Felipe et al., Schneider et al. and Koc and Karaoglan. More references on VRP variants involving the use of electric vehicles can be found in a recent and extensive survey by Pelletier et al. The computation of exact solutions is more challenging than for the classical VRP, because of the additional subproblem of deciding the optimal recharges at some points along the routes. An additional source of complexity is the presence of different recharge technologies, each one characterized by a unit cost and a recharge speed. Schiffer and Walther recently considered a similar problem in the context of location-routing. Sweda et al. studied the optimal recharge policy when the route is given. As with many other variations of the VRP, the most common choice to design effective exact optimization algorithms is to rely upon branch-and-cut-and-price, starting from a reformulation of the routing problem as a set covering or set partitioning problem, where each column represents the duty of a vehicle. For instance, Desaulniers et al. developed a branch- and-price-and-cut algorithm for the exact solution of the EVRP with time windows. In this study we investigate the Electric Vehicle Orienteering Problem, arising as a pricing sub-problem when the EVRP is solved by branch-and-price and in particular we consider a dynamic programming algorithm for the case with multiple technologies.

Dynamic programming for the Electric Vehicle Orienteering Problem with multiple technologies / D. Bezzi, A. Ceselli, G. Righini. ((Intervento presentato al 7. convegno Odysseus tenutosi a Cagliari nel 2018.

Dynamic programming for the Electric Vehicle Orienteering Problem with multiple technologies

D. Bezzi;A. Ceselli;G. Righini
2018-06-04

Abstract

The Electric Vehicle Routing Problem (EVRP) has been introduced by Erdogan and Miller-Hooks under the name of Green Vehicle Routing Problem. Several varia- tions have been studied, including problem with time windows, partial recharges, multiple technologies and both exact and heuristic algorithms have been developed. Examples of heuristic algorithms for the EVRP are given in Felipe et al., Schneider et al. and Koc and Karaoglan. More references on VRP variants involving the use of electric vehicles can be found in a recent and extensive survey by Pelletier et al. The computation of exact solutions is more challenging than for the classical VRP, because of the additional subproblem of deciding the optimal recharges at some points along the routes. An additional source of complexity is the presence of different recharge technologies, each one characterized by a unit cost and a recharge speed. Schiffer and Walther recently considered a similar problem in the context of location-routing. Sweda et al. studied the optimal recharge policy when the route is given. As with many other variations of the VRP, the most common choice to design effective exact optimization algorithms is to rely upon branch-and-cut-and-price, starting from a reformulation of the routing problem as a set covering or set partitioning problem, where each column represents the duty of a vehicle. For instance, Desaulniers et al. developed a branch- and-price-and-cut algorithm for the exact solution of the EVRP with time windows. In this study we investigate the Electric Vehicle Orienteering Problem, arising as a pricing sub-problem when the EVRP is solved by branch-and-price and in particular we consider a dynamic programming algorithm for the case with multiple technologies.
Green routing; Dynamic programming; Column generation
Settore MAT/09 - Ricerca Operativa
Università degli studi di Cagliari
Dynamic programming for the Electric Vehicle Orienteering Problem with multiple technologies / D. Bezzi, A. Ceselli, G. Righini. ((Intervento presentato al 7. convegno Odysseus tenutosi a Cagliari nel 2018.
Conference Object
File in questo prodotto:
File Dimensione Formato  
Odysseus_presentazione.pdf

accesso aperto

Descrizione: Lucidi presentazione
Tipologia: Altro
Dimensione 302.81 kB
Formato Adobe PDF
302.81 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/746534
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact