2011苏北数学建模竞赛B题解答

数学建模王迪B09010601通信工程郑佳佳B09010603通信工程孟天舒B09010604通信工程2题目旅游线路的优化设计摘要本题为典型的旅行商问题（TSP），是组合数学中一个古老而又困难的问题，它易于描述却难以完全解决，属于NP完全问题。对于规模较小的旅行商问题，可以通过穷举得到最优解，但随着问题规模的增大空间复杂度急剧增加，需要通过启发式算法求解。由意大利学者M.Dorigo于1992年首先提出的蚁群系统(AntColonySystem,ACS)是一种新生的仿生进化算法,适用于求解复杂组合优化问题,在解决TSP问题方面取得了较为理想的效果。在此，我们以改进的蚁群算法为基础建立数学模型来设计这些旅游者在五一开始的路线，试图能得到一些合理的结论。(1)第一问是典型的费用TSP问题。对于此问题我们套用基本蚁群算法，查找到城市坐标以及旅游费用，并建立求解矩阵。通过MATLAB软件的模拟，求出若干优化解，取相对最优解作为计算结果。所求得的路线为徐州出发——洛阳市龙门石窟——西安市秦兵马俑——山西祁县乔家大院——青岛市崂山——北京八达岭长城——江西九江庐山——黄山市黄山——常州中华恐龙园——舟山市普陀山——武汉市黄鹤楼——返回徐州，共计3201元。(2)第二问为时间TSP问题。由于时间在具体操作上的波动性，根据数据所得结论将时间的TSP转化为距离TSP问题。求解出的路线为：徐州出发——常州中华恐龙园——舟山市普陀山——黄山市黄山——九江市庐山——武汉市黄鹤楼——洛阳市龙门石窟——西安市秦始皇兵马俑——祁县乔家大院——北京市八达岭长城——青岛市崂山——返回徐州，总计用时11天12小时20分。(3)第三问为有费用约束下的TSP问题。对于此问题利用了试探法和最小元素得到近似解，再用基本蚁群算法进行优化。求解出的路线为：徐州——西安——山西——武汉——黄山——北京——洛阳——徐州，所花费用1839元，游览了5个景点。(4)第四问是在时间约束条件下的TSP问题。解法与前一问类似，求解出的路线为：徐州——北京——洛阳——西安——武汉——祁县——常州——徐州，总时长为4天21小时48分。(5)第五问寻求综合因素优化的问题，通过计算给出评价模型，将价格和费用整合到一个无量纲描述矩阵中。再通过试探法得出最优的方案。最佳路线为：徐州——北京——青岛——西安——祁县——武汉——徐州，总时长4天21小时23分，花费1823元。联系实际情况可知，结果是合理可行的。关键词：旅行商问题（TSP），蚁群算法，动态分析，试探法3一、问题的重述旅游线路的优化设计随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点。假设：(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、模型假设与符号说明省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时42.1模型的基本假设（1）每个景点仅经过一次。（2）只考虑问题中提供的11个旅游景点，不考虑其他中转地点作为TSP的需求点。（3）为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。在问题（2）中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距离的TSP替代时间的TSP。不考虑绕路等特殊情况。在建模时认为两地之间往返的费用时间差异可忽略。（4）在求解费用最少问题时，模型假设时认为住宿，门票，车旅及餐费都必须包含在内。（5）认为网上公布的机票与车票均可以在任意时刻获得，且班次误点等特殊情况不予考虑，忽略转站中的不合理因素。（6）不考虑天气原因对选择交通工具的影响。（7）关于两地间距离仅作比较参考，一切以路径为准。2.2符号说明符号名称G赋权图矩阵C图中的元素（景点）n景点的个数D赋权图的描述矩阵T访问顺序集合L最优解（最小费用或最短路程）dti,ti+1时间ti到ti+1的TSP描述m蚂蚁的总数量k蚂蚁的编号bi(t)t时刻位于城市i的蚂蚁数目τij(t)t时刻路径（i,j）上的信息量Гt时刻C中两两景点之间的残留信息素浓度集合P初始时刻各路径上的信息素量g(C,L,Г)寻优有向图tabuk第k只蚂蚁的禁忌搜索表pkij(t)蚂蚁k在t时刻由i城市转向j城市的转移概率α信息启发式因子β期望启发式因子ηij(t)启发函数ρ信息素挥发系数△τkij(t)t时刻k蚂蚁在路径ij上留下的信息素量Q蚂蚁携带的信息素量Lk本次循环中第k只蚂蚁所走的路程长度5NC所记录的循环次数NCmax最大循环次数三模型的建立与求解3.1基本蚁群算法求解权值不变时单一目标值TSP问题的最优化模型3.1.1TSP问题的图论阐述将旅游景点图优化成完全带权图，问题即可抽象成图论问题：令赋权图为G=(C,L)，其中C={C1,C2,……Cn}为节点，表示各个景点的集合；L={Lij|Ci，CjC}表示各个景点之间的路径，每两个景点间的路径lij都有相关的权值dij与之对应，从而建立起一个D=（dij）矩阵，权值可以表示距离、费用、路径等。由于题目的相关要求可以抽象出一个典型旅行商问题的数学模型：minL=3.1.2基本的蚁群算法模型基本思想：蚁群算法是一种通过模拟自然界蚂蚁寻径的行为的进化算法。蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素，当它们碰到一个还没有走过的路口时,就随机地挑选一条路径前行，与此同时释放出与路线长度有关的信息素，路径越长,释放的激素浓度越低，当后来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高路径概率就会相对较大，这样形成了一个正反馈。最优路径上的激素浓度越来越大,而其它的路径上激素浓度却会随着时间的流逝而消减。这样,整个蚁群最终会找出最优路径。用bi(t)表示城市i的蚂蚁数目，ij表示t时段路径（i，j）上的信息量，n表示景点的个数，m为蚂蚁的总数量，则m=初试时刻，各条路径上信息量相等，均为P，ij（0）=P。又因为蚂蚁不能重复经过同一个城市，因此建立禁忌表（或记录未走过的路径Jk）tabuk(k取正整数)来记录蚂蚁走过的城市，并随时间做动态调整。被随机分散在n个节点的m只蚂蚁同时出发，按照下面的概率公式逐次访问各个城市节点：蚂蚁k以概率kijp访问下一个节点：,0,kijijkklJijijijkjJpjJ在这里，有6ij表示边(,)Lij上的信息素强度。ij表示由节点i到节点j的启发函数，显然距离越长期望度越低，所以在此将ij设为1/ijd。随着时间的推移,可能会出现两种情况:①之前各蚂蚁留下的信息素逐渐消失；②经过多次循环后，路径上的残留信息素过多，淹没了期望程度对蚂蚁选择路径的影响。为了避免这两种情况,在每一只蚂蚁完成一次循环后，我们对引入参数对残留的信息素进行更新。为信息素的挥发速率，是在[0,1]间取值的可变量,用于控制两种信息素的比重。设经过x个时间单位后,蚂蚁完成一次循环,各路径上的信息素的量根据以下式子作出调整：()(1)()ijijijtxt1mkijijkij：蚂蚁在本次循环中留在路径(,)Lij上的信息素强度。kij：蚂蚁k留在路径(,)Lij上的信息素强度。当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。我们将各城市的经纬度通过球面坐标系的转化分别投影到一个二维平面上点的横纵坐标，在求解的时候可直接求出两地的直线距离，即为ijd。3.1.3基本蚁群算法的算法流程在本题中，基本蚁群算法的具体实现步骤如下：1.参数初始化：令t=0；设置最大循环次数NcMax，循环次数Nc=0；将m只蚂蚁置于n个节点上，在每个节点i放置bi(t)只蚂蚁；初始化每条边(i,j)上的信息素量ij(0)=c为一个常量，初始时刻ijk(0)=0；初始化禁忌表tabuk和路径表Lk。2.设置索引号s=1，对k=1~m将蚂蚁k的起始城市放入禁忌表中，并重复以下步骤直至禁忌表填充完整：对k=1~m，利用公式计算转移概率pij，根据伪随机比例规则选择下一景点，将蚂蚁k移动到下一景点j并将其填入禁忌表，同时记录蚂蚁k的路线，索引号自增。3.对k=1~m，根据Lk的记录计算蚂蚁k所走循环路径的总长度，找到最佳路线4.计算每只蚂蚁的信息素增量△τkij(t)75.更新每条路径上的信息素量△τkij(t+n)6.清空禁忌表及路线表。7.Nc++，若NcNcMax，返回步骤2，否则，循环结束。图1基本蚁群算法的程序流程图开始初始化索引号s=1k=k+1蚂蚁k=1计算转移概率pij，选择下一节点j修改禁忌表，记录路线s=s+1根据记录计算权值，记录最优路径更新每条路径上的信息素量k≥蚂蚁总数mNYs≥nNY清空禁忌表及路线表NcNcMaxNc++输出结果，结束YN83.2蚁群算法的模型求解3.2.1问题（1）费用TSP问题的求解根据蚁群算法的解题思路，编写MATLAB程序。将各个景点的经纬度坐标转化为高斯坐标，便于MATLAB的作图。建立文本输入参数，其中权值为两两景点之间的车费，旅游景点门票，住宿费以及餐费等。在车费的选择上在两景点拥有的航班，列车以及长途客运之中选择费用最低的。考虑到住宿的不确定性，以最坏的情况假设每天都需要住宿。首先对参数进行初始化。时间t=0，循环次数NC=0，最大循环次数NCMAX=200，蚂蚁所携带的信息素量为100，初始时刻△τkij(0)=0，蚂蚁数量m=11，景点数n=11，信息启发式因子为1，期望启发式因子为5，信息素挥发系数为0.7，程序运行5次，取相对最优解。MATLAB运行结果为：Shortest_Route=1181695341072Shoetest_Length=750.5对运行