Track: Smart Mobility

Abstract

With an increasing interest in e-commerce, parcel/good delivery is taking a new framework by offering a variety of options to the customers such as an option of flexible delivery. To consider the greenhouse emission requirements imposed by governments, the logistic companies should adapt their infrastructure to use electric vehicles (EVs) more than before. To provide a solution to these concerns, we define the Electric Vehicle Routing Problem with Flexible Deliveries (EVRP-FD). In this problem, a fleet of capacitated fully charged EVs is dispatched from the depot at the beginning of the planning horizon where the depot is equipped with charging facilities. Each customer is associated with multiple delivery locations with non-overlapping time windows and the demand of each customer should be satisfied in one of their locations within its specified time windows. We investigate the case where EVs can return multiple times to the depot for a recharge en-route. The primary objective is minimizing the fleet size and the secondary objective is minimizing the travel costs associated with the utilization of the EVs. We provide the mixed-integer linear problem (MILP) and then propose a hybrid Variable Neighborhood Granular Tabu Search algorithm to solve this problem. We verify the performance of our algorithm on instances from the literature and generate new benchmark instances for the EVRP-FD. Finally, we present a detailed sensitivity analysis and a case study in Nottingham, the UK to provide further insights.