邢立寧 吳 健

國防科技大學

系統(tǒng)工程學院

湖南 長沙 410000

0 引 言

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

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

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

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

考慮廢物包裝時間的車輛路徑規(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ī)劃問題的數(shù)學模型如下：

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

式中：cij為站點i與j之間的距離；xijk為模型的決策變量，取值為0或1，xijk=1表示第k輛車服務完站點i之后立馬服務站點j，否則為0。為了簡化計算，假設(shè)車輛行駛速度為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 算法設(shè)計

2.1 禁忌搜索算法

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

1）禁忌長度

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

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

2）編碼方式

編碼采取實數(shù)編碼方式。每輛車的行駛路徑單獨編碼，該編碼方式更加簡潔直觀。兩輛車的行駛路徑編碼如圖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中回收站點3插入到路徑2中回收站點6的后面，以產(chǎn)生新解。插入算子完全遍歷當前解得到的解集即為鄰域。選取鄰域最好解或者非禁忌最好解作為下一迭代的當前解。

圖3 插入算子Fig. 3 Insertion operator

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

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

2.2 模因算法

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

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

2.2.1 遺傳算法

1）編碼方式

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

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

2）選擇策略

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

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

3）交叉策略

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

圖7 交叉策略Fig. 7 Crossover strategy

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

4）變異策略

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

圖8 變異策略Fig. 8 Mutation strategy

2.2.2 爬山算法

爬山算法是從當前的節(jié)點開始，和周圍鄰居節(jié)點的值進行比較，然后不斷向有提升的方向前進。本文采取首次改進（ first-improvement）策略的爬山算法。首次改進策略是接受搜索過程中出現(xiàn)的第一個改進解。如當前解為[0, 2, 3, 0, 4, 0, 5, 1, 6, 0]，由于開始位置與結(jié)束位置都必須為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)，重新開始搜索并接受第一個改進解。爬山算法的終止條件設(shè)置為當某次提升后在所有鄰域中都找不到改進解。

3 案例分析

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

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

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

禁忌搜索算法參數(shù)設(shè)置如下：總迭代次數(shù)為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 模因算法結(jié)果

模因算法、遺傳算法、爬山算法的迭代次數(shù)設(shè)置為100代，模因算法、遺傳算法的種群規(guī)模設(shè)置為100，交叉率為95%，變異率為10%。通過先驗實驗，發(fā)現(xiàn)在100次迭代過程中加入爬山算法與在最后迭代的10代中加入爬山算法的結(jié)果相差不大，但在最后迭代的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可知，在算法運行時間方面，模因算法相較于另外兩種算法表現(xiàn)較差，但在求解效果上，每種算法的表現(xiàn)均較穩(wěn)定，在解的質(zhì)量方面，模因算法所求解遠遠好于遺傳算法和爬山算法，普遍提升了30%以上。

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

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

4 結(jié)語

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

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