数学建模：走遍全中国

《数学建模：走遍全中国》由会员分享，可在线阅读，更多相关《数学建模：走遍全中国（33页珍藏版）》请在金锄头文库上搜索。

1、走遍全中国摘要本文解决了周游先生周游全中国的最短路径的选取及基于省钱、省时又方便的互联网订票方案。对于问题（1），考虑到从34个城市中制定最短的旅游路线，这是一个对称的旅行商问题（TSP），如果采用动态规划进行求解，空间复杂性及时间复杂性都十分庞大。因此，为解决问题（1），本文采用人工蚁群算法进行求解，即利用MATLAB进行计算机求解，得出全国34个城市点到点最短路径的最优解，此方法节约计算资源，具有良好的可扩展性和健壮性。对于问题（2）与问题（3）本文将其归为一类考虑，即在问题（1）得出的路线最优解的前提下，设计省钱、省时又方便的互联网订票方案。为解决问题（2）（3）,本文将此问题归为多属性

2、决策问题，本文综合考虑了每一个车次或航班的出发时间、达到时间、旅途时间、里程或航程、票价和交通方式，并且将这些因素同周游先生主观因素结合起来，设计决策树，制定相应的问卷调查，然后计算周游先生对城市甲到城市乙中每一个车次和航班的满意度，将满意度最高的作为此路段的最佳订票结果，进而得出全部订票结果（详见附录-最佳订票方案）。部分结果：总旅行时间；购票总价；总行程（实际行程）；平均满意度关键词：TSP ； 人工蚁群 ； 最短路径 ； 决策树 ； 满意度一、 问题重述与分析1.1 问题重述周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：（1

3、）按地理位置（经纬度）设计最短路旅行方案；（2）如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；（3）要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；（4）对你的算法作复杂性、可行性及误差分析；（5）关于旅行商问题提出对你自己所采用的算法的理解及评价。1.2 问题分析随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。在制定旅游计划的同时需要考虑很多方面的问题，比如：旅游路线的选择、交通工具的选择、旅途用时、经济花销等等。为了在完成旅游计划的基础上实现省时、方便、经济的目标

4、，需要制定一个最优的旅游方案。本文给出周游先生的旅游计划游遍中国的省会城市、直辖市、香港、澳门以及台北，要求达到旅途最短、经济、省时又方便的目的，为了实现这一目标，需要制定一个最优的旅游方案。首先要实现旅途最短，本问题属于一个对称旅行商（TSP）问题，很显然，如果利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，本文采用人了工蚁群算法，通过计算机编程可以得到最优以及次优的旅行路线。得到优化后的旅游路径后，本文需要考虑另外的条件，经济问题、时间问题、方便问题等，为了综合考虑这几方面的因素，需要制定一个决策模型，设计决策树与问卷调查，通过

5、问卷调查可以得到人们对于出发时间、达到时间、旅途时间、里程或航程、票价和交通工具的选择标准，再通过合理的计算，得出满意的互联网订票方案。二、 模型的基本假设和符号说明2.1 模型假设（1） 省会与省会之间的距离为球面最短距离；（2） 绘图时省会分布图上经线、纬线近似平行分布；（3） 票价不考虑除打折以外的其他优惠；（4） 在旅行过程中只考虑购票的经济花费，不考虑其他的消费；（5） 旅行中所乘的车次或航班均准点到达；2.2 符号说明 模型（1）： 要经过的城市总数；: 任意两城市之间的距离；： 表示蚂蚁行走的城市集合；: 表示城市1 2n的一个排列；： 信息值；: 挥发因子；： 城市经纬度；:

6、最短路径最优解；: 最短路径次优解； 模型（2）、（3）： : 两城市间的旅行方式（动车、快车卧铺、航空）；: 车次或航班；： 车次或航班的出发时间；: 车次或航班的到达时间；: 车次或航班的旅行时间； ： 车次或航班的里程；： 车次或航班的票价；： 旅行方式的重要性程度；： 出发时间的重要性程度；： 到达时间的重要性程度；： 旅行时间的重要性程度；： 旅行里程的重要性程度；： 旅行价格的重要性程度； ： 旅行方式的满意度； ： 出发时间的满意度；： 到达时间的满意度； ： 旅行时间的满意度； ： 旅途里程的满意度； ： 旅途价格的满意度；： 总行程时间；： 总的停留天数；： 总行程；： 购票

7、总价；： 完成旅游计划总用时；： 平均满意度；三、 模型的建立及求解3.1 问题（1）模型的建立及求解3.1.1 模型的建立周游先生要在全国省会包括直辖市、香港、澳门共34个地点旅游，要求出最短旅行路线。本问题属于一个对称旅行商（TSP）问题，利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，因此，本文采用人工蚁群算法进行求解。图1如图1所示，蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。

8、图2图2为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上

9、再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这就是正反馈效应。人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。在TSP问题中，可以预先知道当前城市到下一个目的地的距离。TSP问题表示为一个N个城市的有向图G=（N，A），其中， 城市之间的距离目标函数为：其中 为城市1，2n的一个排列。,。假设m只蚂蚁在图的相邻节点间移动，从而协作异步地

10、得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：一，信息素值，也称信息素痕迹。二，可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。算法步骤如下：步骤1： 对n个城市的

11、TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧赋信息初始值 假设m只蚂蚁在工作，所有蚂蚁都从同一城市出发。当前最好解是。步骤2：（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点出发，用表示蚂蚁s行走的城市集合，初始为空集，。步骤3（内循环）按蚂蚁的顺序分别计算。当蚂蚁在城市，若或 完成第s只蚂蚁的计算。否则，若 且 则以概率， 到达j， 若且 则到达， 重复步骤3。步骤4：对，若，按中城市的计算路径程度；若，路径长度置为一个无穷大值（即不可到达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若，则。用如下公式对W路径上的信息素痕迹加强，对其他

12、路径上的信息素进行挥发。 得到新的，重复步骤2。在步骤4中，挥发因子对于一个固定的，满足 并且，经过k次挥发，非最优路径的信息素逐渐减少至消失。最总停止计算，输出本次运行的最优路径。3.1.2 模型的求解在求解时利用各个城市的经纬度作为决策变量，运行MATLAB-M文件（详见附录-MATLAB程序1），将34城市的经纬度调入程序。运行多次后，出现多个运行结果。在此，要对多个运行结果进行筛选，即求出多个运行结果中的最优解与次优解。首先需要知道路径中城市与城市之间的距离。将所有城市编号得：城市哈尔滨长春沈阳昆明香港澳门编号123323334利用城市经纬度用MATLAB（详见附录-MATLAB程序2

13、）求出：根据得出的数据能够直接得到城市到距离，进而利用MATLAB求出了最短路径最优解（图1）与次优解（图2）：哈尔滨哈尔滨 图3 图4假设旅行线路的方向如图3、图4所示，对路径上的城市旅游的先后顺序进行编号。路径最优解：路径次优解：3.2 问题（2）（3）模型的建立及求解3.2.1 模型的建立针对在问题（1）中求出的最短路径最优解（最短路径次优解的解法与此相同）在互联网上分别查到城市的旅行方式（动车、快车卧铺、航空）的车次或航班，以及每个车次或航班的出发时间，到达时间，总共花掉的时间，里程，及价格。基于要从互联网上选择最好的车次或航班，每个车次或航班具有不同的参考因素值（旅行方式，出发时间，

14、到达时间，总共时间，里程，票价），因此，把决定车次或航班的问题归为多属性决策问题。这几个属性都属于主观评价的范围，最终结果取决于决策者的主观意见。为了反映决策者的主观意见，这里引入重要性程度与满意度，即对于选择每个车次或航班的每一个参考因素的满意程度。定义：（1）重要性程度为所有参考因素（旅行方式，出发时间，到达时间，总共时间，里程，票价）中每个参考因素占整个参考因素的百分比。（2）满意度为决策者对于每个参考因素的值的满意程度，这里用分值度量。下面是决定车次或航班的决策树：周游先生选择车次或航班出行方式出发时间到达时间总共时间里程价格得出每个车次或航班的最终满意度人在估计事物质的区别时，常采用五中判断表示，