A branch-and-bound integrated simulated annealing algorithm for the electric vehicle routing problem with time windows

Abstract

This paper addresses the electric vehicle routing problem with time windows (EVRPTW) which is one of the more recent research fields investigating the use of electric vehicle technology efficiently in logistics activities. In addition to the traditional vehicle routing problem, the EVRPTW considers the battery capacities of the electric vehicles and their charging operations while satisfying vehicle weight capacity and time windows constraints. The aim of the problem is to find the best route plan for the electric vehicles that minimizes the total distance travelled by the fleet. Due to the limited cruising range of the electric vehicles, the charging operations directly affect the routing plans. Therefore, the visiting time of the electric vehicles to the charging stations in a route has to be planned efficiently. In this context, this paper proposes a simulated annealing algorithm integrated with a branch-and-bound based station inserting operation which inserts the charging stations in a feasible route consisting of customer locations by searching the candidate insertions based on a branching concept. Distinctly from the heuristic based insertion operations the branch-and-bound based station insertion mechanism has the potential to find the best charging station insertion plan for the routes. In computational studies the proposed approach is tested on a benchmark data set, which is formed for the EVRPTW, and the results are compared with the solutions given by existing studies in literature and CPLEX solutions obtained with two hour time limitation. Comparisons show that the proposed algorithm is capable to find good result for the considered EVRPTW instances in smaller computational time.