C最佳旅游路线设计丁一凡-word资料(精)

安徽工程大学数学建模课程设计论文

题目：最佳旅游路线设计

姓名：

丁一凡

班级：		数学112
指导老师：		周金明
成	绩：
完成日期：		2013 年7 月3 日

摘要

本文主要研究的是如何选择最佳线路的问题。对于线路的选择，我们主要考

虑旅行中的费用及旅行时间。我们首先通过网络查找得到各景点（包括景区）之

间的距离，门票费用以及最佳逗留时间，据此将景点图简化成赋权无向图。然后

利用floyd算法得到每2个景点间的最短路径。据此，根据题目要求分别建立0-1

线性规划模型。

问题一给定了时间约束，要求花最少的钱游尽可能多的地方。据此，我们以

花费最少为目标，以时间限制及线路要求为约束，建立0-1规划模型，利用lingo

软件对模型求解。对结果进行综合分析，最后我们向王先生夫妇推荐景点数为16

的路线：乌鲁木齐-达坂城-哈密-库尔勒-楼兰-阿克苏-千佛洞-天鹅湖-伊犁-博乐-

石河子-克拉玛依-阿勒泰-昌吉-天山天池-乌鲁木齐。平均每个景点花费为73.4元，

除了吃饭以外，这对夫妇总共花费估计为4102元。

问题二要提出2条路线游完所有景点，据此，我们首先将所有景点按南北疆

分为2组。这两条路线要求交通费用最少，即总路程最少，我们以总行驶路程为

目标，以相应的条件为约束，建立0-1线性规划模型。利用lingo求解得到每组

路线所需最短时间，并求得其均衡度。然后对其进行调整，找到均衡度最好的一

种分组。我们为王先生夫妇推荐的第一个月的路线为：乌鲁木齐-昌吉-博乐-石

河子-克拉玛依-阿勒泰-额尔齐斯河-喀纳斯湖-天山天池-哈密-吐鲁番-达坂城-乌

鲁木齐，交通费用为740元。第二个月的路线为乌鲁木齐--库尔勒--楼兰--尼雅

遗址--和田--喀什--阿克苏--千佛寺--伊犁--天鹅湖--乌鲁木齐，交通费用为820元。

问题三与问题二相似，我们根据各景点之间的最短路径画出以乌鲁木齐为树

根的树形图，然后按分类原则分为三组。将模型二中的目标函数换为考察时间最

小得到模型三，分别用lingo求解得到每组最佳路线及时间。求其均衡度，然后

对其进行调整。最后，我们对该考察团设计了三条考察路线。路线一：乌鲁木齐

-博乐-伊犁-昌吉-天山天池-吐鲁番-达坂城-乌鲁木齐，考察时间为47天。路线

二：乌鲁木齐-石河子-克拉玛依-天鹅湖-千佛洞-阿克苏-尼亚遗址-和田-喀什-乌

鲁木齐，考察时间为51天。路线三：乌鲁木齐-喀纳斯湖-阿勒泰-额尔齐斯河-

库尔勒-楼兰-哈密-乌鲁木齐，考察时间为48天。

问题四中，由于参加每条路线的人数与该线路上服务能力成正比，我们认为

每个景点只在一条线路上。据此，我们根据假期时间限制以及游遍所有景点所需

时间最少，求得至少要提供4条旅游路线才能满足题意。根据分析，我们发现无

法找到这样4条路线均满足要求，因此，我们将所有景点分为5组，通过多次求

解调整，最终我们为旅行社提供了5种路线。具体结果在正文中给出。

最后，本文对模型进行了分析与评价。

关键词：最短距离均衡度0-1线性规划最佳路线

一、问题的重述

王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。

1．请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。

2．如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。

3．如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。

4．新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客， 在假设参加你们设计的各条路线的游客人数与整条路线的接待提高接待的质量。

能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。

下图是新疆主要景点分布图，各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆新疆旅游网对题。你也可以目做进一步的完善。

二、问题的分析

分析题意可知，本题的目标是寻找最佳旅游线路。便于分析，我们首先将景点进行编号，把实际地图简化为赋权无向图，即转化为图论问题。再考虑旅行中的花费，除吃饭和住宿外，主要考虑交通费用和景点的门票费。因此我们需收集各景点之间的路程、最佳逗留时间以及门票费用。

问题一要找出一条最佳旅游路线，使得夫妇在一个月的时间内花最少的钱游尽可能多的地方，这是一个最佳旅行商问题。对此，首先运用floyd算法求得各 然后我们以平均每个景点的消费额最低为目标，以时间和景景点间的最短路径，
点以及线路要求为约束，建立一个0-1线性规划模型。用lingo求解，便可得到最佳旅游路线以及其他各项信息。

问题二实际上就是要求找到2条路线，均从同一顶点出发再回到此点。这两 分组中，应尽量保证每条线路所包括的点不能重复且它们的并集应是所有景点。

组旅游时间控制在一个月内且均衡。据此，我们可以将所有景点按南北疆分为两类，然后进行调整。选定景点后，同样利用0-1线性规划求解得到最佳路线及所需时间，分别计算几种分组的时间均衡度，选取最好的一组即可。

同问题二，我们依据考察队的组数将所有景点分为问题三是多旅行商问题。

3类，尽量使各组的考察时间相等。由问题一中得到的各景点间的最短路径，画出以乌鲁木齐为起点的树形图，然后按照分类的原则，将景点分为三类，再进行调整即可。确定景点后，建立0-1线性规划模型求解。

问题四与问题三相似，我们首先利用问题一中的模型求得游玩所有景点所需最少时间，再根据五一黄金周时间限制，确定游玩路线至少应分为几条，才可以以分散游客。然后按时间均衡度和花费均衡度都尽可能好的原则将景点进行分类，再按照问题二中的模型求解，即可得所需旅游路线。

三、模型的假设

假设一：王先生夫妇旅游期间，所有的景点均正常开放。

假设二：每晚的住宿费用为100元，大巴的车费为0.15元/km。

假设三：每天的旅游时间加上行车时间不超过10个小时。

假设四：在行驶过程中，所有的道路路况一样，汽车的速度保持在75km/h。假设五：每个景点所花的钱只考虑景点门票费用。

假设六：每一种旅游路线均从乌鲁木齐出发然后回到乌鲁木齐。

假设七：考察团将所有景点均要考察到

四、符号的说明

m M m 1		总交通费用加门票费用 除吃饭外的所有消费（包括住宿费）总的交通费用 总的门票费用 第i 个景点的门票费用 每条路线总的行驶路程
m	2
c i w

c ij	若	x ij	=1，则表示从i 景点去j 景点，否则	x ij	=0
r ij	表示i 景点与j 景点之间的距离
t ij	表示从i 景点到j 景点多需的时间
	表示游客在i 景点的最佳逗留时间
t i

五、模型的建立与求解

5.1模型一

基于分析，我们首先在网上收集各旅游景点之间的路程、门票、最佳逗留时间、汽车的行驶速度以及住宿费用，具体数据见表1，并据此对地图进行了简化，如下图所示:

7额尔齐斯河
8哈纳斯湖

67068

6阿勒泰

437

9克拉玛依

2天山天池

20博乐

231	297	10石河子	21昌吉	1乌鲁木齐	3达坂城	5哈密
		109	38		4吐鲁番
19伊犁		199		600
		18天鹅湖

394

227

11库尔勒

17千佛洞

16阿克苏

243

12楼兰

427

1303

15喀什 14尼雅遗址
437

13和田

著名景点之间的连线图

我们加上了王先生夫妇特别向往的景点天池和达坂城。对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑各景点的最佳逗留时间的和。

表1：各景点最佳逗留时间及门票费用

景点编号	景点名称	逗留时间	门票费用（元）
1	乌鲁木齐	0 天	0
2	天山天池	1 天	100
3	达坂城	1 天	0
4	吐鲁番	2 天	196
5	哈密（回王陵）	1 天	20
6	阿勒泰	1 天	0
7	额尔齐斯河	2 天	0
8	喀纳斯湖	2 天	130
9	克拉玛依	1 天	0
10	石河子	1 天	0
11	库尔勒（博斯湖）	2 天	30
12	楼兰（罗布泊）	2 天	0
13	和田	1 天	0
14	尼亚遗址	1 天	50
15	喀什	3 天	80
16	阿克苏	1 天	0
17	千佛洞。库车大寺	2 天	55
18	天鹅湖	1 天	30
19	伊犁（乾隆格登碑）	4 天	30
20	博乐（怪石沟，博尔塔拉）	2 天	0
21	昌吉	1 天	0

大巴平均行驶速度：75km/h，车费为0.15/km

住宿费用：100元/晚

依题意，要找出一条最佳路线，使王先生夫妇在一个月内花最少的钱游尽可

能多的地方，这是一个优化问题。由以上加权网络图，我们可以通过floyd算法

求得任意两景点间的距离，据此画出一个完备图。基于此，我们可以建立一个0-1

线性规划模型来求解，其中包含两个相矛盾的目标，花最少的钱与游尽可能多的

地方。对此，我们的做法是先给定游玩的景点数，代入模型求得此景点数下最少

需要花费的钱和时间，选取不同的景点数便可得到不同的花费，然后经过综合比

较，选取景点数较多且花费较少的路线作为最佳路线。

旅途中总的消费除吃饭外主要考虑交通费用m1和门票费用m2，而

m 1



21 21 

r



c

，

m

2



1



21 21 

r





c



c



，则得到目标函数：

i 1 j 1

ij

ij

2

i 1 j 1

ij

i

j

m



21 21 

r





1



21 21 

r





c



c



i 1 j 1

ij

ij

2

i 1 j 1

ij

i

j

再考虑约束条件：

约束一：时间约束，游玩所有景点最佳路线的时间不能超过一个月，即300

个小时。此时间包括路上交通所消耗的时间和景点逗留时间，路上消耗的时间为

21 21 

r



t

，景点逗留的总时间为

1



21 21  i1 j1

r





i



t



，由此可得

i 1 j 1

ij

ij

2

ij

j

21 21 

r



t



1



21 21  i1 j1

r





t



t





300

i 1 j 1

ij

ij

2

ij

i

j

约束二：我们假设王先生夫妇游玩的景点数为n，一共有21个景点，为保

证数量，我们规定n=12，13。。。21，由假设可知，所选路线为1个环形，因此

21 21

rijnn12,13...,21

i1 j1

约束三：我们把所有景点连成一个圈，每个景点是圈上的一点。则，对于每

个景点，最多只有一条边进入，同样只允许最多一条边出来。并且只要有一条边

进去就有一条边出来，因此

i

r ij



j

r ij



1, , i j



1,2,...,21

i1

r ij



1

，

约束五：考虑到实际情况，所有的线路出发点均为乌鲁木齐，即

所有的线路的终点也为乌鲁木齐，即

j1

r ij



1

。

约束六：除了乌鲁木齐外，其余的景点游客至多只会游玩一次，即当

i j 

2,3,....,21

时，不会出现

r ij



r

ji



1

，因此我们可得约束：



0, , i j



2,3,....,21

r ij



r

ji

综上所述，我们可以建立如下0-1线性规划：

min

m



21 21  i1 j1

r ij



c ij



1



21 21  i1 j1

r ij





c



c



2

i

j



21 21  i1 j1

r ij



t ij



1



21 21  i1 j1

r





t i



t j





300

s t



2

ij

21 21  i1 j1

r ij



n n



12,13...,21

i

r ij



j

r ij



1, , i j



1,2,...,21

i1

r ij



1,

j1

r ij



1

r ij



r

ji



0, , i j



2,3,.... ,21

分别令n=12,13….21，求解，得到如下结果

N	每个景点的平均消费额	总时间	总费用	具体路线
12	59.1	23 天	709.6	1-21-10-9-20-19-18-16-17-11-12-3-1
13	63.5	25 天	825.7	1-3-11-12-16-17-18-19-20-10-9-6-21-1
14	68.4	26 天	958.7	1-3-11-12-16-17-18-19-20-10-9-6-2-21-1
15	73.4	28.5 天	1101.7	1-3-5-11-12-16-17-18-19-20-10-9-6-21-2-1
16	83.9	30 天	1343.1	1-2-3-4-5-11-17-16-18-19-20-10-9-8-6-21-1

分析上表，一个月内可参观的景点数最多为16个，但其平均消费额也最大为83.9，比景点数为15时的平均消费额高10.5，综合考虑，我们向王先生夫妇推荐景点数为15的旅游路线：1-3-5-11-12-16-17-18-19-20-10-9-6-21-2-1
当n=12时，王先生除吃饭外花费的钱为
=交通费用+门票费用+住宿费=709.6+3000=3709.6元

5.2模型二

据分析，我们需将所有景点分为2组，保证游完每条线路的时间不超过一个

月，且每组的时间尽量相等，即均衡度尽量小。按照实际地理情况，我们将所有景点按南北疆分为如下2组：

第一种分组：按南北疆分

第一组	8，6，7，9，2，1，21，3，4，5，10，20
第二组	19，18，11，17，16，12，15，14，13

以每条线路上所消耗的时间最少为目标，约束条件与问题一相似，建立0-1线性规划模型如下：

min

m



21 21  i1 j1

r ij



c ij



21 21  i1 j1

r ij



t ij



1



21 21  i1 j1

r





t



t





300

s t



2

ij

i

j

n n  i1 j1

r ij



n，

将所选景点重新编号为1. . n

i

r ij



j

r ij



1, , i j



1,2,...,21

i1

r ij



1,

j1

r ij



1

r ij



r

ji



0, , i j



2,3,....,21

其中的取值按所分组中景点个数确定

分别将上述分组代入模型，运用lingo软件求解，得到如下结果

交通费用	具体路线
740 元	1-12-11-10-9-6-7-8-2-5-4-3-1
820 元	1-2-3-5-4-6-7-8-10-9-1

计算上述分组的均衡度：

1		|	w (1)		w (2) |		9.7%
			max( ( ))

对上述分组如下调整
第二种分法：左调整

第一组	8，6，7，9，2，1，21，3，4，5，10
第二组	19，18，11，17，16，12，15，14，13，20