物流配送系統中大規模最短路徑算法的研究

［摘 要］ 在物流配送管理系統中，車輛路徑優化是一個典型的難題，而最短路徑算法是其基礎。傳統的最短路徑算法，如Dijkstra最短路徑算法因性能問題無法適應大規模的拓撲網絡和實時計算。本文在Dijkstra最短路徑算法的基礎上，在方向優先等改進算法的啟發下，設計和開發了基于GIS的大規模最短路徑算法。實驗表明，該算法受拓撲網絡規模的影響極小，能夠快速完成實時最短路徑計算。

［關鍵詞］ 最短路徑；車輛路徑優化；GIS；物流配送；Dijkstra最短路徑算法

［中圖分類號］F270.7［文獻標識碼］A［文章編號］1673-0194（2008）05-0067-03

一、物流配送路徑優化

隨著物流技術和應用的發展，物流配送過程中的車輛路徑優化問題（Vehicle Routing Problem，VRP）［1］成為一個研究的熱點。它是一個NP難題，不能得到解析解，通常只能通過各種啟發式算法得到近似解。物流配送路徑優化問題涉及因素眾多，各種因素之間關系十分復雜。

車輛路徑優化問題的定義依約束和目標的不同而有不同深度的定義。一般是指從一個配送中心用多輛車向多個需求網點送貨。配送中心和網點之間的位置和距離一定，網點的需求配貨量和車輛的容量一定，要求合理安排運輸路線，使得總運程最低，即總路徑最短，費用最少。通過調整約束和優化目標，問題的難度可以進一步提高。但無論如何，優化算法最終都基于網點（包括配送中心）之間的最短路徑。圖1是一個典型的物流配送路徑優化系統的流程圖。

從圖1可以看出，配送路徑優化系統區分為兩部分。左邊流程完成的任務包括：（1）根據GIS地圖數據提取道路、對相交道路進行分割、生成路段拓撲網絡，網絡的節點是路口，弧是節點之間的路段；（2）根據道路拓撲網絡計算任意兩個節點之間的最短路徑。將最短路徑生成過程預先執行的理由是最短路徑算法時空復雜度高，并且通常道路信息變更并不頻繁。右邊是配送路徑優化的流程。通常，VRP優化算法都含兩個過程：（1）生成滿足約束的多條路線；（2）對每條路線采用TSP優化算法繼續優化。這兩個過程都以節點之間的最短路徑作為基礎。因此，最短路徑算法在VRP問題中占有非常重要的地位。

但圖1描述的是一個理想的配送優化系統的流程，即假定路徑的屬性和最短路徑都不更新或更新不頻繁。而實際情況并非如此。如路況數據的變化，包括修路導致的道路不通、雨雪等導致的部分道路行駛難度系數變化以及臨時堵車等情況都將導致預先計算的最短路徑失效。另一方面，對于大規模的拓撲網絡結構，預存所有最短路徑需要非常大的空間，導致配送優化性能下降。

本文在研究各種用于VRP最短路徑算法的基礎上，綜合前人的研究成果，提出可行的基于GIS的大規模最短路徑算法。

二、最短路徑優化算法

最短路徑算法在1959年就已經提出，因其應用廣泛，是TSP、中國郵路問題等問題的子問題，成為運籌學和組合優化領域的熱點問題。目前該算法在國內外已經被廣泛深入研究。最短路徑算法也是VRP優化的基礎，因此，最短路徑算法的最新研究中也包括其在VRP優化中的改進。

1． 傳統最短路徑算法

通常，傳統的最短路徑優化算法是指Dijkstra和Floyd提出的兩個算法［2］。他們都采用圖作為路網拓撲的存儲結構。Dijkstra提出的算法按路徑長度遞增的次序產生最短路徑，實現從某個源點到其余各個節點的最短路徑，時間復雜度是O（n2）。Floyd提出的算法按路徑搜索試探產生最短路徑，時間復雜度也是O（n2），但該算法計算每一對頂點之間的最短路徑。如果需要得到任意兩個節點之間的最短路徑，Floyd算法更合適。國內外對于這兩個算法已經有很多的改進版本［1，3，4］。

2． 面向VRP的最短路徑算法

Dijkstra和Floyd提出的最短路徑優化算法考慮的拓撲網絡是抽象網絡，對于網絡節點和弧并沒有額外的限制。而在VRP問題中，拓撲網絡是路網，因此是平面網絡，且節點和弧都有各種可以用于進一步優化的屬性。人類在這種平面網絡的路由問題上，積累了很多經驗和知識，可以作為啟發式規則用于優化。另一方面，物流配送優化系統一般都是構建在GIS之上，路網在地圖上有直觀的體現。GIS提供的各種特性也都可以用于最短路徑優化。這些考慮利于減少最短路徑搜索過程中的搜索范圍，從而提高算法性能。文獻［3］提出一種直線化的改進Dijkstra算法，通過對臨時標記節點的堆排序使得搜索向目標節點快速逼近。雖然每次搜索的節點集合減少了，但每次計算時拓撲網絡的規模并沒有減少。Dijkstra的搜索策略是廣度優先，文獻［4］提出的算法采用方向優先的方式求兩點之間的最短距離，根據源點到終點的方向可以顯著減少搜索的中間節點，并且這種方式對VRP問題是可行的，因為網點集合構成的僅僅是龐大的路網拓撲網路的一個很小的子網。

三、基于GIS的大規模最短路徑優化算法

在Dijkstra算法及其改進算法的啟發下，本文設計了一種基于GIS的大規模最短路徑優化算法，以適應物流配送優化系統大規模路徑優化的需要。圖2是該算法的流程圖。

由圖2可以看出，算法分為兩部分，但明顯不同于圖1中的算法，生成道路拓撲網絡后并不預先生成最短路徑。而右邊的最短路徑算法是求兩個輸入節點A0和An之間的最短路徑L。以下是算法步驟的說明。

步驟1：根據輸入節點A0和An的經緯度坐標，通過GIS引擎進行直線分割，將直線段A1An等分為n段。設等分點依次是a1，a2，…，an-1。

步驟2：對ai（i=1，2，n-1），在拓撲網絡數據庫中選擇最近的節點，設為Ai。

步驟3：對（Ai，Ai+1）（i=0，2，n-1），在其外接圓包圍的節點集合內應用Dijkstra算法求最短路徑，設為Li。

（Ai，Ai+1）的外接圓定義為：圓心C=（Ai+Ai+1）/ 2，即Ai和Ai+1的中點；半徑r = mAi Ai+1 ，其中m為使得最短路徑存在的最小正整數。外接圓以及外接圓內節點的計算通過GIS引擎可以實現。

步驟4：拼接Li（i=0，2，n-1），作為A0和An之間的最短路徑L。

顯然，n和外接圓半徑r的選擇直接影響每次應用Dijkstra算法求最短路徑的復雜度。當n=1，r =+∞時，即等價于原Dijkstra算法。雖然本文采用外接圓，但理論上可以采用其他形式的外接形，只要包圍兩個端點，并以大概率保證兩個端點之間最短路徑歷經的節點都在其范圍內。雖然，本文算法也使用了直線化和方向的概念，但明顯不同于文獻［3］和［4］提出的算法：（1）每次計算的拓撲網絡規模本身顯著減少；（2）對拓撲網絡的直線分割利于并行快速實現最短路徑；（3）平面圖和GIS的功能得到充分體現。

四、結束語

本文在傳統Dijkstra算法的基礎上，在方向優先等改進算法的啟發下，提出了基于GIS的大規模最短路徑近似算法，以適應物流配送路徑實時優化的需要。該算法體現以下思想和特性：（1）大規模的拓撲網絡通過節點之間的直線分割，每次計算的拓撲網絡規模被顯著減少；（2）分割將拓撲網絡規模對最短路徑計算性能的影響降低到足夠低的程度；（3）Dijkstra算法之外的計算可以通過現有的GIS引擎（如Mapinfo，ArcGIS等）實現。算法分析表明該方法能夠降低大規模最短路徑計算的復雜性，使得最短路徑的實時計算成為可能。

主要參考文獻

［1］ 李軍，郭耀煌. 物流配送車輛優化調度理論與方法［M］. 北京： 中國物資出版社，2001.

［2］ 嚴蔚敏，吳偉民. 數據結構（C語言版） ［M］. 北京： 清華大學出版社，1997.

［3］ 王開義，趙春江，胥桂仙等. GIS領域最短路徑搜索問題的一種高效實現［J］. 中國圖像圖形學報：A版，2003，8（8）：951-956.

［4］ 張連蓬，劉國林，江濤，等. GIS路徑尋優的方向優先搜索法［J］. 測繪通報，2003，（12）：47-49.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”