Genetic algorithm for very large traveling salesman problems and its applications to practical applications

提出了一种求解旅行商问题(TSP)的遗传算法。该遗传算法采用边缘装配交叉(EAX)算法，是一种求解TSP问题的高效算法。我们首先提出了一种改进的EAX算法，该算法的执行效率比原算法快2-7倍。然后，我们提出了一种选择模型，该模型可以在可以忽略的计算代价下有效地保持种群多样性。边缘熵被用来作为种群多样性的指标。我们使用EAX进一步改进了GA的性能，特别是对于10,000多个城市的大型实例。我们的方法与现有方法具有很强的竞争力。此外，通过扩展为TSP开发的遗传算法，我们已经为几个车辆路径问题开发了非常有效的MA。

We have developed an genetic algorithm (GA) for the traveling salesman problem (TSP). The GA uses edge assembly crossover (EAX), which is known to be efficient and effective for solving TSPs. We first propose a modified EAX algorithm that can be executed more efficiently than the original, which is 2-7 times faster. We then propose a selection model that can efficiently maintain population diversity at negligible computational cost. The edge entropy measure is used as an indicator of population diversity. We further improved the performance of the GA with EAX, especially for large instances of more than 10,000 cities. Our method is highly competitive with existing approaches. Moreover, we have developed very efficient MAs for several vehicle routing problems by extending the GA developed for the TSP.