数学建模B题走遍全中国

1、B题：走遍全中国摘要走遍全中国问题是一个旅行商问题，我们通过借助多种数学软件的优势挖掘出大量数据潜在的信息，并将其合理运用，建立模型，使用蚁群算法等来解决问题。本文主要解决旅行商问题，应用蚁群算法，通过MATLAB 编写程序，最终计算出浙江旅行商最短路径。最后画出最短路线图，以直观方式展现在读者面前。旅行商问题(TSP)是一种典型的组合最优化问题，可描述为某旅行商欲往n 个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，计算途径个城市的最短距离，即给定n 个城市和两两城市之间的距离，确定一条经过每个城市并且仅经过一次的路线，要求总路径最短。对于城市数目为

2、n 的地图, 共有n 种不同的路径，城市越多,可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n 很大时，去尝试每一种可能的路径是不可能的，所以需要设计一个有效的算法去寻找最短的路径1,2。蚁群算法原理基于蚁群算法，首先引入TSP 中常用符号：m 为蚁群中蚂蚁数量；bi(t)为t 时刻位于城市i 的蚂蚁个数，且m=ni = 1bi(t)； dij 为城市i 和j 之间的距离； nij 为边（i,j）的能见度，反映由城市i转移到城市j 的启发程度；ij 为边（i,j）上的信息素轨迹强度；tij 为蚂蚁k 在边（i,j）上留下的单位长度轨迹信息素量；Pkij 为蚂蚁k 的转移概率；j 是

3、尚未访问的城市。在初始时刻，各条路径上的信息素量相等，设ij(0)=C，（C 为常数），蚂蚁k(k=1,2,，m)被随机放到某个城市，然后根据各条路径上的信息素量选择下一个城市。在t 时刻，的城市； 和 为2 个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabu list）的数据结构。经过n 个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的量根据下式调整：式中： 表示信息素蒸发后的剩余，则（1-）为衰减系数，表示信息素的减少； 表示信息素增加的量，在式（1）中表示第k 只蚂蚁在时刻dij 留

4、在路径(t,t+1)上的信息素量；，Q 为常数，L（k）为第k个蚂蚁爬过路径(i， j)的长度，等于dij 的值。至此，一个蚂蚁的循环过程结束，由此反迭代多次，最终得出优化结果。关键词：旅行商问题 蚁群算法 经纬度 MAYTLAB程序 层次分析 综合评价问题重述周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：1按地理位置（经纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3 要综合考虑省钱、省时又方便，设定你的评价准则，建

5、立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价。一、问题的分析组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题 (TSP)就是一个经典的组合优化问题，问题要求求得一条遍历所有城市的最短回路，属于NP 难问题。随着城市数目增多，求解问题的空间、时间复杂度将呈指数级增长，若使用穷举搜索法求解，在现有条件下是无法实现的。20世纪90年代，欧洲学者 Dorigo Macro等人从生物进化论中得到

6、启发，通过模拟自然界中蚂蚁集体寻找食物源的行为(群集智能)提出了蚁群算法(Ant Colony Optimization)，该算法最早成功地应用于求解 TSP 问题。后来又用于解决其他组合优化问题，并取得了较好的效果。然而，蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样，存在扩大搜索空间与寻找最优解之间的矛盾(尤其是针对大规模问题)，这意味着蚂蚁要选择的下一个移动的点的可选范围很大，计算时间自然也要增加，而构造候选集就可以把运算时间控制在一定的范围。目前一般都采用最近邻居表(Nearest Neighbor List)来构造候选集，但这种方法没有考虑问题的几何结构，而且存在着一些风险

7、会阻止最优解的生成，出现解的退化。本文在蚁群算法的基础上，针对以上不足和 TSP问题的几何特点，提出了象限近邻表构造候选集的方法，限定了每只蚂蚁下一步移动所能选择的城市，并且利用所构造的候选集，初始化信息素数量，从而大大缩减了解空间，使蚂蚁搜索空间集中于最优解附近。本文算法在对 TSPLIB 的实验结果表明其搜索精度和搜索时间都有较好表现。目前， 蚁群算法己有多种模型， 应用较多的有Ant System(AS)1，Ant Colony System(ACS) 1.2，MAXM1NAS(MMAS)3,其主要思想都是模拟蚂蚁觅食的群集智能。蚂蚁运动时会在路径上释放一种可称之为“信息素”(Phero

8、mone)的物质，通过信息素来交换“路径信息”使整个蚁群的行为具有很高的自组织性，蚂蚁运动形成一个正反馈机制，最终通过蚁群的集体催化行为找出最优路径。蚁群算法主要包括两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息素不断调整自身结构：路上经过的蚂蚁越多，信息素数量越大，则该路径越容易被选择；时间越长，信息素数量越少。在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。这里以ACS作为蚁群算法的一个代表，其结果可普及到其他蚁群算法二、问题的提出周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：1按地理位置（经

9、纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；4 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价三、模型的假设，符号说明（1） 市场的情况，所以只能从有限的市场调查数据中来获取，另外其他类学科的统计信息对整个市场的影响很微小，所以我们可以将其忽略，以减少分析的复杂度；（2） 在求解不同性质的问题时，蚁群算法的模型也有所不同，但主要思想都是生成一定数量的蚂蚁，通过每

10、只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上，每只蚂蚁从初始节点出发，根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点，直到建立可行解；（3） 每只蚂蚁根据解的优劣程度，更新路径上的信息素。如此周而复始，直到蚁群找到最优解；（4） 以n个城市的旅行商问题(Traveling Salesman Problem,TSP)为例来说明基本蚁群算法(Ant Colony System，ACS)8。TSP是指旅行商按一定顺序访问每一个城市，每个城市仅能访问一次，最后回到起点，且路径最短；（5） TSP的实质是在n个节点的完全图上找到一条最短的哈密顿(Hamilton)路径，是一个易于描

11、述却难于处理的NP难题；（6） 设m是蚁群中蚂蚁的数量，dij(i，j=1，2，n)表示城市i和城市j之间的距离， 表示时刻在城市i与城市j路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等， (C为常数)。蚂蚁通过概率策略选择下一个要访问的城市，令表示在时刻蚂蚁k从城市i转移到城市j的概率；（7） 假设周先生自带充足食物，并不考虑住宿问题；四、模型的建立各城市经纬度分布：城市经度纬度北京e11628n3954上海e12129n3114天津e11711n3909重庆e10632n2932哈尔滨e12641n4545长春e12519n4352沈阳e12324n4150呼和浩特e11148n

12、4049石家庄e11428n3802太原e11234n3752济南e117n3638郑州e11342n3448西安e10854n3416兰州e10349n3603银川e10616n3820西宁e10145n3638乌鲁木齐e8736n4348合肥e11718n3151南京e11850n3202杭州e12009n3014长沙e113n2811南昌e11552n2841武汉e11421n3037成都e10405n3039贵阳e10642n2635福州e11918n2605台北e12131n2503广州e11315n2308海口e11020n2002南宁e10820n2248昆明e10241n25拉

13、萨e9110n2940香港e11410n2218全国各大城市所处位置中国当前火车车次车次类型始发站始发时间到站时间查询站开车时间终点站终到时间2007普快沈阳16:1800:13哈尔滨00:28佳木斯07:512051空调普快大连12:1501:09哈尔滨01:21牡丹江06:522017普快大连12:2701:18哈尔滨01:36牡丹江07:11K7056/K7053快速密山13:0002:13哈尔滨02:24齐齐哈尔05:422008普快佳木斯19:2002:15哈尔滨02:31沈阳09:451302空调普快满洲里13:3302:22哈尔滨02:51北京21:40K265空调快速北京12:

14、3803:25哈尔滨03:45牡丹江09:071489空调普快天津11:5103:17哈尔滨03:52佳木斯11:082124/2125普快丹东15:5803:44哈尔滨04:03齐齐哈尔13:272156/2157普快乌兰浩特20:5804:22哈尔滨04:22哈尔滨04:22K339空调快速北京12:5104:22哈尔滨04:37佳木斯11:416601/6604普客哈尔滨东04:0504:20哈尔滨04:40立志11:586229普客哈尔滨东04:1404:29哈尔滨04:49乌伊岭21:281301空调普快北京10:0304:48哈尔滨05:03满洲里18:24T47空调特快北京17:

15、0805:00哈尔滨05:16齐齐哈尔07:54K929空调快速大连16:3305:18哈尔滨05:34佳木斯12:416202普客哈尔滨东05:1205:27哈尔滨05:38五家06:21K546/K547空调快速西安20:4605:28哈尔滨05:44齐齐哈尔09:10K7026快速七台河19:4605:36哈尔滨05:53哈尔滨东06:084225空调普快山海关16:3505:57哈尔滨05:57哈尔滨05:572195空调普快锦州19:4405:57哈尔滨05:57哈尔滨05:57K7076空调快速鸡西21:2505:58哈尔滨05:58哈尔滨05:58K7018快速乌伊岭18:120

16、5:36哈尔滨06:00哈尔滨东06:254140普快佳木斯21:1005:42哈尔滨06:02哈尔滨东06:174138普快双鸭山20:0006:05哈尔滨06:05哈尔滨06:054191/4194普快绥芬河20:1005:47哈尔滨06:10满洲里21:15T129空调特快大连20:4806:03哈尔滨06:19大庆07:41K7098/K7095/K7094快速海拉尔06:2306:07哈尔滨06:24哈尔滨东07:001546/1547普快德州11:0306:29哈尔滨06:29哈尔滨06:296227普客哈尔滨06:3606:36哈尔滨06:36一面坡10:55K552/K553空

17、调快速温州13:0506:38哈尔滨06:38哈尔滨06:384031普快哈尔滨东06:0006:15哈尔滨06:41黑河19:34K7034空调快速黑河20:3006:25哈尔滨06:47哈尔滨东07:201122/1123普快南昌14:3106:57哈尔滨06:57哈尔滨06:57K7005空调快速哈尔滨东06:2006:35哈尔滨07:00佳木斯12:53K7092空调快速满洲里19:0006:38哈尔滨07:03哈尔滨东07:18Z15空调直达北京21:2007:04哈尔滨07:04哈尔滨07:04K7022/K7020快速鹤北20:2006:51哈尔滨07:07哈尔滨东07:26L7

18、220普客哈尔滨07:0807:08哈尔滨07:08平房07:45Z1空调直达北京21:1407:10哈尔滨07:10哈尔滨07:106203普客双城堡05:3507:19哈尔滨07:19哈尔滨07:19K7050空调快速加格达奇20:2607:21哈尔滨07:21哈尔滨07:21T261空调特快大连21:5407:28哈尔滨07:28哈尔滨07:28T5001空调特快哈尔滨07:3007:30哈尔滨07:30齐齐哈尔09:57K7024空调快速绥芬河21:1807:26哈尔滨07:38哈尔滨东07:58K7032快速绥化05:5507:38哈尔滨07:38哈尔滨07:38T236/T237空

19、调特快广州东18:2007:42哈尔滨07:42哈尔滨07:426208普客哈尔滨07:4507:45哈尔滨07:45双城堡10:03K7011空调快速哈尔滨07:4607:46哈尔滨07:46亚布力南10:492035/2038普快图们19:5007:44哈尔滨08:04哈尔滨东08:256201普客五家06:5208:09哈尔滨08:09哈尔滨08:09K7001空调快速哈尔滨东07:2708:00哈尔滨08:15牡丹江12:55T5021空调特快哈尔滨东07:2208:05哈尔滨08:18齐齐哈尔10:38T17空调特快北京21:2608:26哈尔滨08:26哈尔滨08:26K7036空

20、调快速黑河21:2008:07哈尔滨08:28哈尔滨东08:52T181/T184空调特快哈尔滨08:3408:34哈尔滨08:34汉口12:09T155/T158空调特快哈尔滨08:4508:45哈尔滨08:45泰州07:541450/1451空调普快日照05:1008:38哈尔滨08:54牡丹江14:50D28动车组哈尔滨08:5808:58哈尔滨08:58北京17:10K7015快速哈尔滨东08:1708:37哈尔滨08:59齐齐哈尔12:37K7062/K7063快速齐齐哈尔04:5608:43哈尔滨09:02佳木斯16:53D178动车组哈尔滨09:0609:06哈尔滨09:06天津

21、17:442624空调普快满洲里19:5708:57哈尔滨09:16大连21:384074普快齐齐哈尔05:3409:18哈尔滨09:18哈尔滨09:181324/1325空调普快武昌17:2009:28哈尔滨09:28哈尔滨09:284132普快前进镇18:1009:18哈尔滨09:30哈尔滨东10:00K7028快速密山21:0409:20哈尔滨09:32哈尔滨东09:471171/1174空调普快哈尔滨09:3309:33哈尔滨09:33太原13:221521空调普快天津16:0809:35哈尔滨09:35哈尔滨09:354075普快哈尔滨09:3809:38哈尔滨09:38嫩江18:0

22、71524/1525空调普快石家庄10:2109:42哈尔滨09:42哈尔滨09:42K55/K58空调快速哈尔滨09:4709:47哈尔滨09:47上海17:436214普客让湖路05:1009:27哈尔滨09:50哈尔滨东10:15T5002空调特快齐齐哈尔07:2909:57哈尔滨09:57哈尔滨09:576254普客绥化06:3509:40哈尔滨10:00哈尔滨东10:352155/2158普快哈尔滨10:0010:00哈尔滨10:00乌兰浩特18:18L7219普客平房08:4009:55哈尔滨10:03哈尔滨东10:18T5003空调特快哈尔滨10:2010:20哈尔滨10:20齐

23、齐哈尔12:471523/1526空调普快哈尔滨10:3110:31哈尔滨10:31石家庄07:256233普客五常07:0510:20哈尔滨10:35哈尔滨东10:50K7082快速东方红20:2910:48哈尔滨10:48哈尔滨10:48K701/K704空调快速哈尔滨11:4511:45哈尔滨11:45青岛15:57K7058/K7060快速满洲里20:3711:30哈尔滨11:50哈尔滨东12:054024/4025普快齐齐哈尔06:3311:40哈尔滨12:05伊春20:27K7002空调快速牡丹江07:4312:05哈尔滨12:05哈尔滨12:052510普快齐齐哈尔08:1811

24、:50哈尔滨12:10沈阳北18:55T5004空调特快齐齐哈尔10:2212:50哈尔滨12:50哈尔滨12:502015普快江北07:1112:52哈尔滨12:52哈尔滨12:52D173动车组沈阳北08:5513:02哈尔滨13:02哈尔滨13:02K7112/K7109快速牡丹江06:3312:41哈尔滨13:02北安18:48K20快速满洲里01:0112:40哈尔滨13:04北京05:32K40空调快速齐齐哈尔09:0412:40哈尔滨13:04北京05:32T5005空调特快哈尔滨13:1013:10哈尔滨13:10齐齐哈尔15:36D174动车组哈尔滨13:1813:18哈尔滨

25、13:18沈阳北17:24K7006空调快速佳木斯07:2913:20哈尔滨13:20哈尔滨13:20T5022空调特快齐齐哈尔11:0413:25哈尔滨13:25哈尔滨13:25K129/K132快速江北08:1913:13哈尔滨13:28齐齐哈尔17:10K7003空调快速哈尔滨13:3013:30哈尔滨13:30牡丹江17:521545/1548普快哈尔滨13:3313:33哈尔滨13:33德州09:05K7007空调快速哈尔滨13:4413:44哈尔滨13:44佳木斯19:33T5023空调特快哈尔滨13:4613:46哈尔滨13:46齐齐哈尔16:06K7110/K7111快速北安0

26、6:4213:39哈尔滨14:03牡丹江20:07K7046空调快速讷河07:4914:05哈尔滨14:05哈尔滨14:05K7045空调快速哈尔滨14:2714:27哈尔滨14:27讷河19:542016普快哈尔滨14:3514:35哈尔滨14:35江北19:531416/1417普快菏泽12:3614:36哈尔滨14:36哈尔滨14:361323/1326空调普快哈尔滨14:4014:40哈尔滨14:40武昌10:03K7042空调快速漠河县19:4414:25哈尔滨14:43哈尔滨东14:582509普快沈阳07:1714:24哈尔滨14:48齐齐哈尔18:28K551/K554空调快速

27、哈尔滨14:5314:53哈尔滨14:53温州08:311470/1471空调普快徐州13:5814:56哈尔滨14:56哈尔滨14:56K130/K131快速齐齐哈尔11:1114:46哈尔滨15:02江北20:23K39空调快速北京23:0014:49哈尔滨15:10齐齐哈尔18:37K19快速北京23:0014:49哈尔滨15:10满洲里03:05D25动车组北京07:1515:19哈尔滨15:19哈尔滨15:19K7064/K7061快速佳木斯07:0514:59哈尔滨15:22齐齐哈尔19:401813/1816普快包头10:4015:29哈尔滨15:29哈尔滨15:294023/4

28、026普快伊春07:3515:17哈尔滨15:35齐齐哈尔20:13D26动车组哈尔滨15:3815:38哈尔滨15:38北京23:33T242/T243空调特快合肥17:4716:10哈尔滨16:10哈尔滨16:101391/1394空调普快佳木斯08:4515:59哈尔滨16:19烟台21:591814/1815普快哈尔滨16:2916:29哈尔滨16:29包头21:18T5006空调特快齐齐哈尔14:0416:32哈尔滨16:32哈尔滨16:324131普快哈尔滨东15:5716:12哈尔滨16:35前进镇06:496206普客哈尔滨东15:3016:22哈尔滨16:36双城堡17:47

29、T311空调特快沈阳北10:5816:16哈尔滨16:43齐齐哈尔20:27T5007空调特快哈尔滨16:5516:55哈尔滨16:55齐齐哈尔19:226213普客哈尔滨东16:1416:50哈尔滨17:05让湖路20:56K7081快速哈尔滨17:0817:08哈尔滨17:08东方红07:08T156/T157空调特快泰州18:0517:11哈尔滨17:11哈尔滨17:112052空调普快牡丹江11:0217:01哈尔滨17:16大连05:236225普客哈尔滨东16:5317:12哈尔滨17:20玉泉19:006253普客哈尔滨东16:4517:00哈尔滨17:23绥化20:531415

30、/1418普快哈尔滨17:2917:29哈尔滨17:29济南16:23K7059/K7057快速哈尔滨东17:0617:21哈尔滨17:48满洲里08:04K7031快速哈尔滨17:5117:51哈尔滨17:51绥化19:35K926/K927空调快速郑州15:5917:52哈尔滨17:52哈尔滨17:521121/1124普快哈尔滨17:5817:58哈尔滨17:58南昌07:566207普客双城堡16:2517:43哈尔滨17:59哈尔滨东18:286231普客五常14:3818:00哈尔滨18:00哈尔滨18:00K56/K57空调快速上海09:2718:03哈尔滨18:03哈尔滨18:

31、03K7035空调快速哈尔滨东17:0817:40哈尔滨18:08黑河05:304076普快嫩江08:4218:16哈尔滨18:16哈尔滨18:166234普客哈尔滨18:1818:18哈尔滨18:18五常21:29K7004空调快速牡丹江13:3918:13哈尔滨18:22哈尔滨东18:371490空调普快佳木斯10:5518:00哈尔滨18:24天津10:28T5008空调特快齐齐哈尔15:5618:24哈尔滨18:24哈尔滨18:24K7016快速齐齐哈尔14:4018:42哈尔滨18:42哈尔滨18:42K340空调快速佳木斯11:2818:27哈尔滨18:44北京10:16T5024

32、空调特快齐齐哈尔16:2918:50哈尔滨18:50哈尔滨18:50K925/K928空调快速哈尔滨18:5218:52哈尔滨18:52郑州23:14K7027快速哈尔滨东18:2118:36哈尔滨18:55密山07:104073普快哈尔滨18:5618:56哈尔滨18:56齐齐哈尔22:32K7019/K7021快速哈尔滨东18:1518:41哈尔滨18:59鹤北06:16T182/T183空调特快汉口15:4219:05哈尔滨19:05哈尔滨19:05T235/T238空调特快哈尔滨19:0919:09哈尔滨19:09广州东08:08K7093/K7096/K7097快速哈尔滨19:151

33、9:15哈尔滨19:15海拉尔17:31T241/T244空调特快哈尔滨19:1619:16哈尔滨19:16合肥17:506205普客双城堡18:1719:23哈尔滨19:23哈尔滨19:23K7012空调快速亚布力南16:2819:31哈尔滨19:31哈尔滨19:312036/2037普快哈尔滨东18:4719:08哈尔滨19:33图们08:08K266空调快速牡丹江13:5019:20哈尔滨19:40北京10:376204普客哈尔滨19:4719:47哈尔滨19:47双城堡21:076228普客一面坡15:1519:53哈尔滨19:53哈尔滨19:53K930空调快速佳木斯12:3019:

34、39哈尔滨19:55大连09:08K545/K548空调快速齐齐哈尔16:0719:50哈尔滨20:06西安07:02K7008空调快速佳木斯14:0019:52哈尔滨20:07哈尔滨东20:224137普快哈尔滨20:1520:15哈尔滨20:15双鸭山06:37K7049空调快速哈尔滨20:2220:22哈尔滨20:22加格达奇07:474032普快黑河07:3620:03哈尔滨20:23哈尔滨东20:484192/4193普快满洲里05:4720:12哈尔滨20:30绥芬河06:10K702/K703空调快速青岛18:2020:32哈尔滨20:32哈尔滨20:322623空调普快大连07

35、:3420:20哈尔滨20:33满洲里10:042123/2126普快齐齐哈尔10:3820:20哈尔滨20:40丹东08:582196空调普快哈尔滨20:4720:47哈尔滨20:47锦州06:531469/1472空调普快哈尔滨20:5520:55哈尔滨20:55徐州22:581172/1173空调普快太原17:0020:57哈尔滨20:57哈尔滨20:57K7025快速哈尔滨东20:2720:42哈尔滨20:57七台河07:07K7033空调快速哈尔滨东20:1320:33哈尔滨20:58黑河06:56T18空调特快哈尔滨21:1021:10哈尔滨21:10北京08:31K7091空调快

36、速哈尔滨东20:0720:49哈尔滨21:15满洲里09:04T262空调特快哈尔滨21:1821:18哈尔滨21:18大连06:33K7023空调快速哈尔滨东20:5221:07哈尔滨21:27绥芬河07:06Z16空调直达哈尔滨21:3621:36哈尔滨21:36北京07:20Z2空调直达哈尔滨21:4221:42哈尔滨21:42北京07:261449/1452空调普快牡丹江15:2221:24哈尔滨21:48日照23:59D27动车组北京13:5021:58哈尔滨21:58哈尔滨21:58K7041空调快速哈尔滨东21:1521:30哈尔滨21:58漠河县18:29K7075空调快速哈尔

37、滨22:0022:00哈尔滨22:00鸡西06:426602/6603普客立志14:1021:34哈尔滨22:01哈尔滨东22:16T48空调特快齐齐哈尔18:5421:43哈尔滨22:04北京09:131392/1393空调普快烟台17:1821:47哈尔滨22:10佳木斯05:05T130空调特快大庆20:2721:56哈尔滨22:14大连07:31K7017快速哈尔滨东21:3921:54哈尔滨22:22乌伊岭09:402667普快营口12:1222:20哈尔滨22:35漠河县20:146230普客乌伊岭06:2022:09哈尔滨22:36哈尔滨东22:512631/2634普快赤峰06

38、:4322:37哈尔滨22:37哈尔滨22:372096普快佳木斯15:1022:19哈尔滨22:38盘锦09:00D177动车组天津14:0522:49哈尔滨22:49哈尔滨22:491522空调普快哈尔滨22:5322:53哈尔滨22:53天津13:314139普快哈尔滨东22:1922:34哈尔滨22:55佳木斯06:082727空调普快沈阳15:2422:29哈尔滨23:00绥芬河08:502018普快牡丹江17:0222:38哈尔滨23:07大连11:162728空调普快绥芬河12:5822:57哈尔滨23:14沈阳06:10K7054/K7055快速齐齐哈尔19:2423:05哈尔

39、滨23:20密山11:432632/2633普快哈尔滨23:2123:21哈尔滨23:21赤峰15:022095普快盘锦11:0923:10哈尔滨23:25佳木斯06:482668普快漠河县21:5022:54哈尔滨23:28营口09:40T312空调特快齐齐哈尔20:5223:30哈尔滨23:45沈阳北07:08MTSP 数学模型以点0 表示旅行商的出发城市,称为源点,点1 ,2 , , l表示m 个旅行商需访问的城市。定义变量xij k = 1 , 旅行商k 通过弧段( i , j) ;0 , 否则yki = 1 , 旅行商k 访问城市i ;0 , 否则cij 表示旅行商经过对应弧段( i

40、 , j) 所需的费用, 如时间、距离、花费等。则得到以下模型:目标函数为Z = min (max ( z1 , z2 , , zm ) ) (1)式中zk = li =0 lj =0cij x ij k , k = 1 ,2 , , m (2)约束条件mk =1yki = m , i = 01 , i = 1 ,2 , , l(3)li =0xij k = ykj , j = 0 ,1 , , l ; k = 1 ,2 , , m (4)lj =0xij k = yki , i = 0 ,1 , , l ; k = 1 ,2 , , m (5)X = ( xij k ) S (6)式中, S

41、 为支路消去约束, 即消去构成不完整路线的解, 具体含义可参见文献6 。在该模型中, 式(1) 表示使m 个旅行商中的旅行费用最大的那个最小化;式(2) 表示各个旅行商的费用;式(3) 表示从指定城市0 出发, 所有城市只有某一个旅行商严格访问一次;式(4) 表示任意一条弧的终点城市仅有一个起点城市与之相连;式(5) 表示任意一条弧的起点城市仅有一个终点城市与之相连;式(6) 表示消去构成不完整线路的解。2 递阶遗传算法在生物学领域,染色体的结构是一系列基因按层次排列而成的,一些基因控制着另一些基因。染色体可表示为包括控制基因和参数基因的递阶结构, 参数基因处于最低级,控制基因处于上级,下级基

42、因串受上级基因的控制。在基因编码时,控制基因常采用整数编码,不同整数信息表示对应的基因处于不同的激活状态, 而与该基因相联系的低级基因串则处于对应的状态。为计算方便和加强遗传算法在解空间的搜索能力,参数基因采用实数编码,每个基因用一个实数代表。这样定义染色体结构的遗传算法称为递阶遗传算法,它比传统遗传算法包含更多的信息,因而能处理更复杂的问题。目前,递阶遗传算法已在神经网络、模糊系统、车间调度等方面得到了较好的应用729 。3 递阶遗传算法设计基于MTSP 的特点,可以设计成二级递阶染色体结构描述其结构和参数,控制基因中的每一个等位基因表示城市,参数基因中的每一个等位基因表示所路过的旅行商。对

43、于给定问题,其控制基因和参数基因个数是确定的,都为不含源点的城市个数l , 控制基因取值为1 l 中互不相等的整数, 参数基因取值为1 m 中的整数, m 为旅行商个数,因此优化MTSP 只需确定基因信息。例如,对于有8 个城市(含源点城市) 、旅行商数上限为3 的MTSP ,假设城市0 为源点,本文采用二级递阶染色体结构描述如图1 所示。如控制基因中第1 个等位基因取值为4 ,对应的参数基因取值为2 时,表示城市4 由旅行商2 访问;控制基因中第2 个等位基因取值为5 ,对应的参数基因取值为3 ,表示城市5由旅行商3 访问,其余以此类推。图1 染色体的递阶结构设计3. 1 群体规模选择合适的

44、群体规模对遗传算法的收敛具有重要意义。群体太小难以求得满意的结果,群体太大则计算复杂。根据经验,群体规模一般取10160 。3. 2 适值函数遗传算法在进行选择操作时会出现欺骗问题 10 :在遗传进化的初期,通常会产生一些超常的个体,若按照比例选择法,这些异常个体因竞争力太突出而控制了选择过程,影响算法的全局优化性能;在遗传进化的后期,即算法接近收敛时,由于种群中个体适值差异较小,继续优化的潜能降低,可能获得某个局部最优解。适值函数设计不当有可能造成这种问题的出现。由于优化目标为最小化路程或费用值,因此令目标函数作指数变换得到适值函数f = exp ( - Z) (7)式中,为正实数。3. 3

45、 选择选择是用来确定重组或交叉个体, 以及备选个体将产生多少个子代个体。选择的第一步是计算适值, 采用按比例的适值分配,是利用各个个体选择的概率决定其子孙的遗留可能性。若某个个体i ,其适值为f i ,则其被选择的概率表示为Pi = f i Mk =1f k (8)然后计算各个染色体的累积概率qi = Mi =1pi (9)第二步用轮盘赌选择法进行选择。为了选择交配个体, 需要进行多轮选择,每一轮产生一个0 , 1 均匀随机数, 将该随机数作为选择指针来确定备选个体。3. 4 交叉与变异递阶遗传算法的交叉与变异操作分为控制基因交叉与变异以及参数基因交叉与变异。2632 系统工程与电子技术第31 卷交叉在遗传操作中起核心作用, 交叉概率较大可增强遗传算法开辟新搜索空间的能力, 但性能好的基因串遭到破坏的可能性较大, 算法收敛速度降低, 且不稳定;若交叉概率较小,则遗传算法搜索可能陷入迟钝状态。对于控制基因串交叉可以采用基于路径表示部分匹配交叉(partiallymatched crossover , PMX) 、顺序交叉(ordered crossover ,OX) 、循环交叉(cycle c