Department of Industrial Engineering
Electric Vehicle Routing Problem with Flexible Deliveries
Mir Ehsan Hesam Sadati
Faculty of Engineering and Natural Sciences, Sabanci University
With an ever-growing interest in e-commerce, parcel delivery is taking new shapes by offering a variety of options to the customers such as an option for selecting multiple delivery locations. From another perspective, this increase in demand requires a new fleet of vehicles that should be added to the current capacities of parcel delivery companies. To meet the greenhouse emission requirements imposed by governments, these 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), for the first time. In the EVRP-FD, a fleet of capacitated fully charged EVs dispatch 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 full or partial recharge en-route. The solution to EVRP-FD finds the number of utilized EVs and their routes that might include returns to the depot for recharging while minimizing the travel costs associated with the utilization of the EVs. We first develop a mathematical model for the EVRP-FD 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.