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

数学建模

王迪B09010601通信工程

郑佳佳B09010603通信工程

孟天舒B09010604通信工程

题目

旅游线路的优化设计

摘要

本题为典型的旅行商问题（TSP），是组合数学中一个古老而又困难的问题，它易于描

述却难以完全解决，属于NP完全问题。对于规模较小的旅行商问题，可以通过穷举得到最

优解，但随着问题规模的增大空间复杂度急剧增加，需要通过启发式算法求解。

由意大利学者于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），蚁群算法，动态分析，试探法

一、 问题的重述

旅游线路的优化设计

随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一

位旅游爱好者打算现在的今年的五月一日早上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元的旅游费用，想尽可能多游览景点，请建立相关

数学模型并设计旅游行程表。

二、 模型假设与符号说明

2.1 模型的基本假设

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

（2） 只考虑问题中提供的11个旅游景点，不考虑其他中转地点作为TSP的需求点。

（3） 为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。在问题

（2）中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距离的TSP

替代时间的TSP。不考虑绕路等特殊情况。在建模时认为两地之间往返的费用时

间差异可忽略。

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

内。

（5）认为网上公布的机票与车票均可以在任意时刻获得，且班次误点等特殊情况不予考

虑，忽略转站中的不合理因素。

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

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

2.2 符号说明

符号 名称

G 赋权图矩阵

C 图中的元素（景点）

n 景点的个数

D 赋权图的描述矩阵

T 访问顺序集合

L 最优解（最小费用或最短路程）

d 时间t到t的TSP描述

ti,ti+1ii+1

m 蚂蚁的总数量

k 蚂蚁的编号

b(t) t时刻位于城市i的蚂蚁数目

i

τt时刻路径（i,j）上的信息量 (t)

ij

t时刻C中两两景点之间的残留信息素浓度集合 Г

初始时刻各路径上的信息素量 P

寻优有向图 g(C,L,Г)

第k只蚂蚁的禁忌搜索表 tabu

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

信息启发式因子 α

期望启发式因子 β

启发函数 η(t)

信息素挥发系数 ρ

t时刻k蚂蚁在路径ij上留下的信息素量 △τ(t)

蚂蚁携带的信息素量 Q

本次循环中第k只蚂蚁所走的路程长度 L

所记录的循环次数 N

k

ij

ij

k

ij

k

k

C

N 最大循环次数

Cmax

三模型的建立与求解

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

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

令赋权图为G=(C,L)，其中C={C,C,……C}为节点，表示各个景点的集合；L={L|Ci，Cj C}表

12nij

示各个景点之间的路径，每两个景点间的路径l都有相关的权值d与之对应，从而建立起

ijij

一个D=（d）矩阵，权值可以表示距离、费用、路径等。由于题目的相关要求可以抽象出

ij

一个典型旅行商问题的数学模型：

minL=

3.1.2基本的蚁群算法模型

基本思想：蚁群算法是一种通过模拟自然界蚂蚁寻径的行为的进化算法。蚂蚁群找到食

物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路

径上释放出一种特殊的信息素，当它们碰到一个还没有走过的路口时,就随机地挑选一条路

径前行，与此同时释放出与路线长度有关的信息素，路径越长,释放的激素浓度越低，当后

来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高路径概率就会相对较大，这样形成了

一个正反馈。最优路径上的激素浓度越来越大,而其它的路径上激素浓度却会随着时间的流

逝而消减。这样,整个蚁群最终会找出最优路径。

用b(t)表示城市i的蚂蚁数目，表示t时段路径（i，j）上的信息量，n表示景点

i



ij

的个数，m为蚂蚁的总数量，则m=

初试时刻，各条路径上信息量相等，均为P，（0）=P。又因为蚂蚁不能重复经过同



ij

一个城市，因此建立禁忌表（或记录未走过的路径J）tabu(k取正整数)来记录蚂蚁走过的

kk

城市，并随时间做动态调整。

被随机分散在个节点的只蚂蚁同时出发，按照下面的概率公式逐次访问各个城市节

nm

点：蚂蚁以概率访问下一个节点：

k

在这里，有

p

ij

k



ij

表示边上的信息素强度。

L(i,j)



ijij

表示由节点到节点的启发函数，显然距离越长期望度越低，所以在此将设为

i

j

1/d

ij

。

随着时间的推移,可能会出现两种情况:①之前各蚂蚁留下的信息素逐渐消失；②经过

多次循环后，路径上的残留信息素过多，淹没了期望程度对蚂蚁选择路径的影响。为了避免

这两种情况,在每一只蚂蚁完成一次循环后，我们对引入参数对残留的信息素进行更新。





为信息素的挥发速率，是在[0,1]间取值的可变量,用于控制两种信息素的比重。

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

x

调整：





ij

：蚂蚁在本次循环中留在路径上的信息素强度。

L(i,j)





ij

k

：蚂蚁留在路径上的信息素强度。

k

L(i,j)

当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改

路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最

后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者

是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立

新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基

本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复

记忆和学习的过程，得到了最短路径，即全局最优解。

我们将各城市的经纬度通过球面坐标系的转化分别投影到一个二维平面上点的横纵坐

标，在求解的时候可直接求出两地的直线距离，即为

d

ij

。

3.1.3基本蚁群算法的算法流程

在本题中，基本蚁群算法的具体实现步骤如下：

1.参数初始化：

令t=0；

设置最大循环次数Nc，循环次数Nc=0；

Max

将m只蚂蚁置于n个节点上，在每个节点i放置b(t)只蚂蚁；

i

初始化每条边(i,j)上的信息素量?(0)=c为一个常量，初始时刻??(0)=0；

ijij

k

初始化禁忌表tabu和路径表L。

kk

2.设置索引号s=1，对k=1~m将蚂蚁k的起始城市放入禁忌表中，并重复以下步骤直至禁忌

表填充完整：

对k=1~m，利用公式计算转移概率p，根据伪随机比例规则选择下一景点，将蚂蚁k移动到

ij

下一景点j并将其填入禁忌表，同时记录蚂蚁k的路线，索引号自增。

3.对k=1~m，根据L的记录计算蚂蚁k所走循环路径的总长度，找到最佳路线

k

4.计算每只蚂蚁的信息素增量?△τ(t)

k

ij

k

5.更新每条路径上的信息素量△τ(t+n)

ij

6.清空禁忌表及路线表。

++，若Nc，返回步骤2，否则，循环结束。

Max

开始

初始化

索引号s=1

蚂蚁k=1

计算转移概率p，选择下一节点j

ij

修改禁忌表，记录路

k=k+1

N

k≥蚂蚁总数m

Y

s=s+1

N

s≥n

Y

根据记录计算权值，记录最优路径

更新每条路径上的信息素量

清空禁忌表及路线表

Nc++

Y

Nc

Max

N

输出结果，结束

图1基本蚁群算法的程序流程图

3.2蚁群算法的模型求解

3.2.1问题（1）费用TSP问题的求解

根据蚁群算法的解题思路，编写MATLAB程序。将各个景点的经纬度坐标转化为高斯坐标，

便于MATLAB的作图。建立文本输入参数，其中权值为两两景点之间的车费，旅游景点门票，

住宿费以及餐费等。在车费的选择上在两景点拥有的航班，列车以及长途客运之中选择费用

最低的。考虑到住宿的不确定性，以最坏的情况假设每天都需要住宿。

首先对参数进行初始化。时间t=0，循环次数NC=0，最大循环次数NCMAX=200，蚂蚁所携带

的信息素量为100，初始时刻△τ(0)=0，蚂蚁数量m=11，景点数n=11，信息启发式因子

k

ij

为1，期望启发式因子为5，信息素挥发系数为0.7，程序运行5次，取相对最优解。

MATLAB运行结果为：

Shortest_Route=

Shoetest_Length=

750.5

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

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

县乔家大院——青岛市崂山——北京八达岭长城——江西九江庐山——黄山市黄山

——常州中华恐龙园——舟山市普陀山——武汉市黄鹤楼——返回徐州，反向亦可。

（2） 具体行程：

时间 事件 费用

5.113:40-5.119:从徐州出发，乘1085普快（硬座）到达洛34元

25 阳

5.119:25-5.28:0入住于洛阳东宣假日酒店 198元+60元（吃饭等其他

0 费用）

5.28:00-5.211:0在洛阳市龙门石窟游玩3小时 120元

0

5.217:55-5.223:从洛阳出发，乘1184/1181普快（硬座）到28元

06 达西安

5.223:06-5.308:入住于西安西安华清豪泰商务会所 130元+60元

00

5.308:00-5.310:在西安市秦始皇兵马俑游玩2个小时 90元

00

5.320:52-5.407:从西安出发，乘2670普快（硬座）到达太45元

45 原

5.408:30-5.409:从太原出发，乘L7815（硬座）到达祁县 13元

44

5.409:44-5.412:在祁县乔家大院游玩3个小时 40元+60元

44

5.414:55-5.416:从祁县出发，乘4626次列车（硬座）返回7元

08 太原

5.421:36-5.508:从太原出发，乘K884/K881K-快速（硬座）120元

45 到达青岛

5.508:45-5.514:在青岛市崂山游玩6个小时 100元+60元

45

5.520:07-5.605:从崂山出发，乘T26T-特快（硬座）到达北116元

38 京

5.608:00-5.611:在北京八达岭长城游玩3个小时 45元+60元

00

5.612:14-5.704:从北京出发，乘坐1453普快（硬座）到达145元

14 九江

5.708:00-5.715:在九江市庐山游玩7个小时 180元+60元

00

5.719:42-5.723:从庐山出发，乘坐K13/K12K-快速（硬座）41元

07 到鹰潭

5.723:11-5.804:从鹰潭出发，乘坐K156K-快速（硬座）到51元

08 黄山

5.808:00-5.815:在黄山市黄山游玩7个小时 230元+60元

00

5.819:10-5.904:从黄山出发，乘K8420/K8417K-快速（硬座）73元

46 到常州

5.908:00-5.912:在常州市恐龙园游玩4个小时 160元+60元

00

5.922:30-5.1005从常州出发，乘坐K57/K78K-快速（硬座）73元

:19 到宁波

5.1006:30-5.100从宁波出发，乘坐大巴+快艇到达普陀山 70元

8:40

5.1008:40-5.101在舟山市普陀山游玩6个小时 160元+60元

4:40

5.1014:40-5.101从普陀山出发，乘坐大巴+快艇返回宁波 70元

6:50

5.1021:28-5.110从宁波出发，乘坐Z32/Z33Z-直特（硬卧）143元

7:16 到武昌

5.1108:00-5.111在武汉市黄鹤楼游玩2个小时 80元+60元

0:00

5.1116:54-5.120从汉口出发，乘坐2614/2615普快（硬座）39元

4:13 返回徐州

总计：3201元

表1问题1的具体行程

时间TSP问题的求解

在本问题这一经典的TSP问题模型中，通过对于模型之中城市的集合L={L|C，C C}，可

ijij

以建立一个与之对应的描述矩阵D=(d)描述。

ij

由于问题中的限制条件以及时间的不可控性，在假设中选择使用距离的TSP替代时间的TSP。

根据网络上的数据可知，若选择单一交通工具，旅途中的时间与旅途的长度成正比，而在本

题的情况下可以乘坐的航班较少，在不考虑费用的情况下，可以近似认为选择的交通工具只

有长途汽车与火车两种，且不同车种和班次之间的速度差异可以忽略。

那么，仍然根据蚁群算法的解题思路，使用各个城市的经纬度，转化为高斯坐标进行定位，

而两两景点之间的有向线段的权值用城市之间的距离表示，根据一些既定的班次并对距离做

了调整（可参见附录）。

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

Shortest_Route=

Shortest_length=

5179

作图结果如下：

图2MATLAB运行结果

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

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

方案：徐州出发——常州中华恐龙园——舟山市普陀山——黄山市黄山——九江市庐

山——武汉市黄鹤楼——洛阳市龙门石窟——西安市秦始皇兵马俑——祁县乔家大

院——北京市八达岭长城——青岛市崂山——返回徐州，反向旅行一样不再赘述。

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

图3旅行路线仿真模拟图

（3） 根据原题中的假设，制定具体的旅游计划如下：

时间 事件 费用

5.109:35-5

从徐州出发，乘K58/K55（硬座）到达常州 70元

.115:19

5.115:19-5189元+60元（吃

入住于常州福兰特连锁旅店晋陵店

.208:00 饭等其他费用）

5.208:00-5

在常州市恐龙园游玩4小时 160元

.212:00

5.214:40-5

从常州出发，乘东方航空公司MU5692到达北京 960元

.216:25

5.219:10-5从北京机场换乘中国南方航空股份有限公司CZ3185到达

1180元

.221:15 宁波

5.221:15-5

入住于宁波格调时尚宾馆 148元

.308:00

5.306:30-5

从宁波出发，乘坐大巴+快艇到达普陀山 70元

.308:40

5.308:40-5

在舟山市普陀山游玩6个小时 200元+60元

.314:40

5.314:40-5

从普陀山出发，乘坐大巴+快艇返回宁波 70元

.316:50

5.316:50-5

入住于宁波格调时尚宾馆 148元

.409:02

5.409:02-5从宁波出发，乘K8498K-快速（硬座），中转K70/K67K-

92元

.418:25 快速（硬座）到达黄山

5.418:25-5

入住黄山宏村清和丹客栈 60元

.508:00

5.508:00-5

在黄山市黄山游玩7个小时 230元+60元

.515:00

5.518:28-5从黄山市出发，乘K70/K67(硬座)，中转1586/1587普快

92元

.603:02 （硬座）到达庐山

5.608:00-5

在九江市庐山游玩7个小时 180元+60元

.615:00

5.619:33-5

从庐山出发，乘坐D3230D-动车（二等软座）到达汉口 80元

.621:46

5.621:46-5

入住于武汉尚果创意酒店 169元

.708:00

5.708:00-5

在武汉市黄鹤楼游玩2个小时 80元+60元

.710:00

5.710:10-5从武汉出发，乘中国南方航空公司CZ8189，中转杭州，1620元

.716:35 转乘G52717到达洛阳

5.716:35-5

.808:00

5.808:00-5

.811:00

5.811:01-5

.816:05

5.816:05-5

.908:00

5.908:00-5

.910:00

5.910:50-5

.912:00

5.912:27-5

.913:41

5.913:41-5

.916:41

5.916:49-5

.918:07

5.918:15-5

.919:35

5.919:35-5

.1008:00

5.1008:00-

5.1011:00

5.1013:45-

5.1015:05

5.1015:05-

5.1108:00

5.1108:00-

5.1114:00

5.1115:25-从青岛出发，乘坐山东航空股份有限公司SC4823，中转

5.1120:20 徐州，乘坐中国四川航空公司3U8814到达徐州

入住于洛阳东宣假日酒店 198元

游玩3个小时在洛阳市龙门石窟 120元+60元

从洛阳出发，乘坐K1130/K1131K-快速（硬座）到达西安 55元

入住于西安华清豪泰商务会所 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元

1390元

表2问题2的具体行程

3.2试探法求解权值不变时有约束条件TSP问题的最优化模型

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

为求解汉密尔顿图子集在给定条件下的最优解，使得问题复杂度增加。

与无约束条件的单一权值问题相同，首先建立以图为基础的模型。

其中：

D=

为加权描述矩阵；

X=

为决策的0-1矩阵

对于（3）（4）问之中对于游览景点数最多的要求，0-1规划矩阵及其子集规模庞大，因此

必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法。由于约束条件，应该先

依据权值分配每个景点的优先级，再依据优先级对TSP问题进行动态分析，选取优先级高的

景点试探满足一定条件之下的最优路线，并由蚁群算法得出固定的子集的路径最优解。

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

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

（1） 改进的最小元素法

最小元素法的宗旨是每一步都取当前的最优值。算法步骤为对费用矩阵D做n次下列循环：

在D中找到一个最小值Dij，令x=1:；将D的第i列所有数据改为无穷大，如果 =n，

ij

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

ijij

由贪婪法，可得满足条件的最优解为徐州——北京——祁县——西安——洛阳——武汉——

徐州，最小费用为1913元。可以近似认为满足条件时最多的游览景点数为5.由于存在时间

上的不确定导致费用的波动，将子集的元素个数从5个可以扩大至6个。

根据每个景点的费用，为每个景点加权值，选择其中权值最低的5至6个景点，用蚁群算法

模拟出最优化的解。各个景点的权值可以简化为：

X=

j

（2） 调整优化

调整优化指的是将一个离最优解很近的初始解调整到调整算法下无法更优的程度。调整法主

要是用试探法对子集的个数进行优化，也可以通过对蚁群算法的设置优化图形的路线。采用

试探法可以列举出游览不同个数个景点时的费用变化。

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

Shortest_Route=

4173652

Shortest_Length=

2390

图3MATLAB运行结果

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

（1） 具体行程：

时间 事件 费用

5.114:05-5.20从徐州出发，乘K1354/K1351（硬座）到达常

2:05 州 113元

90元+60元（吃饭等其他

在西安市秦始皇兵马俑游玩2个小时 费用）

5.220:52-5.30

6:19 从西安出发，乘2670（硬座）到达山西祁县 39元

5.308:00-5.31

1:00 在山西祁县乔家大院游玩3个小时 40元+60元

5.313:47-5.32

1:29 从山西出发，乘K237/K240（硬座）到达武汉 67元

5.321:19-5.40

8:00 入住于武汉尚果创意酒店 169元

5.408:00-5.41

0:00 在武汉市黄鹤楼游玩2个小时 80元+60元

5.412:47-5.41从武汉出发，乘动车D3024/D3021（二等软座）

5:02 到达合肥 112元

5.415:17-5.42

1:10 从合肥出发，乘2025普快（硬座）到达黄山 49元

5.421:10-5.50

8:00 入住于黄山宏村清和丹客栈 60元

5.508:00-5.51

5:00 在黄山市黄山游玩7个小时 230元+60元

5.515:00-5.60

9:00 入住于黄山宏村清和丹客栈 69元

5.609:21-5.70

5:07 从黄山出发，乘K46快车（硬座）到达北京 182元

5.708:00-5.71

1:00 在八达岭长城游玩3个小时 45元+60元

5.716:55-5.80从北京出发，乘T231特快列车（硬座）到达

1:55 洛阳 106元

5.608:00-5.61

1:00 在洛阳市龙门石窟游玩3个小时 120元+60元

5.612:47-5.61从洛阳出发，乘1086列普快（硬座）返回徐

8:43 州 34元

总计：1839元

表3问题3的具体行程

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

本题与问题（3）类似，仍然是先根据贪婪法求得子集中元素个数的近似解，依据加权后每

个景点的优先级筛选优先级高的景点。用蚁群算法实现最优解。

其结果如下：

图4MATLAB运行结果

时间 事件 费用

5.109:35-5.11

0:45 从徐州出发，乘KN2904航班到达北京 550元

5.112:00-5.1145元+60元（吃饭等其他

5:00 在八达岭长城游玩3个小时 费用）

5.119:20-5.12

1:05 从北京出发，乘MU5695到达洛阳机场 787元

5.122:00-5.20

8:00 入住于洛阳东宣假日酒店 198元

5.208:00-5.21

1:00 在洛阳市龙门石窟游玩3个小时 120元+60元

5.214:53-5.22从洛阳出发，乘K128/125快车（硬座）到达

0:13 西安 55元

5.221:00-5.30

8:00 入住于西安华清豪泰商务会所 130元

5.308:00-5.31

0:00 在西安市秦始皇兵马俑处游玩2个小时 90元+60元

5.311:50-5.31从西安咸阳机场，乘MF8218航班到达武汉天

2:55 河机场 608元

5.314:00-5.31

6:00 在武汉市黄鹤楼游玩2个小时 90元+60元

5.322:20-5.32从武汉天河机场出发，乘MU2364航班到达太540元

3:40 原武宿机场

5.405:00-5.40从太原出发，乘2462/2463普快（硬座）到达

6:08 祁县 7元

5.408:00-5.41

1:00 在祁县乔家大院游玩3个小时 40元+60元

5.412:29-5.41

3:47 从祁县出发，乘1096普快（硬座）到达太原 7元

5.417:53-5.51从太原出发，乘K374/371快车（软卧）到达

2:58 常州 458元

5.514:00-5.51

8:00 在常州恐龙园游玩3个小时 160元+60元

5.600:09-5.60从常州出发，乘K76/77快车（硬座）返回徐

5:48 州 70元

表4问题4的具体行程

3.3求解多目标TSP问题

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

（1） 确定多目标TSP问题的优化模型，本题中只考虑费用与时间两个因素的优化；

（2） 给定各个目标因素的优先级。本题中，以费用为第一优先级，时间为第二优先级。

（3） 对给定的指标进行无量纲化处理，使得各个指标具有可比性。

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

D’=D/d

min

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

min

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

量，定为求解矩阵。

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

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

值为：

X=

j

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

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

图5MATLAB运行结果

具体行程如下：

时间 事件 费用

5.109:35-5.110:4从徐州出发，乘坐中国联合航空公司KN2904航班到达北

550元

5 京

5.110:45-5.113:4

在北京八达岭长城游玩3个小时 45元+60元

6

5.122:48-5.207:3

从北京出发，乘坐T25T-特快（硬座）到达青岛 116元

8

5.208:00-5.214:0100元+60

在青岛市崂山游玩6个小时

0 元

5.215:16-5.305:2从青岛出发，乘坐1112/1113普快（硬坐）到达中转站郑

123元

8 州

5.306:02-5.312:4

从中转站郑州出发，乘坐K1363K-快速（硬坐）到达西安 73元

2

5.312:24-5.314:2

4

5.318:20-5.403:3

2

5.405:00-5.406:0

8

5.408:00-5.411:0

0

5.412:29-5.413:4

7

5.418:01-5.509:4

4

5.509:44-5.511:4

4

5.518:40-5.604:2

3

在西安市秦始皇兵马俑游玩2个小时 90元+60元

从西安出发，乘坐T42T-特快（硬座）到达太原站 103元

从太原出发，乘2462/2463普快（硬座）到达祁县 7元

在祁县乔家大院游玩3小时 40+60元

从祁县出发，乘坐1096普快返回太原 7元

从太原出发，乘K520/K521K-特快（硬坐）到达武汉 150元

在武汉市黄鹤楼游玩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算法的旅游路径智能选择系统.上海：华东师范大学

[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:');

9.

D=load('D:');

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.

whileNC<=NC_max

19.

%putants

20.

Randpos=[];

51.

end

52.

%recordthebestroute

53.

L=zeros(m,1);

54.

fori=1:m

55.

R=Tabu(1,:);

56.

forj=1:(n-1)

57.

L(i)=L(i)+D(R(j),R(j+1));

58.

end

59.

L(i)=L(i)+D(R(1),R(n));

60.

end

61.

L_best(NC)=min(L);

62.

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

63.

R_best(NC,:)=Tabu(pos(1),:);

64.

L_ave(NC)=mean(L);

65.

NC=NC+1;

66.

%refresh

67.

Delta_Tau=zeros(n,n);

68.

fori=1:m;

69.

forj=1:(n-1);

70.

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i)

71.

end

九江市庐山 3289211.33

舟山市普陀山 3320681.882

江常州北京洛阳

苏中华八达市石

徐恐龙岭长门石

州 园 城 窟

0 454 473 779 775 640 687 810 631 840 528

454 0 714 1209 1198 452 738 1212 595 396 华恐龙864

473 714 0 724 947 933 956 1146 1231 1040 1029

779 1209 724 0 601 达岭长1138 1471 1599 888 1421 1328

3.各城市之间的距离

青岛山西祁黄山武汉西安市九江舟山

市崂县乔家市黄市黄秦始皇市庐市普距离

山 大院 山 鹤楼 兵马俑 山 陀山

江苏徐

州

常州中

园

青岛市

崂山

北京八

城

山西祁

县乔家775 1198 947 601 0 430 1306 931 537 1160 1578

大院

洛阳市

石门石528 864 933 888 430 0 963 604 359 817 1235

窟

黄山市

黄山

武汉市

黄鹤楼

西安市

秦始皇810 1138 537 814 1212 1231 359 1242 0 1041 1603

兵马俑

九江市

庐山

舟山市

普陀山

640 452 956 1421 1306 963 0 528 1242 298 490

687 1328 931 604 528 0 814 738 1146 243 1009

631 1471 1160 243 595 1040 817 298 1041 0 779

840 1599 1578 396 1029 1235 1603 779 0 490 1009

江北京常州洛阳

苏八达中华市石

徐岭长恐龙门石

州 城 园 窟

0 392 471 412 410 399.5 449 348 335 517 600

62 433 0 503 490 458.5 423 414 445 600 574 华恐龙

70 418 559 503 0 313.5 535 627 445 740 810

99 0 549 431 465 382 532 459 430 575 792 达岭长

4.各城市之间的最低旅行价格

青岛山西祁黄山武汉西安市九江舟山

市崂县乔家市黄市黄秦始皇市庐市普

山 大院 山 鹤楼 兵马俑 山 陀山

江苏徐

州

常州中

园

青岛市

崂山

北京八

城

山西祁

县乔家579.5 387 0 472 517 390 321 646.5

大院

洛阳市

石门石34 534 465 492 609 346 382 0 468 373 308

窟

黄山市

黄山

武汉市

黄鹤楼

西安市

秦始皇55 574 505 511 654 443 329 406 489 440 0

兵马俑

九江市

庐山

舟山市

普陀山

111365.581.

.5 5 5

99 482 525 475 527 475 455 496 0 440 419

39 514 658 500 541 443 369 442 481 0 411

87 579 650 0 554 438 439.5 440 395 379 361

140 523 690 524 0 625 474.5 527 417 390 474

西安

武汉市秦

市黄始皇

鹤楼 兵马

俑

5.各城市之间的车旅时间

江苏中华青岛市八达祁县市石黄山市九江市舟山市

徐州 恐龙崂山 岭长乔家门石黄山 庐山 普陀山

常州北京山西洛阳

园 城 大院 窟

江

苏

徐

州

常

州

中

华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

岭

长

城

山

西

祁

县

0 7.37 11.33 4.17 9.87 7.67 14.08 8.17 8.58 15.5 19.73

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

门

石

窟

黄

山

市7.08 9.92 12.33 5 9.12 12.12 0 8.1 3.83 17.7 16.58

黄

山

武

汉

市

黄

鹤

楼

西

安

市

秦

始6.58 9.75 7.83 4.75 5.2 4.33 8.83 3.17 0 12.88 10.83

皇

兵

马

俑

九

江

市8.5 10.83 11.75 5.25 10.12 14.08 16.7 5.58 7.88 0 13.62

庐

山

舟

山

市

普

陀

山

6.17 8.05 7.45 4.83 5.45 9.75 13.1 0 3.17 10.58 8.75

13.73 8.53 9 6.75 10.7 10.83 17.58 4.75 6.83 14.62 0

6.各城市之间的无量纲化整合权值

江常州北京洛阳

苏中华八达市石

徐恐龙岭长门石

州 园 城 窟

17.2217.312.6916.78江苏徐20.216.4016.432923.731.37

0 18.62

294 8882 941 765 州 8588 529 4 0588 706

5.10 20.414.2320.26521.21常州中18.316.2218.838224.421.41

青岛山西祁黄山武汉西安市九江舟山

市崂县乔家市黄市黄秦始皇市庐市普

山 大院 山 鹤楼 兵马俑 山 陀山

华恐龙9351177 529 29 412 6118 647 4 7706 235

园 29

青岛市22.4413.6212.00020.3622.019.8914.918227.526.82

崂山 118 412 59 412 6529 118 4 1471 353

北京八4.0

达岭长8170 15.33

城 65

山西祁10.

县乔家1490

大院 41

洛阳市

石门石0

窟

黄山市19.0414.153523.620.0921.715.9719.50223.70

黄山 118 3 7059 647 7118 059 35 824

武汉市13.258218.218.6619.1620.814.8513.30220.2

黄鹤楼 4 8588 177 765 0294 941 94 4706

西安市8.1

秦始皇0 976

兵马俑 47

九江市23.9123.8524.815.1320.04624.0221.314.7216.4976

庐山 412 941 6765 235 47 118 1765 706 5

舟山市19.9123.222.1321.65522.814.2218.771123.0

普陀山 235 9412 235 88 4471 059 8 3177

7.3

8880

24

17.6415.013.43514.4217.614.397019.127.04

706 0647 29 647 4706 6 6177 412

23.8220.9521.313.9211.641124.226.7113.513.58

412 235 2588 059 8 2294 471 3 235

22.817.7210.388825.525.745.622.1219.211.9218.305