Hybrid iterated local search algorithm for the vehicle routing problem with lockers

In the Vehicle Routing Problem (VRP) with Lockers, the vertices in a graph are divided into two key subsets: a customer set and a locker set, with lockers serving as alternative delivery points for the customer’s parcel. This paper presents a generic VRP with lockers, where a customer’s parcel can be delivered either to its home within a time windows or to a nearby locker, where they can pick it up at any time. The objective is to design a set of routes for a fleet of homogeneous vehicles in order to minimize the total travel, vehicle and assignment costs in a such manner that each locker can be visited at most once, the capacities of the vehicles and lockers are not exceeded and the time windows constraints are ensured. To solve this problem. we propose a hybrid metaheuristic that combines Iterated Local Search with a Set Partitioning-like model. Our algorithm uses several classical and specific neighborhood operators. We demonstrate the effectiveness of the proposed methodology by evaluating it on benchmark literature instances from three problems that we show that are encompassed by the generic problem defined in this paper. The results show that we found or improved 432 out of 490 best known solutions.