B题：走遍全中国
摘要
走遍全中国问题是一个旅行商问题，我们通过借助多种数学软件的优势挖掘出大量数据潜在的信息，并将其合理运用，建立模型，使用蚁群算法等来解决问题。本文主要解决旅行商问题，应用蚁群算法，通过MATLAB 编写程序，最终计算出浙江旅行商最短路径。最后画出最短路线图，以直观方式展现在读者面前。
旅行商问题(TSP)是一种典型的组合最优化问题，可描述为某旅行商欲往n 个城市推销货物，从某个城市出发，沿途经过各个城市一次后 返回出发城市，要确定一条行走的路线，计算途径个城市的最短距离，即给定n 个城市和两两城市之间的距离，确定一条经过每个城市并且仅经过一次的路线，要求总路径最短。对于城市数目为n 的地图, 共有n 种不同的路径，城市越
多,可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n 很大时，去尝试每一种可能的路径是不可能的，所以需要设计一个有效的算法去寻找最短的路径[1,2]。
蚁群算法原理
基于蚁群算法，首先引入TSP 中常用符号：m 为蚁群中蚂蚁数量；bi(t)为t 时刻位于城市i 的蚂蚁个数，且m=n i = 1Σbi(t)； dij 为城市
i 和j 之间的距离； nij 为边（i,j）的能见度，反映由城市i转移到城市j 的启发程度；τij 为边（i,j）上的信息素轨迹强度；△tij 为蚂蚁k 在边（i,j）上留下的单位长度轨迹信息素量；Pkij 为蚂蚁k 的转移概率；j 是尚未访问的城市。 在初始时刻，各条路径上的信息素量相等，设τij(0)=C，（C 为常数），蚂蚁k(k=1,2,?，m)被随机放到某个城市，然后根据各条路径上的信息素
量选择下一个城市。在t 时刻，的城市；α 和β 为2 个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabu list）的数据结构。经过n 个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的量根据下式调整：式中：ρ 表示信息素蒸发后的剩余，则（1-ρ）为衰减系数，表示信息素的减少； 表示信息素增加的量，在式（1）中表示第k 只蚂蚁在时刻dij 留在路径(t,t+1)上的信息素量；，Q 为常数，L（k）为第k个蚂蚁爬过路径(i， j)的长度，等于dij 的值。至此，一个蚂蚁的循环过程结束，由此反迭代多次，最终得出优化结果。
关键词：旅行商问题 蚁群算法 经纬度 MAYTLAB程序 层次分析 综合评价
问题重述
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
3． 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。
一、问题的分析
组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题 (TSP)就是一个经典的组合优化问题，问题要求求得一条遍历所有城市的最短回路，属于NP 难问题。随着城市数目增多，求解问题的空间、时间复杂度将呈指数级增长，若使用穷举搜索法求解，在现有条件下是无法实现的。
20世纪90年代，欧洲学者 Dorigo Macro等人从生物进化论中得到启发，通过模拟自然界中蚂蚁集体寻找食物源的行为(群集智能)提出了蚁群算法(Ant Colony Optimization)，该算法最早成功地应用于求解 TSP 问题。后来又用于解决其他组合优化问题，并取得了较好的效果。
然而，蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样，存在扩大搜索空间与寻找最优解之间的矛盾(尤其是针对大规模问题)，这意味着蚂蚁要选择的下一个移动的点的可选范围很大，计算时间自然也要增加，而构造候选集就可以把运算时间控制在一定的范围。目前一般都采用最近邻居表(Nearest Neighbor List)来构造候选集，但这种方法没有考虑问题的几何结构，而且存在着一些风险会阻止最优解的生成，出现解的退化。本文在蚁群算法的基础上，针对以上不足和 TSP问题的几何特点，提出了象限近邻表构造候选集的方法，限定了每只蚂蚁下一步移动所能选择的城市，并且利用所构造的候选集，初始化信息素数量，从而大大缩减了解空间，使蚂蚁搜索空间集中于最优解附近。本文算法在对 TSPLIB 的实验结果表明其搜索精度和搜索时间都有较好表现。
目前， 蚁群算法己有多种模型， 应用较多的有Ant System(AS)[1]，Ant Colony System(ACS) [1.2]，MAXM1NAS(MMAS)[3],其主要思想都是模拟蚂蚁觅食的群集智能。蚂蚁运动时会在路径上释放一种可称之为“信息素”(Pheromone)的物质，通过信息素来交换“路径信息”使整个蚁群的行为具有很高的自组织性，蚂蚁运动形成一个正反馈机制，最终通过蚁群的集体催化行为找出最优路径。
蚁群算法主要包括两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息素不断调整自身结构：路上经过的蚂蚁越多，信息素数量越大，则该路径越容易被选择；时间越长，信息素数量越少。在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。这里以ACS作为蚁群算法的一个代表，其结果可普及到其他蚁群算法
二、问题的提出
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
4． 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
1
5．关于旅行商问题提出对你自己所采用的算法的理解及评价
三、模型的假设，符号说明
（1） 市场的情况，所以只能从有限的市场调查数据中来获取，另外其他类学
科的统计信息对整个市场的影响很微小，所以我们可以将其忽略，以减少分析的复杂度；
（2） 在求解不同性质的问题时，蚁群算法的模型也有所不同，但主要思想都
是生成一定数量的蚂蚁，通过每只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上，每只蚂蚁从初始节点出发，根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点，直到建立可行解； （3） 每只蚂蚁根据解的优劣程度，更新路径上的信息素。如此周而复始，直
到蚁群找到最优解；
（4） 以n个城市的旅行商问题(Traveling Salesman Problem,TSP)为例来说
明基本蚁群算法(Ant Colony System，ACS)[8]。TSP是指旅行商按一定顺序访问每一个城市，每个城市仅能访问一次，最后回到起点，且路径最短；
（5） TSP的实质是在n个节点的完全图上找到一条最短的哈密顿(Hamilton)
路径，是一个易于描述却难于处理的NP难题；
（6） 设m是蚁群中蚂蚁的数量，dij(i，j=1，2，?n)表示城市i和城市j之
间的距离， 表示时刻在城市i与城市j路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等， (C为常数)。蚂蚁通过概率策略选择下一个要访问的城市，令表示在时刻蚂蚁k从城市i转移到城市j的概率； （7） 假设周先生自带充足食物，并不考虑住宿问题；
四、模型的建立
各城市经纬度分布： 城市 经度 北京 e116°28′ 上海 e121°29′ 天津 e117°11′ 重庆 e106°32′ 哈尔滨 e126°41′ 长春 e125°19′ 沈阳 e123°24′ 呼和浩特 e111°48′ 石家庄 e114°28′ 太原 e112°34′ 济南 e117° 郑州 e113°42′ 西安 e108°54′ 兰州 e103°49′ 银川 e106°16′
纬度 n39°54′ n31°14′ n39°09′ n29°32′ n45°45′ n43°52′ n41°50′ n40°49′ n38°02′ n37°52′ n36°38′ n34°48′ n34°16′ n36°03′ n38°20′ 2
西宁 e101°45′ 乌鲁木齐 e87°36′ 合肥 e117°18′ 南京 e118°50′ 杭州 e120°09′ 长沙 e113° 南昌 e115°52′ 武汉 e114°21′ 成都 e104°05′ 贵阳 e106°42′ 福州 e119°18′ 台北 e121°31′ 广州 e113°15′ 海口 e110°20′ 南宁 e108°20′ 昆明 e102°41′ 拉萨 e91°10′ 香港 e114°10′ 全国各大城市所处位置
n36°38′ n43°48′ n31°51′ n32°02′ n30°14′ n28°11′ n28°41′ n30°37′ n30°39′ n26°35′ n26°05′ n25°03′ n23°08′ n20°02′ n22°48′ n25° n29°40′ n22°18′
中国当前火车车次
车次 2007 2051
类型 始发站 始发时间 到站时间 查询站 开车时间 终点站 终到时间 普快 沈阳 16:18 00:13 哈尔滨 00:28 佳木斯 07:51 空调普快 大连 12:15 01:09 哈尔滨 01:21 牡丹江 06:52 3
车次 类型 始发站 始发时间 到站时间 查询站 开车时间 终点站 终到时间 2017 普快 大连 12:27 01:18 哈尔滨 01:36 牡丹江 07:11 K7056/K7053 快速 密山 13:00 02:13 哈尔滨 02:24 齐齐哈尔 05:42 2008 普快 佳木斯 19:20 02:15 哈尔滨 02:31 沈阳 09:45 1302 空调普快 满洲里 13:33 02:22 哈尔滨 02:51 北京 21:40 K265 空调快速 北京 12:38 03:25 哈尔滨 03:45 牡丹江 09:07 1489 空调普快 天津 11:51 03:17 哈尔滨 03:52 佳木斯 11:08 2124/2125 普快 丹东 15:58 03:44 哈尔滨 04:03 齐齐哈尔 13:27 2156/2157 普快 乌兰浩特 20:58 04:22 哈尔滨 04:22 哈尔滨 04:22 K339 空调快速 北京 12:51 04:22 哈尔滨 04:37 佳木斯 11:41 6601/6604 普客 哈尔滨东 04:05 04:20 哈尔滨 04:40 立志 11:58 6229 普客 哈尔滨东 04:14 04:29 哈尔滨 04:49 乌伊岭 21:28 1301 空调普快 北京 10:03 04:48 哈尔滨 05:03 满洲里 18:24 T47 空调特快 北京 17:08 05:00 哈尔滨 05:16 齐齐哈尔 07:54 K929 空调快速 大连 16:33 05:18 哈尔滨 05:34 佳木斯 12:41 6202 普客 哈尔滨东 05:12 05:27 哈尔滨 05:38 五家 06:21 K546/K547 空调快速 西安 20:46 05:28 哈尔滨 05:44 齐齐哈尔 09:10 K7026 快速 七台河 19:46 05:36 哈尔滨 05:53 哈尔滨东 06:08 4225 空调普快 山海关 16:35 05:57 哈尔滨 05:57 哈尔滨 05:57 2195 空调普快 锦州 19:44 05:57 哈尔滨 05:57 哈尔滨 05:57 K7076 空调快速 鸡西 21:25 05:58 哈尔滨 05:58 哈尔滨 05:58 K7018 快速 乌伊岭 18:12 05:36 哈尔滨 06:00 哈尔滨东 06:25 4140 普快 佳木斯 21:10 05:42 哈尔滨 06:02 哈尔滨东 06:17 4138 普快 双鸭山 20:00 06:05 哈尔滨 06:05 哈尔滨 06:05 4191/4194 普快 绥芬河 20:10 05:47 哈尔滨 06:10 满洲里 21:15 T129 空调特快 大连 20:48 06:03 哈尔滨 06:19 大庆 07:41 K7098/K7095/K7094 快速 海拉尔 06:23 06:07 哈尔滨 06:24 哈尔滨东 07:00 1546/1547 普快 德州 11:03 06:29 哈尔滨 06:29 哈尔滨 06:29 6227 普客 哈尔滨 06:36 06:36 哈尔滨 06:36 一面坡 10:55 K552/K553 空调快速 温州 13:05 06:38 哈尔滨 06:38 哈尔滨 06:38 4031 普快 哈尔滨东 06:00 06:15 哈尔滨 06:41 黑河 19:34 K7034 空调快速 黑河 20:30 06:25 哈尔滨 06:47 哈尔滨东 07:20 1122/1123 普快 南昌 14:31 06:57 哈尔滨 06:57 哈尔滨 06:57 K7005 空调快速 哈尔滨东 06:20 06:35 哈尔滨 07:00 佳木斯 12:53 K7092 空调快速 满洲里 19:00 06:38 哈尔滨 07:03 哈尔滨东 07:18 Z15 空调直达 北京 21:20 07:04 哈尔滨 07:04 哈尔滨 07:04 K7022/K7020 快速 鹤北 20:20 06:51 哈尔滨 07:07 哈尔滨东 07:26 L7220 普客 哈尔滨 07:08 07:08 哈尔滨 07:08 平房 07:45 Z1 空调直达 北京 21:14 07:10 哈尔滨 07:10 哈尔滨 07:10 6203 普客 双城堡 05:35 07:19 哈尔滨 07:19 哈尔滨 07:19 K7050 空调快速 加格达奇 20:26 07:21 哈尔滨 07:21 哈尔滨 07:21 T261 空调特快 大连 21:54 07:28 哈尔滨 07:28 哈尔滨 07:28
4
相关推荐：
loading