文档介绍：该【数学建模B题走遍全中国 】是由【1781111****】上传分享，文档一共【17】页，该文档可以免费在线阅读，需要了解更多关于【数学建模B题走遍全中国 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..B题:走遍全中国摘要走遍全中国问题是一个旅行商问题,我们通过借助多种数学软件的优势挖掘出大量数据潜在的信息,并将其合理运用,建立模型,使用蚁群算法等来解决问题。本文主要解决旅行商问题,应用蚁群算法,通过MATLAB编写程序,最终计算出旅行商最短路径。最后画出最短路线图,以直观方式展现在读者面前。旅行商问题(TSP)是一种典型的组合最优化问题,可描述为某旅行商欲往n个城市推销货物,从某个城市出发,沿途经过各个城市一次后返回出发城市,要确定一条行走的路线,计算途径个城市的最短距离,即给定n个城市和两两城市之间的距离,确定一条经过每个城市并且仅经过一次的路线,要求总路径最短。对于城市数目为n的地图,共有n种不同的路径,城市越多,可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n很大时,去尝试每一种可能的路径是不可能的,所以需要设计一个有效的算法去寻找最短的路径[1,2]。蚁群算法原理基于蚁群算法,首先引入TSP中常用符号:m为蚁群中蚂蚁数量;bi(t)为t时刻位于城市i的蚂蚁个数,且m=ni=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个参数,分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。为了阻止蚂蚁重复访问,为每只蚂蚁都设计一个被称为禁忌表(tabulist)的数据结构。经过n个时刻,蚂蚁完成一次循环,各路径上信息素“蒸发”和增加的量根据下式调整:式中:ρ表示信息素蒸发后的剩余,则(1-ρ)为衰减系数,表示信息素的减少;表示信息素增加的量,在式(1)中表示第k只蚂蚁在时刻dij留在路径(t,t+1)上的信息素量;,Q为常数,L(k)为第k个蚂蚁爬过路径(i,j)的长度,等于dij的值。至此,一个蚂蚁的循环过程结束,由此反迭代多次,最终得出优化结果。关键词:旅行商问题蚁群算法经纬度MAYTLAB程序层次分析综合评价问题重述周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、、澳门、台北。请你为他按下面要求制定出行方案:(经纬度)设计最短路旅行方案;,每个城市停留3天,可选择航空、铁路(快车卧铺或动车),设计最经济的旅行互联网上订票方案;、省时又方便,设定你的评价准则,建立数学模型,修订你的方案;:...对你的算法作复杂性、可行性与误差分析;。一、问题的分析组合优化是运筹学的重要分支,主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。这类问题通常随着问题规模的扩大,问题空间呈现组合爆炸特征,无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题,问题要求求得一条遍历所有城市的最短回路,属于NP难问题。随着城市数目增多,求解问题的空间、时间复杂度将呈指数级增长,若使用穷举搜索法求解,在现有条件下是无法实现的。20世纪90年代,欧洲学者DorigoMacro等人从生物进化论中得到启发,通过模拟自然界中蚂蚁集体寻找食物源的行为(群集智能)提出了蚁群算法(AntColonyOptimization),该算法最早成功地应用于求解TSP问题。后来又用于解决其他组合优化问题,并取得了较好的效果。然而,蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样,存在扩大搜索空间与寻找最优解之间的矛盾(尤其是针对大规模问题),这意味着蚂蚁要选择的下一个移动的点的可选围很大,计算时间自然也要增加,而构造候选集就可以把运算时间控制在一定的围。目前一般都采用最近邻居表(NearestNeighborList)来构造候选集,但这种方法没有考虑问题的几何结构,而且存在着一些风险会阻止最优解的生成,出现解的退化。本文在蚁群算法的基础上,针对以上不足和TSP问题的几何特点,提出了象限近邻表构造候选集的方法,限定了每只蚂蚁下一步移动所能选择的城市,并且利用所构造的候选集,初始化信息素数量,从而大大缩减了解空间,使蚂蚁搜索空间集中于最优解附近。本文算法在对TSPLIB的实验结果表明其搜索精度和搜索时间都有较好表现。目前,蚁群算法己有多种模型,应用较多的有AntSystem(AS)[1],AntColonySystem(ACS)[],MAXM1NAS(MMAS)[3],其主要思想都是模拟蚂蚁觅食的群集智能。蚂蚁运动时会在路径上释放一种可称之为“信息素”(Pheromone)的物质,通过信息素来交换“路径信息”使整个蚁群的行为具有很高的自组织性,蚂蚁运动形成一个正反馈机制,最终通过蚁群的集体催化行为找出最优路径。蚁群算法主要包括两个基本阶段:适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息素不断调整自身结构:路上经过的蚂蚁越多,信息素数量越大,则该路径越容易被选择;时间越长,信息素数量越少。在协作阶段,候选解之间通过信息交流,以期望产生性能更好的解。这里以ACS作为蚁群算法的一个代表,其结果可普与到其他蚁群算法二、问题的提出周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、、澳门、台北。请你为他按下面要求制定出行方案:(经纬度)设计最短路旅行方案;,每个城市停留3天,可选择航空、铁路(快车卧铺或动车),设计最经济的旅行互联网上订票方案;、省时又方便,设定你的评价准则,建立数学模型,修订你的方案;、可行性与误差分析;:...关于旅行商问题提出对你自己所采用的算法的理解与评价三、模型的假设,符号说明(1)市场的情况,所以只能从有限的市场调查数据中来获取,另外其他类学科的统计信息对整个市场的影响很微小,所以我们可以将其忽略,以减少分析的复杂度;(2)在求解不同性质的问题时,蚁群算法的模型也有所不同,但主要思想都是生成一定数量的蚂蚁,通过每只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上,每只蚂蚁从初始节点出发,根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点,直到建立可行解;(3)每只蚂蚁根据解的优劣程度,更新路径上的信息素。如此周而复始,直到蚁群找到最优解;(4)以n个城市的旅行商问题(TravelingSalesmanProblem,TSP)为例来说明基本蚁群算法(AntColonySystem,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′n39°54′e121°29′n31°14′e117°11′n39°09′e106°32′n29°32′e126°41′n45°45′e125°19′n43°52′e123°24′n41°50′呼和浩特e111°48′n40°49′e114°28′n38°02′e112°34′n37°52′e117°n36°38′e113°42′n34°48′e108°54′n34°16′e103°49′n36°03′e106°16′n38°20′:..e101°45′n36°38′乌鲁木齐e87°36′n43°48′e117°18′n31°51′e118°50′n32°02′e120°09′n30°14′e113°n28°11′e115°52′n28°41′e114°21′n30°37′e104°05′n30°39′e106°42′n26°35′e119°18′n26°05′台北e121°31′n25°03′e113°15′n23°08′e110°20′n20°02′e108°20′n22°48′e102°41′n25°e91°10′n29°40′e114°10′n22°18′全国各大城市所处位置中国当前火车车次车次类型始发站始发时间到站时间查询站开车时间终点站终到时间2007普快16:1800:1300:2807:512051空调普快12:1501:0901:2106:52:..类型始发站始发时间到站时间查询站开车时间终点站终到时间2017普快12:2701:1801:3607:11K7056/K7053快速密山13:0002:1302:2405:422008普快19:2002:1502:3109:451302空调普快满洲里13:3302:2202:5121:40K265空调快速12:3803:2503:4509:071489空调普快11:5103:1703:5211:082124/2125普快15:5803:4404:0313:272156/2157普快乌兰浩特20:5804:2204:2204:22K339空调快速12:5104:2204:3711:416601/6604普客东04:0504:2004:40立志11:586229普客东04:1404:2904:49乌伊岭21:281301空调普快10:0304:4805:03满洲里18:24T47空调特快17:0805:0005:1607:54K929空调快速16:3305:1805:3412:416202普客东05:1205:2705:38五家06:21K546/K547空调快速20:4605:2805:4409:10K7026快速七台河19:4605:3605:53东06:084225空调普快山海关16:3505:5705:5705:572195空调普快19:4405:5705:5705:57K7076空调快速鸡西21:2505:5805:5805:58K7018快速乌伊岭18:1205:3606:00东06:254140普快21:1005:4206:02东06:174138普快双鸭山20:0006:0506:0506:054191/4194普快绥芬河20:1005:4706:10满洲里21:15T129空调特快20:4806:0306:1907:41K7098/K7095/K7094快速海拉尔06:2306:0706:24东07:001546/1547普快11:0306:2906:2906:296227普客06:3606:3606:36一面坡10:55K552/K553空调快速13:0506:3806:3806:384031普快东06:0006:1506:4119:34K7034空调快速20:3006:2506:47东07:201122/1123普快14:3106:5706:5706:57K7005空调快速东06:2006:3507:0012:53K7092空调快速满洲里19:0006:3807:03东07:18Z15空调直达21:2007:0407:0407:04K7022/K7020快速鹤北20:2006:5107:07东07:26L7220普客07:0807:0807:08平房07:45Z1空调直达21:1407:1007:1007:106203普客双城堡05:3507:1907:1907:19K7050空调快速加格达奇20:2607:2107:2107:21T261空调特快21:5407:2807:2807:28:..类型始发站始发时间到站时间查询站开车时间终点站终到时间T5001空调特快07:3007:3007:3009:57K7024空调快速绥芬河21:1807:2607:38东07:58K7032快速05:5507:3807:3807:38T236/T237空调特快东18:2007:4207:4207:426208普客07:4507:4507:45双城堡10:03K7011空调快速07:4607:4607:46亚布力南10:492035/2038普快图们19:5007:4408:04东08:256201普客五家06:5208:0908:0908:09K7001空调快速东07:2708:0008:1512:55T5021空调特快东07:2208:0508:1810:38T17空调特快21:2608:2608:2608:26K7036空调快速21:2008:0708:28东08:52T181/T184空调特快08:3408:3408:34汉口12:09T155/T158空调特快08:4508:4508:4507:541450/1451空调普快日照05:1008:3808:5414:50D28动车组08:5808:5808:5817:10K7015快速东08:1708:3708:5912:37K7062/K7063快速04:5608:4309:0216:53D178动车组09:0609:0609:0617:442624空调普快满洲里19:5708:5709:1621:384074普快05:3409:1809:1809:181324/1325空调普快武昌17:2009:2809:2809:284132普快前进镇18:1009:1809:30东10:00K7028快速密山21:0409:2009:32东09:471171/1174空调普快09:3309:3309:3313:221521空调普快16:0809:3509:3509:354075普快09:3809:3809:38嫩江18:071524/1525空调普快10:2109:4209:4209:42K55/K58空调快速09:4709:4709:4717:436214普客让湖路05:1009:2709:50东10:15T5002空调特快07:2909:5709:5709:576254普客06:3509:4010:00东10:352155/2158普快10:0010:0010:00乌兰浩特18:18L7219普客平房08:4009:5510:03东10:18T5003空调特快10:2010:2010:2012:471523/1526空调普快10:3110:3110:3107:256233普客五常07:0510:2010:35东10:50K7082快速红20:2910:4810:4810:48K701/K704空调快速11:4511:4511:4515:57K7058/K7060快速满洲里20:3711:3011:50东12:054024/4025普快06:3311:4012:0520:27:..类型始发站始发时间到站时间查询站开车时间终点站终到时间K7002空调快速07:4312:0512:0512:052510普快08:1811:5012:10北18:55T5004空调特快10:2212:5012:5012:502015普快江北07:1112:5212:5212:52D173动车组北08:5513:0213:0213:02K7112/K7109快速06:3312:4113:02北安18:48K20快速满洲里01:0112:4013:0405:32K40空调快速09:0412:4013:0405:32T5005空调特快13:1013:1013:1015:36D174动车组13:1813:1813:18北17:24K7006空调快速07:2913:2013:2013:20T5022空调特快11:0413:2513:2513:25K129/K132快速江北08:1913:1313:2817:10K7003空调快速13:3013:3013:3017:521545/1548普快13:3313:3313:3309:05K7007空调快速13:4413:4413:4419:33T5023空调特快13:4613:4613:4616:06K7110/K7111快速北安06:4213:3914:0320:07K7046空调快速讷河07:4914:0514:0514:05K7045空调快速14:2714:2714:27讷河19:542016普快14:3514:3514:35江北19:531416/1417普快12:3614:3614:3614:361323/1326空调普快14:4014:4014:40武昌10:03K7042空调快速漠河县19:4414:2514:43东14:582509普快07:1714:2414:4818:28K551/K554空调快速14:5314:5314:5308:311470/1471空调普快13:5814:5614:5614:56K130/K131快速11:1114:4615:02江北20:23K39空调快速23:0014:4915:1018:37K19快速23:0014:4915:10满洲里03:05D25动车组07:1515:1915:1915:19K7064/K7061快速07:0514:5915:2219:401813/1816普快10:4015:2915:2915:294023/4026普快07:3515:1715:3520:13D26动车组15:3815:3815:3823:33T242/T243空调特快17:4716:1016:1016:101391/1394空调普快08:4515:5916:1921:591814/1815普快16:2916:2916:2921:18T5006空调特快14:0416:3216:3216:324131普快东15:5716:1216:35前进镇06:496206普客东15:3016:2216:36双城堡17:47:..类型始发站始发时间到站时间查询站开车时间终点站终到时间T311空调特快北10:5816:1616:4320:27T5007空调特快16:5516:5516:5519:226213普客东16:1416:5017:05让湖路20:56K7081快速17:0817:0817:08红07:08T156/T157空调特快18:0517:1117:1117:112052空调普快11:0217:0117:1605:236225普客东16:5317:1217:20玉泉19:006253普客东16:4517:0017:2320:531415/1418普快17:2917:2917:2916:23K7059/K7057快速东17:0617:2117:48满洲里08:04K7031快速17:5117:5117:5119:35K926/K927空调快速15:5917:5217:5217:521121/1124普快17:5817:5817:5807:566207普客双城堡16:2517:4317:59东18:286231普客五常14:3818:0018:0018:00K56/K57空调快速09:2718:0318:0318:03K7035空调快速东17:0817:4018:0805:304076普快嫩江08:4218:1618:1618:166234普客18:1818:1818:18五常21:29K7004空调快速13:3918:1318:22东18:371490空调普快10:5518:0018:2410:28T5008空调特快15:5618:2418:2418:24K7016快速14:4018:4218:4218:42K340空调快速11:2818:2718:4410:16T5024空调特快16:2918:5018:5018:50K925/K928空调快速18:5218:5218:5223:14K7027快速东18:2118:3618:55密山07:104073普快18:5618:5618:5622:32K7019/K7021快速东18:1518:4118:59鹤北06:16T182/T183空调特快汉口15:4219:0519:0519:05T235/T238空调特快19:0919:0919:09东08:08K7093/K7096/K7097快速19:1519:1519:15海拉尔17:31T241/T244空调特快19:1619:1619:1617:506205普客双城堡18:1719:2319:2319:23K7012空调快速亚布力南16:2819:3119:3119:312036/2037普快东18:4719:0819:33图们08:08K266空调快速13:5019:2019:4010:376204普客19:4719:4719:47双城堡21:076228普客一面坡15:1519:5319:5319:53K930空调快速12:3019:3919:5509:08K545/K548空调快速16:0719:5020:0607:02:..类型始发站始发时间到站时间查询站开车时间终点站终到时间K7008空调快速14:0019:5220:07东20:224137普快20:1520:1520:15双鸭山06:37K7049空调快速20:2220:2220:22加格达奇07:474032普快07:3620:0320:23东20:484192/4193普快满洲里05:4720:1220:30绥芬河06:10K702/K703空调快速18:2020:3220:3220:322623空调普快07:3420:2020:33满洲里10:042123/2126普快10:3820:2020:4008:582196空调普快20:4720:4720:4706:531469/1472空调普快20:5520:5520:5522:581172/1173空调普快17:0020:5720:5720:57K7025快速东20:2720:4220:57七台河07:07K7033空调快速东20:1320:3320:5806:56T18空调特快21:1021:1021:1008:31K7091空调快速东20:0720:4921:15满洲里09:04T262空调特快21:1821:1821:1806:33K7023空调快速东20:5221:0721:27绥芬河07:06Z16空调直达21:3621:3621:3607:20Z2空调直达21:4221:4221:4207:261449/1452空调普快15:2221:2421:48日照23:59D27动车组13:5021:5821:5821:58K7041空调快速东21:1521:3021:58漠河县18:29K7075空调快速22:0022:0022:00鸡西06:426602/6603普客立志14:1021:3422:01东22:16T48空调特快18:5421:4322:0409:131392/1393空调普快17:1821:4722:1005:05T130空调特快20:2721:5622:1407:31K7017快速东21:3921:5422:22乌伊岭09:402667普快12:1222:2022:35漠河县20:146230普客乌伊岭06:2022:0922:36东22:512631/2634普快06:4322:3722:3722:372096普快15:1022:1922:3809:00D177动车组14:0522:4922:4922:491522空调普快22:5322:5322:5313:314139普快东22:1922:3422:5506:082727空调普快15:2422:2923:00绥芬河08:502018普快17:0222:3823:0711:162728空调普快绥芬河12:5822:5723:1406:10K7054/K7055快速19:2423:0523:20密山11:432632/2633普快23:2123:2123:2115:022095普快11:0923:1023:2506:48:..类型始发站始发时间到站时间查询站开车时间终点站终到时间2668普快漠河县21:5022:5423:2809:40T312空调特快20:5223:3023:45北07:08MTSP数学模型以点0表示旅行商的出发城市,称为源点,点1,2,,l表示m个旅行商需访问的城市。定义变量xijk=1,旅行商k通过弧段(i,j);0,否则yki=1,旅行商k访问城市i;0,否则cij表示旅行商经过对应弧段(i,j)所需的费用,如时间、距离、花费等。则得到以下模型:目标函数为Z=min(max(z1,z2,?,zm))(1)式中zk=Σli=0Σlj=0cijxijk,k=1,2,?,m(2)约束条件Σmk=1yki=m,i=01,i=1,2,?,l(3)Σli=0xijk=ykj,j=0,1,?,l;k=1,2,?,m(4)Σlj=0xijk=yki,i=0,1,?,l;k=1,2,?,m(5)X=(xijk)∈S(6)式中,S为支路消去约束,即消去构成不完整路线的解,具体含义可参见文献[6]。在该模型中,式(1)表示使m个旅行商中的旅行费用最大的那个最小化;式(2)表示各个旅行商的费用;式(3)表示从指定城市0出发,所有城市只有某一个旅行商严格访:..;式(4)表示任意一条弧的终点城市仅有一个起点城市与之相连;式(5)表示任意一条弧的起点城市仅有一个终点城市与之相连;式(6)表示消去构成不完整线路的解。2递阶遗传算法在生物学领域,染色体的结构是一系列基因按层次排列而成的,一些基因控制着另一些基因。染色体可表示为包括控制基因和参数基因的递阶结构,参数基因处于最低级,控制基因处于上级,下级基因串受上级基因的控制。在基因编码时,控制基因常采用整数编码,不同整数信息表示对应的基因处于不同的激活状态,而与该基因相联系的低级基因串则处于对应的状态。为计算方便和加强遗传算法在解空间的搜索能力,参数基因采用实数编码,每个基因用一个实数代表。这样定义染色体结构的遗传算法称为递阶遗传算法,它比传统遗传算法包含更多的信息,因而能处理更复杂的问题。目前,递阶遗传算法已在神经网络、模糊系统、车间调度等方面得到了较好的应用[729]。3递阶遗传算法设计基于MTSP的特点,可以设计成二级递阶染色体结构描述其结构和参数,控制基因中的每一个等位基因表示城市,参数基因中的每一个等位基因表示所路过的旅行商。对于给定问题,其控制基因和参数基因个数是确定的,都为不含源点的城市个数l,控制基因取值为1~l中互不相等的整数,参数基因取值为1~m中的整数,m为旅行商个数,因此优化MTSP只需确定基因信息。例如,对于有8个城市(含源点城市)、旅行商数上限为3的MTSP,假设城市0为源点,本文采用二级递阶染色体结构描述如图1所示。如控制基因中第1个等位基因取值为4,对应的参数基因取值为2时,表示城市4由旅行商2访问;控制基因中第2个等位基因取值为5,对应的参数基因取值为3,表示城市5由旅行商3访问,其余以此类推。。群体太小难以求得满意的结果,群体太大则计算复杂。根据经验,群体规模一般取10~160。[10]:在遗传进化的初期,通常会产生一些超常的个体,若按照比例选择法,这些异常个体因竞争力太突出而控制了选择过程,影响算法的全局优化性能;在遗传进化的后期,即算法接近收敛时,由于种群中个体适值差异较小,继续优化的潜能降低,可能获得某个局部最优解。适值函数设计不当有可能造成这种问题的出现。由于优化目标为最小化路程或费用值,因此令目标函:ThedocumentwascreatedwithS