Metaheuristic Approach for the Location and Routing Problem with Truck and Drones: A Sustainable Perspective

Last-mile deliveries have increased the generation of footprint emissions in the last decade. Therefore, digitization and the application of new technologies for distribution processes have emerged as a new direction of sustainable operations, e.g., Electric vehicles, Unmanned Aerial Vehicles (UAVs), among others. Considering these facts, this research aims to analyze the impact of incorporating UAVs in a last-mile delivery problem in terms of CO2 emissions and economic cost. Formally, we combine the well-known facility location and vehicle routing problem defined as the location routing problem with truck-and-drones. A metaheuristic procedure is proposed to solve the problem. The proposed metaheuristic generates an initial solution from the clustering of a big route (a route that connects all clients in a locally optimal way) and creates a neighborhood with perturbed solutions at each iteration. Then, the procedure selects the solution that improves the objective values and discards solutions which have been visited previously. The search continues until it does not have a neighbor to visit or has exceeded a maximum number of iterations. As the problem has two different objectives, the logic used in the clustering process differs according to the criterion to be optimized. The results are promising since the metaheuristic can find good quality solutions in very low computational times. The average percentage gap between the Lower Bound of the Mixed Integer Linear Program for the problem and the metaheuristic is up to 1% and in some cases retrieved optimal solutions.