邢立寧 吳 健

國防科技大學(xué)

系統(tǒng)工程學(xué)院

湖南 長沙 410000

0 引 言

隨著人們環(huán)保意識(shí)的增強(qiáng)和一系列新的環(huán)境保護(hù)法律法規(guī)的出臺(tái)，綠色物流成為現(xiàn)代物流可持續(xù)發(fā)展的必然之路。合理規(guī)劃車輛路徑是實(shí)現(xiàn)綠色物流的關(guān)鍵環(huán)節(jié)[1-3]。

車輛路徑規(guī)劃問題（vehicle routing problem，VRP）是指：合理調(diào)度一定數(shù)量的車輛通過一系列的收貨點(diǎn)和發(fā)貨點(diǎn)，在滿足相應(yīng)約束條件（車輛容量、時(shí)間窗口等）下，達(dá)到運(yùn)輸總費(fèi)用最低、路程最短等目標(biāo)[4-5]。在此基礎(chǔ)上，多個(gè)學(xué)者延伸出多個(gè)問題的變種，主要包括：帶時(shí)間窗的車輛路徑規(guī)劃問題（vehicle routing problem with time window，VRPTW），加入服務(wù)客戶的時(shí)窗約束，即服務(wù)客戶的時(shí)間在一定范圍內(nèi)；與車型相關(guān)的車輛路徑規(guī)劃問題（mixed fleet vehicle routing problem，MFVRP ），考慮負(fù)責(zé)運(yùn)輸?shù)能囕v屬性（容量、速度）不同；帶多車場的車輛路徑規(guī)劃問題（multi-depot vehicle routing problem，MDVRP），是指有多個(gè)車場同時(shí)為多個(gè)客戶提供服務(wù)，在滿足客戶需求的前提下，使總運(yùn)輸成本最??；隨機(jī)車輛路徑規(guī)劃問題（stochastic vehicle routing problem，SVRP），涉及運(yùn)輸中遇到的不確定信息，比如訂單到達(dá)隨機(jī)、服務(wù)時(shí)間不確定等。這些問題多數(shù)從收發(fā)貨點(diǎn)數(shù)量、車輛數(shù)量、收發(fā)貨方式、用戶需求等角度研究車輛路徑規(guī)劃問題，較少從物品本身性質(zhì)來規(guī)劃車輛路徑。根據(jù)《中華人民共和國固體廢物污染環(huán)境防治法》第八十三條之規(guī)定“運(yùn)輸危險(xiǎn)廢物，應(yīng)當(dāng)采取防止污染環(huán)境的措施，并遵守國家有關(guān)危險(xiǎn)貨物運(yùn)輸管理的規(guī)定”，液體、半固體等危險(xiǎn)廢物需進(jìn)行適當(dāng)?shù)陌b并貼有危險(xiǎn)廢物標(biāo)簽后，才能進(jìn)行收集、貯存、運(yùn)輸。因此研究廢物運(yùn)輸路徑規(guī)劃問題時(shí)，可將包裝時(shí)間考慮進(jìn)來。

基本的車輛路徑規(guī)劃問題已經(jīng)被證明是NP-Hard問題，即不存在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解的算法。因此更復(fù)雜的車輛路徑規(guī)劃問題同樣不存在多項(xiàng)式時(shí)間內(nèi)可求得精確解的算法[6]。國內(nèi)外學(xué)者求解車輛路徑規(guī)劃問題的方法大致分為精確算法、啟發(fā)式算法以及元啟發(fā)式算法3類。精確算法是以分支定界、動(dòng)態(tài)規(guī)劃為典型的算法[7-8]。此類算法能從理論上求得最優(yōu)解，但局限性在于只適用于小規(guī)模場景，擴(kuò)展性不足，并且簡化了問題約束，無法滿足實(shí)際工程需要。啟發(fā)式算法有距離越近越優(yōu)先、沖突消解和任務(wù)分配等算法，此類算法能夠在短時(shí)間內(nèi)生成可行的路徑方案，但求解策略較為簡單，解質(zhì)量較低，無法提升資源的使用效率[9]。元啟發(fā)式算法是以遺傳算法、蟻群算法、粒子群算法為典型的算法[10-11]，此類算法是通過模擬自然界生物種群演化機(jī)理和群體行為，對問題進(jìn)行迭代尋優(yōu)，能在一定時(shí)間內(nèi)生成較優(yōu)解，因而在車輛路徑規(guī)劃問題中應(yīng)用較為廣泛?；诖?，本文研究廢物回收的車輛路徑規(guī)劃問題時(shí)，考慮廢物包裝時(shí)間，并構(gòu)建問題數(shù)學(xué)模型，設(shè)計(jì)兩種算法即禁忌搜索算法和模因算法進(jìn)行求解。

1 問題描述與數(shù)學(xué)模型

考慮廢物包裝時(shí)間的車輛路徑規(guī)劃問題描述如下：1個(gè)回收中心點(diǎn)和N個(gè)回收站點(diǎn)，回收中心點(diǎn)擬派K輛車回收廢物，所有車輛均從回收中心點(diǎn)出發(fā)，最后到達(dá)回收中心點(diǎn)。該問題可用G=(V,E)的有向連通圖表示（見圖1），V表示回收中心點(diǎn)和回收站點(diǎn)的集合，E表示圖中所有邊的集合。圖1中有3條車輛行駛路徑，分別為0→2→7→0，0→6→1→0，0→5→4→3→0。

圖1 車輛路徑規(guī)劃示意圖Fig. 1 Vehicle route diagram

本車輛路徑規(guī)劃問題的數(shù)學(xué)模型如下：

1）目標(biāo)函數(shù)即車輛行駛總路程最短為

式中：cij為站點(diǎn)i與j之間的距離；xijk為模型的決策變量，取值為0或1，xijk=1表示第k輛車服務(wù)完站點(diǎn)i之后立馬服務(wù)站點(diǎn)j，否則為0。為了簡化計(jì)算，假設(shè)車輛行駛速度為1，則車輛從站點(diǎn)i到站點(diǎn)j的時(shí)間tij與距離cij相等。

2）每個(gè)回收站點(diǎn)只被服務(wù)一次，

3）車輛均從回收中心點(diǎn)出發(fā)，最后到達(dá)回收中心點(diǎn)，即

4）時(shí)間約束為

式中：si為廢物包裝的時(shí)間；wik、wjk分別為第k車輛在第i個(gè)和第j個(gè)站點(diǎn)的開始包裝時(shí)間；aj、bj分別為站點(diǎn)j接受廢物回收的最早、最晚時(shí)間。當(dāng)車輛到達(dá)站點(diǎn)j的時(shí)間小于aj，則必須等待；當(dāng)車輛到達(dá)站點(diǎn)j的時(shí)間超過bj，則需放棄該站點(diǎn)。

5）車輛容量約束為

式中：di為站點(diǎn)i的廢物容量；Ck為第k輛車容量。

2 算法設(shè)計(jì)

2.1 禁忌搜索算法

禁忌搜索（tabu search，TS）算法是由Glover于1986年提出的一種帶有記憶策略的局部搜索算法。禁忌算法以傳統(tǒng)爬山算法為基礎(chǔ)開展搜索優(yōu)化，并通過禁忌表記錄優(yōu)化過程中的局部最優(yōu)解或產(chǎn)生局部最優(yōu)解的操作，以避免對局部最優(yōu)空間的重復(fù)搜索，達(dá)到跳出局部最優(yōu)、開辟優(yōu)質(zhì)解空間的效果。

1）禁忌長度

在禁忌搜索算法中，禁忌長度即禁忌解集的大小是影響算法性能的主要因素。為增強(qiáng)算法在不同問題規(guī)模的適應(yīng)能力，設(shè)禁忌長度為任務(wù)集T規(guī)模的某一比例。禁忌對象直接為解，即回收路徑總長度。

式中αT為比例系數(shù)，取值為0.1～0.3。

2）編碼方式

編碼采取實(shí)數(shù)編碼方式。每輛車的行駛路徑單獨(dú)編碼，該編碼方式更加簡潔直觀。兩輛車的行駛路徑編碼如圖2所示，車輛1的行駛路徑為0→1→2→3→5→0，車輛2的行駛路徑為0→4→6→0。

圖2 解的編碼Fig. 2 The coding of the solution

3）插入算子

采用插入算子產(chǎn)生新解，如圖3所示。圖中，選擇路徑1中回收站點(diǎn)3插入到路徑2中回收站點(diǎn)6的后面，以產(chǎn)生新解。插入算子完全遍歷當(dāng)前解得到的解集即為鄰域。選取鄰域最好解或者非禁忌最好解作為下一迭代的當(dāng)前解。

圖3 插入算子Fig. 3 Insertion operator

禁忌搜索算法流程如圖4所示。

圖4 禁忌搜索算法流程圖Fig. 4 The flow chart of tabu search algorithm

2.2 模因算法

采用遺傳算法與局部搜索算法相結(jié)合的模因算法解決廢物回收車輛路徑規(guī)劃問題。遺傳算法能夠保證解的多樣性，但不能保證求得一個(gè)較優(yōu)解，而局部搜索算法即爬山算法可在遺傳算法的基礎(chǔ)上，對解進(jìn)行鄰域搜索，實(shí)現(xiàn)解的多樣性與集中性。算法流程如圖5所示。

圖5 模因算法流程圖Fig. 5 The flow chart of memetic algorithm

2.2.1 遺傳算法

1）編碼方式

個(gè)體編碼采取實(shí)數(shù)編碼方式。為了方便遺傳算法的交叉變異操作，采取與圖3不同的的編碼方式，將所有車輛的行駛路徑進(jìn)行統(tǒng)一編碼，當(dāng)作一個(gè)個(gè)體，如圖6所示。圖中，節(jié)點(diǎn)2, 3為一條路徑，節(jié)點(diǎn)4為一條路徑，節(jié)點(diǎn)5, 1, 6為一條路徑，其中0表示路徑的起點(diǎn)和終點(diǎn)。

圖6 解的編碼Fig. 6 The coding of the solution

2）選擇策略

選擇策略采用輪盤賭策略。假設(shè)共有N個(gè)個(gè)體，第i個(gè)個(gè)體的適應(yīng)度為fits(i)，第i個(gè)個(gè)體被選擇的概率為

由式（9）可知，適應(yīng)度越高的個(gè)體被選中進(jìn)入下一代的概率越大。

3）交叉策略

交叉策略采取部分交叉映射（partially mapped crossover，PMX）。種群中的個(gè)體隨機(jī)進(jìn)行兩兩配對，配對成功的兩個(gè)個(gè)體作為父代1和父代2進(jìn)行交叉操作。首先選兩個(gè)交叉點(diǎn)，交換中間部分，確定映射關(guān)系，最后將未換部分按映射關(guān)系恢復(fù)合法性，具體操作如圖7所示。

圖7 交叉策略Fig. 7 Crossover strategy

完成交叉策略后，隨機(jī)選擇幾個(gè)位置，將表示起點(diǎn)和終點(diǎn)的0隨機(jī)插入，以完成了兩個(gè)完整解的交叉操作。本實(shí)驗(yàn)中，交叉率設(shè)置為95%。

4）變異策略

變異策略采用兩點(diǎn)互換。隨機(jī)生成兩個(gè)基因位，并交換兩個(gè)基因位上的基因，如圖8所示。本實(shí)驗(yàn)中，變異率設(shè)置為10%。

圖8 變異策略Fig. 8 Mutation strategy

2.2.2 爬山算法

爬山算法是從當(dāng)前的節(jié)點(diǎn)開始，和周圍鄰居節(jié)點(diǎn)的值進(jìn)行比較，然后不斷向有提升的方向前進(jìn)。本文采取首次改進(jìn)（ first-improvement）策略的爬山算法。首次改進(jìn)策略是接受搜索過程中出現(xiàn)的第一個(gè)改進(jìn)解。如當(dāng)前解為[0, 2, 3, 0, 4, 0, 5, 1, 6, 0]，由于開始位置與結(jié)束位置都必須為0，因此從第二個(gè)節(jié)點(diǎn)開始嘗試兩兩節(jié)點(diǎn)依次進(jìn)行交換，即(2, 3), (2, 0),…, (2, 6),(3, 0), …, (1, 6)，交換后計(jì)算解的提升情況，如果有提升，則接受此解。如2和6交換可得到有提升的解，則當(dāng)前解變成[0, 6, 3, 0, 4, 0, 5, 1, 2, 0]。此時(shí)下一輪搜索序列變更為(6, 3), (6, 0),…, (6, 1), (3, 0), …, (1,2)，重新開始搜索并接受第一個(gè)改進(jìn)解。爬山算法的終止條件設(shè)置為當(dāng)某次提升后在所有鄰域中都找不到改進(jìn)解。

3 案例分析

某制造企業(yè)為提高資源利用率，給社會(huì)環(huán)境和企業(yè)帶來可觀的經(jīng)濟(jì)效益，需對某產(chǎn)品的廢物進(jìn)行回收。根據(jù)前期市場售賣產(chǎn)品情況，100個(gè)站點(diǎn)有產(chǎn)品廢物，為此該企業(yè)建立了1個(gè)回收中心點(diǎn)。各站點(diǎn)的地理位置、廢物質(zhì)量以及所需包裝時(shí)間見附表1，其中節(jié)點(diǎn)0為回收中心點(diǎn)，剩余100個(gè)節(jié)點(diǎn)為回收站點(diǎn)。

附表1 回收點(diǎn)的基本數(shù)據(jù)Table 1 Basic data of recycling site

3.1 禁忌搜索算法結(jié)果

禁忌搜索算法參數(shù)設(shè)置如下：總迭代次數(shù)為2000，禁忌長度分別為10, 20, 40。禁忌搜索算法運(yùn)行10次，最好解如下：

回收路徑1: 0→45→83→99→94→96→0；

回收路徑2: 0→27→31→88→7→0；

回收路徑3: 0→40→53→26→0；

回收路徑4: 0→62→11→90→10→0；

回收路徑5: 0→2→21→73→41→56→4→0；

回收路徑6: 0 →14→44→38→43→58→0；

回收路徑7: 0→36→47→19→8→46→17→0；

回收路徑8: 0→12→76→78→34→35→77→0；

回收路徑9: 0→65→71→9→66→1→0；

回收路徑10: 0→63→64→59→48→0；

回收路徑11: 0→28→29→79→50→68→0；

回收路徑12: 0→39→23→67→55→25→0；

回收路徑13: 0→33→81→3→54→24→80→0；

回收路徑14: 0→69→30→51→20→32→70→0；

回收路徑15: 0→95→98→61→86→91→100→0；

回收路徑16: 0→82→18→84→60→89→0；

回收路徑17: 0→72→75→22→74→0；

回收路徑18: 0→52→6→0；

回收路徑19: 0→92→42→15→87→57→97→0；

回收路徑20: 0→59→5→16→85→37→93→0。

3.2 模因算法結(jié)果

模因算法、遺傳算法、爬山算法的迭代次數(shù)設(shè)置為100代，模因算法、遺傳算法的種群規(guī)模設(shè)置為100，交叉率為95%，變異率為10%。通過先驗(yàn)實(shí)驗(yàn)，發(fā)現(xiàn)在100次迭代過程中加入爬山算法與在最后迭代的10代中加入爬山算法的結(jié)果相差不大，但在最后迭代的10代中加入爬山算法時(shí)，算法時(shí)間有了巨大的提升。因此，本文選擇在最后迭代的10代中加入爬山算法。模因算法運(yùn)行10次，其中一個(gè)解的表達(dá)方式如下：

0→96→13→92→76→80→54→0→21→81→78→33→24→55→93→0→28→4→20→66→65→9→68→75→72→37→16→84→85→2→26→8→49→70→6→59→7→18→77→58→97→60→32→35→12→71→79→34→29→30→63→62→43→57→23→74→0→52→22→73→67→39→46→86→38→98→61→95→88→11→64→90→17→47→19→69→87→56→40→89→83→27→45→36→3→0→100→44→42→5→1→51→50→91→15→94→99→14→82→31→25→41→10→48→53→0。

該解可解碼為：

回收路徑1：0→96→13→92→76→80→54→0；

回收路徑2：0→21→81→78→33→24→55→93→0；

回收路徑3：0→28→4→20→66→65→9→68→75→72→37→16→84→85→2→26→8→49→70→6→59→7→18→77→58→97→60→32→35→12→71→79→34→29→30→63→62→43→57→23→74→ 0；

回收路徑4：0→52→22→73→67→39→46→86→38→98→61→95→88→11→64→90→17→47→19→69→87→56→40→89→83→27→45→36→3→0；

回收路徑5：0→100→44→42→5→1→51→50→91→15→94→99→14→82→31→25→41→10→48→53→0。

爬山算法、遺傳算法和模因算法的算法運(yùn)行時(shí)間和距離如表1所示，距離對比如圖9所示。由表1和圖9可知，在算法運(yùn)行時(shí)間方面，模因算法相較于另外兩種算法表現(xiàn)較差，但在求解效果上，每種算法的表現(xiàn)均較穩(wěn)定，在解的質(zhì)量方面，模因算法所求解遠(yuǎn)遠(yuǎn)好于遺傳算法和爬山算法，普遍提升了30%以上。

圖9 距離對比Fig. 9 Comparison of distance

表1 算法結(jié)果對比Table 1 Comparison of algorithm results

4 結(jié)語

本文構(gòu)建了考慮廢物包裝時(shí)間的車輛回收路徑問題的模型，并設(shè)計(jì)了禁忌搜索算法與模因算法求解該問題。結(jié)果表明：在算法運(yùn)行時(shí)間上，模因算法稍遜色一點(diǎn)，但在求解質(zhì)量上，禁忌搜索算法與模因算法均優(yōu)于爬山算法、遺傳算法。

在未來的研究工作中，將在現(xiàn)有算法框架的基礎(chǔ)上，一方面集成更多的進(jìn)化算法（蟻群算法、粒子群算法）與局部搜索算法（模擬退火算法等），另一方面考慮多種不同性質(zhì)的物品包裝，以豐富車輛回收路徑問題的研究方法。