Heuristic Solutions for Electric Vehicle Routing Problem with Time Windows and Recharging Stations

Due to the regulation and laws concerning the emission of greenhouse gasses, carriers are starting to use electric vehicles for last-mile deliveries. The limited battery capacities of these vehicles necessitate visits to recharging stations during delivery tours of industry-typical length, which have to be considered in the route planning to avoid inefficient vehicle routes with long detours. This thesis seeks to propose new heuristic solution methods for Electric Vehicle Routing Problem with Time Windows (E-VRPTW), which incorporates the possibility of recharging at any of the available charging stations to minimize the total travel distance based on the Clarke and Wright (CW) Saving Heuristic. The solution method focuses on the construction of routes according to waiting time of vehicles, determined priority of customers with regard to their earliest starting service time, customers’ demands and etc. Moreover, the recharging rate, vehicle freight capacity, battery capacity, time windows and recharging time are considered to make it close to real-life logistics problems. Numerical tests are performed on newly designed instances by Schneider and performances of proposed methods are discussed. Keywords: Vehicle Routing Problem, Clarke and Wright Saving Heuristic, Green Logistic, Electric Vehicles, Combinatorial Optimization