旅游线路的设计

旅游线路的设计

题 目 ： 旅行线路的优化设计 摘要

本文考虑的是旅行时刻（费用）不受的情形下，如何安排旅行路线不重复且有返回的游玩完所有景点，使得费用（时刻）最少，以及费用（时刻）受或两者都受时，如何安排不重复且有返回的路线使得游玩的景点最多。

（一）对优化模型的明白得：

路线优化模型：第一我们明白本问题属于旅行路线的优化问题。为了建立模型，第一应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。

本问题要紧是解决两方面的问题：（1）、（2）两问是在时刻或旅行费用不限的情形下，游完十个景点如何样才能够做到费用最省或是时刻最省；（3）、（4）、（5）问是在旅行时刻或是旅行费用或是两者都有约束条件的情形下，如何样才能够玩更多的地点。

依照对第一方面问题的分析可知，该问题属于旅行商问题（Traveling Salesman Problem,TSP）。对旅行商问题的明白得：一位销售商从N个都市的某个都市动身，不重复的走完其余N-1个都市并回到原动身点，在所有可能路径中求出路径长度最短的一条。用图语言描述TSP：给出一个图G=（V，E），每边eE上有非负权值w(e)， 查找G的Hamilton圈C，使得C的总权W(c)w(e)最

eE(c)小。在一定程度上，各景点间的

距离与两点间的单程最省路费（单程最短时刻）是成正比的，因此把两景点的最省路（最短时刻）作为权值w(e)是可行的。

第二面要解决的问题是在费用（时刻）有或两者都有的情形的情形下观赏的景点近可能多，依照这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标

（二）综上所述，得到各种条件下的最优路线方案见表1.1：

表1.1 问题 结果 （1） 3012元 旅行路线 徐州常州市恐龙园黄山市黄山舟山市普陀山九江市庐山武汉市黄鹤楼洛阳市龙门石窟西安市秦始皇 兵马俑祁县乔家大院八达岭长城青岛市崂山徐州（2） 9.4天 徐州黄山市黄山舟山市普陀山九江市庐山青岛市崂山武汉市黄鹤楼八达岭长城洛阳市龙门石窟西安市秦始皇兵马俑祁县乔家大院常州市恐龙园徐州 （3） 1954元 7个景点 （4） 4.6天 5个景点 （5） 1201元 4.6 天 3个景点 徐州常州市恐龙园西安市秦始皇兵马俑祁县乔家大院八达岭长城青岛市崂山武汉市黄鹤楼徐州 徐州九江市庐山洛阳市龙门石窟八达岭长城西安市秦始皇兵马俑常州市恐龙园徐州徐州常州市恐龙园西安市秦始皇兵马俑八达岭长城徐州 由于不同的网站公布的信息存在一定偏差，因此该结果仅依求解时提供的

网站信息。

【关键词】多目标规划 旅行商问题 Hamilton圈 线性加权 最优化

一、问题重述

随着人们生活水平的提高，旅行逐步成为最热门的户外活动之一。在旅行的过程中，我们不仅能够感受大自然之美、放松心情，而且能够领会不同地点的文化气息、拓宽视野。

旅行者在今年五月一日8点之后从江苏徐州动身，到全国一些闻名景点旅行，最后回到徐州。由于跟团旅行会受到，旅行者打算自己背包出游。出行路途中有以下几个条件：（A）城际交通出行能够乘火车（含高铁）、长途汽车或飞机（不承诺包车或包及），同时车票或机票可预定到。（B）市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。（C）旅行费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20：:00至次日早晨7：:00之间，假如在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。（D）假设景点的开放时刻为8:00至18:00.

依照以上条件考虑到旅行者的以下需求：

1、在时刻不限的情形下，游玩全部景点，旅行费用最省；

2、在旅行费用不限的情形下，游玩全部景点，旅行时刻最短； 3、在旅行费用一定的情形下，游玩尽可能多的景点； 4、在时刻一定的情形下，游玩尽可能多的景点；

5、在时刻和旅行费用都一定的情形下，游玩尽可能多的景点。

针对以上几种情形，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、航班号、起止时刻、票价等）、宾馆地点和名称，门票费用，在景点的停留时刻等信息。

二、问题分析

2.1问题背景分析

关于人们生活水平不断提高，越来越多的人会选择在节假日游玩一下祖国的大好河山，领会一下各地的风土人情和人文气息。在旅行的时候人们往往会想，如何样才能花最少的费用、时刻游玩预订的地点，如何样设计路线才能在有限的费用、时刻内游玩更多的地点。这就需要我们建立高效有用的数学模型来解决这些问题。

2.2对题目的明白得

第一我们明白本问题属于旅行路线的优化问题。为了建立模型，第一应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。

本问题要紧是解决两方面的问题：（1）、（2）两问是在时刻或旅行费用不限的情形下，游完十个景点如何样才能够做到费用最省或是时刻最省；（3）、（4）、（5）问是在旅行时刻或是旅行费用或是两者都有约束条件的情形下，如何样才能够玩更多的地点。

第一方面

依照对第一方面问题的分析可知，问题目的在于当时刻（费用）不限的情形下求游完所有景点并回到动身地点所用的费用（时刻）的最小值。该问题属于旅行商问题（Traveling Salesman Problem,TSP）。为了建立数学模型，第一应该将各个景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：

旅行商问题：一位销售商从N个都市的某个都市动身，不重复的走完其余N-1个都市并回到原动身点，在所有可能路径中求出路径长度最短的一条。用数学语言描述TSP，即给定一组N个都市和它们两两之间的直达距离，查找一条闭合的旅程，使得每个都市刚好通过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=（V，E），每边eE上有非负权值w（e）， 查找G的Hamilton圈C，使得C的总权W(c)eE(c)w(e)最小。TSP问题是一个典型的组合

优化问题，其可能的搜索路径随着都市数目N的增加呈指数增长，属于NP完全问题。

了解了以上只是后，我们更加确定了该问题确实是旅行商问题。只是在实际的处理中，我们把两景点的最省路费（最短时刻）最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时刻）是成正比的，因此把两景点的最省路（最短时刻）作为权值w（e）是可行的。

第二方面

这一方面要解决的问题是在费用（时刻）有或两者都有的情形的情形下观赏的景点近可能多，依照这种要求可从以下方案入手：

建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标

三、模型假设

1、在旅行期间，天气晴朗，列车和航班没有延误同时准时到站，市内交通也没有显现长时刻的堵塞

2、该旅行者是成年人，不考虑学生票的问题

3、旅行者在两地旅行来回时刻和路上花的费用是相同的

四、符号约定

Xij ——路线决策变量（0—1变量） Lij ——从i地到j地的路费、路上的差不多消费和需住宿时的住宿费用（单

位：元） （i，j=12……11）

Pi ——地区景点的第一门票费用（单位：元）（i=1，2……10） Pij ——i景点和j景点的门票费用之和（单位：元）（i=1，2……10）

T ——在景点所在地区停留的时刻，包括在景点的游玩时刻和停留住宿等

时刻（单位：天）（i,j=1,2……11）

A ——每天的差不多消费60（单位：元） M ——旅行总共的消费（单位：元） S ——旅行总共的用时（单位：小时） Sij ——i景点和j景点的所用时刻之和，（单位：小时）（i=1，2……10） Tij ——从i景点到j景点的时刻，包括旅途是时刻、停留等车时刻、住宿

时刻（单位：小时）（i,j=1,2……11）

Ti ——在景点i的观光时刻（单位：小时）（i=1，2……10）

五、模型建立与求解

5.1

1、问题明白得

在时刻不受的情形下，可游玩完所有景点，要求消费总和最低。也确实是说，从徐州动身，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中总的花费最少。这一过程中我们尽量选择廉价的交通工具。

2、模型分析

我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。 为了达到旅行费用最低，交通方式的费用应采纳最低，同时应该尽量幸免住宿，因此我们采取晚上乘火车去下一个景点。现给出旅行景点门票费用，每天差不多费用（吃饭等其它费用60元），市内交通（从火车站到旅行景点的双程费用））的最低费，见表5.1.1。

表5.1.1 旅行景常州青岛八达祁县洛阳黄山武汉秦始九江舟山点 市恐市崂岭长乔家市龙市黄市黄皇兵市庐市普龙园 山 城 大院 门石山 鹤楼 马俑 山 陀山 窟 门票费160 70 50 40 80 150 50 90 180 160 用（元/人） 差不多60 60 60 60 60 60 60 60 60 60 费用 市内交29路304地铁直达81路旅行10路306102轮船通 （4路（42号车（4班车（4路路（28元） 元） 线换（20元） （26元） （12（24元） 乘元） 元） 元） 元） 一天总2241341442361141622248计费用 元 元 元 元 元 元 元 元 差不多分析，该问题属于旅行商问题，这一过程中费用最省确实是求最小路途费用的Hamilton圈。我们把两景点的最省路费最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最省路费作为权值w（e）是可行的。

① 阻碍消费的因素：

路费 919快车（30元） 140120元 元 总住宿费 费差不多消费 用 门票费

②目标函数的确定：

用Lij表示 i景点到j景点的途中花费，并引入路线决策变量Xij

1 通过i到j的路段 Xij=



0 不通过i到j的路段

用Pj表示j地区景点的第一门票费用，T表示在景点所在地区停留的时刻 则总费用，则目标函数为：

MXijPiAT

i1j1i1111110

③约束条件的确定:

由于每个景点只能有一条边出去，因此对j景点Xij之和影等于1，既：

Xij1 i=1,2......11

j111

同理，每个景点只能有一条边到里面去，因此对i景点Xij之和也应等于1，既:

Xji1 i=1,2……11

j111

应该注意的是，除了起点和终点（差不多上徐州）以外，各边不构成Hamilton圈。

3、模型建立

综上分析，建立Hamilton圈的线性规划模型：

minMXijPiAT

11111111011Xij1j1 i=1,2......11 s.t.11Xji1j1

4、模型求解

（注：上网查阅列车时刻表（ ://shike.peoplerail /），尽量保证车次是晚间发车同时到达下一个景点时不耽搁游玩，上网（ :// zhuna.cn/search/）找到了满足条件的宾馆。我们得到了从一个景点到另一个景点所需的最低费用（火车费用，在火车内行驶一天吃饭的费用和遇到需要住宿时的住宿费用），见表5.1.2。

表5.1.2 费用徐州 常州 青岛 北京 祁县 洛阳 黄山 武汉 西安 九江 舟山 (元) 徐州 0 62 130 154 179 122 159 158 159 118 176 常州 62 0 150 140 180 125 73 361 165 120 193 青岛 130 150 0 116 120 245 360 373 363 371 422 北京 154 140 116 0 94 106 182 210 210 225 493 祁县 179 180 120 94 0 184 248 379 109 337 569 洛阳 122 125 245 106 184 0 287 87 33 125 546 黄山 159 73 360 182 248 287 0 205 206 120 200 武汉 158 361 373 210 379 87 205 0 267 177 674 西安 159 165 363 210 109 33 206 267 0 207 313 九江 118 120 371 225 337 125 120 177 207 0 169 舟山 176 193 422 493 569 246 200 674 313 169 0

依照建立的模型，我们利用LINGO软件编程得到全局最优解为3012元，最佳的旅行路线如下：

徐州 常州市恐龙园 黄山市黄山 舟山市普陀山 九江市庐山 武汉市黄鹤楼 青岛市崂山

八达岭长城 祁县乔家大院 西安市秦始皇兵马俑 洛阳市龙门石窟

据此，我们为该旅行爱好者设计了详细的行程表，见表5.1.3：

表5.1.3 列车车列车起止地点 次 列车起止时刻 票价 游玩行程 徐州—>乘29路至常州市恐龙园，门票120常州 1348 5月1日 21:43—03:34 62元 元，在恐龙园大约停留9个小时 常州—>5月2日20:02—5月3黄山 K8418 日06:55 73元 乘旅行班车至黄山，门票150元， 在黄山大约停留10个小时 黄山—>5月3日20:56—5月4鹰潭 2239 日03:31 30元 鹰潭—>5月4日23:04—5月5乘船至舟山市，转乘27路公交车宁波东 K474 日06:40 77元 到达，门票160元，在普陀山大约宁波—>停留7个小时 舟山 乘船 5月5日上午 33元 舟山—>乘102路至庐山，门票180元， 宁波 乘船 5月5日下午15:00 33元 在庐山大约停留9个小时 宁波—>杭州 杭州—>九江 九江—>十堰 十堰—>武汉 武汉—>洛阳 洛阳—>西安 西安—>太原 太原—>祁县 祁县—>北京 北京—>青岛 青岛—>徐州 D3108 5月5日16:15—17:42 5月5日18:03—5月6K253 日03:47 5月6日19:15—5月7K1078 日05:43 5月7日23:45—5月8T258 日06:06 K862 1045 T42 2462 2604 T25 K70 46元 90元 53元 乘10路车到武汉黄鹤楼，门票50元 元，大约停留5个小时 5月9日00:30—09:26 87元 乘81路车至龙门石窟，门票80 元，大约停留5个小时 5月9日22:33—5月10日03:57 33元 乘306旅行专线至秦始皇兵马俑， 门票90元，大约停留6个小时 5月10日18:20—5月11日03:34 86元 乘直达车至祁县乔家大院，门票40元，大约停留4个小时 5月11日05:00—06:08 23元 5月11日13:33—5月12日04:00 94元 乘地铁2号线，再转乘919快车， 门票50元，大约停留6个小时 5月12日22:48—5月116乘304路至崂山，门票70元，在13日07:38 元 崂山内大约停留7个小时 5月13日19:10—5月13014日05:06 元 到家 （注：该行程的设置使得夜间的住宿均在火车内） 5.2

1、问题明白得

在费用不受的情形下，可游玩完所有景点，要求所用的时刻最短。也确实是说，从徐州动身，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中所用时刻最少。这一过程中我们尽量选择高速的交通工，同时将在旅行景点停留的时刻设为最短的符合要求的时刻。

2、模型分析

我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。差不多分析，该问题属于旅行商问题，这一过程中时刻最省确实是求最省时刻路线的Hamilton圈。我们把两景点的最短时刻（包括旅途中的时刻和停留、住宿的时刻）作为赋权值w（e），在此，我们把两景点间的时刻类比于旅行商问题中的路程，因此把两景点的最短时刻作为权值w（e）是可行的。

①阻碍总时刻的因素：

旅途时刻 总住宿时刻 时停留观光时刻 刻②目标函数的确定：

用Tij表示从i景点到j景点的时刻，包括旅途是时刻、停留等车时刻、住宿时刻（单位：小时）（i,j=1,2……11）

Ti表示在景点i的观光时刻（i=1，2……10） 则总时刻，既目标函数为：

STijXijTi

i1j1i1111110③约束条件的确定

由于每个景点只能有一条边出去，因此对j景点Xij之和影等于1，既：

Xij1 i=1,2......11

j111

同理，每个景点只能有一条边到里面去，因此对i景点Xij之和也应等于1，既:

Xji1 i=1,2……11

j111应该注意的是，除了起点和终点（差不多上徐州）以外，各边不构成Hamilton圈。

3、模型建立

综上分析，建立Hamilton圈的线性规划模型：

minSTijXijTi

i1j1i1111110

11Xij1j1 i=1,2......11 s.t.11Xji1j1

4、模型求解

依照网上查阅列车时刻表（ ://shike.peoplerail ），航班时刻表（ :// 17u.cn/FlightTimeResult__CZX_PEK_0_1.html）和长途汽车时刻表（ :// ctqcp /BusSchedule/tts.do），我们得到了任意两个景点之间除去游玩景点之外的最短旅行时刻，见表5.2.1。

表5.2.1 时刻徐常崂八乔龙黄黄秦庐山 普（h） 州 州山 达家门山 鹤始陀恐岭大石楼 皇山 龙长院 窟 兵园 城 马俑 徐州 0 24 24 24 29.625.724 24 24 24 24 8 5 常州24 0 17.3 17.3 17.3 17.3 17.3 17.3 10.817.73 15.5 恐龙3 园 崂山 24 17.3 0 16.3 17 19.216.3 1.75 16.213.08 14.25 5 5 八达24 17.3 16.3 0 18.51.75 13.42.17 2.83 12.75 22.8岭长8 2 3 城 乔家29.617.3 17 18.50 38 42.239.414 38 38.3 大院 8 8 5 3 龙门25.717.3 19.21.75 38 0 62 19.2 14.617．87 17 石窟 5 5 7 黄山 24 17.3 16.3 13.442.440.7 0 15.616.138 14.3 2 5 7 7 黄鹤24 17.3 1.75 2.17 39.419.2 15.60 16.3 14 14.3 楼 3 7 秦始24 10.816.22.83 14 14.616.116.3 0 38 14.3 皇兵3 5 7 7 马俑 庐山 24 17.713.012.738 17.838 14 38 0 14.63 8 5 7 7 普陀24 15.5 14.222.838.3 17 14.3 14.3 14.3 14.67 0 山 5 3 依照建立的模型，我们利用LINGO软件编程得到全局最优解为7.7天（其中在景点停留的时刻按最短时刻运算）。据分析，该游客在无车离开时能够在景点停留更多的时刻，因此此结果偏小。能够通过开往下一景点的车次时刻表，运算出该游客在景点区或车站（包括机场）停留的时刻。因此通过车次（航班）时刻表查询可得出的最短天数为9.4天。

最佳的旅行路线如下：

舟山市普陀徐州 黄山市黄九江市庐青岛市崂

山 山 山 山 武汉市黄 鹤楼

祁县乔家秦始皇兵洛阳市龙八达岭长 常州恐龙园 大院 马俑 门石窟 城 据此，我们为该旅行爱好者设计的详细行程表，见表5.2.2：

表5.2.2 起止地点 列车车次起止时刻 票价 游玩行程 住宿情形 （或航班号或汽车） 徐州—>黄K174 5月1日10：99元 乘旅行班住在黄山山 52—13:45 车到达黄假日酒店山，门票（黄山市150元，在屯溪区浣景点大约江中路4停留了9小号）118元 时 黄山—>上FM9268 5月2日580元 乘27路至5月2日晚海 22:30-23:30 普陀山，门住在上海票160元，吉泰连锁上海—>舟MU53 5月3日07：740元 在景点大酒店（闸北山 25—>08:20 约停留6小区中心北时 路1038号）108元 舟山—>上FM9426 5月3日740元 乘102路至5月3日晚海 15:40—九江，门票住在九江16:25 180元，在格林豪泰景点大约连锁酒店上海—>九FM9271 5月3日710元 停留8小时 （九江市江 19:30—长虹大道20:50 九江—>上海 上海—>青岛 FM9230 FM9271 5月4日17：45—19:05 5月4日19:30—20:50 740元 710元 乘304路至崂山，门票70元，在景点大约停留6个半小时 乘10路至武汉，在景点大约停留2小时 青岛—>武汉 C23632 5月5日15:55—18:00 1000元 武汉—>北京 CA1334 5月6日10:40—12:35 1080元 北京—>洛阳 MU5227 5月6日19:20—21:05 860元 洛阳—>西安 长途汽车 5月7日12：20—16:40 69元 西安—>北京 北京—>太原 MU5696 MU5296 5月8日10:25—11:45 5月8日13:25—14:25 860元 590元 乘地铁2号线换乘919快车到达，大约停留4小时 乘81路至5月6日晚洛阳，在景住在洛阳点大约停易家国际留3小时 青年旅舍（洛阳市中井东路329号）120元 乘306路到5月7日晚达，在景点住在西安大约停留2美宝宾馆小时 后宰门店（西安市新城区后宰门3号）138元 乘直达车5月8日晚到达乔家住在平遥大院，在景程家老院点大约停民俗宾馆留3小时 （山西晋中市平遥280号）130元 5月4日晚住在青岛人湶宾馆（青岛市南区湖南路号）120元 5月5日晚住在武汉天都时尚宾馆（武汉市汉口沿江大道17码头门楼）138元 无 太原—>祁县 祁县—>太原 太原—>北京 北京—>常州 常州—>徐州 5.3

1095 1096 MU5295 D309 K516 5月8日19:14—20:27 5月9日12:29—13:47 5月9日15:30—16:40 5月9日21:16—06:00 5月10日13:31—19:33 7元 8元 590元 县城内北大街125号）108元 乘29路至5月9日晚恐龙园，在住在动车景点大约内 停留4小时 290元 70元 到家 1、问题明白得

在游客预备了2000元旅行费的情形下，想尽可能多的游玩景点，要求游玩的景点数最多。也确实是说，从徐州动身，尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所的费用不超过2000元。在这一过程中我们不仅要考虑到景点所用的车费，还要考虑景点的门票费用，使得这两者相加起来尽可能的少。在去景点的过程中要尽量选择火车作为的交通工具。

2、模型分析

我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。差不多分析该题是已知费用的最大限度求最佳路径问题，因此要选择到下一景点总的最低费用作为去下一景点的前提条件且剩余费用要足够回到徐州。如前面模型，我们把两景点的最省路费作为赋权值w(e)，在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短路费作为权值w(e)是可行的。

①阻碍景点数的因素：

旅途坐车费用 不多于2000住宿、差不多费用 门票费用 元的费用 ② 目标函数的确定：

假设总费用未知，但满足条件（<=2000元），用M表示 用Pij表示i景点和j景点的门票费用之和，（单位：元）（i=1，2……10） 用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij

1 通过i到j的路段  Xij=

0 不通过i到j的路段

用C表示旅行的景点数目

则最多景点数，既目标函数为： C=

Xij

i1j11111③ 约束条件的确定：

由于M=车费+差不多费用+门票费，因此用函数表示为：

11111 M=LijXijPijXijA(C1)2000

2i1j1i1j1由于每个景点只能有一条边出去，因此对j景点Xij之和影等于1，既：

1111Xij1或0 i=1,2......11

j111

同理，每个景点只能有一条边到里面去，因此对i景点Xij之和也应等于1，既：

Xji1或0 i=1,2……11

j111应该注意的是，除了起点和终点（差不多上徐州）以外，各边不构成Hamilton圈。

3、模型建立

综上分析，能够建立多种回来的Hamilton圈的线性规划模型：

maxC/M

111111111MLijXijPijXij60(C1)20002i1j1i1j111 s.t.Xij1或0 i=1,2……11

j111Xji1或0j1

4、模型求解

可得满足要求的旅行路线如下：

徐州 常州恐龙园 秦始皇兵马俑 祁县乔家大院 武汉市黄鹤楼 青岛市崂山 八达岭长城

我们为该旅行爱好者设计的行程表，见表5.3.1：

表5.3.1 起止地点 列车车次 起止时刻 票价 徐州—>常1348 5月1日62元 州 21:43—5月2日03:34 游玩行程 住宿情形 乘29路至在火车内住常州市恐龙宿 园，门票常州—>西安 T52 5月2日20:53—5月3日12:24 165元 西安—>太原 太原—>祁县 祁县—>北京 T42 2462 2604 5月3日18:20—5月4日03:34 5月4日05:00—06：08 5月4日13:33—5月5日04:00 86元 23元 120元，在恐龙园大约停留9个小时 乘 306路在火车内住到达，门票宿 90元，在景点大约停留4小时 乘直达车到在车内住宿 达，门票40元，在景点大约停留4小时 乘地铁2号线，再换乘919快车，门票50元，在景点大约停留8小时 乘304路到达，门票70元，在景点大约停留7小时 乘10路车去黄鹤楼，门票50元，在景点大约停留7小时 在车内住宿 94元 北京—>青岛 T25 5月5日22:48—5月6日07:38 116元 在车内住宿 青岛—>郑州 郑州—>武汉 K208 D123 5月6日16:15—5月7日05:40 5月7日14:48—18:34 5月8日16:20—01:52 5月8日15:36—22:49 140元 68元 武汉—>邯郸 邯郸—>徐州 K522 103元 到家 5月7日晚住在武汉天都时尚宾馆（武汉市汉口沿江大道17马头门楼）105元 K233 82元

经运算，此路线的总费用为1954元（小于2000元），共玩了六个景点。

5.4

1、问题明白得

在游客只有五天能够旅行的情形下，想尽可能多的游玩景点。也确实是说，从徐州动身，在仅有的时刻内尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车、等车行程中所用的时刻，还要考虑到在景点停留的时刻，要使得这两者相加起来尽可能的少。因此再在去景点的过程中要尽量选择飞机作为交通工具，且尽量减少转机（转车）次数。

2、模型分析

我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。差不多分析该题是已知确定的时刻求解最佳路径问题，因此要考虑到在时刻最充分利用的前提下五天之内回到徐州。如前面模型，我们把两景点的最省时刻作为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短时刻作为权值w（e）是可行的。

①阻碍景点数的因素：

坐车（飞机）、转

车（转机）时刻

不 多 于旅社住宿时刻 五

天

的 时刻

旅行景点观赏停 留时刻

②目标函数的确定：

假设游玩的天数未知，用S表示，但满足条件（<=120小时） 用Sij表示i景点和j景点的所用时刻之和，（单位：小时）（i=1，2……10） 用Tij表示从i景点到j景点的时刻，（单位：小时）（i,j=1,2……11） 并引入路线决策变量Xij

1 通过i到j的路段  Xij=

0 不通过i到j的路段

洛阳市龙门石窟 用C表示旅行的景点数目

则最多景点数，既目标函数为： C=

Xij

i1j11111③约束条件的确定：

由于S=等车、转车时刻+住宿时刻+景点停留时刻，因此用函数表示为：

11111 S=TijXijSijXij120

2i1j1i1j1由于每个景点只能有一条边出去，因此对j景点Xij之和影等于1，既：

1111Xij1或0 i=1,2......11

j111

同理，每个景点只能有一条边到里面去，因此对i景点Xij之和也应等于1，既：

Xji1或0 i=1,2……11

j111应该注意的是，除了起点和终点（差不多上徐州）以外，各边不构成Hamilton圈。

3、模型建立

综上分析，能够建立多种回来的Hamilton圈的线性规划模型：

maxC/S

111111111STijXijSijXij1202i1j1i1j111 s.t.Xij1或0 i=1,2……11

j111Xji1或0j1

4、模型求解

可得满足要求的旅行路线如下：

徐州 九江市庐山 洛阳市龙门石常州市恐龙园 秦始皇兵马俑 八达岭长城

我们为该旅行爱好者设计的行程表，见表5.4.1：

表5.4.1 起止地点 列车车次或起止时刻 票价 飞机航班 徐州—>九K614 5月1日58元 江 21:06—5月2日07:07 九江—>南D6377 5月2日42元 昌 17:18—18:13 南昌—洛阳 K790 5月2日130元 19:07—5月3日09:26 洛阳—>北K270 5月3日19：106元 京 28—5月4日05:57 游玩行程 住宿情形 乘102路到在车内住宿 达庐山，在景点大约停留8小时 乘81路到在车内住宿 龙门石窟，在景点大约停留4小时 北京—>西安 CA1223 5月4日12:30—14:25 5月4日17:20—5月5日11:39 1050元 西安—>常州 K378 165元 常州—>徐州 5月5日70元 17:39—22:13 从图中可知该旅客5月5日24时之前差不多到家，总共玩了五处景点。 T138 乘地铁2号在车内住宿 线，再转乘919快车，在景点大约停留3小时 乘306旅行无住宿 专线到达，在景点大约停留2小时 乘29路车在车内住宿 到达恐龙园，在景点大约停留5小时 到家 5.5

1、问题明白得

基于对三、四问题的分析下，在游客只有五天时刻和2000元费用能够旅行的情形下，想尽可能多的游玩景点。也确实是说，从徐州动身，在仅有的时刻和有限的经费内尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车、等车行程中所用的时刻和费用，还要考虑到在景点停留的时刻和门票费，要使得这两者相加起来尽可能的少。因此要综合考虑三、四两种情形。 2、模型分析

我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。差不多分析该题是已知时刻和费用制约的前提下求解最佳路径问题，因此要考虑到能充分利用五天时刻和2000元费用回到徐州。在时刻和费用都有约束的条件下，选择一个作为约束条件，减少目标规划。

②目标函数的确定：

假设总费用未知，用M表示，但满足条件（<=2000元）

假设游玩的天数未知，用S表示，但满足条件（<=120小时） 用Pij表示i景点和j景点的门票费用之和，（单位：元）（i=1，2……10） 用Sij表示i景点和j景点的所用时刻之和，（单位：小时）（i=1，2……10） 用Tij表示从i景点到j景点的时刻，（单位：小时）（i,j=1,2……11） 并引入路线决策变量Xij

Xij=

0 不通过i到j的路段

用C表示旅行的景点数目 则最多景点数，既

目标函数一：

1 通过i到j的路段

C=

目标函数二：

Xij

i1j1111111111M=LijXijPijXijA(C1)

2i1j1i1j1④ 约束条件的确定：

由于S=等车、转车时刻+住宿时刻+景点停留时刻，因此用函数表示为：

111111111 S=TijXijSijXij120

2i1j1i1j1由于每个景点只能有一条边出去，因此对j景点Xij之和影等于1，既：

1111

Xij1或0 i=1,2......11

j111

同理，每个景点只能有一条边到里面去，因此对i景点Xij之和也应等于1，既：

Xji1或0 i=1,2……11

j111应该注意的是，除了起点和终点（差不多上徐州）以外，各边不构成Hamilton圈。

3、模型建立

综上分析，能够建立多种回来的Hamilton圈的线性规划模型：

maxC/M（目标函数一）

111111111 M=LijXijPijXij60(C1)（目标函数二）

2i1j1i1j1111111111STijXij2SijXij120i1j1i1j111Xij1或0s.t.j1 i=1,2……11 11Xji1或0j1M2000 4、模型求解

可得满足要求的旅行路线如下：

徐州 常州市恐龙园 八达岭长城

西安市秦始皇兵马俑

我们为该旅行爱好者设计的行程表，见表5.5.1：

起止地点 列车车次或飞机航班 徐州->常州 1230 表5.5 .1 起止时刻 票价 5月2日10:09—15:57 160元 游玩行程 乘29路至常州市恐龙园，门票120元，在恐龙园大约停留6个小时 乘 306路到达，门票90元，在景点大约停留4小时 乘地铁2号线，再换乘919快车，门票50元，在景点大约停留8小时 到家 住宿情形 5月1日晚住在常州蓝色快舟营销人连锁店（常州市 博爱路50号）120元 无住宿 常州—>西安 K360 5月3日14:25—09:20 90元 西安—>北京 T42 5月4日18:20—09:02 150元 在车内住宿 北京—>徐T31 5月5日15：106元 州 39—23:05 由表格可知总共用时4.6天，共花费金额为1201元。

六、模型评判

（1） 问题一、二建立了单目标的优化模型，将各景点的路线转化为纯数学形式的点线集合，进行了图论方面的分析，同时通过适当的线性加权，还将各景点的门票、每天的差不多费用和市内交通费用考虑在内，增加了模型的有用性。 （2） 问题三、四和五则有了条件的约束，在问题一、二模型的基础上，增加了该旅行者对旅行路线意向的考虑，变成不目标优化问题，求解比较复杂，因此模型中通过拟合或先行加权把多目标优化转化为较简单的单目标优化，求得了合适的旅行路线，比问题一、二的模型更能适用于实际生活。

（3）在建立费用最少模型时，我们把两景点间的交通费用、住宿费用、每天的差不多费用和门票费用作为边i到j的赋权值；在建立时刻最短模型时我们把两景点间的旅行费用作为边i到j的赋权值，分别构成了有向赋权图，巧妙地将原问题转化为图论的旅行商问题。 （4）本题所建立的数学模型是在LINGO环境下进行的。LINGO软件是一个利用线性和非线性最优化方法将复杂的大型规划问题转化为简明公式的工具，具有简单有用的特点。在本题中，通过LINGO建立并求解了最优化模型，从而在可行解中得到了最佳结果。

七、模型推广与应用

专门多的游客往往会因为没有安排好合理的路线而玩不尽兴，专门在经费和时刻有的条件下不能去更多的景点观赏更美得风景，这就要我们制定合理的路线，满足自己的旅行需求，玩到更多的景点。

关于学生、工薪阶层来讲，费用因素在旅行中占有较大的比重，因此要选择合适的省钱路线旅行。

关于领导阶层而言，时刻因素在旅行中占有专门大比重，因此要选择合理的省时路线旅行。

旅行线路的优化设计，不仅在省时、省钱方面做到最优考虑，而且为在时刻，金钱方面有制约的设计旅行线路最优化和最大化。真正是站在旅行者角度摸索问题，为旅行者设计最合适最经济最省时的旅行线路。

八、参考文献

[1] 张宏伟，牛志广，《LINGO8.0及其在环境系统优化中的应用》，天津大学出版社，2005年

[2] 梗素云，屈婉玲，张立昂，《离散数学》（第四版），清华大学出版社，2018年

[3]姜启源，谢金星，叶俊，《数学模型》（第三版），高等教育出版社， 2005年

[4] 王庚，王敏生，《现代数学建模方法》，科学出版社，2018年

附录：

题（1）代码： model: sets:

cities/1..11/:level; !level(i)=the level of city; link(cities,cities):money,x; endsets

data:!money matrix,it need not be symmetirc; money=0 62 130 154 179 122 159 158 159 118 176 62 0 150 140 180 125 73 361 165 120 193 130 150 0 116 120 245 360 373 363 371 422 154 140 116 0 94 106 182 210 210 225 493 179 180 120 94 0 184 248 379 109 337 569 122 125 245 106 184 0 287 87 33 125 546 159 73 360 182 248 287 0 205 206 120 200 158 361 373 210 379 87 205 0 267 177 674 159 165 363 210 109 33 206 267 0 207 313 118 120 371 225 337 125 120 177 207 0 169 176 193 422 493 569 546 200 674 313 169 0;

enddata

n=@size(cities); !the model size;

p=160+ 70+ 50+ 40+ 80+ 150+ 50+ 90+ 180+ 160; g=4+4+30+20+4+26+4+12+24+28; T=60*10;

min=@sum(link(i,j)|i#ne#j:money(i,j)*x(i,j))+p+T+g; @for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))=1; @sum(cities(j)|j#ne#i:x(i,j))=1; @for(cities(j)|j#gt#1#and#j#ne#i:

level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i); ); );

@for(link:@bin(x)); @for(cities(i)|i#gt#1:

level(i)<=n-1-(n-2)*x(1,i); level(i)>=1+(n-2)*x(i,1); ); End

题（2）代码： model: sets:

cities/1..11/:level; !level(i)=the level of city;

link(cities,cities):time,x; endsets data:

time=0 24 24 24 29.68 25.75 24 24 24 24 24

24 0 17.3 17.3 17.3 17.3 17.3 17.3 10.83 17.73 15.5 24 17.3 0 16.3 17 19.25 16.3 1.75 16.25 13.08 14.25 24 17.3 16.3 0 18.58 1.75 13.42 2.17 1.83 12.75 22.83 29.68 17.3 17 18.58 0 38 42.45 39.43 14 38 38.3 25.75 17.3 19.25 1.75 38 0 40.7 19.2 14.67 17.87 17 24 17.3 16.3 13.42 42.45 40.7 0 15.67 16.17 38 14.3 24 17.3 1.75 2.17 39.43 19.2 15.67 0 16.3 14 14.3 24 10.83 16.25 2.83 14 14.67 16.17 16.3 0 38 14.3 24 17.73 13.08 12.75 38 17.87 38 14 38 0 14.67

24 15.5 14.25 22.83 38.3 17 14.3 14.3 14.3 14.67 0;

enddata

n=@size(cities); !the model size;

T=4+6+3+3+3+7+2+2+7+6;

min=@sum(link(i,j)|i#ne#j:time(i,j)*x(i,j))+T; @for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))=1; @sum(cities(j)|j#ne#i:x(i,j))=1; @for(cities(j)|j#gt#1#and#j#ne#i:

level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i); ); );

@for(link:@bin(x)); @for(cities(i)|i#gt#1:

level(i)<=n-1-(n-2)*x(1,i); level(i)>=1+(n-2)*x(i,1); ); End

题（3）代码： model: sets:

cities/1..11/:level; !level(i)=the level of city; link(cities,cities):money,x,p; endsets

data:!money matrix,it need not be symmetirc; money=0 62 130 154 179 122 159 158 159 118 176 62 0 150 140 180 125 73 361 165 120 193

130 150 0 116 120 245 360 373 363 371 422 154 140 116 0 94 106 182 210 210 225 493 179 180 120 94 0 184 248 379 109 337 569 122 125 245 106 184 0 287 87 33 125 546 159 73 360 182 248 287 0 205 206 120 200 158 361 373 210 379 87 205 0 267 177 674 159 165 363 210 109 33 206 267 0 207 313 118 120 371 225 337 125 120 177 207 0 169 176 193 422 493 569 546 200 674 313 169 0; p=0 160 70 50 40 80 150 50 90 180 160

160 0 230 210 200 240 310 210 250 340 320 70 230 0 120 110 150 220 120 160 250 230 50 210 120 0 90 130 200 100 140 230 210 40 200 110 90 0 120 190 90 130 220 200 80 240 150 130 120 0 230 130 170 260 240 150 310 220 200 190 230 0 200 240 330 310 50 210 120 100 90 130 200 0 140 230 210 90 250 160 140 130 170 240 140 0 210 250 180 340 250 230 220 260 330 230 210 0 340 160 320 230 210 200 240 310 210 250 340 0;

enddata

n=@size(cities); !the model size;

m=@sum(link(i,j)|i#ne#j:money(i,j)*x(i,j))+a+f; a=@sum(link(i,j)|i#ne#j:p(i,j)*x(i,j))/2;

f=c*60;

c=@sum(link(i,j)|i#ne#j:x(i,j)); max=c/m; m=2000;

@for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))<=1; @sum(cities(j)|j#ne#i:x(i,j))<=1; @for(cities(j)|j#gt#1#and#j#ne#i:

level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i); ); );

@for(link:@bin(x)); @for(cities(i)|i#gt#1:

level(i)<=n-1-(n-2)*x(1,i);

level(i)>=1+(n-2)*x(i,1); ); End

题（4）代码： model: sets:

cities/1..11/:level; !level(i)=the level of city; link(cities,cities):time,x,s; endsets data:

time=0 24 24 24 29.68 25.75 24 24 24 24 24

24 0 17.3 17.3 17.3 17.3 17.3 17.3 10.83 17.73 15.5 24 17.3 0 16.3 17 19.25 16.3 1.75 16.25 13.08 14.25 24 17.3 16.3 0 18.58 1.75 13.42 2.17 1.83 12.75 22.83 29.68 17.3 17 18.58 0 38 42.45 39.43 14 38 38.3 25.75 17.3 19.25 1.75 38 0 40.7 19.2 14.67 17.87 17 24 17.3 16.3 13.42 42.45 40.7 0 15.67 16.17 38 14.3 24 17.3 1.75 2.17 39.43 19.2 15.67 0 16.3 14 14.3 24 10.83 16.25 2.83 14 14.67 16.17 16.3 0 38 14.3 24 17.73 13.08 12.75 38 17.87 38 14 38 0 14.67

24 15.5 14.25 22.83 38.3 17 14.3 14.3 14.3 14.67 0;

s=0 4 6 3 3 3 7 2 2 7 6 4 8 10 7 7 7 11 6 6 11 10 6 10 12 9 9 9 13 8 8 13 12 3 7 9 6 6 6 10 5 5 10 9 3 7 9 6 6 6 10 5 5 10 9 3 7 9 6 6 6 10 5 5 10 9

7 11 13 10 10 10 14 9 9 14 13 2 6 8 5 5 5 9 4 4 9 8 2 6 8 5 5 5 9 4 4 9 8

7 11 13 10 10 10 14 9 9 14 13 6 10 12 9 9 9 13 8 8 13 12;

enddata

n=@size(cities); !the model size; max=c/m;

c=@sum(link(i,j)|i#ne#j:x(i,j));

m=@sum(link(i,j)|i#ne#j:time(i,j)*x(i,j))+a; a=@sum(link(i,j)|i#ne#j:s(i,j)*x(i,j))/2; m=24*5;

@for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))<=1;

@sum(cities(j)|j#ne#i:x(i,j))<=1; @for(cities(j)|j#gt#1#and#j#ne#i:

level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i); ); );

@for(link:@bin(x)); @for(cities(i)|i#gt#1:

level(i)<=n-1-(n-2)*x(1,i); level(i)>=1+(n-2)*x(i,1); ); End

题（5）代码： model: sets:

cities/1..11/:level; !level(i)=the level of city; link(cities,cities):money,time,p,s,x; endsets data:

money=0 62 130 154 179 122 159 158 159 118 176 62 0 150 140 180 125 73 361 165 120 193 130 150 0 116 120 245 360 373 363 371 422 154 140 116 0 94 106 182 210 210 225 493 179 180 120 94 0 184 248 379 109 337 569 122 125 245 106 184 0 287 87 33 125 546 159 73 360 182 248 287 0 205 206 120 200 158 361 373 210 379 87 205 0 267 177 674 159 165 363 210 109 33 206 267 0 207 313 118 120 371 225 337 125 120 177 207 0 169 176 193 422 493 569 546 200 674 313 169 0; p=0 160 70 50 40 80 150 50 90 180 160

160 0 230 210 200 240 310 210 250 340 320 70 230 0 120 110 150 220 120 160 250 230 50 210 120 0 90 130 200 100 140 230 210 40 200 110 90 0 120 190 90 130 220 200 80 240 150 130 120 0 230 130 170 260 240 150 310 220 200 190 230 0 200 240 330 310 50 210 120 100 90 130 200 0 140 230 210 90 250 160 140 130 170 240 140 0 210 250 180 340 250 230 220 260 330 230 210 0 340 160 320 230 210 200 240 310 210 250 340 0; time=0 24 24 24 29.68 25.75 24 24 24 24 24

24 0 17.3 17.3 17.3 17.3 17.3 17.3 10.83 17.73 15.5 24 17.3 0 16.3 17 19.25 16.3 1.75 16.25 13.08 14.25 24 17.3 16.3 0 18.58 1.75 13.42 2.17 1.83 12.75 22.83

29.68 17.3 17 18.58 0 38 42.45 39.43 14 38 38.3 25.75 17.3 19.25 1.75 38 0 40.7 19.2 14.67 17.87 17 24 17.3 16.3 13.42 42.45 40.7 0 15.67 16.17 38 14.3 24 17.3 1.75 2.17 39.43 19.2 15.67 0 16.3 14 14.3 24 10.83 16.25 2.83 14 14.67 16.17 16.3 0 38 14.3 24 17.73 13.08 12.75 38 17.87 38 14 38 0 14.67

24 15.5 14.25 22.83 38.3 17 14.3 14.3 14.3 14.67 0;

s=0 4 6 3 3 3 7 2 2 7 6 4 8 10 7 7 7 11 6 6 11 10 6 10 12 9 9 9 13 8 8 13 12 3 7 9 6 6 6 10 5 5 10 9 3 7 9 6 6 6 10 5 5 10 9 3 7 9 6 6 6 10 5 5 10 9

7 11 13 10 10 10 14 9 9 14 13 2 6 8 5 5 5 9 4 4 9 8 2 6 8 5 5 5 9 4 4 9 8

7 11 13 10 10 10 14 9 9 14 13 6 10 12 9 9 9 13 8 8 13 12;

enddata

n=@size(cities); !the model size;

m1=@sum(link(i,j)|i#ne#j:money(i,j)*x(i,j))+a+f; a=@sum(link(i,j)|i#ne#j:p(i,j)*x(i,j))/2; m1=2000; f=c*60;

m2=@sum(link(i,j)|i#ne#j:time(i,j)*x(i,j))+b; b=@sum(link(i,j)|i#ne#j:s(i,j)*x(i,j))/2; m2=24*5;

c=@sum(link(i,j)|i#ne#j:x(i,j)); max=c/m1;

@for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))<=1; @sum(cities(j)|j#ne#i:x(i,j))<=1; @for(cities(j)|j#gt#1#and#j#ne#i:

level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i); ); );

@for(link:@bin(x)); @for(cities(i)|i#gt#1:

level(i)<=n-1-(n-2)*x(1,i);

level(i)>=1+(n-2)*x(i,1); ); End