Multi-start Iterated Local Search for the Mixed Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles

This paper deals with a real world application that consists in the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles including new constraints, denoted VRP-HFCC. This problem is defined by a set of customers that have to be served by a mixed fleet of vehicles composed of heterogenous fleet of Electric Vehicles (EVs) with distinct battery capacities and operating costs, and a set of identical Conventional Vehicles (CVs). The EVs could be charged during their trips in the available charging stations, which offer charging with a given technology of chargers and time dependent charging costs. Charging stations are also subject to operating time windows constraints. EVs are subject to the compatibility constraints with the available charging technologies and they could be partially charged. Intermittent charging at the depot is also allowed provided that constraints related to the electricity grid are satisfied. The objective is to minimize the number of employed vehicles and to minimize the total travel and charging costs. The developed multi-start algorithm is based on the Iterated Local Search metaheuristic which uses a Large Neighborhood Search with two different insertion strategies in the Local Search procedure. Different implementation schemes of the proposed method are tested on a set of real data instances with up to 550 customers as well as on generalized benchmark instances.