Enhancing variable neighborhood search by adding memory: Application to a real logistic problem

This paper addresses a real problem of designing the routes over a planning period with flexibility in the dates of delivery. Specifically, a method based on the strategy Variable Neighborhood Search (VNS) is designed for this problem. The VNS-based method takes some ideas from routing-first cluster-second strategies for routing problems. In addition, it has two important features: it uses a memory-based shaking procedure and it allows, under some conditions, to move from the current solution to a worse solution (Skewed VNS). This procedure performs better than its basic version (no memory, not skewed). Computational experiments with real-data-based instances show that our VNS obtains better results than previous methods for this problem. The method is simple, with an easy implementation and can be adapted to other routing problems.