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

龙源期刊网 https://www.wendangku.net/doc/e51043607.html,

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

作者：辛虹

来源：《旅游纵览·行业版》2013年第01期

摘要：针对经典旅行商问题，本文提出了中心辐射算法，该算法首先计算节点中心，然

后比较节点与中心连线的与横坐标轴夹角，再按角度从小到大按顺序依次连接节点，完成了走行路线设计。算例分析并与贪心算法结果比较。表明该算法具有简单实用性，能够对具体问题实现快速计算，为工程问题分析提供基础。

关键词：旅行商问题；中心辐射算法；可视化设计

旅行商问题（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问题的其中一个解可以表述为一个循环排列，它也可以表示为的一条路径，是该路径中第个经过的城市。显然，满足，若时，的解才是可行