基于雙向搜索的運輸路線優(yōu)化算法

賈珺，孫靜瑜，侯冰

（1.軍事科學院 軍事運籌分析研究所，北京100091；2.軍事科學院 軍隊建設(shè)研究部，北京100091；3.總裝備部 電子信息部電子局，北京100034）

1 引 言

在后勤補給的運籌研究中運輸路線的優(yōu)化問題是一個很有代表性的問題，它具體是指當從某基地向某陣地運送物資時，如果有多條路線可選擇，通過給定每條道路的最大通過能力，即單位時間內(nèi)所能通過的最大車輛數(shù)目及通過代價（如長度、時間等），確定一條運輸路線，使得所走的路程為最短或者在給定時間內(nèi)通過的車輛數(shù)目最大，或者在代價最小的條件下通過的車輛數(shù)目最多[1]。其中所走的路程為最短這個問題可以轉(zhuǎn)換為通過的路程最短、耗費的時間最短或造成的損失最小等，是運輸路線優(yōu)化研究中應(yīng)用最為廣泛的。

2 運輸路線有向圖化簡

運輸路線的數(shù)字化指的是將一個物理的運輸路線圖轉(zhuǎn)變?yōu)橛嬎銠C可以識別和處理的數(shù)據(jù)類型。在圖論中大量使用的簡單有向圖是不包含環(huán)和平行邊的有向圖，它可以作為運輸路線圖的抽象表示，這一步抽象工作一般為人工完成，也可以使用模式識別和計算機圖形學的方法通過計算機輔助完成。構(gòu)建好的有向圖可以將其點和邊的關(guān)系用關(guān)聯(lián)矩陣的方式表示出來。

2.1 運輸路線有向圖的構(gòu)建

通常在運輸路線的優(yōu)化問題中是將運輸路線抽象為無向圖，因為從實際考慮，兩個點之間如果有道路相連，在不考慮特殊因素的條件下其應(yīng)該是雙向互通的，但是對于一次實際的后勤補給運輸來說，從起點出發(fā)到終點結(jié)束，在計算最短路徑的情況下肯定不會出現(xiàn)在任意兩個端點之間的往返運動。例如，如果對于路線1：v1v2v3v2v4為一條路徑，那么路徑2：v1v2v4必存在且長度要小于路徑1；在某些特定條件下，某兩個端點可能存在單向連通，所以利用有向圖構(gòu)建運輸路線更加符合實際情況。綜上，可以將運輸路線抽象化為起點只有出度而終點只有入度的有向圖，其余端點之間的關(guān)系以實際情況決定。如圖1所示，其中V={v1，v2，…，v9}為頂點集，E={e1，e2，…，e20}為邊集，v1為運輸路線的起點，v8為運輸路線的終點。由上面分析可知，生成的最短路徑應(yīng)該是基于圖G的一個初級通路v1…v8，即沒有重復頂點的通路。

2.2 關(guān)聯(lián)矩陣的構(gòu)建及化簡

運輸路線有向圖為G=＜V，E＞，其中V={v1，v2，…，vn}為頂點集，n為頂點個數(shù)，E={e1，e2，…，em}為邊集，m為邊的條數(shù)。圖G的關(guān)聯(lián)矩陣=1，2，…，n，j=1，2，…，m。

下面給出懸掛點和懸掛邊的定義。設(shè)vi（i=1，2，…，n）∈V，且vi不是運輸路線的起點或終點，當以下任一種情況出現(xiàn)時，稱vi為懸掛點：①M的行向量Mi中僅存在一個非零值mij，mij=1或mij=—1（j=1，2，…，m）；②M的行向量Mi中僅有一對非零值mij和mik，mij=1，mik=—1（j、k=1，2，…，m，j≠k），且存在vl（l=1，2，…，n，l≠i）∈V，使得mlj+mlk=0，mlj≠0，mlk≠0。當vi為懸掛點時，與vi相連的邊ej為懸掛邊，即滿足mij≠0的邊ej為懸掛邊。

針對圖1，關(guān)聯(lián)矩陣是一個9×20的矩陣，如下：

根據(jù)上面的定義，v9為圖1中的懸掛點，e19、e20為懸掛邊。如果在最短通路中有v9，其必然存在一個往返的過程，因此生成的最短路徑的初級通路肯定與v9、e19、e20不相關(guān)，可以在關(guān)聯(lián)矩陣中刪掉與v9相關(guān)的行、與e19和e20相關(guān)的列，將關(guān)聯(lián)矩陣化簡為8×18的矩陣。

經(jīng)過對有向圖起點和終點的選取以及對關(guān)聯(lián)矩陣采取去除與懸掛點和懸掛邊相關(guān)聯(lián)的行列后，就得到簡化后的基于運輸路線有向圖的關(guān)聯(lián)矩陣，其數(shù)據(jù)量相對其它算法構(gòu)建的無向完全圖已經(jīng)大幅度減少。通過這種方法可以減少在后期算法中的運算量，降低算法的時間和空間復雜度。

3 雙向搜索算法

3.1 算法定義

設(shè)簡化后的有向圖G=＜V，E＞，其中V={v1，v2，…，vn}為頂點集，n為簡化后的頂點個數(shù)，E={e1，e2，…，em}為邊集，m為簡化后邊的條數(shù)。

定義1：以v1作為起點，遍歷其作為出度點的邊，再以得到的邊集查找對應(yīng)的入度點，這樣就輸出一個路徑集L1={v1v2，v1v3，…}，然后以路徑集中各路徑的終點為起點重復以上步驟，并在查找過程中刪除有重復點的路徑，得到路徑集L2={v1v2v3，v1v3v2，…}，重復以上步驟集L={L1，L2，…，LA}。稱以上這種查找為基于有向圖的正向搜索，簡稱正向搜索。

定義2：以vn作為起點，遍歷其作為入度點的邊，再以得到的邊集遍歷對應(yīng)的出度點，這樣就輸出一個路徑集R1={vnvn—1，vnvn—2，…}，然后以路徑集中各路徑的終點為起點重復以上步驟，并在查找過程中刪除有重復點的路徑，得到路徑集R2={vnvn—1vn—2，vnvn—2vn—1，…}，重復以上步驟得到路徑合集R={R1，R2，…，RB}。稱以上這種查找為基于有向圖的逆向搜索，簡稱逆向搜索。

定義3：使用正向搜索和逆向搜索同時對有向圖G=＜V，E＞進行的搜索稱為基于有向圖的雙向搜索，簡稱雙向搜索。

引理：對有向圖G=＜V，E＞進行的雙向搜索可全遍歷頂點集V={v1，v2，…，vn}和邊集E={e1，e2，…，em}。

這是顯而易見的。

定理1：對有向圖G=＜V，E＞進行雙向搜索，存在vi∈L且vi∈R，使得L中的一條路徑li={v1…vi}和R中的一條路徑ri={vn…vi}組成的通路l為v1到vn的最短路徑。

證明：設(shè)l為v1到vn的最短路徑

若vi?L且vi∈R，由引理可知必存在vj使得lj={v1…vj}?li且ri?rj={vn…vj}，則有vj∈L且vj∈R，使得lj={v1…vj}和rj={vn…vj}組成的通路l為v1到vn的最短路徑。

同理可證vi∈L且vi?R情況。則定理證畢。

3.2 算法思想

根據(jù)兩個端點分別循環(huán)使用正向搜索和逆向搜索，得到路徑合集L={L1，L2，…，LA}和R={R1，R2，…，RB}，對其進行化簡，將L中終點相同的路徑進行比較，選出長度最短的，這樣組成化簡后的路徑合集Lmin={v1…v2，v1…v3，…}，同理對R進行化簡后得到新的路徑合集Rmin={vn…vn—1，vn…vn—2，…}。

在Lmin和Rmin中搜索終點重合的路徑組成一條由v1到vn的通路：s1=v1e1…en—1vn，當遍歷完Lmin和Rmin中所有重合的路徑后，會得到一個由v1到vn通路的集合S，設(shè)其有m項，則有：S={s1，s2，…，sm}，那么需要的最短路徑即為min（S）所對應(yīng)的路徑。通過這樣的方式，就可以將起點和終點之間的最短路徑求出。其基本的思路也可以用圖2來表示。

3.3 算法分析

有向圖的關(guān)聯(lián)矩陣表示的是有向圖中端點和邊的關(guān)系，雙向搜索算法就是利用關(guān)聯(lián)矩陣端點和邊的關(guān)系進行的一種搜索，與以往搜索算法相比主要有兩點改進：

第一是通過分析有向圖，刪除圖中與起點和終點無關(guān)的懸掛邊和懸掛點，縮小了矩陣的規(guī)模，從根本上避免了毫無必要的全圖遍歷，降低了算法的時間和空間復雜度。

4 結(jié) 論

本文提出了基于有向圖關(guān)聯(lián)矩陣的雙向搜索算法，對以往最短路徑的單向全遍歷算法進行了改進，將遍歷的周期減少了一半。該算法可有效提高優(yōu)化運輸路線的效率，降低優(yōu)化路線的時間。

1 張最良，李長生，趙文志，等.軍事運籌學[M].北京：軍事科學出版社，1993.

2 胡桐清.人工智能軍事應(yīng)用教程[M].北京：軍事科學出版社，1999.

3 汲萬峰，姜禮平，朱建沖，等.基于遺傳算法的航路規(guī)劃模型研究[J].軍事運籌與系統(tǒng)工程，2010，24（2）：52—55.