走遍全中国`

走遍全中国

指导教员：彭宜青

组员：金诗铭 鲁斌 崔占森

摘要

本文解决了周游先生周游全中国的最短路径的选取及基于省钱、省时又方便的互联网订票方案。

对于问题一，考虑到从34个城市中制定最短的旅游路线，这是一个对称的旅行商问题（TSP），如果采用动态规划进行求解，空间复杂性及时间复杂性都十分庞大。因此，为解决问题一，本文将问题转化为图论问题，采用蚁群算法进行求解，即利用MATLAB进行计算机求解，得出全国34个城市点到点最短路径的最优解，最短路径为15978公里。

对于问题二，原本只要在问题一的基础上，沿着第一问的制定的路线按照最便宜的乘坐方式乘坐即可，但是由于部分城市之间没有火车直达也没有飞机到达，所以要进行路线的优化，在线路优化的基础上，再就结合最便宜乘坐方式的原则，就可以得出最经济的订票方案，花费8430元。

对于问题三，本文以问题二为基础，综合考虑节约时间和节约钱两个因素，考虑周先生的实际情况，侧重节约时间这个因素，并且在充分理解如何确定3天的停留时间的基础上，遍历所有线路，得到最优线路。计算得出旅途时间为105天，花费为10242元。

对于问题四，基于蚁群算法的复杂度分析，以及模型的可行性，误差分析，在数学理论原理的基础上，给出蚁群算法的复杂度分析，并通过MATLAB运行的结果，给出相应地可行性以及误差分析，该算法的误差大致为2.48%。在本问题中对基本蚁群算法模型给出模型检验，因此不再单独对模型检验进行阐述。

对于问题五，简要阐述了对于本文所采用蚁群算法及模型的理解和相应地评价。

关键词：旅行商问题 蚁群算法 最短旅游路程 模型评价

一、问题重述

周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：

问题一、按地理位置（经纬度）设计最短路旅行方案；

问题二、如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；

问题三、要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；

问题四、对你的算法作复杂性、可行性及误差分析；

问题五、关于旅行商问题提出对你自己所采用的算法的理解及评价。

二、模型假设与符号说明

2.1模型假设

1、将城市与路径的关系转化成图论问题。

2、在解决第二问和第三问的过程中为了使问题更加实际化，各加合理化、简约化，假设认为从广州和澳门等效为一点。

3、在每个城市中停留时，难免遇到等车、堵车等延时情况在此问题中我们不作考虑。

4、在网上订票只考虑理想情况，即票足够，并且忽略某些地区不能在互联网上的票的限制，而且票价不考虑除打折以外的其他优惠 5、绘图时省会分布图上经线、纬线近似平行分布

2.2 符号说明

G：表示有向图矩阵

V：表示顶点集合中的元素，即城市 A：表示图的弧集，即路径 n：表示要经过城市的总数 dij：表示任意两城市间的距离

xij：表示是否经过两座城市 ?ij：表示路径上的信息量 ?ij：表示启发函数 ?：表示信息启发式因子 ?：表示期望启发式因子

kpij(t)：表示蚂蚁k在t时刻由i城市转向j城市的转移概率

tabuk: 表示第k只蚂蚁的禁忌搜索表 ?: 表示信息素挥发系数 k ??ij(t)：表示t时刻k蚂蚁在路径ij上留下的信息素量 Lbest ：表示到目前为止所找到全局最短路径长度

Q：表示蚂蚁携带的信息素量

Lk：表示本次循环中第k只蚂蚁所走的路程长度 m：表示蚂蚁的总数量 k：表示蚂蚁的编号

nc：表示所记录的循环次数 NCmax：表示最大循环次数

三、问题分析

针对问题一，要根据地理位置设计最短旅游路线，这是一个典型的对称TSP问题，如果利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，本文采用蚁群算法，通过计算机编程可以得到最优的旅行路线。

针对问题二，要求制定最经济的订票方案，由于实际情况的约束，将城市与城市之间的线路分为有火车通过和无火车通过两类，在此基础上优化旅游线路，得到最终的结果。

针对问题三，要综合考虑省时间和省钱两方面因素，考虑到周先生是退休的老人，在两者关系上优先考虑节约时间。也就是在问题二的基础上加入时间这个指标，遍历所有路线得到最优解。

四、模型的建立与求解

4.1最短旅游方案模型的建立与求解 4.1.1建立图论的数学模型

将中国各省会、直辖市之间的关系转化为图论问题，并做以下分析:

建立有向图G，且记G?(V,A)。其中V?{v1,v2,......,vn}称为图G的顶点集，V中的每个元素vi(i?1,2,......,n)称为该图的一个顶点，在该题中表示n个城市；A?{a1,a2,......,an}称为图G的弧集，A中的每个元素ak记为ak?(vi,vj)称为该图的一条从vi到vj的弧，在此题中表示各个城市两两连线的集合。

设城市个数为n，dij表示两个城市i与j之间的距离，xij?0或1（1表示走过城市i到城市j的路，0表示没有选择走这条路）。本题可以看成是对称的旅行商问题，则旅行商问题的数学模型为：

min?dijxij

i?j

4.1.2建立蚂蚁算法的数学模型 （1）状态转移规则

因为蚂蚁k不能重复经过一个城市，所以建立禁忌表tabuk(k?1,2,.....m) 来记录蚂蚁走过的城市，禁忌表随着时间做动态变化。

建立蚂蚁k由i城市转移到j城市的状态转移概率如下：

?[?ij(t)]?[?ik(t)]?j?tabuk????k pij(t)???[?is(t)][?is(t)] （1）

s?tabuk??0j?tabuk? 上式中?为信息启发式因子，表示路径的相对重要性，是对所积累的信息素影响作用的一个加权值；?为期望启发式因子，表示能见度的相对重要性； 每只蚂蚁必须依据以城市距离和连接边上信息素的数量为变量的概率函数，决定选择下一城市的概率。

每只蚂蚁必须根据禁忌表和概率函数寻找下一个城市，以保证该蚂蚁从起点出发遍历其它城市一次并且只有一次，并最终返回到起点。 （2）信息素的全局更新规则

当m只蚂蚁成功地完成一次寻径过程后，将选出目标函数值最小的路由，用以完成全局信息素的更新，使得较优解保留下来，对后继蚂蚁产生影响，加快收敛到最优解的速度。

设i，j为两个相连节点，则有：

?ij(i,j)?(1??)?ij(i,j)?????ij(i,j) （2） 其中，变量??ij(i,j)是在t时刻，节点i，j间链路上信息素的增加量

if(i,j)?global?best?tour?(Lbest)?1 ??ij(i,j)??otherwise0??是位于[0,1]上的“激素”挥发因子；Lbest 为到目前为止所找到全局最短路径长度。

（3）信息素的局部更新

对于第k只蚂蚁，在建立一个解得过程中也同时进行激素迹的更新，如果节点i，j是它所选择路径上的两个相邻节点，规则如下：

?ij(t)?(1??)?ij(t)?????ij(t)

否则，不更新。其中，0???1，??ij(t)??0，?0是各条链路上信息素的初始值，通常取同一值，表示同一环境。

k信息素的更新策略有多种方法，每种跟新策略的主要差别体现在??ij(t)的求法上。我们规定蚂蚁在完成一个循环后更新所有路径上的信息素，其方程式为：

?Q?k蚂蚁本次循环经过（i,j）??k??ij(t)??Lk???否则?0? （3）

上式中Q表示蚂蚁携带信息素的量，其值得大小影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

4.1.3基于蚁群算法的实现步骤

本题基于蚁群算法的实现步骤如下：

step1：初始化参数：初始化信息量Q，信息启发式因子?，期望启发式因子?，信息素挥发系数?，初始化时间t，蚂蚁个数m，城市个数n，最大迭代次数Ncmax；

step2：迭代次数nc??；

step3：蚂蚁个数自增k??；

step4：蚂蚁选择可以到达的城市，按照状态转移规则移动到城市j； step5：对于城市j，由于已经到达，所以添加到禁忌表中；

step6: 判断所有城市是否遍历，若未完全遍历表明蚂蚁个数没有达到m，则

转向执行step3，否则执行step7；

（3）更新最短路径信息素，使step7：由于信息素的改变，要求按照公式（2）

得较优解保留下来，加快收敛到最优解的速度；

step8：若nc?Ncmax表明没有满足终止条件，即转向执行step2，否则执行step9；

step9：输出最优结果。 流程图如下：

本文来源：https://www.bwwdw.com/article/5vht.html