RECHARGE STRATEGIES FOR THE ELECTRIC VEHICLE ROUTING PROBLEM WITH TIME WINDOWS IN DETERMINISTIC AND STOCHASTIC ENVIRONMENTS

Merve Keskin
Industrial Engineering, PhD Dissertation, 2018

Thesis Jury

Prof. Dr. Bülent Çatay (Thesis Advisor), Prof. Dr. Tonguç Ünlüyurt, Assoc. Prof. Deniz Aksen, Asst. Prof. Duygu Taş, Assoc. Prof. Güvenç Şahin

Date & Time: 11th, December 2018 –  10:00 AM

Place: FENS L056

Keywords : electric vehicle routing, metaheuristics, green logistics

Abstract

Due to increasing concerns about greenhouse gas emissions, using alternative fuel vehicles have been increasing in recent years. Hence, green vehicle routing problems have gained attention. Electric vehicles (EVs) are one of these vehicles and many companies have been converting their fleets such that they include EVs. In this dissertation, we address four problems which are about routing of an EV fleet. The difference between this problem and the classical vehicle routing problem is that vehicles have batteries as the energy source and they may recharge them at the recharging stations to continue their routes.

First problem studies the EV routing problem where the customers have demands, service times, time windows and the batteries of the vehicles can be recharged partially at the recharging stations. Since the problem is difficult to solve, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic.

Second problem studies an extension of the first problem where the recharging stations are equipped with multiple types of chargers which differ by recharging rates and unit recharging costs. The problem is modeled in two different ways. To solve it, we embed an exact solver in an ALNS heuristic and benefit from search ability of the heuristic and optimization of the solver.

In the third problem, the assumption that recharging stations are always available is relaxed and waiting times at the stations are considered. An EV may wait for some time in the queue before recharging due to other EVs at the station. These waiting times depend on the time of the day, i.e., they are longer in the rush hours and they are known in advance. Furthermore, the recharging time is assumed to be a nonlinear function of the recharge amount. The solution method involves an ALNS heuristic which is enriched by the solutions of an exact solver, similar to the previous method.

The last problem also considers waiting times at the recharging stations. However, they are now random variables, the EVs do not have information about the queue lengths of the stations unless they visit them. The problem is modeled as a two-stage stochastic program with recourse and is solved by an ALNS heuristic.