Cheapest Insertion and Disruption of Routes Operators for Solving Multi-Depot Electric Vehicle Location Routing Problem with Time Windows and Battery Swapping via GRASP and RVND

Abstract

The Multi-Depot Electric Vehicle Location Routing Problem with Time Windows and Battery Swapping (MDEVLRPTW-BS) aims to mitigate the environmental impacts caused by the use of vehicles with an internal combustion engine and uses economically viable electric vehicles in transportation services with time window restrictions. This problem is complex as one must define (i) the location of the battery swapping stations, (ii) the depots to be used from a list of candidates, and (iii) the assignment and routing of a fleet of electric vehicles. We propose here two constructive methods to solve MDEVLRPTW-BS, namely, Cheapest Insertion and Disruption of Routes. These constructive approaches are used with the Greedy Randomized Adaptive Search Procedure (GRASP) and the Random Variable Neighborhood Descent (RVND) method with six movement operators. Two of these operators, namely Isolate and ChangeBSS, are also proposed here for solving MDEVLRPTW-BS. The proposals are compared with a technique from the literature using instances with 5, 10, and 15 customers, and the proposed approaches presented good results, mainly regarding the processing time. Also, we propose new sets of instances larger than those from the literature. Thus, the search techniques can be analyzed when subjected to greater and more realistic situations. These new instances are composed of 100, 144, 288, 360, 420, and 600 customers. For these cases, the approaches also obtained good and promising results, mainly when the Disruption of Routes approach (GRASP-DR-RVND) is used.