改进TSP模型在最优旅游路线规划中的应用

（河海大学a.水利水电学院；b.大禹学院，南京210098）

根据已有的摘要：现讨论了风景区游览最优路线规划问题，

TSP模型，结合实际游览情况（如排队等时）提出了多时间约束条件下的改进TSP模型，并结合实际生活中可能遇到的更多情况进行了合理的分析和适当的模型推广。

最优路径规划关键词：TSP模型；多时间条件约束；

中图分类号：F590文献标识码：Ａ文章编号：1005-913X（2018）09-0158-03

旅行商问题（TSP，TravelingSalesmanProblem）

是数学领域又称为旅行推销员问题、货郎担问题，

中著名问题之一。该问题假设有一个旅行商人要拜访n个城市，从初始城市出发依次拜访每个城市，且每个城市仅能拜访一次，最终回到出发点。TSP问题是在所有可能的路线中选择行程最短的路径。TSP问题具有广泛的应用背景，是组合优化领域研究的热点。传统的TSP问题的核心约束是1个旅行

（如旅行商人，而现实中更多体现为多个旅行商人

因团体）对特定景点或旅行线路的旅行规划问题，

此，有必要对传统的TSP问题进行改进。

一、复杂多时间约束改进TSP问题

假设有m个旅行团，在12为了便于分析问题，

且要点同时从A地点出发，以某个步行速度行进，

求这几个旅行团在17点前到达B地点，并且途中

后到的团每个景点同时只能容纳1个旅游团游览，

为使m个旅游团游览完景区中所要等待先到的团，

应如何设计路线。有景点且等待总时间最短，

与传统该问题是一种连续型多相关变量问题，

TSP模型相比，变量数增加至m个，另有重要约束条件，m个旅游团不可同时参观，即每个景点只能

问题需要求解m个旅游团分别能容纳一个旅游团，

游览完全部n个景点且游览总时间最长的游览路

而它们的参观路线线。同时，m个旅游团共同参观，

各不相同，这就需要我们分别设计它们的路线。

考察该问题，这是一个拥有m个非完全的变量，并且在到达和游览时间约束之外另行增加了等待时间变量，我们将用增加的约束方程来仔细阐述以上观点。

收稿日期：2018-08-27

图1复杂多时间约束的改进TSP模型

（一）假设前提第一，所有游客均游览完所有景点且不重复游览并全部到达湿地商业街。

不存第二，所有游客均按园区规划道路行走，

在抄近道的情况，实际路程与预计路程一致。

第三，景区中各景点均相互连通，游玩各景点之间相互。

第四，所有游客游览时间在预计游览时间范围

不存在等待内，进入景点的时间均在开放时间内，

插队情况。

第五，雨、雪等恶劣天气情况下对参观的影响不在考虑范围之内。

（二）问题求解如前所述，该问题是一类多变量多时间约束的

为了得到m个旅游团游览改进TSP问题，类似的，

建立游览时间完全部景点且游览时间最长的结果，

（2）内求和为m个旅函数，构造式（1）和式。其中，

外求和为游览完所游团游览一个景点的时间总和，

并且要求等待时有景点时间求和，函数取最大值，

间最短，从而得到游览时间最长的结果。

（1）……………………（2）……………………

对原TSP问题中已经引入多次的路径选择情

根据题意，况方程进行拓展，m个旅游团同时行动，

得式（3）与即增加变量R，R=1，2，3,……，m。由此，

式（4）。

基金项目：江苏高校品牌专业建设工程资助项目”（英文标志：Top-notchAcademicProgramsProjectofJiangsuHigherEducation

Institutions，英文标志简称：TAPP）

研究方向：水利水电工程；作者简介：王治力(1998-)，男，哈尔滨人，本科学生，陈秋同(1997-)，男，江苏滨海人，本科学生，研究

工程力学。方向：水利水电工程；王俊杰(1999-)，男，河北邯郸人，本科学生，研究方向：

158北方经贸移X=1

７i≠j７ij

i，j=1，2，…，7R=1，……，m……（3）i，j=1，2，…，7R=1，……，m……（4）

此差值它们到达某景点的时间之间应该存在差值，

数学表达式即为不小于游览时间，

………………………………（8）

二、改进模型的实际应用

以某旅行社在设计安略湖风景区的旅行路线

在12点同时时考虑如下问题。如果有三个旅游团，

从景石出发，步行速度为2km/h，且要求三个旅行团在17点前到达湿地商业街，并且途中每个景点同时只能容纳一个旅游团游览，后到的团要等待先到

为使三个旅游团游览完景区中所有景点且等的团，

待总时间最短，应如何设计路线。表1是各景点之

（单位：间最短步行距离m），表2是游览各景点所需

时间。

单位：m

湿地博物馆湿地商业街500

2005804503604600190

69039077005506501900

4752856652655150460650

R旅游团离开某景点的时间等于其到达时间、

此式中包含了新增的时等待时间、游览时间的和，

间约束，等待时间，总时间变成

……………………………（5）

（6）此外根据到达时间约束构造出式

（6）……………………

模型中有关游览时间的约束

……………………………………（7）

所以由于m个旅游团不能同时参观一个景点，

移X=1

i≠j

ji

表1景点之间的最短步行距离

距离景石

游客服务中心阳光草坪森林小剧场儿童科普体验区儿童戏水场湿地博物馆湿地商业街

景石0300360210530475500690

游客服务中心3000380270230285200390

阳光草坪3603800510230665580770

森林小剧场21027051004702654500

儿童科普体验区儿童戏水场5302302304700515360550

表3各旅行团旅行时间规划结果

第1旅游团景点其他参量第2旅游团第3旅游团（停（停（停游览时间游览时间游览时间单位离开时间点达到时间点留时间，单位离开时间点达到时间点留时间，单位离开时间点达到时间点留时间，分钟）分钟）分钟）12:0014:2212:1115:0013:1815:3816:1216:476020367030603057203043分钟分钟分钟12:0014:5213:1115:3014:1515:5816:4217:3012:0013:5212:1114:3012:5815:0815:4216:1703040304720307360分钟233分钟37分钟12:0014:2212:5115:0013:4515:2816:1217:3012:0013:2212:1114:0012:3814:3815:1215:47030203037203010360分钟270分钟0分钟12:0013:5212:3114:3013:1514:5815:4217:30景石游客服务中心阳光草坪森林小剧场儿童科普体验区儿童戏水场湿地博物馆湿地商业街总步行时间总游览时间总等待时间表2各景点游览时间

景点时间游览时间10-30分钟20-60分钟开放时间9:00-16:009:00-17:009:00,9:30,10:00,10:30,11:00,11:30,森林小剧场30分钟12:00,12:30,13:00,13:30,14:00,14:30,15:00,15:30,16:00,16:30,17:00(半点和整点开放)儿童科普体验区30-60分钟儿童戏水场湿地博物馆湿地商业街20-60分钟30-60分钟30分钟以上9:00-17:009:00-17:009:00-17:009:00-21:30游客服务中心阳光草坪三、模型的拓展讨论

即在TSP基本复杂多时间约束改进TSP问题，

模型基础上进行的多约束条件改进。在原TSP模型

仅考虑游客来往于中，忽略了游览中复杂的情况，

以此作为路景点间的路程，寻找其中的最短路程，

实际生活径选择的依据。显然，无论在何种情况下，

中都不会与此模型相符的情况，原模型可以看做单因素下风景区游览最优路线规划模型最简单的应

现增加了实际生活中存在用实例，不具有实用性，

的等待情况进行了部分改进。但仍有一些不合实际的情况，对此我们增加了一些新的约束条件。

一是假设三个旅游团的步行速度可以在1km/h

159NORTHERNECONOMYANDTRADE到3km/h之间调节，但是总的平均步行速度不能超过2km/h。本假设的解决可以从介值定理的角度来

旅对这个问题进行分析。反映在时间函数上来说，

肯定介于最快的速度和最游团在行进过程中速度，

慢的速度之间。所以行进用时介于v=1km/h的耗时与v=3km/h的耗时之间，我们可以得出

（9）………………………

再通过总体的行进速度不能超过2km/h约束条件得出

（10）………………

二是不同旅游团从景石出发的时间具有不确

定性，例如，多个旅游团在不同的时间从景石出发开始游览。

不同的旅游团从景石出发的时间不确定，这个时候我们以早上九点为时间参考原点。这里我们给定每个旅游团的出发时间DTOR，此时到达商业街的时间可以顺延，假设延长度为L，那么我们可以得到第一个约束方程（11）

（11）TgR≤TOR+L……………………………

三是每个景点的等待时间也存在不确定性因

或者受到素，例如，旅游设施短时间的维护和清理，

散客客流的影响。

(上接第141页)

假设由于短时间在每个点的等待时间不确定，

维护，不能进入景点游玩，设维护时间段为[TT1，

则则TiR≥TT2或者TiR≤TT1，若因为散客影响，TT2]，

依次增加每个点对应的等待时间即可。

参考文献：

但琦.数学建模与数学实验[M].北京:高等教[1]赵静，

育出版社，2014:106-109.

孙兆亮.数学建模算法与应用[M].北京:国防工[2]司守奎，

业出版社，2017:58-70.

[3]FrankR.GiordanoWilliamP.Fox数学建模[M].北京：

机械工业出版社，2016:214-221.

[4]冯俊文.中国邮递员问题的整数规划模型[J].系统管理

学报，2010(6):684-688.

李翔.复杂网络理论及其应用[M].北京:清华[5]汪小帆，

大学出版社，2009.[6]胡运权，查看清.运筹学基础及应用[M].北京:高等教育

出版社，2004.

赵连朋.改进的模拟退火和遗传算法[7]姚明海，王娜，

求解TSP问题[J].计算机工程与应用，2013(14):60-65.[8]李俊纬.物流配送TSP问题的研究[D].哈尔滨：哈尔滨

工业大学，2017.[9]冯剑，岳琪.模拟退火算法求解TSP问题[J].森林

工程，2008(1):94-96.

王功巧］［责任编辑：

提高服务水修专业时要做好多部门的协调和合作，

平和效率。另外要提高学分制的弹性，不仅要降低最低毕业总学分要求，而且应该减少对每学年修读学分数量的，加大选修课学分的比重。允许学生按照个人能力和个人计划，适当延长在校的学习年限，自主安排攻读第二专业。探索暑假学期，以灵

社会调查、社会实活安排时间相对集中的实验课、

践、企业实习、专家讲座以及部分高级课程。

参考文献：

[1]ChristopherBajada，RowanTrayler.Interdisciplinary

businesseducation:curriculumthroughcollaboration[J].Education+Training,2013,55(4/5):385-402.[2]GünterBl?schl，GemmaCarr，ChristianBucher.Promoting

interdisciplinaryeducation?theViennaDoctoralProgrammeonWaterResourceSystems[J].HydrologyandEarthSystemSciences,2012,16(2):457.[3]MauraBorrego，MargaretJFoster，JeffreyEFroyd.Systematic

literaturereviewsinengineeringeducationandotherdevelopinginterdisciplinaryfields[J].JournalofEngineeringEducation,2014,103(1):45-76.[4]MartinDavies，MarciaDevlin，MalcolmTight.Interdisciplinary

highereducation:Perspectivesandpracticalities[M].England:EmeraldGroupPublishingLimited,2010.

黄江美.高校复合型人才培养模式改革的研究[D].南宁：广西大学，2008.

[6]李兴业.美英法日高校跨学科教育与人才培养探究[J].

现代大学教育，2004(5).

[7]陈莹.学科交叉背景下经管类专业人才培养模式研

究[J].郧阳师范高等专科学校学报，2013(3).

[8]谭俊杰.基于交叉学科视角的国际经济与贸易专业应

——以广西民族师范学院为用型人才培养升级版研究—例[J].教育现代化，2018(14).

尚东昌.多学科交叉在国际贸易复合[9]毕鹏，魏吉才，

型人才培养模式中的应用研究[J].佳木斯大学社会科学学报，2012(4).

韩冰.多学科渗透交叉的金融专业人才培养[10]王春平，

模式研究———以双学位教育为契机[J].当代教育理论与实践，2011(8).[11]赖明勇，王华，杨晶晶.学科交叉和经济管理人才培

养———以湖南大学经济与贸易学院为例[J].当代教育论坛：校长教育研究，2008(2).

梁经锐“[12]李业，林养素，.3＋2”复合型国际贸易专业

的创办与实践[J].华南理工大学学报：自然科学版，1996(11).[13]陈晋，肖东生.美国国际贸易人才培养模式初探[J].外

国教育，2001(6).

［责任编辑：马欣］

[5]

160