数学建模：走遍全中国

《数学建模：走遍全中国》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：（1）按地理位置（经纬度）设计最短路旅行方案；（2）如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；（3）要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；（4）对你的算法作复杂性、可行性及误差分析；（5）关于旅行商问题提出对你自己所采用的算法的理解及评价。1.2问题分析随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。在制定旅游计划的同

4、时需要考虑很多方面的问题，比如：旅游路线的选择、交通工具的选择、旅途用时、经济花销等等。为了在完成旅游计划的基础上实现省时、方便、经济的目标，需要制定一个最优的旅游方案。本文给出周游先生的旅游计划—游遍中国的省会城市、直辖市、香港、澳门以及台北，要求达到旅途最短、经济、省时又方便的目的，为了实现这一目标，需要制定一个最优的旅游方案。首先要实现旅途最短，本问题属于一个对称旅行商（TSP）问题，很显然，如果利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，本文采用人了工蚁群算法，通过计

5、算机编程可以得到最优以及次优的旅行路线。得到优化后的旅游路径后，本文需要考虑另外的条件，经济问题、时间问题、方便问题等，为了综合考虑这几方面的因素，需要制定一个决策模型，设计决策树与问卷调查，通过问卷调查可以得到人们对于33出发时间、达到时间、旅途时间、里程或航程、票价和交通工具的选择标准，再通过合理的计算，得出满意的互联网订票方案。一、模型的基本假设和符号说明2.1模型假设（1）省会与省会之间的距离为球面最短距离；（2）绘图时省会分布图上经线、纬线近似平行分布；（3）票价不考虑除打折以外的其他优惠；（4）在旅行过程中只考虑购票的经济花费，

6、不考虑其他的消费；（5）旅行中所乘的车次或航班均准点到达；2.2符号说明模型（1）：：要经过的城市总数；:任意两城市之间的距离；：表示蚂蚁行走的城市集合；:表示城市12……n的一个排列；：信息值；:挥发因子；：城市经纬度；:最短路径最优解；:最短路径次优解；模型（2）、（3）：:两城市间的旅行方式（动车、快车卧铺、航空）；:车次或航班；：车次或航班的出发时间；:车次或航班的到达时间；33:车次或航班的旅行时间；：车次或航班的里程；：车次或航班的票价；：旅行方式的重要性程度；：出发时间的重要性程度；：到达时间的重要性程度；：旅行时间的重要性程

7、度；：旅行里程的重要性程度；：旅行价格的重要性程度；：旅行方式的满意度；：出发时间的满意度；：到达时间的满意度；：旅行时间的满意度；：旅途里程的满意度；：旅途价格的满意度；：总行程时间；：总的停留天数；：总行程；：购票总价；：完成旅游计划总用时；：平均满意度；33一、模型的建立及求解3.1问题（1）模型的建立及求解3.1.1模型的建立周游先生要在全国省会包括直辖市、香港、澳门共34个地点旅游，要求出最短旅行路线。本问题属于一个对称旅行商（TSP）问题，利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，因此，本

8、文采用人工蚁群算法进行求解。图1如图1所示，蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过