Uma abordagem evolucionária para o projeto de redes eixo-raio com alocação simples

Abstract

The designing of hub-and-spoke networks with single allocation is the focuss of this work. This is a very important problem in the discrete location research, and it has many applications in several contexts such as telecommunication and information systems, and cargo and passengers transportation networks, amongst others. To tackle this problem, 3 evolutionary approaches are investigated: genetic algorithm (GA), named GGA; GGA with local search; e GGA with variable neighborhood descend (VND). The GGA has a very efficient construction phase that provides high quality individuals for the initial population. In addition, the developed operators, specific for the problem, are able to improve the solutions over the evolutionary process. As the promising individuals of the population are not submitted to a solution refinement procedure, this work proposes 4 local searches to the problem. Considering that each proposed local search explores a determined solution only in one specific neighborhood, this dissertation proposesone technique, known as VND, that explores the solution space trough systematics exchanges of neighborhood structure, and enables the different local searches be exploited in one solution. For the performance evaluation of the proposed methods, computational experiments using the data set of the Australian post service (AP) are carried out. Initially, the proposed GGA is compared with three others GAs considered to be state-of-the-art in the literature. The results show that the GGA clearly outperforms the others studied GAs both in solution quality andCPU time to obtained a target solution. Then, the GGA is compared with the GGA combined with the local searches. It is noticed that the combination of the GA with the proposed local searches provide better solutions than the GGA alone, and requires less CPU time to obtaineda target solution. The best solutions presented are provided by the GGA combined with VND that outperforms the GGA with local search of re-allocation in all evaluate metrics, and it is faster to achieve a target solution. Furthermore, the GGA-VND is also more efficient to achievethe optimal solution of the test instances.