最短路算法在優化中的應用

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

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

一、引言

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

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

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

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

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

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

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

二、最短路問題在旅游線路中的優化模型

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變為P標號

[Pνji=Tνji]

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

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

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

三、最短路問題在優化中的具體應用

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

（一）在實際中的分析

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

下面我們來看圖1簡單的交通網絡圖（假設方向）。每條弧線旁邊的數字表示通過這條單行線所需要的最短距離。現在假設某旅游愛好者從[ν1]出發，通過這個交通網絡到達[ν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]弧線旁邊的數字和。例如某旅游愛好者的旅游路線可以是從[ν1]出發途徑[ν2]，[ν5]，然后到[ν6]，那么這條路線可以相應的表示成（[ν1]，[ν2]，[ν5]，[ν6]），通過的總路程是7個單位。圖1是在節點很少的情況下進行計算的，我們可以利用筆或通過自己的觀察得出最短路徑，但是隨著節點數的增加，計算難度便會快速增長，此時我們就需要計算機來幫助求解，運用運籌學中的最短路問題和改進的矩陣算法求解。

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

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

（二）旅游線路最優化的Dijkstra算法

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

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]。

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

四、結語

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

參考文獻：

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

[2]關發蘭.區域旅游系統網絡結構分析與網絡優化設計——以四川省為例[C].旅游開發與旅游地理，1989.