Matlab求解旅行商问题的算法应用(2)
时间:2017-06-07 11:49 来源:毕业论文 作者:毕业论文 点击:次
2.1.1 最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到. 如何确定最短路线. 2.1.2 TSP问题最简单的求解方法是枚举法。它的解是多文的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为 . 可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值. 求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程. 2.1.3 旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路. 2.1.4 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点. TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题. 2.2 TSP问题分析及数学模型 2.2.1 TSP问题分析 旅行商问题的各个城市间的距离可以用代价矩阵来表示，就是邻接矩阵表示法. 如果 ，则 . 先说明旅行商问题具有最优解结构. 设 是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市 已经求出，则问题转化为求 到s的最短路径，显然 一定构成一条从 到s的最短路径，如果不然，设 是一条从 到s的最短路径且经过 个城市，则 将是从S出发的路径长度最短的简单回路且比 要短，从而导致矛盾. 所以，旅行商问题一定满足最优性原理. 2.2.2 旅行商问题的数学模型 从一个原点出发经过所指定的点一次并且仅有一次再回到原点的最短路径。若对于城市 的一个访问顺序为 ，其中 ，并且记 ，旅行商问题的数学模型为： 3 TSP问题求解思想及算法简介 3.1 分支限界法 TSP问题在组合优化中是一个求最小的带权哈密顿回路问题, 哈密顿圈是一个完全无向图，每个顶点的度为２．因此， 假设n 个城市为n 个顶点， 顶点集合 ，各个城市之间有路连接就称两个顶点间有一条边，用 ，表示边的集合，且 。用 表示距离矩阵，D是一个对称阵， 是一个0-1型变量， = ，当点i和点j之间有边的时候为1，否则为0. 因此数学模型为： 3.2 动态规划法 假设从顶点 出发，令 表示从顶点 出发经过 中各个顶点一次且仅一次，最后回到出发点 的最短路径的长度，开始时， ,于是，旅行商问题的动态规划函数为： 3.3 模拟退火算法 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素. 模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解. 模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动. 也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A. 模拟退火算法描述： 若 (即移动后得到更优解)，则总是接受该移动 若 (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定） 根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为 ，表示为： 其中k是一个常数，exp表示自然指数，且 . 这条公式说白了就是：温度越 高，出现一次能量差为 的降温的概率就越大；温度越低，则出现降温的概率就越小. 又由于 总是小于0（否则就不叫退火了），因此 ，所以 的函数取值范围是 . (责任编辑：qin) |