摘要：在中國旅游業(yè)發(fā)展快速的時代背景下，四川旅游業(yè)發(fā)展規(guī)模越來越大，在此情況下人們對于旅游線路的選擇越來越多樣化。從空間和時間角度出發(fā)，旅游線路的優(yōu)化問題變得錯綜復雜?；谏鲜鰡栴}，本文以四川部分旅游景點為例，首先應用圖論的知識，將旅游景點以及各景點之間的旅游路線構成一個圖，繼而應用運籌學中的Dijkstra算法優(yōu)化問題。

關鍵詞：旅游線路 最短路算法 運籌學方法

一、引言

現(xiàn)代經(jīng)濟的飛速發(fā)展，人們在對生活的要求越來越高，繼而旅游業(yè)成為近幾年來人們青睞的對象。旅游業(yè)的日趨完善，旅游目的地、旅游路線、旅游景點、旅游生活的條件也越來越多樣化，使得人們在做出旅游規(guī)劃時難度增加。近年來，旅游社團的產(chǎn)品層出不窮，也有不少人在假日帶著全家人自駕出游。在出行中，旅游景點和旅游線路的選擇是最難和最重要的環(huán)節(jié)。所以我們要設計合理的旅游路線，讓旅游者有計劃，有目的地安排自己的旅游活動，簡言之最重要的是，花最少的錢，看最多的風景。

（一）旅游線路研究的意義

在理解旅游線路含義后，研究如何選擇旅游線路問題一般基于旅游者、旅游社和旅游景點決定。而對于這三個主體而言，旅游線路是他們在旅游線路中經(jīng)常需要做出規(guī)劃和選擇的決策問題。做出決策的主要效果是：盡最大程度、最好地滿足消費者，使他們的消費成本最小，日程安排最方便。在選擇規(guī)劃路線時需考慮各個景區(qū)線路在空間上的合理和科學。

（二）旅游線路的研究歷史

國外旅游研究已有悠久歷史，不同研究者相繼發(fā)表了自己不同的觀點。在1969年，一些理論研究者相繼提出了各種結構模型，在理論研究的今天還是有不少地方值得借鑒。中國旅游線路研究相對國外來說，時間較短，經(jīng)驗也不豐富。在上世紀九十年代，國內對于旅游線路還沒有規(guī)范性的統(tǒng)籌定義。由于國內各學者的背景不同，大家在旅游線路研究上看法不一。

（三）旅游線路的影響因素

首先對于旅游者來說影響最大的是心理因素，其中包括好奇心理、懷舊心理。旅游者都希望包攬所有的心理完成一場完美的旅行。其二就是成本因素，對于廣大旅游愛好者來說，不管選擇怎樣的出行方式，做出怎樣的旅游規(guī)劃，對于價格成本來說都是至關重要的，都希望花最少的錢看最多的景點。其三就是自然因素，每一個景區(qū)都有自己特有的風景、文化、歷史，這些是難以改變的客觀因素。

二、最短路問題在旅游線路中的優(yōu)化模型

Dijkstra算法

具體步驟：給出一個固定的賦權有向圖

[S=V，A，] 開始（[i=1]），

設[S1=νs]，[Pνs=0，λνs=0]

[對每一個ν≠νs]，設[Tν=+∞，λν=M]，[K=S].

第一步，若[Si=V]，停止計算，要滿足對每個

[ν∈Si]，[dνs，νt=Pν]；

如果不滿足則轉入第二步。

第二步，考察每個使[νk，νj∈A]且[νj?Si]的點[νj]。

如果[Tνjgt;Pνk+ωkj，]則把[Tνj]修改成

[Tνk+ωkj]，把[λνj]修改為[k]；

如果不滿足則轉入第三步 。

第三步，設[Tνji=minνj?SiTνj]

如果[Tνjilt;+∞]，則把[νji]的T變?yōu)镻標號

[Pνji=Tνji]

設[Si+1=Si?νji]，[k=ji]

把[i]換成[i+1]，再轉入第一步進行計算；如果不滿足則算法終止。

此時對每一個[νj?Si]，[dνs，ν=Tν]

三、最短路問題在優(yōu)化中的具體應用

本文以四川及周邊旅游城市為例，設計在不考慮旅游費用的情況下，兩個旅游景點在最短距離和最短時間的情況下對旅游線路最優(yōu)化線路選擇。

（一）在實際中的分析

在運用最短路算法的時候，我們常常需要把理論性的概念轉化為可操作的實質性線路。例如我們設計一條出行路線“成都→樂山→西昌→攀枝花”的旅游線路，大致的方向已經(jīng)確定，那么不妨考慮如何從樂山到西昌呢？現(xiàn)有三種方案可以考慮：第一種，先從樂山坐大巴到峨眉，峨眉坐火車到成都；第二種，樂山坐大巴到成都，再從成都坐直通車到西昌；第三種，樂山坐大巴到雅安，再從雅安坐大巴到西昌。三種交通方式，都有相應不一樣的組合路程，時間，和旅游成本，此時就需要我們在三者中做出權衡，繼而選擇最優(yōu)化的旅游線路方案。

下面我們來看圖1簡單的交通網(wǎng)絡圖（假設方向）。每條弧線旁邊的數(shù)字表示通過這條單行線所需要的最短距離。現(xiàn)在假設某旅游愛好者從[ν1]出發(fā)，通過這個交通網(wǎng)絡到達[ν6]，求所需要通過的最短路徑。在圖中我們可以看到從[ν1]通往[ν]6的路徑是非常多的，如依次通過[ν1]，[ν2]，[ν4]，[ν6]，也可以從[ν1]，[ν3]，[ν5]，[ν6]等。但對于不同的旅游線路所通過的路程具體是完全不一樣的。第一條線路通過的距離為2+2+4=8單位，而后一條線路通過的距離為5+6+3=14單位，由此看來不同的交通路線所通過的距離都是不一樣的。用圖的語言來描述，從[ν1]到[ν6]的交通線路中，[ν1]到[ν]6的路線是一一對應的，所需要通過的距離就是相對應的[ν1]到[ν6]弧線旁邊的數(shù)字和。例如某旅游愛好者的旅游路線可以是從[ν1]出發(fā)途徑[ν2]，[ν5]，然后到[ν6]，那么這條路線可以相應的表示成（[ν1]，[ν2]，[ν5]，[ν6]），通過的總路程是7個單位。圖1是在節(jié)點很少的情況下進行計算的，我們可以利用筆或通過自己的觀察得出最短路徑，但是隨著節(jié)點數(shù)的增加，計算難度便會快速增長，此時我們就需要計算機來幫助求解，運用運籌學中的最短路問題和改進的矩陣算法求解。

在這個問題中看到了簡單的最短路的簡單模型，現(xiàn)在以四川省及其四川省周邊旅游景點為例，旅游愛好者的目的是從出發(fā)地到目的地的距離最短，從而時間最短，所花費的成本也最低，旅游地圖如圖2所示。其中0表示甘孜州，1到6依次表示九寨溝、瀘沽湖、康定、三星堆、樂山、真佛山。對于游客來說怎么求出兩個景點之間的最短距離非常重要，比如游客從甘孜州出發(fā)到達真佛山，如何做出路線最短，時間最短的路線規(guī)劃設計。此時將每一個旅游景點看做是圖中的頂點，各個頂點的交通路線看作是圖中的邊，邊上的權重看做是一個景點到另一個景點的距離?！薇硎緵]有直接到這兩個旅游景點的路線。建立這樣一個數(shù)學模型以后便可以運用運籌學中圖論的最短路算法在求解。

根據(jù)這個圖論可以求出任意一個景點到另一個景點的最短路距離。在優(yōu)化問題中和生活聯(lián)系最密切是最短路問題，它常常直接解決生活的實際問題，比如用于設備更新，線路安排，廠區(qū)布局，管道鋪設等，而且常常作為解決實際生活中的基本工具。

（二）旅游線路最優(yōu)化的Dijkstra算法

接下來我們運用Dijkstra算法和四川旅游景點間距離圖進行計算，得出最優(yōu)化的旅游線路。

Dijkstra算法

對于最短路的研究，目前公認最好的方法是在1995年Dijkstra提出來的。在Dijkstra算法中，給定一個賦權有向圖（[S=V，A]），對于圖論中每一條邊[a=νi，νj]，則相應的權[ωa=ωij]，又給定[S]中的兩個頂點νt，νs，用[P]表示在[S]中從[ν1]到[ν2]的一條路[P]的權重是[P]中所有邊權重的和，記為[ωP]. 最短路問題就是[S]圖中選擇從[νs]到[νt]的最短路徑，即滿足

[ωp0=minpωp]

在上式中稱[P0]是[νs]到[νt]的最短路。[P0]的權稱之為[νs]到[νt]的距離，記為[dνs，νt]，且[dνs，νt]和[dνt，νs]不一定相等。

具體算法如下所示：

（1）當i=1時

[S1=ν1]，[Pν1=0]，[λν1=0]，[Tνi=+∞]，

[λνi=M（i=2，3，4，5，6）]，以及k=1。

轉入第二步，因[ν1，ν2∈A]，[ν1?S1] ，

[Pν1+ω12lt;Tν2]，所以把[Tν2]改為

[Pν1+ω12=5]，[λν2]改為1；

同理可得，將[Tν3]改為[Pν1+ω13=5]，[λν3]改為1，把[Tν4]改為[Pν1+ω14=2]，將[λν4]改為1。

轉入第三步，在所有的T標號中[Tν4]最小，于是

令[Pν4=1]，令[S2=S1?ν3=ν1，ν4]，k=4。

（2）i=2，轉入第二步將[Tν5]修改成

[Pν4+ω45=5]，修改k=4。轉入第三步，在所有T的標號中，[Tν5]最小，

于是令[Pν5=5]，令[S2=ν1，ν4，ν5]，k=5。

（3）i=3，轉入第二步，把[Tν6]修改為

[Pν5+ω56=6]，k修改為5。

轉入第三步，在所有T的所有標號中，[Tν6]最小，

于是令[Pν6=6]，令[S3=ν1，ν4，ν5，ν6]

（4）i=4，轉入第二步，把[Tν7]修改為

[Pν6+ω67=9]，令[Pν7=9]，

[S4=ν1，ν4，ν5，ν6，ν7]，k=7

（5）i=5，轉入第三步，此時僅有的T標號為[ν7]，故算法終止。

在這種算法中我們得到了最短路線即

[S4=ν1，ν4，ν5，ν6，ν7]。

但是這些都是單目標的最優(yōu)化設計，在實際生活中還需要考慮距離，費用，時間進行綜合考慮，建立多目標的優(yōu)化模型。

四、結語

本文只討論了在距離最短，時間最短（花費的成本）的條件下完成的，在實際生活中，旅游愛好者的滿意程度才是最重要的。我們以一個旅行社的角度出發(fā)，想要得到游客的滿意，首先得使游客在旅游行中，不斷熱情高漲，這就需要給游客提供一個好的旅游景點，突出新奇，再者是他們舒服的出游方式，愉快的旅游活動。到達旅游景區(qū)后還要保證旅游服務的質量，其中就包括吃飯，住宿，游行。在旅游社團出行方式中，還要考慮出游景點的人群如何組隊，不同年齡，不同生活方式的人對旅游的需求不一樣，這就需要旅游社團在設計旅游規(guī)劃時格外注意。

參考文獻：

[1]許興臣，馮玉清.旅游行程的設計與推廣[J]. 旅游學刊，1992（2）：14—18.

[2]關發(fā)蘭.區(qū)域旅游系統(tǒng)網(wǎng)絡結構分析與網(wǎng)絡優(yōu)化設計——以四川省為例[C].旅游開發(fā)與旅游地理，1989.