Multi-Depot Electric Vehicle Routing Problem with Half-Open Rotations: A Formulation and Metaheuristic Algorithms

Abstract

Motivated by achievement of net-zero emission goals surrounding all over the world, this paper introduces a novel problem called Multi-Depot Electric Vehicle Routing Problem with Half-Open Rotations (MDEVRP-HOR). While rotation refers to the set of all routes assigned to an EV, half-open signifies that the departure and arrival depot of an EV may differ. EVs meet customer demands, can replenish load at any depot, and may recharge at depots or recharging stations. The objective is to minimize the total cost arising from use of EVs and distance traversed by respecting load capacity, battery capacity, and maximum tour time constraints. The problem is formulated as Mixed Integer Linear Program (MILP) and procedures from the recent literature are tailored to improve the mathematical model. However, since CPLEX can inherently find optimum solutions for only smallsized instances, two metaheuristics namely Memetic Algorithm (MA) and Simulated Annealing (SA) are developed with a novel encoding and decoding strategy along with bespoke mechanisms specifically designed to exploit the half-open rotation structure of the problem. Algorithm parameters are optimized using the Taguchi method, and the proposed approaches are evaluated on benchmark instances from the literature. Computational results demonstrate that (i) the half-open rotation strategy significantly improves routing decisions and reduces total cost, and (ii) while MA provides higher-quality solutions, SA achieves competitive results with substantially shorter computational times. We also report comparative results of the MA with state-of-the-art literature for the special case of the problem where there exist a single depot and time windows.