Data di Pubblicazione:
2018
Citazione:
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.
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.
Tipologia IRIS:
14 - Intervento a convegno non pubblicato
Keywords:
Green routing; Dynamic programming; Column generation
Elenco autori:
D. Bezzi, A. Ceselli, G. Righini
Link alla scheda completa: