孫波，劉士彩，王玉瀟，郭帥，張家迎

（1.山東科技大學(xué)信息工程系；2. 山東科技大學(xué)機(jī)電工程系；3. 山東科技大學(xué)網(wǎng)絡(luò)中心，泰安271000，中國）

1 引言

近年來，隨著交通事業(yè)的快速發(fā)展，越來越多的人傾向于出行旅游，而大多數(shù)人在出行時會選擇自駕，那么合理的線路規(guī)劃就顯得尤為重要。兩個城市間的線路規(guī)劃問題已取得重大成就，但途經(jīng)多個城市時，如何選擇最短線路，制定多個目標(biāo)間的交通線路規(guī)劃方案，節(jié)約出行時間，成為許多學(xué)者關(guān)注的重點(diǎn)。

最短路徑問題是經(jīng)典的線路規(guī)劃問題，在路徑規(guī)劃方面有很多已經(jīng)取得成效的算法，如Dijkstra算法、蟻群算法、遺傳算法、Floyd算法等。其中，王佳[1]等將Dijkstra算法應(yīng)用在京津冀旅游交通線路優(yōu)化的實(shí)際問題上。Dijkstra算法[2]是目前多數(shù)系統(tǒng)解決最短路徑問題的理論基礎(chǔ)，其優(yōu)點(diǎn)是程序設(shè)計(jì)簡單、通用性強(qiáng)；缺點(diǎn)是該算法不是專門地針對特定兩點(diǎn)。蟻群算法是一種新型算法，是觀察蟻群的行為時受啟發(fā)而提出的，王震霆等[3]提出蟻群算法能適應(yīng)環(huán)境的變化并且還有記憶能力，但蟻群算法的正反饋過程容易陷入局部極小值，為此提出了一種改進(jìn)的蟻群算法以解決擴(kuò)大搜索空間和尋找最優(yōu)解之間的矛盾。張雁翔等[4]在研究旅行商（Traveling Salesman Problem，TSP）問題時發(fā)現(xiàn)是高度并行、隨機(jī)、自適應(yīng)的全局尋優(yōu)搜索算法，該算法具有強(qiáng)大的魯棒性和全局搜索能力；缺點(diǎn)是局部尋優(yōu)能力較差且容易出現(xiàn)早熟現(xiàn)象。代修宇等[5]在優(yōu)化改良Floyd算法時發(fā)現(xiàn)該算法雖然能夠求出任意一對頂點(diǎn)之間的最短路徑，但是它的每一個頂點(diǎn)分別要與其它n-1個頂點(diǎn)作為邊的長度進(jìn)行比較，因此其時間復(fù)雜度為O（n3），并且傳統(tǒng)Floyd算法不能直觀反映出各個頂點(diǎn)之間最短路徑序列的先后關(guān)系。

以上算法在線路優(yōu)化問題上各有優(yōu)勢，且都可以有效的解決線路優(yōu)化問題，但要解決多地間的線路優(yōu)化問題，求最短Hamilton回路的改良圈算法相比于以上算法要簡便很多，基于Hamilton回路的改良圈算法具有簡單易懂、效率高、且適用范圍廣等優(yōu)點(diǎn)?，F(xiàn)今，汽車出行成為主流的出行方式，如果出行的起點(diǎn)和終點(diǎn)重合，利用Hamilton回路的自身特點(diǎn)可以很好地求解此類問題。本文通過改良圈算法求解權(quán)值最短Hamilton回路，制定了多目標(biāo)間的線路規(guī)劃方案，大大縮短了人們的出行時間，為人們的出行提供了便利。

2 算法介紹

哈密頓圖（Hamilton path）是一個含有哈密頓回路的無向圖，由指定的起點(diǎn)到達(dá)指定的終點(diǎn)，途中經(jīng)過所有其他節(jié)點(diǎn)且只經(jīng)過一次，閉合的哈密頓路徑稱作哈密頓回路，含有圖中所有頂點(diǎn)的路徑稱作哈密頓路徑[6]。哈密頓回路圖，與歐拉回路圖互相呼應(yīng)，歐拉回路要求通過每條邊有且僅有一次，而哈密頓回路圖則要求通過每個頂點(diǎn)有且僅有一次。哈密頓的實(shí)現(xiàn)需要滿足以下兩個條件：

（1）哈密頓圖是封閉的環(huán)；

（2）哈密頓圖是一個連通圖，且圖中任意兩點(diǎn)可達(dá)經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)有且僅有一次。

Hamilton改良圈算法步驟如下：

（1）從任何節(jié)點(diǎn)開始，將其加入到解的集合中，進(jìn)行初始化，構(gòu)造圖G（s，e），s表示一個節(jié)點(diǎn)，e表示一條邊，下面圖1-圖3反映了G（s，e）的變化。在圖G（s，e）中找到一個起點(diǎn)s1，從與該結(jié)點(diǎn)連接的邊中選擇最短的那條邊的結(jié)點(diǎn)加入到解的集合中，這就是所謂的最近鄰居，即尋找距離s1最近的點(diǎn)s2，若同時有多條邊距離相等，任選一條即可，且保證s2與s1之間的權(quán)重值最小，構(gòu)成線路s1s2，如圖1所示。

圖1 兩點(diǎn)間線路規(guī)劃

（2）從上述運(yùn)算所選的最近鄰居出發(fā)，重復(fù)上述過程，但應(yīng)避免已選擇過的結(jié)點(diǎn)，以免提前形成回路，即再以s2為起點(diǎn)，尋找與s2權(quán)重距離最小的點(diǎn) s3，構(gòu)成s1s2s3，如圖2所示。

圖2 三點(diǎn)間線路規(guī)劃

（3）以此類推，當(dāng)所有結(jié)點(diǎn)都加到解的集合中后，將最后加入的結(jié)點(diǎn)與起始結(jié)點(diǎn)連接，就可以得到哈密頓回路了，若已經(jīng)選出路線s1s2…si，再在圖G中找到一個與 si（i=1，2，…，n）最近的點(diǎn) si+1，就得到了 s1s2…sisi+1，如圖3所示。

圖3 多點(diǎn)間線路規(guī)劃

（4）當(dāng)i+1＜n-1時，用i代替i+1重復(fù)3），否則回路 A= s1s2…sns1。

（5）當(dāng)所有結(jié)點(diǎn)都加到解的集合中后，將最后加入的結(jié)點(diǎn)與起始結(jié)點(diǎn)連接，就可以得到哈密頓回路了。

為了得到一個更好的算法，本文應(yīng)用改良算法即可得到優(yōu)化后的Hamilton A：

（6）對于 1≤ i＜i+1＜j≤ n，構(gòu)建新的 Hamilton 圈Aij=s1…sj-1sj-2…si+1sj+1…sns1它是由 A 中將 si和 sj之間的邊逆序后得到的。

（7）若 w（sisj）+w（si+1s(j+1） ＜w（sjsj+1）+w（sjsj+1），則該圈替換有效，繼續(xù)執(zhí)行以上步驟，直至無法優(yōu)化。

3 模型建立

在途經(jīng)城市個數(shù)確定的情況下，為了解決多目標(biāo)的線路規(guī)劃問題，最小化人們的出行距離，節(jié)省出行時間及出行費(fèi)用，根據(jù)城市與城市間距離，構(gòu)建基于Hamilton算法的線路規(guī)劃模型，完成多個城市間的線路規(guī)劃[7]。多目標(biāo)的線路規(guī)劃問題首先要確定其對應(yīng)的目標(biāo)函數(shù)，然后確定滿足該函數(shù)的約束條件，構(gòu)建最優(yōu)Hamilton圈，完成模型的建立。

基于改良圈算法的推導(dǎo)，需要確定其相應(yīng)的參數(shù)。令x_ij表示從第i個城市到第j個城市所要行走的距離，r_ij是判斷出行者是否從第i個城市到第j個城市的0-1型變量，n表示途徑的城市個數(shù)，令目標(biāo)函數(shù)D表示多目標(biāo)間的最短出行距離。

該目標(biāo)函數(shù)需要滿足以下約束條件：

（1）城市個數(shù)約束。整個出行線路是封閉圖形，即出行者最終要重新回到起點(diǎn)，當(dāng)i,j的值從1取到n時，rij的和表示出行者要途經(jīng)的城市總數(shù)，城市個數(shù)約束為：

（2）0-1變量的約束。Hamilton算法最終線路為一個回路，每個節(jié)點(diǎn)代表一個城市，每一個點(diǎn)只可以有一條邊與之相連，若有一條邊輸入則必須有一條邊輸出，得到以下約束：

當(dāng)i=1時，表示起點(diǎn)，此時∑i=1rij=1；

當(dāng)j=1時，表示回到起點(diǎn)，此時∑j=1rij=1。

綜上可知其約束條件為：

根據(jù)Hamilton改良圈算法和已構(gòu)建的目標(biāo)函數(shù)，求取各目標(biāo)城市出行最佳線路，即要在圖 中求解出一個權(quán)值最小的Hamilton圈，即最優(yōu)圈。求解最優(yōu)圈的思想為：先求出一個Hamilton圈A，然后修改A得到具有較小權(quán)的另一個Hamilton圈，反復(fù)修改得到最優(yōu)圈。按照以上思路，先用最鄰近算法求解近似最優(yōu)Hamilton圈，步驟如下：

（1）選取任意一個頂點(diǎn)s0作為起點(diǎn)，找一條與s0關(guān)聯(lián)且權(quán)最小的邊e1， e1的另一個端點(diǎn)記作 v1，得到一條路s0s1；

組織是人類走向文明的產(chǎn)物。作為一個獨(dú)立的概念，組織傳播最早見于西蒙(H.A.Siom)在1945年發(fā)表的關(guān)于管理行為的文章中。由于受到企業(yè)管理理論的影響，組織傳播研究早期主要集中于組織內(nèi)部的管理傳播技巧方面。20世紀(jì)70～80年代后，在社會學(xué)、文化學(xué)等學(xué)科的介入下，組織傳播研究呈現(xiàn)多元化的趨勢?，F(xiàn)在，西方的組織傳播研究可分為功能主義、解釋主義和批判學(xué)派三大取向，并以功能主義為主導(dǎo)[12]。韋伯將組織定義為一個為完成協(xié)作任務(wù)而進(jìn)行的具有一定目的性人際活動的體系。在一個組織中，交流能否被接受取決于上層領(lǐng)導(dǎo)的權(quán)力合法化的程度。

（2）假設(shè)已選出路線s1s2…si，在現(xiàn)有路徑中找到一個與si最鄰近的頂點(diǎn)si+1，得到s0s1s2…sisi+1；

（3）若i+1＜n-1 ，則用i代替i+1返回（2），否則，記為Hamilton圈A=s0s1…sns0；，停止。

于是得到了一個近似最優(yōu)圈，但最鄰近算法求得的Hamilton圈一般不是最優(yōu)解，在此基礎(chǔ)上，繼續(xù)通過改良圈算法，就可以獲得更短的Hamilton圈。將A=s1s2…sns1作為改良圈算法的初始圈，按照以下方法，最終可以得到一個最優(yōu)圈A1。

（4） 所 有 滿 足 1＜i+1＜n 的 i，j ， 可 構(gòu) 造 新 的Hamilton 圈 ： Aij=s1s2…sisjsj-1sj-2…si+1sj+1sj+2…sns1，它是由圈A刪去邊sisi+1和sjsi+1，添加邊vivi和vi+1vj+1后得到的，若 w（sisj）+w（si+1sj+1）＜w（sjsj+1）+w（sjsj+1），則以Aij代替圈A，Aij稱為A的改良圈。

（5）返回（4），直至無法改進(jìn)，得到最優(yōu)圈A1，停止。

建立以上模型后，得到了一個最優(yōu)的Hamilton圈，下面通過實(shí)例驗(yàn)證此算法的有效性。

4 模型仿真

以某游客的山東省內(nèi)自駕游為例，假設(shè)游客需途經(jīng)濱州、濟(jì)南、濰坊、臨沂、聊城、青島六座城市作為線路規(guī)劃點(diǎn)，分別以1、2、3、4、5、6代表這六座城市，為縮短路程，應(yīng)用構(gòu)建的模型，求解最優(yōu)Hamilton，規(guī)劃了出行線路，驗(yàn)證算法的可行性。城市路線分布及其城市間距離如圖4所示。

圖4 最短線路距離

根據(jù)圖得到各城市間的距離數(shù)據(jù)如下

（1，2）=163.5；（1，3）=167.5；（1，4）=354.2；（1，5）=241；（1，6）=315.4；

（2，3）=208.2；（2，4）=246.9；（2，5）=126.6；（2，6）=351.2；

（3，4）=249；（3，5）=312.1；（3，6）=175.4；

（4，5）=353；（4，6）=276.5；

（5，6）=467.7；

由此，得到距離矩陣Q：

根據(jù)模型得到目標(biāo)函數(shù)值：

為了驗(yàn)證算法的有效性，將距離矩陣代入到程序中，利用matlab軟件實(shí)現(xiàn)算法。主要算法如下：

function main

clc，clear

global a

a=zeros（6）；

a（1，2）=163.5；a（1，3）=167.5；a（1，4）=354.2；a（1，5）=241；a（1，6）=315.4；

a（2，3）=208.2；a（2，4）=246.9；a（2，5）=126.6；a（2，6）=351.2；

a（3，4）=249；a（3，5）=312.1；a（3，6）=175.4；

a（4，5）=353；a（4，6）=276.5；

a（5，6）=467.7；

a=a+a'；L=size（a，1）；

c1=[1 2:5 6]；

[circle，long]=modifycircle（c1，L）；

c2=[1 6 2:5]；

[circle2，long2]=modifycircle（c2，L）；

if long2＜long

long=long2；

circle=circle2；

end

circle，long

matlab程序運(yùn)行結(jié)果如下：

circle =

1 3 6 4 2 5

long =

1.2339 e+03

所得結(jié)果顯示以濱州為起點(diǎn)遍歷其他五座城市并回到起點(diǎn)的最短路徑為：1→3→6→4→2→5→1，即：濱州→濰坊→青島→臨沂→濟(jì)南→聊城，得到的六節(jié)點(diǎn)有向圖如圖5。

圖5 六節(jié)點(diǎn)有向圖

根據(jù)有向圖得到鄰接矩陣Z如下，其中1表示兩城市間存在連線，該線路在Hamilton回路中，0表示兩城市間無連線。

則此Hamilton回路總長為1233.9km，與目標(biāo)函數(shù)所求數(shù)據(jù)相同，驗(yàn)證了該算法具有好的有效性。城市間的線路即是通過導(dǎo)航軟件所得出的兩城市間的最短線路，簡化后的線路規(guī)劃圖如圖6。

圖6 線路規(guī)劃圖

5 結(jié)語

本文通過基于Hamilton回路的改良圈算法來解決現(xiàn)實(shí)中的交通線路規(guī)劃問題，求取步驟為：首先通過導(dǎo)航類軟件獲得任意兩地點(diǎn)間的最短線路及距離，然后構(gòu)建一個賦權(quán)的完全圖G（s，e），邊上的權(quán)就是兩點(diǎn)間最短路線的距離，利用MATLAB求取最短路線。利用改良算法求取最優(yōu)哈密頓回路，是解決線路規(guī)劃的主流算法，算法簡單易懂，且適用范圍廣，利于推廣；利用Matlab軟件進(jìn)行了實(shí)例驗(yàn)證，結(jié)果表明了算法具有可行性與有效性。本文以山東的6個城市作為例子，進(jìn)而可通過該例推廣到全國各地的出行線路優(yōu)化當(dāng)中，優(yōu)化出行線路。

基于本文的研究，其他研究者可以將出行的時間和金錢花費(fèi)賦予一定的權(quán)重，代替距離來解決出行的最小花費(fèi)問題，求取利益最大化的線路。此外，影響游客出行的因素包括路程、交通費(fèi)用和時間等，利用改良算法可求出出行時間最短或花費(fèi)最少的線路，但道路的路況、交通擁堵狀況等問題都對時間和費(fèi)用有較大影響，在后期的研究中，將進(jìn)一步綜合研究各種因素，考慮各因素影響的權(quán)重，根據(jù)實(shí)際路況信息，設(shè)計(jì)并建立更合理的模型。