考慮廢物包裝時間的車輛回收路徑規(guī)劃方法

邢立寧 吳 健

國防科技大學

系統(tǒng)工程學院

湖南 長沙 410000

0 引 言

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

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

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

1 問題描述與數學模型

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

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

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

1）目標函數即車輛行駛總路程最短為

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

2）每個回收站點只被服務一次，

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

4）時間約束為

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

5）車輛容量約束為

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

2 算法設計

2.1 禁忌搜索算法

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

1）禁忌長度

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

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

2）編碼方式

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

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

3）插入算子

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

圖3 插入算子Fig. 3 Insertion operator

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

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

2.2 模因算法

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

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

2.2.1 遺傳算法

1）編碼方式

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

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

2）選擇策略

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

由式（9）可知，適應度越高的個體被選中進入下一代的概率越大。

3）交叉策略

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

圖7 交叉策略Fig. 7 Crossover strategy

完成交叉策略后，隨機選擇幾個位置，將表示起點和終點的0隨機插入，以完成了兩個完整解的交叉操作。本實驗中，交叉率設置為95%。

4）變異策略

變異策略采用兩點互換。隨機生成兩個基因位，并交換兩個基因位上的基因，如圖8所示。本實驗中，變異率設置為10%。

圖8 變異策略Fig. 8 Mutation strategy

2.2.2 爬山算法

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

3 案例分析

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

附表1 回收點的基本數據Table 1 Basic data of recycling site

3.1 禁忌搜索算法結果

禁忌搜索算法參數設置如下：總迭代次數為2000，禁忌長度分別為10, 20, 40。禁忌搜索算法運行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 模因算法結果

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

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。

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

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

表1 算法結果對比Table 1 Comparison of algorithm results

4 結語

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

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