Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows

Abstract

Increasing environmental concerns and legal regulations have led to the development of sustainable technologies and systems in logistics, as in many fields. The adoption of multi-echelon distribution networks and the use of environmentally friendly vehicles in freight distribution have become major concepts for reducing the negative impact of urban transportation activities. In this line, the present paper proposes a two-echelon electric vehicle routing problem. In the first echelon of the distribution network, products are transported from central warehouses to satellites located in the surroundings of cities. This is achieved by means of large conventional trucks. Subsequently, relatively smaller-sized electric vehicles distribute these products from the satellites to demand points/customers located in the cities. The proposed problem also takes into account the limited driving range of electric vehicles that need to be recharged at charging stations when necessary. In addition, the proposed problem considers time window constraints for the delivery of products to customers. A mixed-integer linear programming formulation is developed and small-sized instances are solved using CPLEX. Furthermore, we propose a constructive heuristic based on a modified Clarke and Wright savings heuristic. The solutions of this heuristic serve as initial solutions for a variable neighborhood search metaheuristic. The numerical results show that the variable neighborhood search matches CPLEX in the context of small problems. Moreover, it consistently outperforms CPLEX with the growing size and difficulty of problem instances.

Keywords

• routing
• two-echelon electric vehicle routing problem
• variable neighborhood search
• large neighborhood search
• Clarke and Wright savings