A fast approximative approach for the Vehicle Routing Problem

In this paper we introduce a three-step heuristic for a complex version of the Vehicle Routing Problem. The Vehicle Routing Problem is focused on the design of optimal delivery routes. A new memory-based approach is developed in order to gather highly valuable experience to predict the best routes in advance. A clustering representation is proposed to allow the system to achieve a simplified abstraction of the model and making use of the pre-existing knowledge to solve more efficiently real instances of the problem. With these elements a new approximative fast approach is developed. The process transforms the VRP in a set of more simple Travelling Salesman Problems which are remarkably easier to solve. A comparison between the results achieved and the application of a genetic algorithm technique is performed. The obtained results demonstrate a noteworthy improvement in terms of performance and time consumption in relation to previous approximative approaches.