旅游线路的优化设计论文

旅游线路的优化设计

摘要

旅游一向被认为是提高人们生活质量的重要活动，如何针对旅行者的不同要求或者偏好，从而设计一条合理的旅游线路，已经成为旅游爱好者及旅游公司的关注热点。本文通过分析旅游行程安排与旅游用时及所需费用间的动态影响，以整个旅游日程安排系统为研究对象，通过Lingo求解获得可信结果。

问题一要求找出旅游10个景点在所给出的约束条件下所需的最少费用的旅游线路。对此，在传统TSP基础上，根据实际情况，把费用分为城际交通费、城内交通费、住宿费、门票费和餐饮费，确立相应的约束条件和目标函数，最终得到了最小费用为2949.5元的行程安排。

问题二实质上是在问题一的基础上将旅游费用约束改为对时间的约束。文中以旅游用时最短为优化目标，在重新建立与时间无关的约束条件，最终得到了

7.948天游览完所有旅游景点的行程安排。

问题三要求在有限费用下尽可能多的游览景点，相较于前两问，此处旅游景点的选择也成为模型的决策变量。如何合理地反映这一因素是第三问的难点。通过重新修改了TSP模型中的入度和出度条件，在问题一的基础上建立了关于旅游景点数目最多的整数规划模型，求解得到了实际旅游景点数目为7个的旅游方案，并在文中给出了具体行程安排。

问题四是在问题三的基础上将旅费约束换为时间约束。类似问题三，以游览景点数目最多为目标，建立了规划模型，并同样得出旅游景点数目为7个的旅游方案，并在文中给出了具体行程安排。

对于问题五，以问题三和问题四为基础，加入两个约束条件即旅费约束和时间约束，最终得到了实际游览景点数目为5，旅游总花费1432.5元，历时5天的结果，并在论文中给出了具体的日程安排。 该模型可以有效解决旅游线路规划问题。

关键字：旅游规划 线路优化设计 TSP模型

一、问题的重述

随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。

表1. 预选的十个省市旅游景点

假设：

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

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

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

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

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

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

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

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

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

二、问题的假设

1) 晚上20：00 至次日早晨7：00 之间，如果在某地停留超过6 小时，必须住宿；

2) 假设景点的开放时间为8:00 至18:00；

3) 假设不考虑买票困难，即随时都能买到符合规定的票； 4) 不考虑出游、交通时的意外状况； 5) 假设交通工具的班次固定不变；

6) 假设网上的宾馆住宿费用，门票费用，车费确实可信，且不因五一黄金周到来而改变；

7）忽略因自然原因及人为原因造成的交通堵塞，航班取消等可能。

三、符号与说明

其他符号在问内均有详细说明在此不再一一列出。

四、问题的分析与建模准备

本问题主要研究最佳旅游线路的设计问题。实质就是一个旅游线路设计问题。本文要求从徐州出发到各个省市的十个旅游景点，要在满足相关的约束条件之下，选择设计合理的旅游线路，达到省时经济的最佳效果是本文的目标。基于对此的研究，建立数学模型，设计出最佳旅游线路。

对于问题一，要求找出旅游10个景点在所给出的约束条件下所需的最少费用的旅游线路。我们利用散点图得出十个景点的大致位置，由于飞机费用远大于火车和城际长途客车的费用，所以在此问中略去考虑飞机作为城际交通方式的可能，根据所给的约束条件，使用Lingo编程对模型求解。得出最省钱的路径和对应的最少费用。

对于问题二，是在费用不限的条件下游览10个景点所需的最少时间。总耗时包括交通时间，景点逗留时间以及住宿时间。同问题一相似，只不过此题考虑的是时间而非费用。由于飞机要比火车以及汽车快的多，所以我们有理由相信飞机是最省时间的。没有机场的景点选择高铁代替。而在城内，为了节约时间，选择出租车作为城内交通方式是合理的。利用Lingo软件求出旅游线路。得出最省时的路径和对应的最少时间。

对于问题三，在旅游费用有限的条件下，要求游览尽可能多的景点。仍考虑用问题一的建模思想，增加题中所给旅游费用的约束条件，建立以游览景点个数为目标函数的优化模型进行求解，得出可旅游景点最多的旅游线路。

对于问题四，是在问题二的基础上进行优化，在旅游时间有限的条件下，增加题中所给旅行时间的约束条件，建立以游览景点个数为目标函数的优化模型进行求解，从而得出在得出可旅游景点最多的旅游线路。

对于问题五，是在问题三和问题四的基础上，在旅游费用和旅行时间均有限的双重条件下，要求游览尽可能多的景点。建立约束条件，再次优化旅游线路网，利用Lingo求出最佳解，可得出可旅游景点最多的旅游线路。

考虑到实际情况，经过分析之后，我们对模型行进了以下简化，以方便计算求解：

1.由于第一站肯定从徐州出发，我们假定早上8:00以后出发：Td1jkm8即

T

j1k1m

113

d1jkm

.xijkm8这一条件要求我们只需查找从徐州八点以后出发的交通方

式对应的班次。以下五个问题不在重复这一条件

2.当班次很多时，为了简化计算量我们去掉了从早上六点到中午十二点的班次让其尽量在晚上出行，另外将时间相近的车次省略。

3.如果两个城市间没有合适的火车直达，我们通过上网寻找出分时段的依靠中间站转车到达的三至五条最佳路径代替。

经过上述简化之后，我们可以通过Lingo解出结果，并根据结果建立陆相应游线路时刻表。

五、模型的建立与求解

5.1问题一：时间不限，费用最少

5.1.1模型的概述

在实际情况中，对于处于在经济水平不算很高的群体来说，比如学生，往往他们能投入的旅游资金较少，而时间确可以很充裕。问题一要求在时间不限的前提下，找出旅游完所有景点花费最少费用的旅游线路。所以从徐州旅游完10个城市回到徐州花费最少即为所求的目标函数。根据题中所给的约束条件我们建立了约束条件方程组，利用Lingo软件求解即可得出该目标函数下的最优解。 5.1.2模型的建立

设0-1矩阵x表示经过的各城市之间的线路，则

1，若选用从第i个城市到第j个城市第k种交通方式的第m个班次xijkm

0，若未选用从第i个城市到第j个城市第k种交通方式的第m个班次

考虑到每个城市前只有一个城市，则

x

i1k1mij

113

ijkm

1j1,2,,11

考虑到每个城市后只有一个城市，则

x

j1k1mij

113

ijkm

1i1,2,,11

但是，仅以上约束小件不能避免再一次遍历中产生多余一个互不连通的回

路，为此我们引入额外变量ui（i1,2,,11），附加以下充分约束条件：

uiuj11xijkm10

k1m

3

1ij11

根据题中所给的条件，将旅游费用分为五类，分别是城际交通费、城内交通费、住宿费、门票费和餐饮费。其中，城际交通费是指在不同城市之间进行旅行产生的交通费用之和；城内交通费是指在城内往返火车站、汽车站或机场与旅游景点时产生的费用之和。

（1）城际交通费：M1xijkm.Gijkm

i1j1k1m1111

3

其中， Gijkm表示从第i个城市到j个城市选用第k的第m个班次的交通费用。

根据实际情况，我们将城际交通工具分为三类，分别是飞机、火车（包括高铁和动车）、长途汽车。不同的交通方式也对应着不同的时刻表、行程时间和所需的交通费用。

由上表达式可以看出m的值，直接决定了被约束变量x的大小，而x的大小又与计算量密切相关。对于不同的i，j，k，通常对应不同的m。 而在实际的编程中矩阵的格式的要求，不同的i，j，k必须对应大小相当的m。为了减少计算时间，我应当尽量使m小。方法就是，对于班次较多的情况，我们做人工剔除，提出那些费用和时间相近的班次，使m大大减小，减少计算时间。 （2）城内交通费：M2Ni

i211

其中，Ni表示在第i城市内，去景点游玩时往返所需的交通费用。

根据实际情况，我们将城内的交通方式分为公交（包括地铁）和出租车。同样，不同的交通方式也对应着不同的行程时间和所需的交通费用。 （3）住宿费：M3Sihi

i211

其中，Si表示在第i个城市是否需要住宿，需要则Si为1，不需要则Si为0；

hi表示在在第i个城市的住宿费用。

①Si的求解：

根据题中所给条件，在第i个城市是否需要住宿的充分必要条件是晚上20：00至次日早晨7：00之间，如果在第i个城市停留超过6小时。当Tai8ti1时，即景点未开门前已可以到达景点，则游览完后，离开该城市最早的时刻为

8ti1ti2，那么根据题意知无需住宿的条件是离开该地的时间在当天8ti1ti2和次日2点之间；为当Tai8ti1时，即达到景点的时间必须在Taiti1以后，则离开城市的最早的时刻为82ti1ti2，那么根据题意知无需住宿的条件是离开该

地的时间在当天82ti1ti2和次日2点之间。所以我们建立以下关系式： 条件1：Tai[1,18ti1ti2] 条件2：Tdi123

其中，1为当Tai8ti1时，由8ti1ti2Tdi24得出Tdi的区间范围；

2为当Tai8ti1时，由Tai2ti1ti2Tdi24得出Tdi的区间范围；

3为0Tdi2。

其中，Tdi表示离开第i个城市的时刻，即Tdi

x

j1k1m11

3

113

ijkm

.Tdijkm

Tai表示到达第i个城市的时刻，即Taixjikm.Tdijkm

j1k1m

当条件一和条件二同时满足时，即Tai[1,18ti1ti2]和Tdi123同时成立，则可以得出Si0，若不满足上述条件则Si1。

②hi的求解：

hi值可根据每个城市的消费水平由网上查找给出。由于上文中我们已将一个

城市内的交通费用看成只与交通方式有关，即从相应车站（机场）到景点的来回费用只与k有关，所以为了简化计算，宾馆的位置只被设置在车站（机场）附近或者景点附近，且每个位置只选择一个价位，在要求费用最少时，选择50元/晚，在不考虑费用时，选择150元/晚。 (4)景点门票费：M4Ji

i211

其中，Ji表示在第i个城市的景点门票费用。可由网上查找给出。

(5) 餐饮费：M560

t1t2

24

其中，t1表示城域时间，即旅游完10个景点后回到徐州，途中在穿行不同城市

时所需要的交通时间。

t2表示城内时间，即旅游完10个景点后回到徐州，从各城市火车站、汽

车站或者机场到达旅游景点往返和在景点停留时间所需时间之和。

① 城际时间的求解：

城际时间：t1xijkm.tijkm

i1j1k1m1111

3

其中，tijkm表示从第i个城市到j个城市选用第k的第m个班次的交通时间。 ② 城内时间的求解： 城内时间：t2Tcni

i211

其中，Tcni

TdiTai,当TdiTai2ti1ti2(必要条件）

表示在第i个城市从火车

TT24,当TT2tt(充分条件）diaii1i2diai

站、汽车站或者机场往返旅游景点和在景点停留时间之和。

上述必要条件是不一定符合的，也有可能TcniTdiTai24，我们再根据算出实际结果进行检验。

为了简明起见，我们将旅行时划分间用下图直观表达：

问题一中要求总的旅游费用最低，则可以建立以下模型：

minMMi

i1

5

113



xijkm1j1,2,,11

i1k1m

ij113xijkm1i1,2,,11i1k1m

s.t. ij

3

uiuj11xijkm101ij11

k1m

xijkm0或1i,j1,,n

ui为实数i1,,n

5.1.3模型的求解

将以上的目标函数和约束条件通过Lingo编程求解。 对求解结果稍加分析，我们可以得到时间不限、费用最少情况下的最佳旅游线路，为了清晰可见我们把线路图在下面的地图上标出：

地图说明：上图表示的旅游线路为从徐州出发，途经青岛，北京，祁县（太原），西安，洛阳，武汉，九江，芜湖（中转），黄山，常州，宁波（中转），舟山，宣城（中转），再回到徐州。

通过求解得出的旅游线路，我们为该旅游爱好者制定了详细的旅游行程计划表，如下表所示：

时间不限、费用最少情形下的旅游行程计划表

图表说明：横轴表示从5月一号开始每一天的日期，纵轴按照每格半小时表示出该天的内的二十四小时，中间部分即为对应日期和时刻所对应的活动。为了强调起见，旅游景点的活动用灰色背景标出。该表的下方为每天对应每项活动所需费用的加和。

根据表中数据我们可以得出：

城际交通费M1xijkm.Gijkm826(元）

i1j1k1m1111

3

城内交通费M2Ni166(元）

i2

11

住宿费：M3Sihi100 （元）

i2

11

景点门票费：M4Ji1225(元）

i2

11

餐饮费：M560

t1t2

632.5(元）

24

5

所以，总旅行所需费用MMi2949.5(元）

i1

至此，我们求得了最省钱的旅游线路和对应的最少费用为2949.5元。 5.2问题二：费用不限，时间最少

问题二实质上是在问题一的基础上消除旅游费用约束，加入对时间的考虑作为优化目标，即要求我们设计合适的旅游行程表，使游客能在最短时间内遍历所有景点。同问题一相似，只不过此题考虑的是时间而非费用。由于飞机要比火车以及汽车快的多，所以我们有理由相信飞机是最省时间的。没有机场的景点选择高铁代替。而在城内，为了节约时间，选择出租车作为城内交通方式是合理的。 目标obj：总时间最小

minT(t1t2)

113



xijkm1j1,2,,11

i1k1m

ij113xijkm1i1,2,,11i1k1m

s.t. ij

3

uiuj11xijkm101ij11

k1m

xijkm0或1i,j1,,n

ui为实数i1,,n

将以上的目标函数和约束条件通过Lingo编程求解，对求解结果稍加分析，我们可以得到时间不限、费用最少情况下的最佳旅游线路，为了清晰可见我们把线路图在下面的地图上标出：

地图说明：上图表示的旅游线路为从徐州出发，途经青岛，太原(中转)，祁县，北京，西安，洛阳，郑州（中转），九江，芜湖（中转），黄山，宣城（中转），宁波，常州，再回到徐州。

可得该旅游线路和方式下的最少时间：minT(t1t2)7.948(天）

通过求解得出的旅游线路，我们为该旅游爱好者制定了详细的旅游行程计划表，如下表所示：

费用不限、时间最少情形下的旅游行程计划表

图表说明：横轴表示从5月一号开始每一天的日期，纵轴按照每格半小时表示出该天的内的二十四小时，中间部分即为对应日期和时刻所对应的活动。为了强调起见，旅游景点的活动用灰色背景标出。该表的下方为每天对应每项活动所需费

用的加和。

根据表中数据我们可以得出：

城际交通费M1xijkm.Gijkm2424(元）

i1j1k1m1111

3

城内交通费M2Ni885(元）

i2

11

住宿费：M3Sihi450 （元）

i2

11

景点门票费：M4Ji1225(元）

i2

11

餐饮费：M560

t1t2

475(元）

24

5

所以，总旅行所需费用MMi5459(元）

i1

5.3问题三：费用有限，游览景点最多

在旅游费用有限的条件下，要求游览尽可能多的景点。仍考虑用问题一的建模思想，增加题中所给旅游费用有限（小于等于2000）、从第一个城市出发回到第一个城市和每个城市的出度和入度相等的约束条件，建立以游览景点个数为目标函数的优化模型进行求解，得出可旅游景点最多的旅游线路。 目标obj：旅游景点最多

maxZxijkm

i1j1k1m1111

3

113

113

xijkmxijkm1或0i,j1,2,,111k1mi1k1miijij113113x1jkmxi1km1j1k1mi1k1m

5

s.t. Mi2000i1

3

uiuj11xijkm101ij11

k1m

xijkm0或1i,j1,,n

ui为实数i1,,n

将以上的目标函数和约束条件通过Lingo编程求解，对求解结果稍加分析，我们可以得到在总旅游资金不超过2000元情况下尽可能多游览景点的最佳旅游线路，为了清晰可见我们同样把线路图在下面的地图上标出：

地图说明：上图表示的路径为从徐州出发，途经武汉，洛阳，西安，祁县，北京，青岛，济南（中转），再回到徐州。

这样，maxZxijkm7即最多可游览7个景点。

i1j1k1m1111

3

通过求解得出的旅游线路，我们为该旅游爱好者制定了详细的旅游行程计划表，如下表所示：

费用有限、游览景点最多情形下的旅游行程计划表

图表说明：横轴表示从5月一号开始每一天的日期，纵轴按照每格半小时表示出该天的内的二十四小时，中间部分即为对应日期和时刻所对应的活动。为了强调起见，旅游景点的活动用灰色背景标出。该表的下方为每天对应每项活动所需费用的加和。

根据表中数据我们可以得出：

城际交通费M1xijkm.Gijkm698(元）

i1j1k1m1111

3

城内交通费M2Ni86(元）

i2

11

住宿费：M3Sihi（元） 0

i2

11

景点门票费：M4Ji655(元）

i2

11

餐饮费：M560

t1t2

432.5(元）

24

5

所以，总旅行所需费用MMi1871.5(元）

i1

5.4问题四：时间有限，游览景点最多

对于问题四，我们只要将问题三的中将旅费约束换为时间约束即可。 目标obj：旅游景点最多

maxZxijkm

i1j1k1m1111

3

113

113

xijkmxijkm1或0i,j1,2,,111k1mi1k1miijij113113x1jkmxi1km1j1k1mi1k1ms.t. t1t2245

3uiuj11xijkm101ij11k1mxijkm0或1i,j1,,nui为实数i1,,n

将以上的目标函数和约束条件通过Lingo编程求解，对求解结果稍加分析，我们可以得到在不超过5天情况下尽可能多游览景点的最佳旅游线路，为了清晰可见我们同样把线路图在下面的地图上标出：

地图说明：上图表示的路径为从徐州出发，途经北京，黄山，常州，上海（中转）武汉，洛阳，西安，太原（祁县），最后再回到徐州。

这样，maxZxijkm7即最多可游览7个景点。

i1j1k1m1111

3

通过求解得出的旅游线路，我们为该旅游爱好者制定了详细的旅游行程计划表，如下表所示：

时间有限、游览景点最多情形下的旅游行程计划表

图表说明：横轴表示从5月一号开始每一天的日期，纵轴按照每格半小时表示出该天的内的二十四小时，中间部分即为对应日期和时刻所对应的活动。为了强调起见，旅游景点的活动用灰色背景标出。该表的下方为每天对应每项活动所需费用的加和。

根据表中数据我们可以得出：

城际交通费M1xijkm.Gijkm3589(元）

i1j1k1m1111

3

城内交通费M2Ni525(元）

i2

11

住宿费：M3Sihi50 （元）

i2

11

景点门票费：M4Ji545(元）

i2

11

餐饮费：M560

t1t2

266(元）

24

5

所以，总旅行所需费用MMi4975(元）

i1

5.5问题五：费用和时间有限，游览景点最多

在综合考虑旅游费用和时间的情况下，建立二重约束条件，并争取在景点数相同的情况下费用开支最少。 目标obj：旅游景点最多

maxZxijkm

i1j1k1m1111

3

113

113

xijkmxijkm1或0i,j1,2,,111k1mi1k1miijij113113x1jkmxi1km1j1k1mi1k1mt1t2245s.t. 5

Mi2000i1

3



uiuj11xijkm101ij11

k1m



xijkm0或1i,j1,,n

ui为实数i1,,n

将以上的目标函数和约束条件通过Lingo编程求解，对求解结果稍加分析，我们可以得到在总旅游资金不超过2000元和总天数不超过5天情况下尽可能多

游览景点的最佳旅游线路，为了清晰可见我们同样把线路图在下面的地图上标出：

地图说明：上图表示的路径为从徐州出发，途经北京，太原（中转），祁县，西安，洛阳，武汉，合肥（中转），再回到徐州。

这样，maxZxijkm5即最多可游览5个景点。

i1j1k1m1111

3

通过求解得出的旅游线路，我们为该旅游爱好者制定了详细的旅游行程计划表，如下表所示：

费用时间均有限、游览景点最多情形下的旅游行程计划表

图表说明：横轴表示从5月一号开始每一天的日期，纵轴按照每格半小时表示出该天的内的二十四小时，中间部分即为对应日期和时刻所对应的活动。为了强调起见，旅游景点的活动用灰色背景标出。该表的下方为每天对应每项活动所需费用的加和。

根据表中数据我们可以得出：

城际交通费M1xijkm.Gijkm711(元）

i1j1k1m1111

3

城内交通费M2Ni78(元）

i2

11

住宿费：M3Sihi（元） 0

i2

11

景点门票费：M4Ji375(元）

i2

11

餐饮费：M560

t1t2

268.5(元）

24

5

所以，总旅行所需费用MMi1432.5(元）

i1

六、模型的评价与推广

6.1模型优点：

1、 考虑全面，细致，得到的结果可靠性高：模型综合考虑了交通时间、交通方式、旅游住宿、游览次序等一系列问题。

2、 所建立模型为线性，易于求解：模型形式基本统一，数组表示明确，能有很好的很系统的用lingo求解。

3、使用excel表格做出旅行线路图，使得结果直观清晰。 4、考虑到部分车次的中转站问题，使得模型更加全面。 6.2模型缺点：

1、 对数据的依赖性强，求解前需要处理大量的数据信息； 2、 由于模型建立过程中考虑过于细致，大大增加了求解难度。

3、 模型未考虑发车晚点的情况，可以通过建立了模糊线性规划和灵敏度检验等模型，进一步拓展模型的实践性。

4、对于上述2000元内需要旅游景点最多的情形，未列出所有的2000元内的可能，只是选择了在旅游景点数最大的前提下，选择价格最便宜即可。可以通过列出所有2000元内的所有可能，供不同旅游景点偏好者使用。 6.3模型的推广：

该模型可以广泛的应用于旅游线路规划问题。并且能解决多重限制条件下最

佳旅游线路设计问题。同时，模型还可以广泛应用与其他具有多重限制的条件TSP问题。本题模型的整体思想还适用于各个单独的问题，易于推广。在其他的多目标线路规划问题上，只要将本模型稍作修改即能将此类问题解决。对于限制条件更加复杂的规划问题，我们可以保持模型形式大体不变，增加限制条件来解决。

参考文献

[1] 西北工业大学数模指导委员会.数学建模简明教程. 西北工业大学出版社.2008.

[2] 肖华勇，实用数学建模与软件应用.西北工业大学出版社.2008,11. [3] 李安贵，张志宏.模糊数学及其应用.冶金工业出版社.2005,8.

附录

附录一： 省市 江苏 山东 北京 山西 河南 安徽 湖北 陕西 江西 浙江

景点名称

常州市恐龙园 青岛市崂山 八达岭长城 祁县乔家大院 洛阳市龙门石窟 黄山市黄山 武汉市黄鹤楼

西安市秦始皇兵马俑 九江市庐山 舟山市普陀山

景点门票费用

160 70 45 40 120 230 80 90 180 200

在景点的最短停留时间 4小时 6小时 3小时 3小时 3小时 7小时 2小时 2小时 7小时 6小时