A Branch-Cut-and-Price Algorithm for the Time-Dependent Electric Vehicle Routing Problem with Time Windows

GONZALO LERA ROMERO; JUAN JOSÉ MIRANDA BRONT; SOULIGNAC, FRANCISCO J.

virtual

Workshop; 9th INFORMS Transportation Science and Logistics Society Workshop; 2021

Indian Institute of Management Ahmedabad

The adoption of electric vehicles (EVs) within last-mile deliveries is considered one of the key transformations towards more sustainable logistics. The inclusion of EVs introduces new operational constraints to the models such as a restricted driving range and the possibility to perform recharges in-route. The discharge of the typical batteries is complex and depends on several variables, including the vehicle travel speed, but most of the approaches assume that the energy consumption depends only on the distance traveled. This becomes relevant for distribution problems in large cities, where traffic congestion affects severely the travel speeds. In this paper, we introduce a general version of the Time-Dependent Electric Vehicle Routing Problem with Time Windows (TDEVRPTW), which incorporates the time-dependent nature of the transportation network both in terms of travel times and the battery consumption. We propose a unifying framework to integrate other critical time-dependent times arising during the operations previously studied in the literature, such as the waiting and charging times. We propose a state of the art branch-cut-and-price (BCP) algorithm. Based on extensive computational experiments, we show that the approach is very effective solving instances with up to 100 customers with different time dependent contexts. From a managerial standpoint, our experiments indicate that neglecting the travel speeds can affect the quality of the solutions obtained, where up to 40 percent of the infeasibilities can be caused by exceeding the battery capacity.