A multi-phase heuristic for the delivery pick-up vehicle-routing problem with time-windows

In this paper a new heuristic for the vehicle routing problem is presented. This algorithm was applied to the problem originated from a Portuguese alimentary products distribution company. This company has many clients and more than 130 deliveries per day for all products. When considering these figures, the vehicle routing problem becomes too complex to be manually solved. The necessity of automatisation naturally arises. This new multi-phase heuristic has a constructive phase, a local optimisation phase and a pos-optimisation phase, and aims at the minimisation of the sum of the routes total time. Additional constraints to the vehicle routing problem, driven by the particular company that motivated this work, are considered. In particular, time-windows both for the drivers and for the clients and pick-up together with deliveries are considered.