帶時(shí)間窗裝卸貨問題的改進(jìn)多策略分組編碼遺傳算法

郭東威，丁根宏，劉 偉

(1．周口師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 周口 466000；2．河海大學(xué)理學(xué)院，江蘇 南京 211100)

1 引言

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

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

經(jīng)研究發(fā)現(xiàn)文獻(xiàn)[9]中的組合交叉算子不宜減少車輛數(shù)，文獻(xiàn)[10]中提出的路徑調(diào)整策略均具有隨機(jī)性，針對(duì)這兩個(gè)問題本文提出了易位組合交叉算子、單車路徑重排策略及需求對(duì)換策略，并求解了400個(gè)客戶點(diǎn)的PDPTW標(biāo)準(zhǔn)算例。

2 PDPTW的數(shù)學(xué)模型

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

定義變量：

PDPTW的數(shù)學(xué)模型

多目標(biāo)函數(shù)：

minm

三個(gè)目標(biāo)函數(shù)分別表示使用車輛數(shù)最少、總行駛路程最短、總等待時(shí)間最少。

約束條件1：每個(gè)客戶點(diǎn)只能由一輛車服務(wù)

約束條件2：每個(gè)客戶點(diǎn)只能被服務(wù)一次

約束條件3：變量xijk與yik之間滿足的關(guān)系

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

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

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

約束條件6：時(shí)間窗限制

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的改進(jìn)多策略分組編碼遺傳算法

3.1 分組編碼方案

編碼方式是遺傳算法實(shí)現(xiàn)的關(guān)鍵，F(xiàn)alkenauer[17-18]提出了一種分組編碼方案，2005年P(guān)ankratz G[9]首次將這種分組編碼方案用于求解PDPTW，編碼方式描述如下。

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

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

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

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

3.3 排序保優(yōu)操作

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

3.4 交叉算子

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

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

圖3.2 父代個(gè)體選取圖示

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

圖3.3 易位組合交叉圖示

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

圖3.4 消除重復(fù)情況

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

圖3.5 交叉子代圖

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

圖3.6 組合交叉示意圖

3.5 變異算子

本文采用文獻(xiàn)[9]中的變異算子，其主要步驟為：1)從個(gè)體中隨機(jī)選擇若干個(gè)基因；2)刪除選中基因的車輛，同時(shí)這些車輛服務(wù)的客戶點(diǎn)設(shè)為未安排狀態(tài)；3)將這些未安排的客戶點(diǎn)用啟發(fā)式插入算法重新插入該個(gè)體中，必要時(shí)可以安排新的車輛。

3.6 路徑調(diào)整策略

本文采用兩種路徑調(diào)整策略，以增加算法的尋優(yōu)效果。

A．單車路徑重排策略

算法描述：

begin

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

在路徑i中隨機(jī)選擇l個(gè)需求任務(wù)(2l個(gè)客戶點(diǎn))進(jìn)行滿足前序限制的全排列；

計(jì)算滿足約束條件的排列的代價(jià)，保留代價(jià)最小的排列，得到新個(gè)體P′；

end

B．需求對(duì)換策略

通過對(duì)比不同解的結(jié)構(gòu)發(fā)現(xiàn)，交換個(gè)體P中兩條路徑中的需求，可以優(yōu)化路徑。

算法描述：

begin

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

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

交換crossi,crossj的位置；

if操作可行并能使代價(jià)減少

交換crossi,crossj的位置；

end

end

3.7 適應(yīng)度函數(shù)

在遺傳算法中，適應(yīng)度是區(qū)分種群中個(gè)體優(yōu)劣的唯一標(biāo)準(zhǔn)，是算法進(jìn)化的動(dòng)力。一般適應(yīng)度函數(shù)是根據(jù)優(yōu)化的具體問題，按一定的規(guī)則由目標(biāo)函數(shù)值轉(zhuǎn)化得到。

PDPTW問題比較復(fù)雜，一般存在多個(gè)優(yōu)化目標(biāo)，例如車輛數(shù)最少，行車總路程最短，總等待時(shí)間最少等。本文設(shè)計(jì)了一個(gè)帶權(quán)重的目標(biāo)函數(shù)，即分別對(duì)總路程，車輛數(shù)加權(quán)求和作為目標(biāo)函數(shù)。設(shè)kd為行駛總距離的權(quán)重，kv為車輛總數(shù)的權(quán)重。根據(jù)具體需要，可以靈活設(shè)置kd、kv的值，以達(dá)到所要側(cè)重的目的。一般認(rèn)為，使用車輛數(shù)要比行駛距離重要的多，那么可以設(shè)置kv的值遠(yuǎn)大于kd的值。本文設(shè)計(jì)的目標(biāo)函數(shù)為：

根據(jù)對(duì)適應(yīng)度函數(shù)的要求，適應(yīng)度函數(shù)設(shè)計(jì)如下：

f=zmax-z，

其中，zmax是一個(gè)很大的數(shù)值，可以取目標(biāo)函數(shù)值的一個(gè)上界，也可以取當(dāng)前種群中或到目前為止目標(biāo)函數(shù)值的最大值。

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

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

IMSGGA算法描述：

input：popsize(種群規(guī)模)，m(最大迭代次數(shù))，m1，m2 (調(diào)整策略發(fā)生時(shí)的迭代次數(shù))

begin

啟發(fā)式初始化種群P；

計(jì)算種群P中每個(gè)個(gè)體的適應(yīng)度值，保存適應(yīng)度值高的個(gè)體；

iteration=0；

while(iteration≠m)

對(duì)P中的個(gè)體進(jìn)行交叉操作，產(chǎn)生新種群P′；

計(jì)算P′中個(gè)體的適應(yīng)度值，排序保優(yōu)；

ifiteration≥m1

對(duì)種群P′實(shí)施單車路徑重排策略，形成新種群P″；

else

對(duì)種群P′進(jìn)行變異操作，形成新種群P″；

計(jì)算種群P″中個(gè)體適應(yīng)度值，排序保優(yōu)；

iteration++；

end

ifiteration≥m2

對(duì)當(dāng)前種群實(shí)施需求對(duì)換策略；

iteration++

end

end

return種群中最優(yōu)個(gè)體作為問題的最終解；

end

4 算法測(cè)試

4.1 算例說明

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

4.2 測(cè)試結(jié)果

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

表4 1 400個(gè)客戶點(diǎn)算例結(jié)果比較

5 結(jié)語

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