2023年苏北数学建模竞赛题解答

数学建模

题目旅游线路的优化设计

摘要

本题为经典的旅行商问题(TSP),是组合数学中一种古老而又困难的问题，它易于

描述却难以完全处理，属于NP完全问题。对于规模较小H勺旅行商问题，可以通过穷举

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

由意大利学者M.Dorigo于1992年首先提出I内蚁群系统(AntColonySystcm,ACS)是

一种新生的仿生进化算法，合用于求解复杂组合优化问题，在处理TSP问题方面获得

了较为理想的效果。在此，我们以改善的蚁群算法为基础建立数学模型来设计这些旅游

者在五一开始的路线，试图能得到某些合理H勺结论。

(1)第一问是经典的费用TSP问题。对于此问题我们套用基本蚁群算法，查找到都

市坐标以及旅游费用，并建立求解矩阵。通过MATLAB软件的模拟，求出若

干优化解，取相对最优解作为计算成果。所求得口勺路线为徐州出发一一洛阳

市龙门石窟----西安市秦兵马俑----山西祁县乔家大院----青岛市崂山一

—北京八达岭长城一一江西九江庐山一一黄山市黄山一一常州中华恐龙园

一一舟山市普陀山一一武汉市黄鹤楼一一返回徐州，合计3201元。

(2)第二问为时间TSP问题。由于时间在详细操作上日勺波动性，根据数据所得结论

将时间的TSP转化为距离TSP问题。求解出的路线为：徐州出发一一常州中

华恐龙园一一舟山市普陀山一一黄山市黄山一一九江市庐山一一武汉市黄

鹤楼----洛阳市龙门石窟----西安市泰始皇兵马俑----祁县乔家大院----

北京巾八达岭长城一一青岛巾助山一一返回徐州，总计用时11天12小时2。

分。

(3)第三问为有费用约束下的TSP问题。对于此问题运用了试探法和最小元素得到

近似解，再用基本蚁群算法进行优化。求解出的路线为：徐州一一西安一一

山西一一武汉一一黄山一一北京一一洛阳一一徐州，所花费用1839元，游

览了5个景点。

(4)第四问是在时间约束条件下H'、JTSP问题。解法与前一问类似，求解出的路线为:

徐州一一北京一一洛阳一一西安一一武汉一一祁县一一常州一一徐州，总时

长为4天21小时48分。

(5)第五问寻求综合原因优化的问题，通过计算给出评价模型，将价格和费用整合

到一种无量纲描述矩阵中。再通过试探法得出最优的方案。最佳路线为：徐

州一一北京一一青岛一一西安一一祁县一一武汉一一徐州，总时长4天21

小时23分，花费1823元。联络实际状况可知，成果是合理可行的。

关键词：旅行商问题(TSP),蚁群算法，动态分析，试探法

一、问题的重述

旅游线路H勺优化设计

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

有一位旅游爱好者打算目前的今年H勺五月一日早上8点之后出发，到全国某些著名景点

旅游，最终回到徐州。由于跟团旅游会受到若干限制，他（她）打算自己作为背包客出游。

他预选了十个省市旅游景点。

省市景点名称在景点的最短停留时间

江苏常州市恐龙园4小时

山东青岛市崂山6小时

北京八达岭长城3小时

山西祁县乔家大院3小时

河南洛阳市龙门石窟3小时

安徽黄山市黄山7小时

沏北武汉市黄鹤楼2小时

陕西西安市秦始皇兵马俑2小时

江西九江市庐山7小时

浙江舟山市普陀山6小时

假设:

（A）城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不容许包车或包机），并且车

票或机票可预订到。

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

（C）旅游费用以网上公布为准，详细包括交通费、住宿费、景点门票（第一门票）。晚上

20：（X）至次日上午7：00之间，假如在某地停留超过6小时，必须住宿，住宿费用不超

过200元/天。吃饭等其他费用60元/天。

（D）假设景点的开放时间为8:00至18:00o

问题：

根据以上规定，针对如下的几种状况，为该旅游爱好者设计详细H勺行程表，该行程表应

包括详细H勺交通信息（车次、航班号、起止时间、票价等）、宾馆地点和名称，门票费用,

在景点H勺停留时间等信息。

(1)假如时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立有关数

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

(2)假如旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立有关数

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

(3)假如这位游客准备元旅游费用，想尽量多游览景点，请建立有关数学模型并设计旅

游行程表。

(4)假如这位游客只有5天的时间，想尽量多游览景点，靖建立有关数学模型并设计旅

游行程表。

(5)假如这位游客只有5天的时间和元的旅游费用，想尽量多游览景点，请建立有关数

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

二、模型假设与符号阐明

2.1模型口勺基本假设

(1)每个景点仅通过一次。

(2)只考虑问题中提供於J11个旅游景点，不考虑其他中转地点作为TSP的需求点。

(3)为使问题一定程度上简约化，将都市与途径抽象成点与直线H勺图论问题。在

问题(2)中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距

离的ITSP替代时间的TS"不考虑绕路等特殊状况△在建模时认为两地之间来

回欧I费用时间差异可忽视。

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

括在内。

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

予考虑，忽视转站中的不合理原因。

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

（7）有关两地间距离仅作比较参照，一切以途径为准。

2.2符号阐明

符号名称

G赋权图矩阵

C图中的元素（景点）

n景点的个数

D赋权图的J描述矩阵

T访问次序集合

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

dti.titi时间3到匕”的TSP描述

m蚂蚁的总数量

k蚂蚁的编号

bi(t)t时刻位于都市if、J蚂蚁数目

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

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

p初始时刻各途径上的信息素量

g(c,L,r)寻优有向图

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

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

Q信息启发式因子

B期望启发式因子

nij(t)启发函数

P信息素挥发系数

k

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

Q蚂蚁携带时信息素量

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

Nc所记录的循环次数

N一最大循环次数

三模型的建立与求解

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

3.1.1TSP问题H勺图论论述

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

令赋权图为G=（C,L）,其中C={C,Q……CJ为节点，表达各个景点H勺集合；L={Lij|Ci,

CjEC}表达各个景点之间的途径，每两个景点间的途径1“均有有关的权值d“与之对应,

从而建立起一种。=（九）矩阵，权值可以表达距离、费用、途径等。由于题目於J有关规

定可以抽象出一种经典旅行商问题的数学模型：

n

£dti,ti+1

minL=i=1

3.1.2基本口勺蚁群算法模型

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

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

时会在途径上释放出一种特殊的信息素，当它们碰到一种还没有走过的路口时，就随机

地挑选一条途径前行，与此同步释放出与路线长度有关时信息素，途径越长，释放的激

素浓度越低，当后来H勺蚂蚁再次碰到这个路口的时候,选择激素浓度较高途径概率就会

相对较大，这样形成了一种正反馈。最优途径上的I激素浓度越来越大，而其他的途径上

激素浓度却会伴随时间的流逝而消减。这样，整个蚁群最终会找出最优途径。

用bKt）表达都市蚂蚁数目，行表达t时段途径（i,j）上日勺信息量，n表达

Zbi(t)

景点口勺个数，m为蚂蚁口勺总数量，则『4<二1

初试时刻，各条途径上信息量相等，均为P,",(0)=P。又因为蚂蚁不能反复通

过同一种都市，因此建立禁忌表(或记录未走过的途径L)tabiik(k取正整数)来记录蚂

蚁走过H勺都市，并随时间做动态调整。

被随机分散在〃个节点的机只蚂蚁同步出发，按照下面口勺概率公式逐次访问各个都

市节点：蚂蚁上以概率访问下一种节点：

，jsJk

0，，任4

在这里，有

叼表达边L(z,/)上的信息素强度。

7/g表达由节点，到节点jH勺启发函数，显然距离越长期望度越低，因此在此将％;

设为1/%。

伴随时间的推移，可能会出现两种状况：①之前各蚂蚁留下的信息素逐渐消失；

②通过多次循环后，途径上日勺残留信息素过多，沉没了期望程度对蚂蚁选择途径的影响。

为了防止这两种状况，在每一只蚂蚁完成一次循环后，我们对引入参数夕对残留的信息

素进行更新。夕为信息素H勺挥发速率，是在［0,1］间取值H勺可变量,用于控制两种信息素

内比重。

设通过X个时间单位后，蚂蚁完成一次循环，各途径上的信息素的量根据如下式

子作出调整：

金（，+X）=（1—P）%（，）+夕A金

t=l

Ar..：蚂蚁在本次循环中留在途径上口勺信息素强度。

Ar/：蚂蚁k留在途径〃7,7）上口勺信息素强度。

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

修改途径上的信息索强度，以此来引导其他蚂蚁对该途径的选择，从而到达群体协作的

目口勺，最终判断系统与否满足停止口勺条件（停止条件可以是最大口勺迭代次数，计算机运

行时间，或者是到达系统所要到达H勺数据精度等），假如条件不满足，则蚁群又重新开

始搜索途径，建立新口勺解；否则，系统将退出运行，将所得的成果输出。从上面可以看

出，蚁群优化算法H勺基本思想就是质量越好H勺解和距离越短H勺途径就越能吸引更多的蚂

蚁。蚁群正是通过这种反复记忆和学习口勺过程，得到了最短途径，即全局最优解。

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

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

3.1.3基本蚁群算法日勺算法流程

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

1.参数初始化：

令t=0；

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

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

初始化每条边(i,j)上的I信息素量£0)=c为一种常量，初始时刻j(o)二0：

初始化禁忌表tabu〉.和途径表LKO

2.设置索引号s=l,对k=l~m将蚂蚁k»、J起始都市放入禁忌表中，并反复如下步躲直至

禁忌表填充完整：

对k二l~m,运用公式计算转移暇率小，根据伪随机比例规则选择下一景点，将蚂蚁k移

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

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

4.计算每只蚂蚁的信息素增量

5.更新每条途径上的信息素量△T"(t+n)

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

7.Nc++,若Nc<N=x,返回步骤2,否则，循环结束。

图1基本蚁群算法H勺程序流程组

3.2蚁群算法H勺模型求解

3.2.1问题(1)费用TSE问题的求解

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

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

景点门票，住宿费以及餐费等。在车费的选择上在两景点拥有H勺航班，列车以及长途客

运之中选择费用最低rJ。考虑到住宿日勺不确定性，以最坏的状况假设每天都需要住宿。

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

携带的信息索量为100,初始时刻△T\(O)=O,蚂蚁数量m=ll,景点数n=ll,信息启

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

优解。

MATLAB运行成果为:

ShortestRoute=

1181695341072

Shoetest_Length=

750.5

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

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

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

山市黄山一一常州中华恐龙园一一舟山市普陀山一一武汉市黄鹤楼一一返回徐

州，反向亦可。

（2）详细行程:

时间事件费用

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

19:25洛阳

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

8:00他费用）

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

11:00

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

23:06到达西安

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

08:00

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

10:00

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

07:45太原

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

09:44

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

12:44

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

16:08回太原

5.421:36-5.5从太原出发，乘K884/K881K-迅速（硬120元

08:45座）到达青岛

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

14:45

5.520:075.6从崂山山发，乘T26T特快（硬座）到116元

05:38达北京

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

11:00

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

04:14达九江

5.708:00-5.7在九江市庐山游玩7个小时180元+607C

15:00

5.719:42-5.7从庐山出发，乘坐K13/K12K-迅速（硬41元

23:07座）到鹰潭

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

04:08到黄山

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

15:00

5.819:10-5.9从黄山出发，乘K8420/K8417K-迅速（硬73元

04:46座）到常州

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

12:00

5.922:30-5.10从常州出发,乘坐K57/K78K-迅速（硬73元

05:19座）到宁波

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

08:40

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

14:40

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

16:50

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

07:16卧）到武昌

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

10:00

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

04:13返回徐州

总计：3201元

表1问题1时详细行程

3.2.2问题（2）时间TSP问题的求解

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

可以建立一种与之对应的描述矩阵D=（4）描述。

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

TS1\根据网络上的数据可知，若选择单一-交通工具，旅途中U勺时间与旅途的长度成正

比，而在木题的状况下可以乘坐H勺航班较少，在不考虑费用H勺状况卜•，可.以近似认为选

择的交通匚具只有长途汽车与火车两种，且不一样车种和班次之间的速度差异可以忽

视。

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

位,而两两景点之间的有向线段的权值用都市之间H勺距离表达，根据某些既定的班次并

对距离做了调整（可参见附录）。

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

ShortestRoute=

2117108695431

Shortest_length=

5179

作图成果如下:

图2MATLAB运行成果

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

（1）按地埋经纬度考虑，化蚁群算法循环2UU次H勺成果下，绐旅游者提供如下相对最

优的方案：徐州出发一一常州中华恐龙园一一舟山市普陀山一一黄山市黄山一一

九江市庐山一一武汉市黄鹤楼一一洛阳市龙门石窟一一西安市秦始皇兵马俑一

一祁县乔家大院一一北京市八达岭长城一一青岛市崂山一一返回徐州，反向旅行

一样不再赘述。

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

图3旅行路线仿真模拟图

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

时间事件费用

5.1

09:35-5.1从徐州出发，乘K58/K55（硬座）到达常州70元

15:19

5.1

189元+60元（吃

15:19-5.2入住于常州福兰特连锁旅店晋陵店

饭等其他费用）

08:00

5.2

08:00-5.2在常州市恐龙园游玩4小时160元

12:00

5.2

14:40-5.2从常州出发，乘东方航空企业MU5692到达北京960元

16:25

b.2

从北京机场换乘中国南方航空股份有限企业CZ3185

19:10-5.21180元

到达宁波

21:15

5.2

21:15-5.3入住于宁波风格时尚宾馆148元

08:00

5.3

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

08:40

5.3

08:40-5.3在舟山市普陀山游玩6个小时200元+60元

14:40

5.3

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

16:50

5.3

16:50-5.4入住于宁波风格时尚宾馆148元

09:02

5.4

从宁波出发，乘K8498K-迅速（硬座），中转K硬座67

09:02-5.492元

K-迅速（硬座）到达黄山

18:25

5.4

18:25-5.5入住黄山宏村清和丹客栈60元

08:00

5.5

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

15:00

5.5

从黄山市出发，乘K70/K67（硬座），中转1586/1587普

18:28-5.692元

快（硬座）到达庐山

03:02

5.6

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

15:00

5.6

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

19:33-5.680元

口

21:46

5.6

21:46-5.7入住于武汉尚果创意酒店169元

08:00

5.7

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

10:00

5.7从武汉出发,乘中国南方航空企业CZ8189,中转杭州,

1620元

10:10-5.7转乘G52717到达洛阳

16:35

5.7

16:35-5.8入住于洛阳东宣假日酒店198元

08:00

5.8

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

11:00

5.8

从洛阳出发，乘坐K1130/KU31K-迅速（便座）到

11:01-5.855元

达西安

16:05

5.8

16:05-5.9入住于西安华消豪泰商务会所130元

08:00

5.9

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

10:00

5.9

10:50-5.9从西安出发，乘坐中国南方航空企业CZ6319到达太原310元

12:00

5.9

12:27-5.9从太原出发，乘坐2602/2603到达祁县（硬座）13元

13:41

5.9

13:41-5.9在祁县乔家大院游玩3个小时40元+60元

16:41

5.9

16:49-5.9从祁县出发，乘坐L7816（硬座）到达太原7元

18:07

5.9

18:15-5.9从太原出发，乘坐中国海南航空企业HU7371到达北京300元

19:35

5.9

19:35-5.10入住于北京新宇桥宾馆188元

08:00

5.10

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

11:00

5.10

13:45~5.10从北京出发，乘坐中国国际航空企业CA1575到达青岛651元

15:05

5.10

15:05-5.11入住于青岛海利鑫凤凰山庄180元

08:00

5.11在青圜市崂山游玩6小时100元

ua：uu-5.11

14:00

5.11

从青岛出发，乘坐山东航空股份有限企业SC4823,中

15:25-5.111390元

转徐州，乘坐中国四川航空企业3U8814到达徐州

20:20

表2问题2的详细行程

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

&2.1在约束条件下TSP问题的模型建立

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

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

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

其中：

/D11-Dln\

D=bnl…DnJ为加权描述矩阵；

zxll•••xln\

X」xnl…xmj为决策的OT矩阵

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

比必须详细问题详细分析，结合本题实际状况，寻找行之有效的算法。由于约束条件，

应该先根据权值分派每个景点的优先级，再根据优先级对TSP问题进行动态分析，选用

优先级高的景点试探满足一定条件之下的最优路线，并由蚊群算法得出固定的子集的途

径最优解。

3.2.2模型的求解

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

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

(1)改善的最小元素法

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

环：在D中找到一种最小值Dij,令x『l:；将DH勺第i列所有数据改为无穷大，假如

i=1=n,可将D口勺i行数据全部改为正无穷大。在循环过程中记录满足条件的*.和Xlj

的个数。

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

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

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

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

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

II

XK=1

(2)调整优化

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

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

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

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

ShortestRoute=

413652

Shortest_Length=

2390

图3MATLAB运行成果

对所得H勺数据进行处理，可得如下成果:

（1）详细行程:

时间事件费用

5.114:05-5.2从徐州出发,乘K1354/K1351（硬座）到达

02:05常州113元

5.2

08:00-5.2.10:090元+60元（吃饭等其

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

5.220:52-5.3从西安出发，乘2670（硬座）到达山西祁

06:19县39元

5.308:00-5.3

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

5.313:47-5.3从山西出发，乘K237/K240（硬座）到达武

21:29汉67元

5.321:19-5.4

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

5.408:00-5.4

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

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

15:02座）到达合肥112元

5.415:17-5.4从合肥出发，乘2025普快（硬座）到达黄

21:10山49元

5.421:10-5.5

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

b.5O«:UO-b.b

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

5.515:00-5.6

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

5.609:21-5.7从黄山出发，乘K46快车（硬座）到达北

05:07京182元

5.708:00-5.7

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

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

01:55达洛阳106元

5.608:00-5.6

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

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

18:43徐州34元

总计：1839元

表3问题3的详细行程

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

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

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

其成果如下:

图4MATLAB运行成果

时间事件费用

5.109:35-5.1

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

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

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

5.119:20-5.1

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

5.122:00-5.2

08:00入住于洛阳东官假日酒店198元

5.208:00-5.2

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

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

20:13达西安55元

5.221:00-5.3

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

5.308:00-5.3

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

5.311:50-5.3从西安咸阳机场,乘MF8218航班到达武汉

12:55天河机场608元

5.314:00-5.3

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

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

23:40太原武宿机场540元

5.405:00-5.4从太原出发，乘2462/2463普快（硬座〕

06:08到达祁县7元

5.408:00-5.4

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

5.412:29-5.4从祁具出发,乘1096普快（硬座）到达太

13:47原7元

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

12:58达常州458元

5.514:00-5.5

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

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

05:48徐州70元

表4问题4的详细行程

3.3求解多目标TSP问题

3.3.1多目标TSP问题H勺模型建立

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

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

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

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

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

D'=D/d.tin

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

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

纲量，定为求解矩阵。

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

元素个数。给定各个景点H勺优先级，用试探法选用可能为最优的途径。其中每个

景点的权值为：

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

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

图5MATLAB运行成果

详细行程如下:

时间事件费用

5.109:35-5.1从徐州出发，乘坐中国联合航空企业42904航班到

550元

10:45达北京

5.110:45-5.1

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

13:46

5.122:48-5.2

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

07:38

5.208:00-5.2100元+60

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

14:00元

5.215:16-5.3从吉岛出发,乘坐1112/1113普快（硬坐）到达中转

123元

05:28站郑州

5.306:02-5.3从中转站郑州出发,乘坐K1363K-迅速（硬坐）到达

73元

12:42西安

5.312:24-5.3

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

14:24

5.318:20-5.4

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

03:32

5.405:00-5.4

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

06:08

5.408:00-5.4

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

11:00

5.412:29-5.4从祁县出发，乘坐1096普快返回太原7元

13:47

5.418:01-5.5

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

09:44

5.509:44-5.5

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

11:44

5.518:40-5.6

从武汉出发，乘2614/2615普快（硬坐）返回徐州39元

04:23

总计：1823元

表5问题5的）详细行程

四模型的评价

4.1模型的长处

⑴算法表达借助了MATLAB语言，分析精度高，节省时间，简介形象;

（2）蚁群算法与遗传算法，Floyd算法相比，精确度高；

（3）给出的J方案详细，详实并且可行。

4.2模型H勺缺陷

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

（2）未详细考虑旅途中的安排与时间H勺衔接问题；

（3）蚁群算法耗时较长。

参照文献

[1]徐莉.基于改善遗传算法H勺多目标TSP问题研究M.武汉：武汉理工大学

[2]李闻.蚁群优化算法及其应用研究[D].长沙：湖南大学，.

[3]朱杰.蚁群算法处理TSP问题H勺浅析[J].上海：同济大学，；1009-3044（）22-

724-02.

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

[5]游道明，陈坚.用蚂蚁算法处理多目标TSP问题[J].上海，(10)—1808—0.

[6]燕忠，袁春伟.用蚁群优化算法求解中国旅行商问题[J].南京：东南大学.

[7]汪林林.对“货郎担问题”欧I研究.重庆:重庆邮电学院.

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

南京大学.

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

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

学.

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

[12]马良，蒋馥.多目标旅行售货员问题时蚂蚁算法求解.系统程理论方

法应用，1999；8(4)：23—27

[13]杨忠，鲍明，张阿舟.求解中国旅行商问题的新成果[J].数据采集与处理，

1993,8(3):177-184.

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

[15]许峰，杜军平.改善蚁群算法在旅游线路规划中的应用研究.北京：北京邮电大学

[16]杨志江，李国欣，张敏.管道订购与运输问题.徐州：中国矿业大学

附录

1.基本蚁群算法的MATLAB实现

2.m=ll;

3.Alpha=l;

4.Beta=5;

5.Rho=0.7;

6.NC_max=200;

7.Q=100;

8.C-load('D:\ZD.txt');

9.D=load('D:\JL.txt');

10.n=ll;

11•Eta=l./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.Lave=zeros(NCmax,1);

18whileNC<=NCmax

19

20.%putants

21.Randpos=[];

22.fori=l:(ceil(m/n));

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

24(end

25,Tabu(:,!)=(Randpos(1,1:m));

26.%completetraveling

27.forj=2:n

28.fori=l:m

29.visited=Tabu(i,l:(j-1));

30.J=zeros(1,(n-j+1));

31.P=J;

32.Jc=l;

33.fork=l:n

34.iflength(find(visited==k))==0

35.J(Jc)-k;

36.Jc=Jc-l;

37.end

38.end

39,fork=l:length(J)

40»

P(k)=(Tau(visited(end),J(k))AAlpha)*(Eta(visited(end),J(k))-Beta);

41,end

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

43%selectthenextcity

44.Pcum=cumsum(P);

45.Select=find(Pcum>=rand);

46.to_visit=J(Salect(1));

47.Tabu(i,j)=to_visit;

48.end

49.end

50.ifNC>=2

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

52.end

53.%recordthebestroute

54.L=zeros(mr1);

55.fori=l:m

56.R=Tabu(1,:);

57.forj=l:(n-1)

58.L(i)=L(i)+D(R(j),R(j+l));

59.end

60.L(i)=L(i)+D(R(l：rR(n));

61.And

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,r);

69.fori=l:m;

70.forj=l:(n-1);

71

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+