Comparing matheuristic approaches for the Electric Vehicle Routing Problem with Time Windows

This work addresses the Electric Vehicle Routing Problem with Time Windows (EVRPTW), which has been extensively studied in the recent years due to an increased attention to sustainability in transportation. E-VRPTW differs from the classical VRPTW because the service is provided by a fleet of Electric Vehicles (EVs). Since EVs have a reduced driving range due to the limited battery capacity with respect to their Energy Consumption (EC), possible stops at Recharging Stations (RSs) have to be considered. Among the different EC models introduced in the literature, we refer to that in [1], in which EC is a function of both the EV load and speed, so resulting more realistic. A further relevant feature for the proposed model is considering the EVs' speeds as decision variables. We present a cloneless Mixed Integer Linear Programming (MILP) model for this variant, without cloning the RSs, as done in most of the works in the literature, to avoid increasing the number of binary variables. Moreover, we design two different matheuristics both iterating the solution of reduced versions of the MILP model. In the first approach, subsets of the routing-variables are included exploiting a greedy randomized selection, whereas, in the second one a procedure called Randomized Kernel Search, inspired by the Kernel Search algorithm [2], is iterated. Finally, we compare the MILP model and matheuristics results on instances generated from a benchmark [3]. [1 ] Y. Xiao, X. Zuo, I. Kaku, S. Zhou, X. Pan, Development of energy consumption optimization model for the electric vehicle routing problem with time windows, J Clean Prod 225 (2019) 647-663 [2 ] E. Angelelli, R. Mansini, M. G. Speranza, Kernel search: A general heuristic for the multi-dimensional knapsack problem, Comput & Oper Res 37 (11) (2010) 2017-2026 [3 ] M. Schneider, A. Stenger, D. Goeke, The electric vehicle-routing problem with time windows and recharging stations, Transp Sci 48 (4)(2014) 500-520