帶時間窗裝卸貨問題的改進多策略分組編碼遺傳算法

郭東威，丁根宏，劉 偉

(1．周口師范學院數學與統計學院，河南 周口 466000；2．河海大學理學院，江蘇 南京 211100)

1 引言

帶時間窗裝卸貨問題(Pickup and Delivery Problem with Time Windows，PDPTW)是指為一個位于車場的車隊安排服務路徑來滿足客戶的裝卸貨及運輸需求。每個需求任務包括兩個需求點(客戶點)：一個裝貨點和一個卸貨點。每個需求點都有一個時間窗口，即在該點裝貨或卸貨的最早開始時間和最遲開始時間。車輛不能遲于最遲開始時間到達需求點，可以早于最早開始時間到達，早到的車輛需要等到最早開始時間才能進行服務。同一個需求任務必須由同一輛車進行服務，即完成一個需求任務是指同一車輛在規定的時間窗內先到該需求任務的裝貨點裝貨，再到其卸貨點卸貨。組成車隊的每輛車具有相同的最大負載量，且車輛數目足夠多，每輛車從車場出發，完成配送任務后返回車場。如何安排配送路徑，在滿足約束條件下完成所有需求任務，并且使得所需車輛數最少，行駛總路程最短，等待總時間最少。PDPTW在現實中已有廣泛的應用，如物流配送、公交路線安排等。

根據車輛數可以將PDPTW分為兩類：一類是單車帶時間窗裝卸貨問題(Single-vehicle Pickup and Delivery Problem with Time Windows，1-PDPTW)，指只有一輛車完成所有配送任務；一類是多車輛帶時間窗裝卸貨問題(Multi-vehicle Pickup and Delivery Problem with Time Windows，m-PDPTW)，指有多輛車共同完成所有配送任務。本文研究的PDPTW指的是m-PDPTW。PDPTW屬于組合優化中的NP-hard問題，求其最優解十分困難。已有文獻的求解方法大致可分為兩類：精確算法和啟發式算法。Psaraftis[1]和Desrosiers等[2]分別應用動態規劃算法求解了1-PDPTW。Dumas等[3]1991年應用分枝定界法成功解決了30個需求點以內的m-PDPTW。動態規劃算法及分枝定界算法只能求解小規模的PDPTW，求解大規模問題主要采用啟發式算法。2000年Nanry和Barnes[4]提出了求解PDPTW的禁忌搜索算法；Li和Lim[5]提出了禁忌模擬退火混合算法，在Solomon[6]的VRPTW算例基礎上構造了PDPTW算例，并求出了近似最優解；Jung和Haghani[7]2000年用遺傳算法快速有效的求解了小規模(30個需求點)的PDPTW，但是基本遺傳算法求解大規模的PDPTW效果較差。2002年Jih等[8]提出了家族競爭遺傳算法(FCGA)來求解1-PDPTW，2005年Pankratz[9]提出了求解PDPTW的分組編碼遺傳算法(Grouping Genetic Algorithm)，對規模為100個客戶點的標準算例進行求解取得了較好的結果。國內對PDPTW的研究相對較少，能夠查閱到的文獻非常有限。早期的研究成果主要有：藍伯雄和張躍[10]提出了求解PDPTW的概率式禁忌搜索算法，與非概率式禁忌搜索算法比較，提高了求解效率和精度；賈永基等[11]提出了一種快速禁忌搜索算法，該算法易于改進，可通過簡單的變化來求解多約束的PDPTW 問題。近年來的研究成果主要有：潘立軍和符卓[12-13]提出了一類時差插入檢測法，比已有的插入檢測法具有更快的檢測速度；2014年Ding Genhong等[14]為了對分組編碼遺傳算法中得到的近似最優解進一步優化，在分組編碼遺傳算法中增加了路徑調整策略，提出了多策略分組編碼遺傳算法(Multi-Strategy Grouping Genetic Algorithm，MSGGA)。此外，不少專家學者最近對一些變式問題進行了研究，2017年符卓等[15]用禁忌搜索算法求解了帶軟時間窗的需求依訂單拆分車輛路徑問題，顏瑞等[16]研究了二維裝箱約束的多車場帶時間窗的車輛路徑問題。縱觀國內的研究，不難發現所有文獻中求解的算例均為100或200個客戶點[12,14]或者是作者本人根據VRP算例構造的小規模算例[10-11]，像400個客戶點或更多客戶點的算例在已有文獻中尚未求解。因此，對于PDPTW還需要進一步進行深入的研究。

經研究發現文獻[9]中的組合交叉算子不宜減少車輛數，文獻[10]中提出的路徑調整策略均具有隨機性，針對這兩個問題本文提出了易位組合交叉算子、單車路徑重排策略及需求對換策略，并求解了400個客戶點的PDPTW標準算例。

2 PDPTW的數學模型

假設車輛的數目足夠多，每輛車的最大載貨量為Q。需求任務的個數為L，設需求任務i的裝貨地點為i，卸貨地點為L+i，配送中心用0和2L+1表示。這里不同的點可能代表相同的物理位置，比如某個需求任務的裝貨點和卸貨點可能在同一個物理位置(坐標相同)。設N={1,2,…,L,L+1,…,2L}為客戶點集，即所有裝貨點與卸貨點的集合。P+={1,2,…,L}為裝貨點集合，P-={L+1,L+2,…,2L}為卸貨點集合，M={1,2,…,m}為可調用車輛集，V={0,2L+1}為配送中心集，N*=N∪V表示客戶點與配送中心集。客戶點i的貨物需求量為qi,i∈N，qi的正負分別表示車輛在此裝貨和卸貨，如果是裝貨，則需要車輛把貨物從點i運送到點L+i。[ei,li]和[eL+i,lL+i]分別表示需求任務i的裝貨時間窗口和卸貨時間窗口，每輛車必須在時間窗[e0,l0]內從配送中心出發，在時間窗[e2L+1,l2L+1]內返回配送中心。對?i,j∈N*，tij代表從點i到點j的運輸時間，cij表示從點i到點j的距離。設zik表示車輛k行駛到客戶點i時的負載量，Aik表示車輛k到達客戶點i的時間，si表示車輛在客戶點i的服務時間，則Wik=max{ei-Aik,0}表示車輛k在客戶點i的等待時間，si+Wik表示車輛k在客戶點i的停留時間，ti+si+Wik表示車輛k離開客戶點i的時間。

定義變量：

PDPTW的數學模型

多目標函數：

minm

三個目標函數分別表示使用車輛數最少、總行駛路程最短、總等待時間最少。

約束條件1：每個客戶點只能由一輛車服務

約束條件2：每個客戶點只能被服務一次

約束條件3：變量xijk與yik之間滿足的關系

約束條件4：同一個需求任務必須被同一輛車服務，且裝貨在前卸貨在后

Aik≤AL+i,k，?i∈P+,?k∈M。

約束條件5：車輛必須從配送中心出發到某一裝貨點，最后從某一卸貨點返回至配送中心

約束條件6：時間窗限制

e0≤A0k≤l0，?k∈M；

Aik≤li，?i=1,2,…,2L+1,?k∈M；

約束條件7：車載容量限制

0≤zik≤Q，?i∈N,?k∈M；

zjk=xijk(zik+qi)≤Q，?i,j∈N,?k∈M。

3 求解PDPTW的改進多策略分組編碼遺傳算法

3.1 分組編碼方案

編碼方式是遺傳算法實現的關鍵，Falkenauer[17-18]提出了一種分組編碼方案，2005年Pankratz G[9]首次將這種分組編碼方案用于求解PDPTW，編碼方式描述如下。

分組編碼的每個個體(染色體)包含若干個基因，基因的個數就是所需的車輛數，每個基因代表安排給某一輛車的所有客戶點及滿足前序、負載、時間窗等約束的行駛路徑。因此，每個個體(染色體)都是問題的一個可行解。例如，在某個PDPTW問題中需要3輛車對7個需求任務服務，假設車輛1負責需求任務1、3、5，車輛2負責需求任務2、7，車輛3負責需求任務4、6。圖3.1就是分組編碼的示意圖，它表示包含3個基因的一個染色體(問題的一個可行解)。

圖3.1 分組編碼示意圖注：0表示車場，+i表示裝載點，-i表示卸貨點。

3.2 初始種群的生成及啟發式插入算法

初始種群的生成及交叉、變異算子中都要使用這種啟發式插入算法[9]，它保證了在產生解的過程中路徑的可行性。算法描述：1)選取未安排需求i；2)對個體中的所有單車路徑插入需求i，并檢驗插入的可行性(包括前序、負載、時間窗的限制)；3)計算所有可行插入方案各自增加的代價(行駛路程、等待時間)，選取代價最小的插入方案；4)如果當前沒有路徑可以插入需求i，則新增一輛車安排需求i；5)重復1)到4)，直到所有未安排的需求被插入。

3.3 排序保優操作

在求解最優路徑的迭代過程中，總希望獲得更多的適應度值較好的個體，為此本文在算法中對種群進行排序保優操作，即計算個體的適應度值，將一定個數的最優個體進行復制保留，直接作為下一代的個體，然后再進行下一步遺傳操作。本文中，每次經過遺傳算子(交叉和變異)得到的種群都要進行排序保優操作，使得適應度值好的個體被保留下來，進行繁殖遺傳到下一代。

3.4 交叉算子

交叉算子影響著遺傳算法的收斂速度和最優解的產生，好的交叉算子能夠加快算法的收斂速度和最優解的產生。交叉算子的設計一般依賴于編碼方式，本文改進了文獻[9]中的組合交叉算子，提出了一種易位組合交叉算子。

1.首先選取兩個個體作為父代，確定交叉基因片段。例如，假設有8個需要服務的需求任務，如圖3.2所示(省略車場0)，隨機確定兩個父代中需要交叉的基因片段。為方便表達，被選定的基因片段用方框框起來。

圖3.2 父代個體選取圖示

2.將父代1、父代2選中的基因片段易位，并分別插入到父代2最左端的位置和父代1最左端的位置，如圖3.3。交叉后會出現一部分需求任務被兩輛車服務的情況(如子代1中需求1和6，子代2中需求4)，而且有可能出現同一輛車被安排了兩條路徑(如子代1中的車輛1)。

圖3.3 易位組合交叉圖示

3.為消除需求任務和車輛重復的情況，將原父代中與插入基因片段中相同的需求任務取出，設為未安排狀態。同時，將與插入基因片段重復的車輛去掉，該車輛服務的需求任務設為未安排狀態。操作結果如圖3.4。

圖3.4 消除重復情況

4.按啟發式插入算法將這些未安排需求任務插入兩個子代中。一般，子代1中重復的需求被插入子代2中，子代2中重復的需求被插入到子代1中。重復需求被重新插入之后，去掉重復車輛后剩下的需求仍被插入到原來的子代中。在插入的過程中必要時可以增加額外的車輛以確保路徑的可行性。操作完成后可獲得兩個完整的子代，如圖3.5所示。

圖3.5 交叉子代圖

因為組合交叉法[9]是將父代1(父代2)選定的基因片段直接插入到父代2(父代1)中，如圖3.6所示，這個交叉操作在兩個父代中都增加了車輛，然后再進行3、4兩步的操作(消除重復)，因此最終交叉結果要比易位組合交叉的結果容易增加車輛。當然，兩種交叉方法的結果也都可能減少車輛。

圖3.6 組合交叉示意圖

3.5 變異算子

本文采用文獻[9]中的變異算子，其主要步驟為：1)從個體中隨機選擇若干個基因；2)刪除選中基因的車輛，同時這些車輛服務的客戶點設為未安排狀態；3)將這些未安排的客戶點用啟發式插入算法重新插入該個體中，必要時可以安排新的車輛。

3.6 路徑調整策略

本文采用兩種路徑調整策略，以增加算法的尋優效果。

A．單車路徑重排策略

算法描述：

begin

隨機選擇個體P中的某個基因(車輛路徑)i；

在路徑i中隨機選擇l個需求任務(2l個客戶點)進行滿足前序限制的全排列；

計算滿足約束條件的排列的代價，保留代價最小的排列，得到新個體P′；

end

B．需求對換策略

通過對比不同解的結構發現，交換個體P中兩條路徑中的需求，可以優化路徑。

算法描述：

begin

隨機選擇個體P中兩個基因(車輛路徑)i,j；

在路徑i,j中分別選出對換需求crossi,crossj；

交換crossi,crossj的位置；

if操作可行并能使代價減少

交換crossi,crossj的位置；

end

end

3.7 適應度函數

在遺傳算法中，適應度是區分種群中個體優劣的唯一標準，是算法進化的動力。一般適應度函數是根據優化的具體問題，按一定的規則由目標函數值轉化得到。

PDPTW問題比較復雜，一般存在多個優化目標，例如車輛數最少，行車總路程最短，總等待時間最少等。本文設計了一個帶權重的目標函數，即分別對總路程，車輛數加權求和作為目標函數。設kd為行駛總距離的權重，kv為車輛總數的權重。根據具體需要，可以靈活設置kd、kv的值，以達到所要側重的目的。一般認為，使用車輛數要比行駛距離重要的多，那么可以設置kv的值遠大于kd的值。本文設計的目標函數為：

根據對適應度函數的要求，適應度函數設計如下：

f=zmax-z，

其中，zmax是一個很大的數值，可以取目標函數值的一個上界，也可以取當前種群中或到目前為止目標函數值的最大值。

3.8 改進多策略分組編碼遺傳算法(IMSGGA)

本文根據上述步驟，包括啟發式產生初始種群、分組編碼、排序保優、易位組合交叉、變異、單車路徑重排策略、需求對換策略等設計了改進多策略分組編碼遺傳算法(IMSGGA)。在算法中分別對兩種調整策略設置了迭代參數，即在不同的迭代次數發生不同的調整策略，參數可以視情況具體調整。下面給出IMSGGA算法描述。

IMSGGA算法描述：

input：popsize(種群規模)，m(最大迭代次數)，m1，m2 (調整策略發生時的迭代次數)

begin

啟發式初始化種群P；

計算種群P中每個個體的適應度值，保存適應度值高的個體；

iteration=0；

while(iteration≠m)

對P中的個體進行交叉操作，產生新種群P′；

計算P′中個體的適應度值，排序保優；

ifiteration≥m1

對種群P′實施單車路徑重排策略，形成新種群P″；

else

對種群P′進行變異操作，形成新種群P″；

計算種群P″中個體適應度值，排序保優；

iteration++；

end

ifiteration≥m2

對當前種群實施需求對換策略；

iteration++

end

end

return種群中最優個體作為問題的最終解；

end

4 算法測試

4.1 算例說明

本文采用400個客戶點的國際通用算例集來測試本文算法的性能。算例集共包含60個算例，每個算例至少有400個客戶點。根據客戶點的分布情況分為以下幾類：lc1和lc2的客戶點分布呈聚集狀態，可分為若干聚集塊，lr1和lr2的客戶點分布散亂無規律可循，即它們的客戶點分布隨機，lrc1和lrc2的客戶點分布既有隨機性又有聚集性。

4.2 測試結果

對本文算法編程實現并在PC(Intel(R) Core(TM)，2.10GHz)機上運行。由于算法的本質具有一定的隨機性，對每個算例進行多次運算，取最好的結果與目前已知最好解進行比較。算法運行時種群規模設為10～200不等，迭代次數設為100～5000不等。實驗表明，有些算例種群規模設為10～30，迭代次數100～200，只需幾秒時間就得到了與目前相同的已知最優解，而有些算例種群規模設為30～200，迭代次數達5000次，依然沒有得到最優解。適應度函數中車輛數權重為10000，距離權重設為1。測試結果見表4.1，14個算例結果與目前最優解相同，4個算例lc2_4_3、lrc1_4_1、lrc2_4_2和lrc2_4_3的行駛總路程有所減少。算例符號說明，以lc2_4_3為例，它表示客戶點分布情況屬于lc類(客戶點分布呈聚集狀態)，4表示400個客戶點的算例，3表示lc類的第3個算例。

表4 1 400個客戶點算例結果比較

5 結語

本文研究了求解PDPTW的多策略分組編碼遺傳算法，主要改進了GGA的交叉算子和MSGGA的路徑調整策略，即提出了易位組合交叉算子、單車路徑重排策略及需求對換策略。基本的遺傳算法是基于種群的并行搜索機制，僅僅采用了選擇算子、交叉算子及變異算子來更新種群。路徑調整策略是基于個體的搜索機制，是對并行搜索機制很好的補充，有助于維持種群的多樣性及優異個體的產生。文中設計的路徑調整策略不僅適用于求解PDPTW，也同樣適用于求解其它類型的車輛路徑問題。通過求解400個客戶點的PDPTW通用算例集，將求解結果與已知最優解對比，結果表明了本文算法的有效性。但該算法并沒有得到所有算例的已知最優解，因此還需要進一步研究改進。我們相信在算法中增加合理的路徑調整策略可以提高算法的性能，在設計啟發式搜索算法中有良好的應用前景。此外，本文設計的算法易于改進，只需稍微改變就可以用來求解類似的問題。例如快遞公司帶時間窗的信件收發問題(CCPDPTW)、帶時間窗的電話叫車問題(DARPTW)、帶時間窗的殘疾人接送問題(HTPTW)、飛機航線規劃等。