Recharge strategies for the electric vehicle routing problem with time windows in deterministic and stochastic environments

Official URL: http://risc01.sabanciuniv.edu/record=b1918734 (Table of Contents)

Due to increasing concerns about greenhouse gas emissions in recent years, many companies have had an interest in using alternative fuel vehicles in their fleets. Electric vehicles (EVs) are one of these vehicles and they have various advantages such as zero tailpipe emissions, low maintenance costs and low energy consumption. However, their acquisition costs are higher compared to the conventional vehicles and recharging the battery may take significant amount of time compared to the short fueling times. Hence, to overcome these challenges, logistics decisions have to be made effectively. The problem of planning EVs’ activities has been introduced to the literature as the Electric Vehicle Routing Problem (EVRP), which is a special case of the classical VRP where the fleet consists of EVs. The difference between this problem and the classical VRP is that vehicles have batteries as the energy source and the battery is being discharged while the EV is traveling. Hence, the EVs may recharge their batteries at the recharging stations to continue their routes. These stations are located at distant locations and there are few of them compared to the common fuel stations. Recharging may be performed at any level of the battery and the recharging time increases with the recharge amount. In some stations, there may be different chargers which vary in terms of charging speed. For instance, fast chargers recharge the battery faster, but they incur higher cost. Furthermore, EVs may wait in the queue at the stations since there may be other EVs which arrive earlier and wait for ii service. In this dissertation, we address four problems which consider these different features of the EVRP. First, we study the EVRP with Time Windows where the batteries can be recharged partially at the recharging stations. Second, we extend this problem where the recharging stations are equipped with multiple types of chargers which differ by recharging rates and unit recharging costs. Next, we consider a stochastic environment where an EV may wait in the queue before recharging due to other EVs that have arrived earlier at that station. The waiting times depend on the time of the visit during the day, i.e., they are longer in the rush hours. Furthermore, the recharging time is assumed to be a nonlinear function of the energy recharged. In the final problem, we consider random waiting times at the recharging stations. In this case, the EVs do not have information about the queue lengths of the stations before they arrive at. We propose Adaptive Large Neighborhood Search heuristics and matheuristics to solve these problems effectively