Dynamic programming for the Electric Vehicle Orienteering Problem with multiple technologies

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.