求解PDPTW的混合分組編碼智能算法

張 倩，丁根宏

(河海大學理學院，南京 211100)

隨著互聯網的普及和信息技術的高速發展，人類進入了以網絡為主的信息時代。基于Internet開展的電子商務已經逐漸成為人們進行商務活動的新模式。而物流是電子商務的核心力量，其快速、通暢是電子商務可以正常、順利進行的一個重要保證［1］。

車輛路徑問題(vehicle routing problem，VRP)［2］是物流配送系統中的關鍵環節，是在1959年由Dantzig和Ramser共同提出的。車輛路徑問題是近年來研究的一個熱點問題，其中最廣泛關注的問題如快遞問題中的線路優化問題、信件運輸與投遞問題等［3］。

PDPTW［4－5］是一類具有廣泛實際應用的優化組合問題。PDPTW是指一列車隊必須完成的運輸需求，裝貨點和卸貨點是組成運輸任務的2個需求要素。配送中心的每輛車從車庫出發，沿所選的最優化路線為客戶服務，以滿足客戶的運輸需求，并最終返回車庫。車輛在訪問客戶點時，必須依次服務所有需求，且滿足時間窗、負載的限制，并最終返回車庫。要用最大裝貨量和裝載貨物類型來限制每輛車，但是由于裝貨點和卸貨點所在的實際位置不同，所以車輛必須在給出的時間窗口范圍內訪問到每個客戶點。在解決PDPTW問題時，為了方便，定義其為整數線性規劃問題。由于PDPTW問題比VRP問題多了時間窗限制，所以PDPTW是對VRP的擴展，VRP又是TSP的一種推廣，而TSP已被證明是一個NP－hard問題［6］。因此，在解決PDPTW也具有許多類似的實際困難。由于PDPTW可以作為物流中運籌規劃問題的模型，在實際生活中的應用越來越多，從而引起國內外學者的廣泛關注。

1 PDPTW描述及模型

根據上述對PDPTW問題的定義，給出該問題的總體描述:首先設定不限定配貨車輛的數目，并設負載Q都相同。設有1個中心車庫，需要對L個客戶點進行配送服務，令i為變量，i=1，2，…，L。定義客戶點 i的裝貨地點為 i，卸貨地點為L+i，用點O和2L+1表示中心車場。由于所處的地理位置可能不能和點一一對應，每個貨物都有各自的裝貨點和卸貨點，故有可能出現同一個點既是裝貨點又是卸貨點的情況。設N={1，2，…，L，L+1，…，2L}為所有裝貨點與卸貨點的集合。P+={1，2，…，L}為裝貨點集合，P－={L+1，L+2，…，2L}為卸貨點集合，V={0，2L+1}為中心車場集合，N*=N∪V，M={1，2，…，m}為車輛集合。車輛在客戶點i的貨物裝卸量為qi，i∈N。要從點i運到點L+i，qi為正數時則為裝貨，為負數時則為卸貨，車輛k運輸到客戶點i時的負載量為 zik。設點 i的裝貨時間窗口為［ei，li］，卸貨時間窗口為［eL+i，lL+i］，［e0，l0］表示車輛從中心車場開始的時間窗口，［e2L+1，l2L+1］表示回到中心車場的時間窗口。?i，j∈N*，tij代表從點 i到點 j的行駛時間，cij代表從點i到點j的行駛距離，si為車輛在客戶點i處的服務時間，ti為車輛在客戶點i開始服務的時間，ei表示為允許客戶點i服務的最早時間，li表示為允許客戶點i服務的最遲時間，這里［ei，li］表示一個時間窗。從中心車場派出車輛，為這些客戶點的需求進行服務，并且在客戶點規定的時間窗內進行服務，最后要返回到到中心車場，要求找到使用車輛總費用最少的車輛路徑方案。

針對上面的描述，將引進2個變量:

數學模型［7］為:

在此模型中:式(1)、(2)是目標函數，分別是車輛的數目與每個車輛行駛距離;式(3)表示每個客戶點只被服務1次;式(4)、(5)表示每個客戶點只有1輛智能車進行服務;式(6)表示一個客戶的裝貨點與卸貨點必須由同一輛車進行服務;式(7)、(8)表示車輛必須從中心車場出發，最后要返回至中心車場;式(9)～(11)表示時間窗、前序;式(12)、(13)是車輛負載。

由于PDPTW是多目標優化問題，本文主要研究的優化目標為:① 使用車輛總數最小;② 行車總距離最小，即車輛行駛路線的總長度最小。

2 混合分組編碼智能算法

為減少PDPTW問題的計算復雜度，本文提出了一種混合分組編碼智能算法來求解此類問題。該算法結合了遺傳算法與粒子群算法在解決PDPTW時的優點。

粒子群算法是一種基于群體迭代的優化算法，該算法通過粒子個體之間的互相協助來尋找最優解。葉海燕等［9］提出了分組粒子群算法，這種算法其實是對粒子群算法的一種改進，該算法在運行時將種群分成若干個小組，對每個小組分別設置不同的算法參數進行搜索和優化。本文將繼續采用粒子群算法來搜索不容易搜索到而且精度較高的解。

遺傳算法是一種新型的全局優化搜索算法，它的基本思想就是模擬達爾文適者生存的自然選擇和遺傳機理的進化過程，對優化組合問題中的NP-hard問題的求解非常有效。商麗媛［7］在Giselher Pankratz提出的一種分組編碼遺傳算法［8］基礎上，給出了一種多策略分組編碼遺傳算法，并用該算法對國際上的算例集進行計算，結果表明，該算法的搜索性能比國際上的其他算法要好。本文將在混合分組編碼智能算法后期采用上述改進的分組編碼遺傳算法來進行優化求解。

混合分組編碼智能算法的步驟:

第1步隨機產生1個初始種群P，設定種群規模;

第2步先采用分組粒子群算法進行m次迭代，將初始種群P分成m個小組，在每個小組中對各自的參數進行初始化;

第3步在各個小組內獨立進行粒子群優化迭代，迭代周期為t，對各小組進行相同次數的種群變異和重組操作;

第4步更新各小組中各自的參數;

第5步繼續進行迭代，若滿足終止條件繼續第6步，否則返回第3步;

第6步對種群實施多策略分組編碼遺傳算法優化，根據個體適應度值排序保優;

第7步對選擇后的種群進行交叉操作;

第8步交叉后的種群進行選擇操作，排序保優;

第9步算法繼續進行優化，當滿足算法的終止條件時停止，否則返回第6步。

混合分組編碼智能算法流程見圖1。

圖1 混合分組編碼智能算法流程

3 實例計算

下面給出PDPTW中簡單的算例來分析混合分組編碼智能算法性能。

以某縣為例，縣郵政局M轄有16個郵政支局。該縣郵局M每天將從市局送來的郵件派送到所轄支局，并將由這些支局收寄的郵件運回縣局X。郵車每天早上9:00出發，最遲15:00回到縣局。郵車平均時速為30 km/h，郵車在支局卸裝郵件耗時5 min，每輛郵車最多容納65袋郵件。以縣局M及其所轄的16個支局為研究對象，在規定的時限以及郵車容量的約束下，以郵車數量最少、郵車所行駛的總郵路里程最短為優化目標，合理規劃郵路。表1為每個支局的郵件量。表2為縣支局之間的距離。

表1 每個支局的郵件量

表2 縣支局之間的距離 km

由表1中數據可知，寄達各支局的郵件量為176袋，而從支局收寄的郵件量為170袋。由于郵車最多容納65袋郵件，所以可計算出縣局至少需要3輛郵車才能滿足該縣的郵件運輸需求。得到最少郵車數量為3。

有些文獻中還考慮以空車率造成損失最小為優化目標，但經過測試發現，在最小化空車率造成損失時，雖然目標值有一定減小，但卻造成運行里程和時間的大幅增加，綜合考慮成本時仍是增加的。追求降低空車率會與追求最短里程相沖突，所以這里不予考慮空車率目標。

以總郵路里程最短為目標，即

約束條件包括時間約束:

容量約束:

采用混合分組編碼智能算法進行迭代。得到最優路線為:

車1路線:M—13—1—2—3—4—M

車2路線:M—10—9—8—7—5—6—(4)—M

車3路線:M—14—15—16—(15)—11—12—M

注:括號內表示郵車只經過而不裝卸郵件。

將算法計算的結果與相同實例的其他算法計算結果進行比較，得到如表3結果。

表3 各算法結果的比較

上述所有測試都是在PC(Inter，2.40 GHz)機上進行的。由表3可以看出，混合分組編碼智能算法求解的總花費時間最少，相對于改進型貪心算法［9］和改進蟻群算法［10］，路程縮短了，時間節省了，解的精度更高。

4 結束語

本文在描述PDPTW問題的基礎上，將粒子群算法與分組編碼遺傳算法相結合，提出了一種混合分組編碼智能算法。但該算法在計算PDPTW算例時，只是在相對簡單的算例上得到較好的解，而對國際上的某些算例集還不能達到理想的效果，所以還需對算法進行進一步的改進。

［1］劉華軍，劉軍.電子商務對物流及其管理的影響［J］.商品儲運與保護，2001(1):25－29.

［2］Dantzing G，Rasmer J.The truck dispatching problem［J］.Management science，1959，(6):80 －91.

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

［4］Savelsbergh M W P，Sol M.The General Pickup and Delivery Problem［J］.Transportation Science，1991(29):17－29.

［5］Dumas Y，Desrosiers J，Soumis F.The Pickup and Delivery Problem with Time Windows［J］.European Journal of Operational Research，1991(54):7 －22.

［6］Lenstra J K，Rinnooy K.Complexity of Vehicle Routing and Scheduling Problem［J］.Networks，1981，40(2):221－227.

［7］商麗媛，丁根宏.有時間窗裝卸問題的多策略分組編碼遺傳算法［J］.數學的實踐與認識，2010，40(2):8－14.

［8］Giselher Pankratz.A Gouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows［J］.Operatons Research，2005(27):21 －41.

［9］葉海燕，陳毓靈，高鷹.分組粒子群優化算法［J］.廣州大學學報，2007，6(2):64 －67.

［10］胡震宇，吳華玉，唐燕.郵政運輸網絡中的郵路規劃和郵車調度［J］.數學實踐與認識，2008，38(14):210－221.

［11］商麗媛.車輛路徑問題遺傳算法的設計與分析［D］.南京:河海大學，2006.