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

数学建模

王迪 B09010601 通信工程 郑佳佳 B09010603 通信工程 孟天舒 B09010604 通信工程

题 目 旅游线路的优化设计

摘要

本题为典型的旅行商问题（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），蚁群算法，动态分析，试探法

2

一、 问题的重述

旅游线路的优化设计

随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点。 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院 3小时 河南 洛阳市龙门石窟 3小时 安徽 黄山市黄山 7小时 湖北 武汉市黄鹤楼 2小时 陕西 西安市秦始皇兵马俑 2小时 江西 九江市庐山 7小时 浙江 舟山市普陀山 6小时 假设：

(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。

(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。

(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。 (D) 假设景点的开放时间为8:00至18:00。

问题：

根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。

(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。

(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。

(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。

(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。

(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。

二、 模型假设与符号说明

3

2.1 模型的基本假设

（1） 每个景点仅经过一次。

（2） 只考虑问题中提供的11个旅游景点，不考虑其他中转地点作为TSP的需求点。 （3） 为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。在

问题（2）中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距离的TSP替代时间的TSP。不考虑绕路等特殊情况。在建模时认为两地之间往返的费用时间差异可忽略。

（4） 在求解费用最少问题时，模型假设时认为住宿，门票，车旅及餐费都必须包

含在内。

（5）认为网上公布的机票与车票均可以在任意时刻获得，且班次误点等特殊情况不予考虑，忽略转站中的不合理因素。

（6）不考虑天气原因对选择交通工具的影响。

（7）关于两地间距离仅作比较参考，一切以路径为准。

2.2 符号说明 符号 名称 G 赋权图矩阵 C 图中的元素（景点） n 景点的个数 D 赋权图的描述矩阵 T 访问顺序集合 L 最优解（最小费用或最短路程） dti,ti+1 m k bi(t) τij时间ti到ti+1的TSP描述 蚂蚁的总数量 蚂蚁的编号 t时刻位于城市i的蚂蚁数目 t时刻路径（i,j）上的信息量 t时刻C中两两景点之间的残留信息素浓度集合 初始时刻各路径上的信息素量 寻优有向图 第k只蚂蚁的禁忌搜索表 蚂蚁k在t时刻由i城市转向j城市的转移概率 信息启发式因子 期望启发式因子 启发函数 信息素挥发系数 t时刻k蚂蚁在路径ij上留下的信息素量 蚂蚁携带的信息素量 本次循环中第k只蚂蚁所走的路程长度 4

(t) Г P g(C,L,Г) tabuk pkij(t) α β ηij(t) ρ △τkij(t) Q Lk

NC NCmax

所记录的循环次数 最大循环次数 三 模型的建立与求解

3.1 基本蚁群算法求解权值不变时单一目标值TSP问题的最优化模型 3.1.1 TSP问题的图论阐述

将旅游景点图优化成完全带权图，问题即可抽象成图论问题：

令赋权图为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以概率

pijk访问下一个节点：

pijk???????????ij???ij??,j?Jk????????????l?Jk?ij??ij? ??0?,j?Jk5

在这里，有

?ij表示边L(i,j)上的信息素强度。

?ij表示由节点i到节点j的启发函数，显然距离越长期望度越低，所以在此将?ij设为1/dij。

随着时间的推移, 可能会出现两种情况: ①之前各蚂蚁留下的信息素逐渐消失；②经过多次循环后，路径上的残留信息素过多，淹没了期望程度对蚂蚁选择路径的影响。为了避免这两种情况, 在每一只蚂蚁完成一次循环后，我们对引入参数?对残留的信息素进行更新。?为信息素的挥发速率，是在[0,1]间取值的可变量,用于控制两种信息素的比重。

设经过x个时间单位后, 蚂蚁完成一次循环, 各路径上的信息素的量根据以下式子作出调整：

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

??ij????ijk

??ij：蚂蚁在本次循环中留在路径L(i,j)上的信息素强度。

k?1m??ijk：蚂蚁k留在路径L(i,j)上的信息素强度。

当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。

我们将各城市的经纬度通过球面坐标系的转化分别投影到一个二维平面上点的横纵坐标，在求解的时候可直接求出两地的直线距离，即为

dij。

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)

6

5. 更新每条路径上的信息素量△τkij(t+n) 6. 清空禁忌表及路线表。

7. Nc++，若Nc

开始 初始化 索引号s=1 蚂蚁k=1 计算转移概率pij，选择下一节点j 修改禁忌表，记录路线 k=k+1 N k≥蚂蚁总数m Y s=s+1 N s≥n Y 根据记录计算权值，记录最优路径 更新每条路径上的信息素量 清空禁忌表及路线表 Nc++ Y Nc

7

3.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=

11 8 1 6 9 5 3 4 10 7 2

Shoetest_Length=

750.5

对运行结果的数据进行处理，可以得到以下结论：

（1） 最省钱的旅行方案为：徐州出发——洛阳市龙门石窟——西安市秦兵马俑——山

西祁县乔家大院——青岛市崂山——北京八达岭长城——江西九江庐山——黄山市黄山——常州中华恐龙园——舟山市普陀山——武汉市黄鹤楼——返回徐州，反向亦可。 （2） 具体行程： 时间 事件 费用 5.1 13:40-5.1 从徐州出发，乘1085普快（硬座）到达34元 19:25 洛阳 5.1 19:25-5.2 入住于洛阳东宣假日酒店 198元+60元（吃饭等其8:00 他费用） 5.2 8:00-5.2 在洛阳市龙门石窟游玩3小时 120元 11:00 8

5.2 17:55-5.2 23:06 5.2 23:06-5.3 08:00 5.3 08:00-5.3 10:00 5.3 20:52-5.4 07:45 5.4 08:30-5.4 09:44 5.4 09:44-5.4 12:44 5.4 14:55-5.4 16:08 5.4 21:36-5.5 08:45 5.5 08:45-5.5 14:45 5.5 20:07-5.6 05:38 5.6 08:00-5.6 11:00 5.6 12:14-5.7 04:14 5.7 08:00-5.7 15:00 5.7 19:42-5.7 23:07 5.7 23:11-5.8 04:08 5.8 08:00-5.8 15:00 5.8 19:10-5.9 04:46 5.9 08:00-5.9 12:00 5.9 22:30-5.10 05:19 5.10 06:30-5.10 08:40 5.10 08:40-5.10 14:40 5.10 14:40-5.10

从洛阳出发，乘1184/1181普快（硬座）28元 到达西安 入住于西安西安华清豪泰商务会所 130元+60元 在西安市秦始皇兵马俑游玩2个小时 90元 从西安出发，乘2670普快（硬座）到达45元 太原 从太原出发，乘L7815（硬座）到达祁县 13元 在祁县乔家大院游玩3个小时 40元+60元 从祁县出发，乘4626次列车（硬座）返7元 回太原 从太原出发，乘K884/K881 K-快速 （硬120元 座）到达青岛 在青岛市崂山游玩6个小时 100元+60元 从崂山出发，乘T26 T-特快 （硬座）到116元 达北京 在北京八达岭长城游玩3个小时 45元+60元 从北京出发，乘坐1453普快（硬座）到145元 达九江 在九江市庐山游玩7个小时 180元+60元 从庐山出发，乘坐K13/K12 K-快速 （硬41元 座）到鹰潭 从鹰潭出发，乘坐K156 K-快速（硬座）51元 到黄山 在黄山市黄山游玩7个小时 230元+60元 从黄山出发，乘K8420/K8417 K-快速 （硬73元 座）到常州 在常州市恐龙园游玩4个小时 160元+60元 从常州出发，乘坐K57/K78 K-快速 （硬73元 座）到宁波 从宁波出发，乘坐大巴+快艇到达普陀山 70元 在舟山市普陀山游玩6个小时 160元+60元 从普陀山出发，乘坐大巴+快艇返回宁波 70元 9

16:50 5.10 21:28-5.11 07:16 5.11 08:00-5.11 10:00 5.11 16:54-5.12 04:13 从宁波出发，乘坐Z32/Z33 Z-直特（硬卧）到武昌 在武汉市黄鹤楼游玩2个小时 143元 80元+60元 从汉口出发，乘坐2614/2615普快（硬座）39元 返回徐州 总计：3201元 表1 问题1的具体行程

3.2.2问题（2）时间TSP问题的求解 在本问题这一经典的TSP问题模型中，通过对于模型之中城市的集合L={ Lij|Ci，CjC }，可以建立一个与之对应的描述矩阵D=(dij)描述。

由于问题中的限制条件以及时间的不可控性，在假设中选择使用距离的TSP替代时间的TSP。根据网络上的数据可知，若选择单一交通工具，旅途中的时间与旅途的长度成正比，而在本题的情况下可以乘坐的航班较少，在不考虑费用的情况下，可以近似认为选择的交通工具只有长途汽车与火车两种，且不同车种和班次之间的速度差异可以忽略。

那么，仍然根据蚁群算法的解题思路，使用各个城市的经纬度，转化为高斯坐标进行定位，而两两景点之间的有向线段的权值用城市之间的距离表示，根据一些既定的班次并对距离做了调整（可参见附录）。

在MATLAB算法中对参数初始化后运行程序，运行5次得相对最优解如下：

Shortest_Route=

1 2 11 7 10 8 6 9 5 4 3 1

Shortest_length=

5179

作图结果如下：

图2 MATLAB运行结果

10

对程序运行结果进行处理，可以得到以下结论：

（1） 按地理经纬度考虑，在蚁群算法循环200次的结果下，给旅游者提供以下相对最

优的方案：徐州出发——常州中华恐龙园——舟山市普陀山——黄山市黄山——九江市庐山——武汉市黄鹤楼——洛阳市龙门石窟——西安市秦始皇兵马俑——祁县乔家大院——北京市八达岭长城——青岛市崂山——返回徐州，反向旅行一样不再赘述。

（2） 按照此结果，画出地图上的仿真模拟图：

图3 旅行路线仿真模拟图

（3） 根据原题中的假设，制定具体的旅游计划如下： 时间 事件 5.1 09:35-5.1 从徐州出发，乘K58/K55（硬座）到达常州 15:19 5.1 15:19-5.2 入住于常州福兰特连锁旅店晋陵店 08:00 5.2 08:00-5.2 在常州市恐龙园游玩4小时 12:00 5.2 14:40-5.2 从常州出发，乘东方航空公司MU5692到达北京 16:25 5.2 从北京机场换乘中国南方航空股份有限公司CZ318519:10-5.2 到达宁波 21:15 5.2 21:15-5.3 入住于宁波格调时尚宾馆 08:00 5.3 06:30-5.3 从宁波出发，乘坐大巴+快艇到达普陀山 08:40 11

费用 70元 189元+60元（吃饭等其他费用） 160元 960元 1180元 148元 70元

5.3 08:40-5.3 14:40 5.3 14:40-5.3 16:50 5.3 16:50-5.4 09:02 5.4 09:02-5.4 18:25 5.4 18:25-5.5 08:00 5.5 08:00-5.5 15:00 5.5 18:28-5.6 03:02 5.6 08:00-5.6 15:00 5.6 19:33-5.6 21:46 5.6 21:46-5.7 08:00 5.7 08:00-5.7 10:00 5.7 10:10-5.7 16:35 5.7 16:35-5.8 08:00 5.8 08:00-5.8 11:00 5.8 11:01-5.8

在舟山市普陀山游玩6个小时 200元+60元 从普陀山出发，乘坐大巴+快艇返回宁波 70元 入住于宁波格调时尚宾馆 148元 从宁波出发，乘K8498 K-快速（硬座），中转K70/K67 92元 K-快速（硬座）到达黄山 入住黄山宏村清和丹客栈 60元 在黄山市黄山游玩7个小时 230元+60元 从黄山市出发，乘K70/K67(硬座)，中转1586/1587 普92元 快（硬座）到达庐山 在九江市庐山游玩7个小时 180元+60元 从庐山出发，乘坐D3230 D-动车（二等软座）到达汉80元 口 入住于武汉尚果创意酒店 169元 在武汉市黄鹤楼游玩2个小时 80元+60元 从武汉出发，乘中国南方航空公司CZ8189，中转杭州，1620元 转乘G52717到达洛阳 入住于洛阳东宣假日酒店 198元 游玩3个小时在洛阳市龙门石窟 从洛阳出发，乘坐K1130/K1131 K-快速 （硬座）到达西安 12 120元+60元 55元

16:05 5.8 16:05-5.9 08:00 5.9 08:00-5.9 10:00 5.9 10:50-5.9 12:00 5.9 12:27-5.9 13:41 5.9 13:41-5.9 16:41 5.9 16:49-5.9 18:07 5.9 18:15-5.9 19:35 5.9 19:35-5.10 08:00 5.10 08:00-5.10 11:00 5.10 13:45-5.10 15:05 5.10 15:05-5.11 08:00 5.11 08:00-5.11 14:00 5.11 15:25-5.11 20:20 入住于西安华清豪泰商务会所 130元 在西安市秦始皇兵马俑游玩2个小时 90元+60元 从西安出发，乘坐中国南方航空公司CZ6319到达太原 310元 从太原出发，乘坐2602/2603到达祁县（硬座） 13元 在祁县乔家大院游玩3个小时 40元+60元 从祁县出发，乘坐L7816（硬座）到达太原 7元 从太原出发，乘坐中国海南航空公司HU7371到达北京 300元 入住于北京新宇桥宾馆 188元 在八达岭长城游玩3个小时 45元+60元 从北京出发，乘坐中国国际航空公司CA1575到达青岛 651元 入住于青岛海利鑫凤凰山庄 180元 在青岛市崂山游玩6小时 100元 从青岛出发，乘坐山东航空股份有限公司SC4823，中1390元 转徐州，乘坐中国四川航空公司3U8814到达徐州 表2 问题2的具体行程 3.2 试探法求解权值不变时有约束条件TSP问题的最优化模型 3.2.1 在约束条件下TSP问题的模型建立

在问题3、4中增加了“费用在两千元以内”和“时间在5天以内”的约束条件，问题

13

转化为求解汉密尔顿图子集在给定条件下的最优解，使得问题复杂度增加。 与无约束条件的单一权值问题相同，首先建立以图为基础的模型。 其中：

D=

为加权描述矩阵；

X=

为决策的0-1矩阵

对于（3）（4）问之中对于游览景点数最多的要求，0-1规划矩阵及其子集规模庞大，因此必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法。由于约束条件，应该先依据权值分配每个景点的优先级，再依据优先级对TSP问题进行动态分析，选取优先级高的景点试探满足一定条件之下的最优路线，并由蚁群算法得出固定的子集的路径最优解。

3.2.2 模型的求解

1.问题（3）存在费用约束条件下的最优解

本题先用最小元素法进行估计，再由蚁群算法得到最优解，并用试探法验证合理性。 （1） 改进的最小元素法

最小元素法的宗旨是每一步都取当前的最优值。算法步骤为对费用矩阵D做n次下列循环：在D中找到一个最小值Dij，令xij=1:；将D的第i列所有数据改为无穷大，如果

=n，可将D的i行数据全部改为正无穷大。在循环过程中记录满足条件的xij和

xij的个数。

由贪婪法，可得满足条件的最优解为徐州——北京——祁县——西安——洛阳——武汉——徐州，最小费用为1913元。可以近似认为满足条件时最多的游览景点数为5.由于存在时间上的不确定导致费用的波动，将子集的元素个数从5个可以扩大至6个。

根据每个景点的费用，为每个景点加权值，选择其中权值最低的5至6个景点，用蚁群算法模拟出最优化的解。各个景点的权值可以简化为：

Xj=

（2） 调整优化

调整优化指的是将一个离最优解很近的初始解调整到调整算法下无法更优的程度。调整法主要是用试探法对子集的个数进行优化，也可以通过对蚁群算法的设置优化图形的路线。采用试探法可以列举出游览不同个数个景点时的费用变化。

确定子集个数时的算法仍然由蚁群算法实现。其结果如下： Shortest_Route=

4 1 7 3 6 5 2

Shortest_Length=

2390

14

图3 MATLAB运行结果

对所得的数据进行处理，可得以下结果： （1） 具体行程： 时间 事件 5.1 14:05-5.2 从徐州出发，乘K1354/K1351（硬座）到达02:05 常州 5.2 08:00-5.2.10:00 在西安市秦始皇兵马俑游玩2个小时 5.2 20:52-5.3 从西安出发，乘2670（硬座）到达山西祁06:19 县 5.3 08:00-5.3 11:00 在山西祁县乔家大院游玩3个小时 5.3 13:47-5.3 从山西出发，乘K237/K240（硬座）到达武21:29 汉 5.3 21:19-5.4 08:00 入住于武汉尚果创意酒店 5.4 08:00-5.4 10:00 在武汉市黄鹤楼游玩2个小时 5.4 12:47-5.4 从武汉出发，乘动车D3024/D3021（二等软15:02 座）到达合肥 5.4 15:17-5.4 从合肥出发，乘2025普快（硬座）到达黄21:10 山 5.4 21:10-5.5 08:00 入住于黄山宏村清和丹客栈 5.5 08:00-5.5 15:00 在黄山市黄山游玩7个小时 5.5 15:00-5.6 09:00 入住于黄山宏村清和丹客栈 5.6 09:21-5.7 从黄山出发，乘K46快车（硬座）到达北05:07 京 5.7 08:00-5.7 11:00 在八达岭长城游玩3个小时 5.7 16:55-5.8 从北京出发，乘T231特快列车（硬座）到15

费用 113元 90元+60元（吃饭等其他费用） 39元 40元+60元 67元 169元 80元+60元 112元 49元 60元 230元+60元 69元 182元 45元+60元 106元

01:55 5.6 08:00-5.6 11:00 5.6 12:47-5.6 18:43 达洛阳 在洛阳市龙门石窟游玩3个小时 120元+60元 从洛阳出发，乘1086列普快（硬座）返回徐州 34元 总计：1839元 表3 问题3的具体行程

2.问题（4）存在时间约束条件下的最优解

本题与问题（3）类似，仍然是先根据贪婪法求得子集中元素个数的近似解，依据加权后每个景点的优先级筛选优先级高的景点。用蚁群算法实现最优解。 其结果如下：

图4 MATLAB运行结果

时间 事件 5.1 09:35-5.1 10:45 从徐州出发，乘KN2904航班到达北京 5.1 12:00-5.1 15:00 在八达岭长城游玩3个小时 5.1 19:20-5.1 21:05 从北京出发，乘MU5695到达洛阳机场 5.1 22:00-5.2 08:00 入住于洛阳东宣假日酒店 5.2 08:00-5.2 11:00 在洛阳市龙门石窟游玩3个小时 5.2 14:53-5.2 从洛阳出发，乘K128/125快车（硬座）到20:13 达西安 16

费用 550元 45元+60元（吃饭等其他费用） 787元 198元 120元+60元 55元

5.2 21:00-5.3 08:00 5.3 08:00-5.3 10:00 5.3 11:50-5.3 12:55 5.3 14:00-5.3 16:00 5.3 22:20-5.3 23:40 5.4 05:00-5.4 06:08 5.4 08:00-5.4 11:00 5.4 12:29-5.4 13:47 5.4 17:53-5.5 12:58 5.5 14:00-5.5 18:00 5.6 00:09-5.6 05:48

入住于西安华清豪泰商务会所 130元 在西安市秦始皇兵马俑处游玩2个小时 90元+60元 从西安咸阳机场，乘MF8218航班到达武汉天河机场 608元 在武汉市黄鹤楼游玩2个小时 90元+60元 从武汉天河机场出发，乘MU2364航班到达太原武宿机场 540元 从太原出发，乘2462/2463普快（硬座）到达祁县 7元 在祁县乔家大院游玩3个小时 40元+60元 从祁县出发，乘1096普快（硬座）到达太原 7元 从太原出发，乘K374/371快车（软卧）到达常州 458元 在常州恐龙园游玩3个小时 160元+60元 从常州出发，乘K76/77快车（硬座）返回徐州 70元 表4 问题4的具体行程

3.3 求解多目标TSP问题

3.3.1多目标TSP问题的模型建立

为综合衡量费用TSP与时间TSP问题，建立以下模型评价：

（1） 确定多目标TSP问题的优化模型，本题中只考虑费用与时间两个因素的优化； （2） 给定各个目标因素的优先级。本题中，以费用为第一优先级，时间为第二优先级。 （3） 对给定的指标进行无量纲化处理，使得各个指标具有可比性。

由费用和时间两个描述矩阵，给定无量纲处理为：

D’=D/dmin

其中，D’为处理过后的无量纲矩阵，dmin为描述矩阵中的最小元素。

（4） 对费用与时间两个矩阵，取相同位置坐标的无量纲量进行整合形成一个新的无量

纲量，定为求解矩阵。

（5） 用最小元素法确定在满足费用以及时间同时约束时，有向图包涵的原图的子集的

元素个数。给定各个景点的优先级，用试探法选取可能为最优的路径。其中每个景点的权值为：

Xj=

3.3.2问题（5）多目标TSP问题模型求解

处理数据后用MATLAB进行模拟，所得相对最优解如下：

17

图5 MATLAB运行结果

具体行程如下： 时间 5.1 09:35-5.1 10:45 5.1 10:45-5.1 13:46 5.1 22:48-5.2 07:38 5.2 08:00-5.2 14:00 5.2 15:16-5.3 05:28 5.3 06:02-5.3 12:42 5.3 12:24-5.3 14:24 5.3 18:20-5.4 03:32 5.4 05:00-5.4 06:08 5.4 08:00-5.4 11:00 5.4 12:29-5.4 13:47 5.4 18:01-5.5

事件 从徐州出发，乘坐中国联合航空公司KN2904航班到达北京 在北京八达岭长城游玩3个小时 从北京出发，乘坐T25 T-特快（硬座）到达青岛 在青岛市崂山游玩6个小时 费用 550元 45元+60元 116元 100元+60元 从青岛出发，乘坐1112/1113普快（硬坐）到达中转123元 站郑州 从中转站郑州出发，乘坐K1363 K-快速（硬坐）到达73元 西安 在西安市秦始皇兵马俑游玩2个小时 90元+60元 从西安出发，乘坐T42 T-特快（硬座）到达太原站 103元 从太原出发，乘2462/2463 普快（硬座）到达祁县 7元 在祁县乔家大院游玩3小时 从祁县出发，乘坐1096普快返回太原 40+60元 7元 从太原出发，乘K520/K521 K-特快（硬坐）到达武汉 150元 18

09:44 5.5 09:44-5.5 11:44 5.5 18:40-5.6 04:23 在武汉市黄鹤楼游玩2个小时 80元+60元 从武汉出发，乘2614/2615 普快（硬坐）返回徐州 39元 总计：1823元 表5 问题5的具体行程

四 模型的评价

4.1模型的优点

(1)算法表示借助了MATLAB语言，分析精度高，节约时间，简介形象； （2）蚁群算法与遗传算法，Floyd算法相比，准确度高； （3）给出的方案具体，详实并且可行。 4.2模型的缺点

（1）算法具有一定局限性；

（2）未详细考虑旅途中的安排与时间的衔接问题； （3）蚁群算法耗时较长。

参考文献

[1] 徐 莉. 基于改进遗传算法的多目标TSP问题研究[D] .武汉： 武汉理工大学 [2] 李 闻. 蚁群优化算法及其应用研究[D].长沙：湖南大学，2005.

[3] 朱 杰. 蚁群算法解决TSP问题的浅析[J].上海：同济大学，2008；1009- 3044(2008)22- 724-02.

[4] 夏国成，赵佳宝.智能蚂蚁算法求解多目标TSP问题的改进研究.南京：南京大学，2006.

[5] 游道明，陈坚.用蚂蚁算法解决多目标TSP问题[J].上海 ,2003(10)—1808—0. [6] 燕忠，袁春伟.用蚁群优化算法求解中国旅行商问题[J].南京：东南大学. [7] 汪林林.对“货郎担问题”的研究.重庆：重庆邮电学院.

[8]刘峙麟，李臣，王露.基于层次分析和图论模型的旅游线路设计及其评估.南京：南京大学.

[9] 周康，强小利，同小军，许进.求解TSP算法.武汉：华中科技大学.

[10] 李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究.重庆：重庆邮电大学.

[11] 王宇平,李英华. 求解TSP的量子遗传算法[J]. 计算机学报, 2007, 30 (5) : 7482755.

[12] 马良，蒋馥．多目标旅行售货员问题的蚂蚁算法求解．系统程理论方 法应用，1999；8(4)：23—27

[13] 杨忠, 鲍明, 张阿舟. 求解中国旅行商问题的新结果 [J]. 数据采集与处理, 1993, 8(3): 177-184.

[14]唐建清，邹国霞. 基于Floyd算法的旅游路径智能选择系统.上海：华东师范大学

19

[15]许峰，杜军平.改进蚁群算法在旅游线路规划中的应用研究.北京：北京邮电大学 [16]杨志江，李国欣，张敏. 管道订购与运输问题.徐州：中国矿业大学

附录

1. 基本蚁群算法的MATLAB实现 2. m=11; 3. Alpha=1; 4. Beta=5; 5. Rho=0.7; 6. NC_max=200; 7. Q=100;

8. C=load('D:\\ZB.txt'); 9. D=load('D:\\JL.txt'); 10. n=11;

11. Eta=1./D;

12. Tau=ones(n,n); 13. Tabu=zeros(m,n); 14. NC=1;

15. R_best=zeros(NC_max,n);

16. L_best=inf.*ones(NC_max,1); 17. L_ave=zeros(NC_max,1); 18. while NC<=NC_max 19.

20. %put ants 21. Randpos=[];

22. for i=1:(ceil(m/n));

23. Randpos=[Randpos,randperm(n)]; 24. end

25. Tabu(:,1)=(Randpos(1,1:m)); 26. %complete traveling

20

27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.

for j=2:n for i=1:m

visited=Tabu(i,1:(j-1)); J=zeros(1,(n-j+1)); P=J; Jc=1; for k=1:n

if length(find(visited==k))==0 J(Jc)=k; Jc=Jc+1; end end

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); 41. end

42. P=P/(sum(P));

43. %select the next city 44. Pcum=cumsum(P);

45. Select=find(Pcum>=rand); 46. to_visit=J(Select(1)); 47. Tabu(i,j)=to_visit; 48. end 49. end

50. if NC>=2

51. Tabu(1,:)=R_best(NC-1,:); 52. end

53. %record the best route 54. L=zeros(m,1); 55. for i=1:m

56. R=Tabu(1,:); 57. for j=1:(n-1)

58. L(i)=L(i)+D(R(j),R(j+1)); 59. end

60. L(i)=L(i)+D(R(1),R(n)); 61. end

62. L_best(NC)=min(L);

63. pos=find(L==L_best(NC));

64. R_best(NC,:)=Tabu(pos(1),:); 65. L_ave(NC)=mean(L); 66. NC=NC+1; 67. %refresh

68. Delta_Tau=zeros(n,n); 69. for i=1:m;

70. for j=1:(n-1); 71.

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i) 72. end 73.

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); 74. end

75. Tau=(1-Rho).*Tau+Delta_Tau; 76. %empty tabu

21

77. Tabu=zeros(m,n); 78. end

79. Pos=find(L_best==min(L_best)); 80. shortest_Route=R_best(Pos(1),:) 81. Shorest_Length=L_best(Pos(1)) 82. subplot(1,2,1) 83. N=length(R);

84. scatter(C(:,1),C(:,2)); 85. hold on

86. plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)]) 87. for ii=2:N

88. plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)]) 89. hold on 90. end

91. subplot(1,2,2) 92. plot(L_best) 93. hold on

94. plot(L_ave)

2.各个景点的高斯坐标（3分度） 江苏徐州 常州中华恐龙园 青岛市崂山 北京八达岭长城 山西祁县乔家大院 洛阳市石门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇兵马俑 九江市庐山 舟山市普陀山 39518419.34 40495265.04 40500000 39406614.65 37618114.73 37632856.4 39605926.46 38530395.06 36587493.29 39400011.05 37606139.98 3793326.773 3519739.016 3985613.305 4474604.565 4138111.493 3842336.821 3342855.143 3377492.083 3793717.098 3289211.33 3320681.882 3.各城市之间的距离 江苏徐州 0 454 473 779 常州中华恐龙园 青岛市崂山 北京八达岭长城 779 1209 724 0 山西祁县乔家大院 775 1198 947 601 22

距离 洛阳市石门石窟 黄山市黄山 九武汉西安市江市黄秦始皇市鹤楼 兵马俑 庐山 687 738 810 631 1212 595 1231 1138 舟山市普陀山 840 396 江苏徐州 常州中华恐龙园 青岛市崂山 北京八达岭长城 454 473 0 714 714 0 528 640 864 452 933 956 1146 888 1421328 1 1041029 0 1471599 1 1209 724

山西祁县乔家大院 洛阳市石门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇兵马俑 九江市庐山 舟山市普陀山 775 1198 947 601 0 430 1306 931 537 1161578 0 528 640 687 810 631 840 864 933 452 956 738 1212 595 1146 1231 888 1421 1328 1138 1471 1599 430 1306 931 537 1160 1578 0 963 963 0 604 528 0 814 243 359 817 1235 1242 298 490 604 528 359 1242 814 243 1009 0 1041 1041603 1 0 779 0 1040 102396 9 817 298 1235 490 1009 1603 779 4.各城市之间的最低旅行价格 江苏徐州 0 62 70 99 常州中华恐龙园 青岛市崂山 北京八达岭长城 392 433 418 0 山西祁县乔家大院 399.5 458.5 313.5 382 洛阳市石门石窟 黄山市黄山 九武汉西安市江市黄秦始皇市鹤楼 兵马俑 庐山 348 414 627 459 335 517 445 600 445 740 430 575 舟山市普陀山 600 574 810 792 江苏徐州 常州中华恐龙园 青岛市崂山 北京八达岭长城 山西祁县乔家大院 洛阳市石门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇

471 410 0 490 559 0 412 449 503 423 503 535 431 532 549 465 111365579.5 .5 .5 34 99 39 55 534 465 482 525 514 658 574 505 387 0 472 517 390 321 581646..5 5 609 527 541 654 346 475 443 443 382 455 369 329 23

0 468 496 0 373 440 0 440 308 492 419 475 411 500 0 511 442 481 406 489

兵马俑 九江市庐山 舟山市普陀山 87 140 579 650 523 690 438 625 439.5 474.5 440 395 527 417 379 390 361 0 554 0 474 524 5.各城市之间的车旅时间 常州江苏中华 徐州 恐龙园 江苏徐州 常州中华恐龙园 青岛市崂山 北京八达岭长城 山西祁县乔家大院 洛阳市

北京青岛市八达崂山 岭长城 山西祁县乔家大院 洛阳市石门石窟 西安武汉市秦黄山市市黄始皇黄山 鹤楼 兵马俑 九江市舟山市庐山 普陀山 0 7.37 11.33 4.17 9.87 7.67 14.08 8.17 8.58 15.5 19.73 3.37 0 12 4.5 9.78 9.42 12.92 6.05 7.75 13.83 10.53 5.33 10 0 4.33 5.78 8.57 13.33 3.45 3.83 12.75 9 1.17 5.5 7.33 0 5.2 4.75 9 3.83 3.75 9.25 9.75 6.87 10.78 9.78 5.2 0 10.07 13.12 4.45 4.2 14.12 13.7 4.67 10.42 11.57 4.75 10.07 0 16.12 8.75 3.33 18.08 13.83 24

石门石窟 黄山市7.08 黄山 武汉市6.17 黄鹤楼 西安市秦始6.58 皇兵马俑 九江市8.5 庐山 舟山市13.73 普陀山 9.92 12.33 5 9.12 12.12 0 8.1 3.83 17.7 16.58 8.05 7.45 4.83 5.45 9.75 13.1 0 3.17 10.58 8.75 9.75 7.83 4.75 5.2 4.33 8.83 3.17 0 12.88 10.83 10.83 11.75 5.25 10.12 14.08 16.7 5.58 7.88 0 13.62 8.53 9 6.75 10.7 10.83 17.58 4.75 6.83 14.62 0 6.各城市之间的无量纲化整合权值 江苏徐州 青岛市崂山 17.17.220 388294 82 5.120.0 935411常州中华恐龙园 北京八达岭长城 12.69941 山西祁县乔家大院 洛阳市石门石窟 16.78765 黄山市黄山 20.28588 18.361武汉西安市市黄秦始皇鹤楼 兵马俑 16.416.43290529 4 16.218.83822647 4 九江市庐山 23.70588 24.477舟山市普陀山 31.37706 21.41235 江苏徐州 常州中华恐龙

18.62 14.2320.26521.21529 29 412 25

园 青岛市崂山 北京八达岭长城 山西祁县乔家大院 洛阳市石门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇兵马俑 九江市庐山 舟山市普陀山 29 77 7.322.448880 118 24 4.015.17.64817006706 65 47 10.23.8213.149412 53 41 19.5.622.122467 588 47 9.921.20.09917771647 65 18 7.320.19.16170802765 59 94 8.116.22.63976682235 47 94 11.24.23.85058867941 82 65 17.23.19.91847294235 65 12 13.6212.00020.36412 59 412 0 13.58235 13.43514.4229 647 0 20.95235 0 11.9218.305647 29 18 22.06529 17.64706 21.32588 22.88471 0 19.814.91829118 4 15.314.39703 6 13.911.64112059 8 17.710.38882059 2 19.014.15354118 3 0 14.11118 13.25824 0 15.9719.50223.70059 35 824 20.14.8513.30219.75 247941 94 06 16.14.7711.87613.27212941 47 118 35 21.15.1320.04624.02317235 47 118 65 22.22.1321.65523.33 844235 88 71 06 27.51471 19.16177 24.22294 25.55059 23.67059 18.28588 20.90941 0 26.82353 27.04412 26.71471 25.74177 26.08 18.66177 24.06529 23.91412 0 14.716.49762706 5 23.14.218.77110312059 8 77 26

园 青岛市崂山 北京八达岭长城 山西祁县乔家大院 洛阳市石门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇兵马俑 九江市庐山 舟山市普陀山 29 77 7.322.448880 118 24 4.015.17.64817006706 65 47 10.23.8213.149412 53 41 19.5.622.122467 588 47 9.921.20.09917771647 65 18 7.320.19.16170802765 59 94 8.116.22.63976682235 47 94 11.24.23.85058867941 82 65 17.23.19.91847294235 65 12 13.6212.00020.36412 59 412 0 13.58235 13.43514.4229 647 0 20.95235 0 11.9218.305647 29 18 22.06529 17.64706 21.32588 22.88471 0 19.814.91829118 4 15.314.39703 6 13.911.64112059 8 17.710.38882059 2 19.014.15354118 3 0 14.11118 13.25824 0 15.9719.50223.70059 35 824 20.14.8513.30219.75 247941 94 06 16.14.7711.87613.27212941 47 118 35 21.15.1320.04624.02317235 47 118 65 22.22.1321.65523.33 844235 88 71 06 27.51471 19.16177 24.22294 25.55059 23.67059 18.28588 20.90941 0 26.82353 27.04412 26.71471 25.74177 26.08 18.66177 24.06529 23.91412 0 14.716.49762706 5 23.14.218.77110312059 8 77 26

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