Column generation-based methods for the electric vehicle routing problems with time windows

Official URL: https://risc01.sabanciuniv.edu/record=b2766949_(Table of contents)

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the well-known Vehicle Routing Problem with Time Windows (VRPTW), where a fleet of electric vehicles (EVs) is used instead of conventional vehicles. EVs have a limited driving range, and thus, they may need to visit a station on the route to recharge their batteries. The duration spent to recharge the battery is linearly proportional to the amount of energy transferred. In this thesis, the EVRPTW and the EVRP with Flexible Delivery (EVRP-FD) are studied. The first problem is based on the classical VRPTW and assumes that for each customer only one delivery location and its related time window are provided. In the second problem, this assumption is generalized such that customers are offered the flexibility to specify multiple delivery locations for service to take place within different predetermined time windows. We develop exact and heuristic algorithms based on the Column Generation (CG) method that is embedded in Branch-and-Price (BP) and Branch-and-Price-and-Cut (BPC) procedures to obtain solutions for these problems. Pricing subproblems of those methods are solved by using different labeling algorithms all based on the Pulse algorithm or the ng-route algorithm and improved with the state-of-the-art iv acceleration techniques including (i) a bidirectional search mechanism in which both forward and backward labels are created, (ii) a method to prevent solving the pricing sub-problem at each iteration, (iii) a procedure for dynamically eliminating arcs that connect customers to remote stations from the network during the path generation, (iv) a bounding procedure providing early elimination of sub-optimal routes, and (v) an integer programming model that generates upper bounds. The BPC is strengthened by employing a well-known set of valid inequalities. The methods proposed for solving the EVRPTW are evaluated by using a benchmark data set that includes instances with up to 100 customers and 21 stations and several new solutions are introduced while some existing solutions are improved. The BP procedure with the Pulse algorithm also provides a number of new solutions for the instances with 100 customers to the literature. For the EVRP-FD, we present a new data set including instances with up to 120 customers and an extensive computational study is performed to evaluate the performance of the BP algorithm applied with the bidirectional Pulse procedure.