An urban transportation problem solved by parallel programming with hyper-heuristics

Abstract

An innovative optimization strategy by means of hyper-heuristics is proposed. It consists of a parallel combination of three metaheuristics. In view of the need both to escape from local optima and to achieve high diversity, the algorithm cooperatively combines Simulated Annealing with Genetic Algorithms and Ant Colony Optimization. A Location-Routing Problem (LRP), which aims at the design of transport networks, was adopted for the performance evaluation of the proposed algorithm. Information exchanges took place effectively between the metaheuristics and speeded up the search process. Moreover, the parallel implementation was useful since it allowed several metaheuristics to run simultaneously, thus achieving a significant reduction of the computational time. The algorithmic efficiency and effectiveness were ratified for a medium-size city. The proposed optimization algorithm not only accelerated computations, but also helped to improve solution quality.