Improvement of Solution Using Local Search Operators on the Multi-Trip Electric Vehicle Routing Problem Backhaul with Time Window

In order to reduce greenhouse gas emissions, logistics companies are strongly encouraged to make their operations more environmentally friendly through efficient solutions by implementing electric vehicles (EVs). However, the driving range is one of the aspects that restricts the introduction of EVs in logistics fleets as it poses new challenges in designing distribution routes. In this regard, this paper investigates the issue of the Electric Vehicle Routing Problem (EVRP) raised by logistics companies in real time. There are many models that extend the classic VRP model to consider electric vehicles, but VRP by combining the features of capacity VRP, VRP with time window, backhaul VRP, multi-trip VRP, and electric VRP (MT-EVRPBTW) has not been worked out yet. We present a mathematical model of the MT-EVRPBTW to explain the problem in detail with the objective function to minimize the total distance travelled, where each vehicle could be charged nightly at the depot and during the day at the rest time of the driver in the depot. A feasible initial solution is built using a constructive heuristic to solve this problem, namely, the sequential insertion heuristic, which will be done by improving the solution using Local Search operators. Several Local Search processes using inter-route and intra-route operators for improvement solutions are tested and compared to their performance in measuring the impact of Local Search operator usage on overall travelled distance. Computational experiments for five Local Search operators will be presented and analyzed based on data from one of Indonesia’s post and parcel companies.