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

張 倩，丁根宏

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

隨著互聯(lián)網(wǎng)的普及和信息技術(shù)的高速發(fā)展，人類進(jìn)入了以網(wǎng)絡(luò)為主的信息時代?；贗nternet開展的電子商務(wù)已經(jīng)逐漸成為人們進(jìn)行商務(wù)活動的新模式。而物流是電子商務(wù)的核心力量，其快速、通暢是電子商務(wù)可以正常、順利進(jìn)行的一個重要保證［1］。

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

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

1 PDPTW描述及模型

根據(jù)上述對PDPTW問題的定義，給出該問題的總體描述:首先設(shè)定不限定配貨車輛的數(shù)目，并設(shè)負(fù)載Q都相同。設(shè)有1個中心車庫，需要對L個客戶點進(jìn)行配送服務(wù)，令i為變量，i=1，2，…，L。定義客戶點 i的裝貨地點為 i，卸貨地點為L+i，用點O和2L+1表示中心車場。由于所處的地理位置可能不能和點一一對應(yīng)，每個貨物都有各自的裝貨點和卸貨點，故有可能出現(xiàn)同一個點既是裝貨點又是卸貨點的情況。設(shè)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為正數(shù)時則為裝貨，為負(fù)數(shù)時則為卸貨，車輛k運輸?shù)娇蛻酎ci時的負(fù)載量為 zik。設(shè)點 i的裝貨時間窗口為［ei，li］，卸貨時間窗口為［eL+i，lL+i］，［e0，l0］表示車輛從中心車場開始的時間窗口，［e2L+1，l2L+1］表示回到中心車場的時間窗口。?i，j∈N*，tij代表從點 i到點 j的行駛時間，cij代表從點i到點j的行駛距離，si為車輛在客戶點i處的服務(wù)時間，ti為車輛在客戶點i開始服務(wù)的時間，ei表示為允許客戶點i服務(wù)的最早時間，li表示為允許客戶點i服務(wù)的最遲時間，這里［ei，li］表示一個時間窗。從中心車場派出車輛，為這些客戶點的需求進(jìn)行服務(wù)，并且在客戶點規(guī)定的時間窗內(nèi)進(jìn)行服務(wù)，最后要返回到到中心車場，要求找到使用車輛總費用最少的車輛路徑方案。

針對上面的描述，將引進(jìn)2個變量:

數(shù)學(xué)模型［7］為:

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

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

2 混合分組編碼智能算法

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

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

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

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

第1步隨機(jī)產(chǎn)生1個初始種群P，設(shè)定種群規(guī)模;

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

第3步在各個小組內(nèi)獨立進(jìn)行粒子群優(yōu)化迭代，迭代周期為t，對各小組進(jìn)行相同次數(shù)的種群變異和重組操作;

第4步更新各小組中各自的參數(shù);

第5步繼續(xù)進(jìn)行迭代，若滿足終止條件繼續(xù)第6步，否則返回第3步;

第6步對種群實施多策略分組編碼遺傳算法優(yōu)化，根據(jù)個體適應(yīng)度值排序保優(yōu);

第7步對選擇后的種群進(jìn)行交叉操作;

第8步交叉后的種群進(jìn)行選擇操作，排序保優(yōu);

第9步算法繼續(xù)進(jìn)行優(yōu)化，當(dāng)滿足算法的終止條件時停止，否則返回第6步。

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

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

3 實例計算

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

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

表1 每個支局的郵件量

表2 縣支局之間的距離 km

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

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

以總郵路里程最短為目標(biāo)，即

約束條件包括時間約束:

容量約束:

采用混合分組編碼智能算法進(jìn)行迭代。得到最優(yōu)路線為:

車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

注:括號內(nèi)表示郵車只經(jīng)過而不裝卸郵件。

將算法計算的結(jié)果與相同實例的其他算法計算結(jié)果進(jìn)行比較，得到如表3結(jié)果。

表3 各算法結(jié)果的比較

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

4 結(jié)束語

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

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

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

［3］李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法［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］.數(shù)學(xué)的實踐與認(rèn)識，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］葉海燕，陳毓靈，高鷹.分組粒子群優(yōu)化算法［J］.廣州大學(xué)學(xué)報，2007，6(2):64 －67.

［10］胡震宇，吳華玉，唐燕.郵政運輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度［J］.數(shù)學(xué)實踐與認(rèn)識，2008，38(14):210－221.

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