旅行商问题的中心辐射算法与应用

来源：核心期刊咨询网时间：2021-09-26 16:5512

摘要：一．引言 旅行商问题（Traveling Salesman Problem，简称为TSP），也称为货郎担问题，是著名的组合优化问题，也是一个多局部最优解的问题。它是由爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman在19世纪提出的。TSP是这样提出

　　一.引言

　　旅行商问题(Traveling Salesman Problem，简称为TSP)，也称为货郎担问题，是著名的组合优化问题，也是一个多局部最优解的问题。它是由爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman在19世纪提出的。TSP是这样提出的[1]：假设有一个旅行商人要拜访n个城市，已知这些城市之间的距离，为了每个城市都会到达并且只拜访一次，而且最终要回到原来出发的那个城市，那么他需要怎么选择才能够得到一条最优路径呢?路径的选择目标是要求得的路径总路程为所有路径之中的最小值。换言之，数据包括一个边权值是整数的，且边数有限的完全图。目标是找到一个边权值之和最小的哈密尔顿回路。

　　1954年，TSP问题研究获得重大突破，George Dantzig等描述了一种求解TSP的方法;50年后，2004年，获得一个包含多座城市的TSP问题的解决办法。TSP问题目前研究主要有精确算法和近似算法。精确算法主要包括回溯法，分支定界法和动态规划算法;能保证得到最优解，但是运行时间复杂度是呈指数增加，难以适应大规模计算的要求;近似算法则只能求得近似解，称为次优解。包括构造算法和环路改进算法等。构造算法从某个非法解开始，通过某种增广策略逐步改变该解，直到得到一个合法解为止。这类算法包括最近邻算法、贪心算法等。环路改进算法则在给定初始的合法解之后，使用某种策略来改进初始解，这些策略包括局部搜索、模拟退火、遗传算法等，其中最为简单和有效的方法为局部搜索法。在工程中，TSP问题最早涉猎交通运输和物流运用问题，目前已经应用到印刷电路板的钻孔路线方案设计、连锁店货物配送路线和数控机床的运作等问题[2-8]。显然，构成简化有效的求解方法，是工程应用的重要问题。本文基于构造算法思路，构造简化实用的TSP问题新算法。

　　二.TSP问题的数学模型

　　TSP问题可用有向图表示，其中V表示n个城市，E表示各个城市之间的边。非负矩阵表示各个边的距离，其元素表示城市间的距离。则对变量D的约束是：(1)每个元素是非负整数，即;(2)对角线上元素为 0，即;(3)对于对称TSP问题，矩阵是对称矩阵，即;(4)任意三个元素满足三角不等式，即。TSP问题的其中一个解可以表述为一个循环排列，它也可以表示为的一条路径，是该路径中第个经过的城市。 显然，满足，若时，的解才是可行解。所有可行解的集合构成解空间集S，即 S={n个城市的所有循环排列}。其解空间的规模为，路径长度(约定)为TSP问......

转载请注明来自：http://www.qikan2017.com/lunwen/jgu/22.html