Electric vehicle routing problems

Abstract

Vehicle routing problem is one of the most classical problem in logistics and has been characterized as a successful story of the application of operational research to the real-world logistics. With the deterioration of the environment, more and more high-profile logistic companies have been starting the adoption of the electric vehicles in logistics. In this context, Electric Vehicle Routing Problem (EVRP) is proposed due to the differences of the electric vehicles from the conventional fuelled vehicles. In literature, the main efforts of the researchers are devoted to handling the characteristics of the electric vehicles in making route decisions. The thesis contributes to the literature of the EVRP in proposing novel EVRP variants at a static and a dynamic level, developing robust solution methods for solving the studied problems, elaborately discovering the characteristics of the EVRP, and designing new operators that can be applied to other EVRPs. Three EVRPs are studied covering both static and dynamic perspectives. First, a static EVRP with full recharging and linear recharging function is described and an Enhanced Artificial Bee Colony (EABC) algorithm from the literature is improved to solve the problem, where the algorithm’s efficiency is fully revealed in the computational experiments. Three recharging station selection criteria are proposed and compared. This part establishes a general idea for how to select and insert a recharging station in the route. Following the conclusion that the EABC algorithm is robust in solving EVRP, the EABC algorithm is adopted as a solution framework for the other two studied problems. The study is the pioneer to solve the static EVRP simultaneously considering heterogeneous vehicle fleet, time windows for customers, time windows for recharging stations and depot, partial recharging, current-battery-level-dependent recharging time/cost, and piecewise linear recharging functions. Especially, the total recharging cost is incorporated in the objective function, emphasizing the importance of recharging cost on the route decision. One more recharging station selection criterion is particularly proposed for this problem, showing that different criteria should be adopted as appropriate. Operators are designed in terms of partial recharging amount, recharging station selection, and recharging station location. Abundant experiments demonstrate the operators’ effectiveness in improving the solution quality; and all of them can be applied to other EVRPs because they are specifically designed according to the characteristics of the EVRP. In addition, partial recharging and the heterogeneity of the vehicles are discussed in the experiments, leading to suggestions for the decision-makers. A dynamic EVRP with time windows, partial recharging, and piecewise linear recharging function is further proposed, which can be considered as the dynamic version of the second problem except the identical electric vehicles. A solution method is established on the EABC with a rolling horizon approach. In addition to the adoption of the several operators mentioned above, a new operator to eliminate the future infeasibility in energy constraints is proposed and a route determination heuristic is described, which can also be applied to other EVRPs. Problem properties are finely investigated, and conclusions are drawn in managerial insights.