Last Mile Delivery with Lockers: Formulation and Heuristic

摘要

The creation of efficient routes is essential for different areas having several practical applications mainly in the transport of goods. With the growth of e-commerce and consequently the increase in demand for delivery to end users, minimizing costs in the delivery process has gained more importance, especially the last mile stage. It is in this context that the use of lockers emerges to optimize last mile deliveries. Lockers have compartments of different sizes, with self-service interface and they can be positioned in supermarkets, parks and other areas that are of interest to customers. The problem addressed in this work is to determine the positioning of the lockers and the necessary routes to supply them and to serve the remaining customers. We present a mathematical model to define the problem, but due to the complexity of the problem obtaining a solution can be very expensive and require a lot of computational effort, therefore we present a heuristic, based on Variable Neighborhood Descent (VND), using a greedy construct inspired by the Clark & Wright savings method. By comparing the results of the heuristic with the Gurobi optimizer, we conclude that the heuristic is capable of obtaining competitive solutions in less time than the exact methods.