基于动态规划在旅游线路规划中的应用研究

切吉卓玛

摘要：为给旅行者提供更优的旅游路线，使得所设计的路线更为合理和贴近人们的期望；本文以青海省内多日游为例运用运筹学中动态规划等相关知识，利用LINGO软件，分析各景点之间的最短路径关系，通过建立模型、数据分析来实现目标最优化。

关键词：旅游线路；动态规划；LINGO

一、引言

旅游线路是在旅游景点路线规划过程和线路设计过程中经常用到的词汇。对于个人而言；满足消费需求、在旅游过程中使成本最小、日程安排最方便是最初期望。而在满足基本需求的基础上降低成本、提高效益、并可面对突发事件及时调整路线是旅行社的期望。因此，在规划和设计旅游线路时就要尽可能的考虑旅游线路的科学合理性。从旅游线路的研究方法来说；用动态规划相关知识进行旅游线路分析和运算问题、能做出合理的优化安排、且便于发展有限资源的效益并可获得合理性的结果。

迎合了当前社会的高速发展和旅游业的快速崛起及现代人对精神文化的渴求；且为了促进青海省内旅游发展的力度，以青海省内主要的旅游景点为例，运用动态规划知识探讨并分析旅游路程的情况。并应用LINGO解决最优路径问题；并希望最终能推广LINGO软件及动态规划知识在旅游线路中的实际运用。

二、问题提出

最短路径是網络规划中的基本问题，在网络理论中广泛应用；因许多管理和实际应用问题都与最短路径问题有关；因此，这类问题都可用最短路径问题来建立并优化模型。由动态规划求多个目标之间的多阶段路径问题；并用lingo来解决数据问题，可使结果更为合理实用。选取青海省内部分景点为例，在高速发展的快餐文化及物质文化泛滥而精神需求日益高涨的现状下分析并探讨各个景点之间的最优路径问题。

最短路问题的一个典型应用就是设点问题，设点问题又称为整数规划问题；这类问题可分为连续和离散型两类、单设施和多设施。不同类型的设点问题对设点的要求和指标都会有影响。而在实际旅游问题中的目标景点，为固定存在的多个点由旅客本人选择目标圈中的一些点来规划自己的路程问题，在这类问题中我们主要考虑个人的利益问题即消费成本最小化、日程安排最方便、所花费的路程最短。由动态规划知识得多个目标之间的多阶段路径问题，并用lingo来解决实际中相应的数据问题。lingo api 的作用与complex的作用相同，均为算法引擎；Lingo是数学建模工具；具有简洁的编程语言、友好的编辑和执行环境、更方便纠错与调试；通过调用相应的优化引擎程序来求解模型，可以使得结果更为合理实用。

1.问题假设及其符号说明

1.1问题假设

1、旅客最先从塔尔寺出发；2、十五个目的地旅客都可到达； 3、旅客在途中不发生任何意外事故； 4、旅客在途中身体状况良好且不会影响行程； 5、旅客在途中不做停留，只考虑行程问题； 6、旅客在考虑观光景点时综合各种情况优先考虑离市区较近的景点。

1.2 符号说明

i，j=（1，2…15）分别表示：dij——表示第i个目的地到第j个目的地的距离。D——表示总距离。ai——表示各个目的地i=（1…15）.其中a1=塔尔寺，a2 =青海湖，a3=孟达天池，a4 =龙羊峡，a5 =托索湖，a6 =万丈盐桥，a7 =察尔汗盐湖，a8=昆仑山口，a9 =澜沧江源头，a10 =黄河源，a11=可可西里，a12 =长江源，a13=鲁藏寺旧址，a14=文成公主庙，a15=年保玉则。Xij——表示第i目的地和第j目的地的0-1变量。

2.相关数据

对于选择各个目标景点之间的距离通过高德地图软件查询而得；相关数据如下表：

各景点之间距离（单位为Km）

塔尔寺 青海湖 孟达天池 龙羊峡 托索湖 万丈盐桥 察尔汗盐湖 昆仑山 澜沧江源头 黄河

源 可可西里 长江源 鲁藏寺旧址 文成公主庙

塔尔寺 0 269.1 202.4 169.1 429.9 769 755.8 959.9 773.6 532.9 140.7 1215.2 218.6 820

2.1问题解决

最短路问题是从某地出发，途经若干结点并最后到达目的地，要求找出路程或费用最小的路线。我们把旅游目的地问题看成是一个多阶段决策问题。从a1出发，经过n阶段，每个阶段的决策是选择下一个目的地。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为已去过的目的地不需再去，所以决策集合与前选决策有关，用（ai，A）表示状态，a1时所在目的地，A是还没有去过目的地的集合。在状态（ai，A）决策集合A中，取决策aiA，获得的效益是ai到aj的距离dij，转入下一个状态（ai，A＼{aj}），再用最优化原理寻递推公式。

采用Lingo程序编程求解，Lingo程序编程及运行结果如下：

最优路线：

a1→a13→a4→a2→a5→a10→a9→a14→a12→a11→a3→a7→a6→a15→a3→a1

三、总结

在快餐文化膨胀的现状下，以当下最为流行的旅游为话题引述了其中所可能出现的一切问题。而动态规划恰恰就可解决这类实际问题，尽管所求的问题的过程及方法不计其数；但运用最短路径能更简便精确的求得实际旅游中的最优问题。最短路径问题是算法设计中的经典问题、也是现实世界许多应用中的基本问题。在解决旅游中遇到的各类问题时往往由于缺乏对路线的合理安排，造成了旅游途中自身体力的过度耗费；而且在自身有限时间的不合理利用上也造成了多种困扰。为此，此文将以青海省内旅游为例，并选取部分景点作为目标点；通过动态规划知识寻求各个景点之间的最短路问题，将它看成一个多阶段决策问题。利用最优化原理，寻找递推公式，建立矩阵并采用lingo程序编程求解得出相应问题的结论。通过结论，希望旅游者在旅行途中尽可能的花费最少的路程去观光完各个景点。

参考文献：

[1]刁在筠，刘桂真，宿洁等，运筹学[M][第三版]，北京：高等教育出版社，2007.01.

[2] 张铮. 基于最短路径分析的中间件设计与应用研究[J]. 测绘与空间地理信息. 2013（12）

[3]邹时林，阮见，刘波等，最短路径算法在旅游线路规划中的应用——以庐山为例[J]测绘科学.2008.5