An efficient genetic algorithm for the traveling salesman problem with precedence constraints
An efficient genetic algorithm for the traveling salesman problem with precedence constraints
复制标题
DOI：
10.1016/s0377-2217(01)00227-2
复制
发表时间：
2002-08-01
影响因子：
6.4
通讯作者：
Seo, Y
中科院分区：
文献类型：
--
作者：
Moon, C;Kim, J;Seo, Y
带优先约束的旅行商问题（TSPPC）是组合优化中最困难的问题之一。本文提出了一种求解TSPPC问题的高效遗传算法。该算法的核心概念是拓扑排序（TS），它定义为有向图中顶点的排序。此外，提出了一种新的交叉操作。数值实验的结果表明，该算法产生的最优解，并显示出上级性能相比，传统的算法。(C)2002 Elsevier Science B.V.保留所有权利。
The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph, Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.