A real fuel distribution problem solved by a two phase parallel algorithm that combines simulated annealing and route building heuristics

摘要

This paper makes an extensive description of a real fuel distribution problem. It includes the description of the elements, process, constraints and difficulties of the real problem, as well as the description of the efficient system that has been designed to solve it. This system combines a global strategy working with the whole set of orders and vehicles - global optimisation - and a local one - local optimisation - that tries to improve parts of the global solution, concretely pairs of routes. Both parts are combination of Simulated Annealing and a Route Building Heuristic. The main objective is to obtain good quality results in little time with this aim, the system has been parallelised, and, as a consequence, the same quality results can be obtained dividing the time by the number of processors. Satisfactory average results were obtained: the experts in the company ratified that solutions for problems with 170 orders are obtained in a couple of minutes, and savings greater than 10% are obtained as well. On the other hand, in problems of Solomon's benchmark, average results are very good in distance, whereas in vehicles, they are under 10% worse than the optimal one. This experimentation has been always done by limiting the number of solutions explored to 32,000.