孫波,劉士彩,王玉瀟,郭帥,張家迎
(1.山東科技大學(xué)信息工程系;2. 山東科技大學(xué)機(jī)電工程系;3. 山東科技大學(xué)網(wǎng)絡(luò)中心,泰安271000,中國(guó))
近年來,隨著交通事業(yè)的快速發(fā)展,越來越多的人傾向于出行旅游,而大多數(shù)人在出行時(shí)會(huì)選擇自駕,那么合理的線路規(guī)劃就顯得尤為重要。兩個(gè)城市間的線路規(guī)劃問題已取得重大成就,但途經(jīng)多個(gè)城市時(shí),如何選擇最短線路,制定多個(gè)目標(biāo)間的交通線路規(guī)劃方案,節(jié)約出行時(shí)間,成為許多學(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ì)簡(jiǎn)單、通用性強(qiáng);缺點(diǎn)是該算法不是專門地針對(duì)特定兩點(diǎn)。蟻群算法是一種新型算法,是觀察蟻群的行為時(shí)受啟發(fā)而提出的,王震霆等[3]提出蟻群算法能適應(yīng)環(huán)境的變化并且還有記憶能力,但蟻群算法的正反饋過程容易陷入局部極小值,為此提出了一種改進(jìn)的蟻群算法以解決擴(kuò)大搜索空間和尋找最優(yōu)解之間的矛盾。張雁翔等[4]在研究旅行商(Traveling Salesman Problem,TSP)問題時(shí)發(fā)現(xiàn)是高度并行、隨機(jī)、自適應(yīng)的全局尋優(yōu)搜索算法,該算法具有強(qiáng)大的魯棒性和全局搜索能力;缺點(diǎn)是局部尋優(yōu)能力較差且容易出現(xiàn)早熟現(xiàn)象。代修宇等[5]在優(yōu)化改良Floyd算法時(shí)發(fā)現(xiàn)該算法雖然能夠求出任意一對(duì)頂點(diǎn)之間的最短路徑,但是它的每一個(gè)頂點(diǎn)分別要與其它n-1個(gè)頂點(diǎn)作為邊的長(zhǎng)度進(jìn)行比較,因此其時(shí)間復(fù)雜度為O(n3),并且傳統(tǒng)Floyd算法不能直觀反映出各個(gè)頂點(diǎn)之間最短路徑序列的先后關(guān)系。
以上算法在線路優(yōu)化問題上各有優(yōu)勢(shì),且都可以有效的解決線路優(yōu)化問題,但要解決多地間的線路優(yōu)化問題,求最短Hamilton回路的改良圈算法相比于以上算法要簡(jiǎn)便很多,基于Hamilton回路的改良圈算法具有簡(jiǎn)單易懂、效率高、且適用范圍廣等優(yōu)點(diǎn)?,F(xiàn)今,汽車出行成為主流的出行方式,如果出行的起點(diǎn)和終點(diǎn)重合,利用Hamilton回路的自身特點(diǎn)可以很好地求解此類問題。本文通過改良圈算法求解權(quán)值最短Hamilton回路,制定了多目標(biāo)間的線路規(guī)劃方案,大大縮短了人們的出行時(shí)間,為人們的出行提供了便利。
哈密頓圖(Hamilton path)是一個(gè)含有哈密頓回路的無向圖,由指定的起點(diǎn)到達(dá)指定的終點(diǎn),途中經(jīng)過所有其他節(jié)點(diǎn)且只經(jīng)過一次,閉合的哈密頓路徑稱作哈密頓回路,含有圖中所有頂點(diǎn)的路徑稱作哈密頓路徑[6]。哈密頓回路圖,與歐拉回路圖互相呼應(yīng),歐拉回路要求通過每條邊有且僅有一次,而哈密頓回路圖則要求通過每個(gè)頂點(diǎn)有且僅有一次。哈密頓的實(shí)現(xiàn)需要滿足以下兩個(gè)條件:
(1)哈密頓圖是封閉的環(huán);
(2)哈密頓圖是一個(gè)連通圖,且圖中任意兩點(diǎn)可達(dá)經(jīng)過圖(有向圖或無向圖)中所有頂點(diǎn)有且僅有一次。
Hamilton改良圈算法步驟如下:
(1)從任何節(jié)點(diǎn)開始,將其加入到解的集合中,進(jìn)行初始化,構(gòu)造圖G(s,e),s表示一個(gè)節(jié)點(diǎn),e表示一條邊,下面圖1-圖3反映了G(s,e)的變化。在圖G(s,e)中找到一個(gè)起點(diǎn)s1,從與該結(jié)點(diǎn)連接的邊中選擇最短的那條邊的結(jié)點(diǎn)加入到解的集合中,這就是所謂的最近鄰居,即尋找距離s1最近的點(diǎn)s2,若同時(shí)有多條邊距離相等,任選一條即可,且保證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中找到一個(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時(shí),用i代替i+1重復(fù)3),否則回路 A= s1s2…sns1。
(5)當(dāng)所有結(jié)點(diǎn)都加到解的集合中后,將最后加入的結(jié)點(diǎn)與起始結(jié)點(diǎn)連接,就可以得到哈密頓回路了。
為了得到一個(gè)更好的算法,本文應(yīng)用改良算法即可得到優(yōu)化后的Hamilton A:
(6)對(duì)于 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)化。
在途經(jīng)城市個(gè)數(shù)確定的情況下,為了解決多目標(biāo)的線路規(guī)劃問題,最小化人們的出行距離,節(jié)省出行時(shí)間及出行費(fèi)用,根據(jù)城市與城市間距離,構(gòu)建基于Hamilton算法的線路規(guī)劃模型,完成多個(gè)城市間的線路規(guī)劃[7]。多目標(biāo)的線路規(guī)劃問題首先要確定其對(duì)應(yīng)的目標(biāo)函數(shù),然后確定滿足該函數(shù)的約束條件,構(gòu)建最優(yōu)Hamilton圈,完成模型的建立。
基于改良圈算法的推導(dǎo),需要確定其相應(yīng)的參數(shù)。令x_ij表示從第i個(gè)城市到第j個(gè)城市所要行走的距離,r_ij是判斷出行者是否從第i個(gè)城市到第j個(gè)城市的0-1型變量,n表示途徑的城市個(gè)數(shù),令目標(biāo)函數(shù)D表示多目標(biāo)間的最短出行距離。
該目標(biāo)函數(shù)需要滿足以下約束條件:
(1)城市個(gè)數(shù)約束。整個(gè)出行線路是封閉圖形,即出行者最終要重新回到起點(diǎn),當(dāng)i,j的值從1取到n時(shí),rij的和表示出行者要途經(jīng)的城市總數(shù),城市個(gè)數(shù)約束為:
(2)0-1變量的約束。Hamilton算法最終線路為一個(gè)回路,每個(gè)節(jié)點(diǎn)代表一個(gè)城市,每一個(gè)點(diǎn)只可以有一條邊與之相連,若有一條邊輸入則必須有一條邊輸出,得到以下約束:
當(dāng)i=1時(shí),表示起點(diǎn),此時(shí)∑i=1rij=1;
當(dāng)j=1時(shí),表示回到起點(diǎn),此時(shí)∑j=1rij=1。
綜上可知其約束條件為:
根據(jù)Hamilton改良圈算法和已構(gòu)建的目標(biāo)函數(shù),求取各目標(biāo)城市出行最佳線路,即要在圖 中求解出一個(gè)權(quán)值最小的Hamilton圈,即最優(yōu)圈。求解最優(yōu)圈的思想為:先求出一個(gè)Hamilton圈A,然后修改A得到具有較小權(quán)的另一個(gè)Hamilton圈,反復(fù)修改得到最優(yōu)圈。按照以上思路,先用最鄰近算法求解近似最優(yōu)Hamilton圈,步驟如下:
(1)選取任意一個(gè)頂點(diǎn)s0作為起點(diǎn),找一條與s0關(guān)聯(lián)且權(quán)最小的邊e1, e1的另一個(gè)端點(diǎn)記作 v1,得到一條路s0s1;
組織是人類走向文明的產(chǎn)物。作為一個(gè)獨(dú)立的概念,組織傳播最早見于西蒙(H.A.Siom)在1945年發(fā)表的關(guān)于管理行為的文章中。由于受到企業(yè)管理理論的影響,組織傳播研究早期主要集中于組織內(nèi)部的管理傳播技巧方面。20世紀(jì)70~80年代后,在社會(huì)學(xué)、文化學(xué)等學(xué)科的介入下,組織傳播研究呈現(xiàn)多元化的趨勢(shì)?,F(xiàn)在,西方的組織傳播研究可分為功能主義、解釋主義和批判學(xué)派三大取向,并以功能主義為主導(dǎo)[12]。韋伯將組織定義為一個(gè)為完成協(xié)作任務(wù)而進(jìn)行的具有一定目的性人際活動(dòng)的體系。在一個(gè)組織中,交流能否被接受取決于上層領(lǐng)導(dǎo)的權(quán)力合法化的程度。
(2)假設(shè)已選出路線s1s2…si,在現(xiàn)有路徑中找到一個(gè)與si最鄰近的頂點(diǎn)si+1,得到s0s1s2…sisi+1;
(3)若i+1<n-1 ,則用i代替i+1返回(2),否則,記為Hamilton圈A=s0s1…sns0;,停止。
于是得到了一個(gè)近似最優(yōu)圈,但最鄰近算法求得的Hamilton圈一般不是最優(yōu)解,在此基礎(chǔ)上,繼續(xù)通過改良圈算法,就可以獲得更短的Hamilton圈。將A=s1s2…sns1作為改良圈算法的初始圈,按照以下方法,最終可以得到一個(gè)最優(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,停止。
建立以上模型后,得到了一個(gè)最優(yōu)的Hamilton圈,下面通過實(shí)例驗(yàn)證此算法的有效性。
以某游客的山東省內(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回路總長(zhǎng)為1233.9km,與目標(biāo)函數(shù)所求數(shù)據(jù)相同,驗(yàn)證了該算法具有好的有效性。城市間的線路即是通過導(dǎo)航軟件所得出的兩城市間的最短線路,簡(jiǎn)化后的線路規(guī)劃圖如圖6。
圖6 線路規(guī)劃圖
本文通過基于Hamilton回路的改良圈算法來解決現(xiàn)實(shí)中的交通線路規(guī)劃問題,求取步驟為:首先通過導(dǎo)航類軟件獲得任意兩地點(diǎn)間的最短線路及距離,然后構(gòu)建一個(gè)賦權(quán)的完全圖G(s,e),邊上的權(quán)就是兩點(diǎn)間最短路線的距離,利用MATLAB求取最短路線。利用改良算法求取最優(yōu)哈密頓回路,是解決線路規(guī)劃的主流算法,算法簡(jiǎn)單易懂,且適用范圍廣,利于推廣;利用Matlab軟件進(jìn)行了實(shí)例驗(yàn)證,結(jié)果表明了算法具有可行性與有效性。本文以山東的6個(gè)城市作為例子,進(jìn)而可通過該例推廣到全國(guó)各地的出行線路優(yōu)化當(dāng)中,優(yōu)化出行線路。
基于本文的研究,其他研究者可以將出行的時(shí)間和金錢花費(fèi)賦予一定的權(quán)重,代替距離來解決出行的最小花費(fèi)問題,求取利益最大化的線路。此外,影響游客出行的因素包括路程、交通費(fèi)用和時(shí)間等,利用改良算法可求出出行時(shí)間最短或花費(fèi)最少的線路,但道路的路況、交通擁堵狀況等問題都對(duì)時(shí)間和費(fèi)用有較大影響,在后期的研究中,將進(jìn)一步綜合研究各種因素,考慮各因素影響的權(quán)重,根據(jù)實(shí)際路況信息,設(shè)計(jì)并建立更合理的模型。