禁忌搜索算法下求解TTRP的鄰域算子研究

邊星馳

(武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

甩掛運輸是指使用卡車牽引掛車完成貨物運輸，并在指定地點進行掛車的卸掛、拖帶等操作的一種貨物運輸方式。在甩掛運輸方式下，卡車可與掛車分離，這樣的協(xié)同方式使貨物的裝卸和運輸過程并行，簡化了貨物的裝卸作業(yè)環(huán)節(jié)，縮短了卡車和司機的等待時間，提高了車輛和司機的利用率[1]。在歐美等發(fā)達國家，甩掛運輸發(fā)展較為成熟，其在社會總運輸量中的占比達70%～80%[2]。受限于各種因素的影響，我國的甩掛運輸起步較晚，但近年來以較快的速度發(fā)展。2010年10月，國家發(fā)改委和交通運輸部制訂了《甩掛運輸試點工作實施方案》。在“十二五”期間交通運輸部在全國組織實施209個甩掛運輸試點項目，累計拉動社會投資約278.6億元，為全社會節(jié)省燃油約21萬t，節(jié)約物流成本近300億元。2016年交通運輸部制訂了《綜合運輸服務(wù)“十三五”發(fā)展規(guī)劃》，提出要推動甩掛運輸方式在我國的全面發(fā)展。因此，研究甩掛運輸對推動物流運輸走向集約化發(fā)展，提高運輸系統(tǒng)運行質(zhì)量和社會資源利用率等都具有重要的現(xiàn)實意義。

甩掛運輸路徑規(guī)劃問題(truck and trailer routing problem，TTRP)是傳統(tǒng)車輛路徑問題(VRP)的衍生問題，與VRP相比，TTRP中車輛和客戶均為異質(zhì)，使網(wǎng)絡(luò)中的路徑類型更為復(fù)雜，研究難度增加。TTRP的求解方法主要包括精確式算法和元啟發(fā)式算法兩類。

在甩掛運輸路徑規(guī)劃問題研究方面，BELENGUER等[3]提出利用整數(shù)規(guī)劃模型來解決單卡車的TTRP，并設(shè)計了幾種不同的卡車和掛車的分離方式，最后使用分支定價算法對該問題進行了求解。DREXL[4]提出了一種分支定價算法并用于求解GTTRP(generalized truck and trailer routing problem)，該算法基于動態(tài)規(guī)劃的標號算法實現(xiàn)。ROTHENBCHER等[5]針對帶時間窗的TTRP提出一種分支-價格-切割，并且使用該算法解決了兩個實際場景下的甩掛運輸路徑規(guī)劃問題。

受限于求解規(guī)模和靈活度，在求解TTRP時，精確式算法的使用和相關(guān)研究不及啟發(fā)式算法廣泛深入。在啟發(fā)式算法中，學(xué)者大多采用元啟發(fā)式算法，該算法可行解的質(zhì)量比一般啟發(fā)式算法更優(yōu)，具體包括禁忌搜索算法、模擬退火算法和變鄰域搜索算法等。

CHAO[6]最早提出標準TTRP的概念，構(gòu)造了21個通用的TTRP測試算例，并設(shè)計了基于禁忌搜索的算法框架。SCHEUERER[7]利用禁忌搜索算法求解標準TTRP，并在路徑構(gòu)建階段設(shè)計了T-Sweep和T-Cluster算法，提升了構(gòu)建階段的求解質(zhì)量。LIN等[8]首次采用了基于模擬退火的算法來求解TTRP，在文獻[6]構(gòu)造的21個測試數(shù)據(jù)集中更新了11個當(dāng)前最好解。王超等[9]設(shè)計了一種基于迭代變鄰域的下降算法(iterated variable neighborhood descent，IVND)來求解TTRP，在保證求解質(zhì)量的同時，大幅縮減了算法的求解時間。郝友文等[10]對遺傳算子在VRP中的應(yīng)用做了相關(guān)綜述，并按照選擇算子、交叉算子、變異算子3種算子類型展開描述。

綜上可知，現(xiàn)有針對TTRP的研究主要集中在算法的求解質(zhì)量和運行性能上，缺乏關(guān)于鄰域算子與求解結(jié)果的關(guān)系分析。為了探究鄰域算子與實驗結(jié)果的影響機制，筆者針對鄰域算子與元啟發(fā)式算法求解結(jié)果的影響關(guān)系，設(shè)計了基于禁忌搜索的兩階段算法來求解TTRP，最終通過對比實驗來探究鄰域算子與求解質(zhì)量的關(guān)系。

1 問題描述

標準TTRP模型的描述如下：有多輛卡車和多輛掛車，從中心倉庫出發(fā)，對需求和位置都已知的客戶進行服務(wù)?？ㄜ嚁?shù)和掛車數(shù)已知，掛車可以和任意卡車組合，組合后的車輛稱為完備車輛。由于道路寬度、法律法規(guī)等客觀條件的限制，客戶分為TCs客戶(truck customers)和VCs客戶(vehicle customers)兩類，前者只能單獨由卡車進行服務(wù)，后者既可單獨由卡車進行服務(wù)，也可由完整甩掛車進行服務(wù)。網(wǎng)絡(luò)模型可表示為G=(V,A)，其中V={0,1,2,…，n}為客戶點集合。由于存在兩類車輛和兩類客戶，故TTRP可以抽象出3種類型的路徑，3種路徑的示意如圖1所示。其中，純卡車路徑(PTR)可以服務(wù)TCs和VCs；完備車輛路徑(PVR)沒有子回路；帶子路的完備車輛路徑(CVR)，由一個甩掛運輸車路徑作為主路徑和若干純卡車路徑的子路徑組成。

圖1 TTRP的3種路徑示意圖

2 算法設(shè)計

2.1 算法框架

筆者采用兩階段算法，即在第一階段使用CPLEX和下降改進算法得出問題的初始解，然后使用禁忌搜索算法改進初始解。為了擴大鄰域搜索范圍，在下降改進階段和禁忌搜索階段使用3種不同的鄰域算子。CPLEX通過求解松弛的指派問題將每個客戶分配到某一類路徑上，禁忌搜索算法同時設(shè)置了基于歷史移動的禁忌規(guī)則和基于目標函數(shù)的禁忌規(guī)則，以避免搜索陷入局部最優(yōu)，跳出當(dāng)前鄰域，實現(xiàn)搜索空間的分散化。

在算法的開始階段先進行數(shù)據(jù)(數(shù)據(jù)來源于文獻[6])的讀取，數(shù)據(jù)讀取結(jié)束后進行松弛指派問題的求解，求解完成后每位客戶都會被分配至一條路徑上，依此進行路徑的構(gòu)建。此時構(gòu)建完成的路徑可能存在超載的情況，需要將路徑進行初步優(yōu)化，使不可行解轉(zhuǎn)化為可行解。該階段使用下降改進優(yōu)化算法，當(dāng)新的解具有更短的路徑長度時，接受該解為當(dāng)前最好解，直到不再出現(xiàn)新的更好解時，下降改進階段結(jié)束，將輸出解作為禁忌搜索階段的輸入。禁忌搜索又進一步分為集中搜索階段和分化搜索階段，以避免搜索陷入局部最優(yōu)，當(dāng)搜索滿足最終停止條件時結(jié)束整個算法。

2.2 生成初始路徑

初始路徑的生成通過構(gòu)造一個松弛指派問題來實現(xiàn)，模型的建立參照文獻[6]。松弛指派問題經(jīng)過CPLEX求解，路徑中的每一個客戶都完成了3種路徑中某一種具體路徑的分配，然后按照路徑類型分別進行路徑的構(gòu)建：①對于PTR和PVR，直接使用最小花費插入算法進行路徑構(gòu)造。②由于CVR包含主路徑和子回路，因此分兩部分進行構(gòu)造，主路徑上的VCs利用TSP(旅行商問題)的最小花費插入算法生成路徑。③對于子回路的生成，若已經(jīng)有子回路，則將TCs插入到已有的子回路中。若還不存在子回路，則將TCs連接到主路的VCs上，生成一條新的子回路。

2.3 下降改進

下降改進是一種局部搜索算法，從初始值開始沿一定方向搜索領(lǐng)域內(nèi)的解，直到到達該方向的最優(yōu)解。若存在更好解，則會繼續(xù)迭代；否則終止程序。下降改進算法和禁忌搜索算法的區(qū)別在于后者可以跳出局部最優(yōu)解，而前者不能。

鄰域解N(s)是指當(dāng)前解s的所有可能鄰解，通過對當(dāng)前解s應(yīng)用算子得到。實驗中引入單點移動算子、雙點交換算子和子路重構(gòu)算子3類算子，并在下降改進結(jié)束后使用2-OPT進行路徑內(nèi)優(yōu)化。

2.3.1 單點移動算子

單點移動算子是指在一個路徑中選擇一個客戶點，移動到另一條路徑中。在下降改進階段，移動的條件是該次移動減少了超載量或沒有增加路徑長度，或者在沒有增加超載量的前提下縮短了路徑長度。有以下兩類移動需要被排除：①將TCs移動到帶子路的完備車輛路徑的主路徑上或者完備車輛路徑上；②被移動的VCs是一個根節(jié)點即子路徑的根節(jié)點，作為掛車卸掛點的客戶點。

2.3.2 雙點交換算子

雙點交換算子是指選擇兩條路徑，并在每個路徑中選擇一個客戶點交換到另一條路徑中。移動的條件是交換后的兩條路徑的超載量都沒有增加，同時交換后的路徑中有一條超載量減少或者交換的代價為負值(也就是交換后的目標值小于交換前的目標值)。此處排除的移動同上述單點移動算子。

2.3.3 子路重構(gòu)算子

上述兩個算子都沒有進行子路徑根節(jié)點的移動，而子路重構(gòu)算子則是嘗試改變一條子路徑的根節(jié)點，以期縮短子路徑的長度。具體過程為：保持子路徑中客戶點不變，改變子路徑根節(jié)點的位置，即選擇主路徑中不同于最開始根節(jié)點的其他客戶點作為新的根節(jié)點，如果新的子路徑較之前的子路徑長度有所縮減，則接受此次變換。子路重構(gòu)的過程如圖2所示，其中子路徑的根節(jié)點由a變?yōu)閏。

圖2 子路重構(gòu)示意圖

2.4 禁忌搜索

2.4.1 集中搜索階段

集中搜索階段的主要目的是在當(dāng)前搜索域進行更優(yōu)解的搜索，此階段設(shè)置松弛系數(shù)δ的初始值為0.01，遞增步長λ為0.01，上限為0.10。下降改進階段得到的初始解，是集中搜索階段的輸入。如果有新的更好解出現(xiàn)，則對新的路徑實施下降改進優(yōu)化，然后判斷優(yōu)化后的解是否達到程序結(jié)束條件，如果集中搜索階段、分散搜索階段和集中搜索后的下降改進總運行次數(shù)超過30次，并且有10次沒有新的更好解產(chǎn)生，那么輸出最終解。

2.4.2 分散搜索階段

分散搜索階段的主要目的是使搜索跳出當(dāng)前的搜索域，以嘗試找到當(dāng)前搜索域之外的更好解，避免搜索過程陷入局部最優(yōu)解的狀態(tài)。此階段設(shè)置松弛系數(shù)δ的初始值為0.10，遞增步長λ為0.05。若出現(xiàn)新的可接受解，則結(jié)束該階段的搜索。

2.4.3 禁忌規(guī)則

禁忌規(guī)則包括基于目標值(objective-based tabu restriction，OTB)和基于訪問歷史(frequency-based tabu restriction，F(xiàn)TB)兩種。

OTB限定了禁忌搜索過程中解的值不一定要優(yōu)于當(dāng)前最好解，而是可以稍微大于當(dāng)前最好解。這里設(shè)置的松弛系數(shù)在集中搜索階段和分散搜索階段分別以不同的初始值與步長遞增。計算方式為：當(dāng)前解的目標值-當(dāng)前最好解的目標值<松弛系數(shù)×當(dāng)前最好解的目標值。松弛系數(shù)遞增的條件是當(dāng)前搜索域中不存在新的可接受解出現(xiàn)。

FTB是指如果當(dāng)前進行的移動，在禁忌表記錄的長度內(nèi)，就不再進行移動。禁忌表的長度隨機設(shè)定，為6～10之間的某個整數(shù)，禁忌表內(nèi)記錄的內(nèi)容包括當(dāng)前移動的客戶點i、目標移動路徑的根節(jié)點k和目標路徑的索引x，因為搜索過程中一旦發(fā)生移動，路徑都會變化，所以需要用根節(jié)點k和索引x來共同確定當(dāng)前移動的目標路徑。

2.4.4 鄰域算子

禁忌搜索部分的鄰域算子和下降改進階段的鄰域算子類似，但也有差異，禁忌搜索部分采用單點移動算子和雙點交換算子。

單點移動算子的移動條件較下降改進階段有所變化，執(zhí)行移動的判斷條件為：①插入新客戶點的路徑超載量未增加；②原路徑的超載量有所減少；③此次移動不觸發(fā)OTB禁忌；④此次移動不觸發(fā)FTB禁忌；⑤此次移動觸發(fā)了FTB禁忌，移動后解為新的最好解，當(dāng)候選移動滿足條件①②④或①②⑤或①③④或①③⑤時，則執(zhí)行該次移動為保證解的有效性，移動后的路徑超載量不能大于0。雙點交換算子和單點移動算子思路相同，需同時考慮兩條參與交換的路徑。

3 算例分析

3.1 測試環(huán)境及數(shù)據(jù)

計算機型號：華碩X550VC，CPU四核2.6 GHz，8 GB內(nèi)存；操作系統(tǒng)：Windows10；Python版本：3.6.9；Cplex版本：12.80；代碼運行環(huán)境：WSL(windows subsystem for linux)中的Ubuntu16.04。

為了研究算子不同的使用方式對結(jié)果的影響機制，使用3組測試數(shù)據(jù)，每組數(shù)據(jù)又包含2個算例。數(shù)據(jù)I：50個客戶，1個中心倉庫，5輛卡車，3輛掛車，卡車和掛車的運載量均為100。其中算例1中VCs和TCs的數(shù)量分別為38和12。算例2中VCs和TCs的數(shù)量分別為13和37。數(shù)據(jù)II：100個客戶，1個中心倉庫，8輛卡車，卡車運載量為150，4輛掛車，掛車運載量為100。其中算例3中VCs和TCs的數(shù)量分別為75和25，算例4中VCs和TCs的數(shù)量分別為25和75。數(shù)據(jù)III：199個客戶，1個中心倉庫，17輛卡車，卡車運載量為150，9輛掛車，掛車運載量為100。其中算例5中VCs和TCs的數(shù)量分別為150和49，算例6中VCs和TCs的數(shù)量分別為50和149。選擇3組數(shù)據(jù)的依據(jù)是算例的規(guī)模，根據(jù)客戶數(shù)可劃分為小規(guī)模、中等規(guī)模和大規(guī)模3類。算例數(shù)據(jù)的概況如表1所示。

表1 算例數(shù)據(jù)概況

3.2 實驗組別設(shè)置

組別A：下降改進階段鄰域算子設(shè)置相同，順序執(zhí)行。禁忌搜索階段：①組A1x只使用單點移動算子；②組D0x使用單點移動算子和雙點交換算子。

組別B：禁忌搜索階段鄰域算子設(shè)置相同，使用兩類算子，順序執(zhí)行。下降改進階段：①組B1x只使用單點移動算子；②組B2x使用單點移動算子和雙點交換算子；③組D0x使用單點移動算子、雙點交換算子和子路重構(gòu)算子。

組別C：鄰域算子的數(shù)目相同，下降改進階段使用三類算子，禁忌搜索階段使用兩類算子。各組執(zhí)行順序：①組C1x下降改進階段算子順序執(zhí)行，禁忌搜索階段算子逆序執(zhí)行；②組C2x下降改進階段算子逆序執(zhí)行，禁忌搜索階段算子順序執(zhí)行；③組C3x下降改進階段算子逆序執(zhí)行，禁忌搜索階段算子逆序執(zhí)行；④組D0x下降改進階段算子順序執(zhí)行，禁忌搜索階段算子順序執(zhí)行。其中，x為算例編號，即1～6；組別D為其余3個組的對照組；下降改進階段算子順序執(zhí)行為單點移動算子→雙點交換算子→子路重構(gòu)算子，反之為逆序執(zhí)行；禁忌搜索階段順序執(zhí)行為單點移動算子→雙點交換算子，反之為逆序執(zhí)行。數(shù)據(jù)I、數(shù)據(jù)II、數(shù)據(jù)III的實驗結(jié)果分別如表2～表4所示。

表2 數(shù)據(jù)I的實驗結(jié)果

表3 數(shù)據(jù)II的實驗結(jié)果

表4 數(shù)據(jù)III的實驗結(jié)果

3.3 結(jié)果分析

由表2～表4可知，此次最好實驗結(jié)果的平均BKS差值為10.5%，小規(guī)模與中等規(guī)模算例最好解的平均BKS差值為4.0%。雖與歷史最好解有差距，但整體的求解質(zhì)量是可靠的。

在路徑構(gòu)建階段，相同算例數(shù)據(jù)構(gòu)建后的路徑長度仍存在差異，這是由于路徑生成算法的隨機性造成的，隨機性的設(shè)置是為了增強算法搜索的多樣性。在禁忌搜索階段，6個算子A1x的最好解相比于D0x，平均有3.02%的差距，但在求解時間上少了21.7%。數(shù)據(jù)II和數(shù)據(jù)III中，B1x無法達成此階段的優(yōu)化目標，無法使超載量降為0。數(shù)據(jù)III中，B2x也無法將超載量降為0。數(shù)據(jù)I中，C1x組與A1x組的最好解差距不大。數(shù)據(jù)II中，C1x組與D0x組的最好解差距約為4%，求解時長也增加了3倍。數(shù)據(jù)I中，C2x組和C3x組下降改進階段的求解時長和路徑長度都差于D0x組，在最好解上也差于D0x組。數(shù)據(jù)II和數(shù)據(jù)III中，C2x組和C3x組都不能達到下降改進的優(yōu)化目標。

從以上結(jié)果可以看出，在下降改進階段，算子的數(shù)目不宜過少，算子過少無法達到下降改進階段不超載的目標。在數(shù)據(jù)I和數(shù)據(jù)II的實驗中，下降改進階段和禁忌搜索階段使用充足的算子，會得到更好的結(jié)果，但同時需要更長的求解時間。其中，下降改進階段若只使用兩類算子，雖然也能夠完成最終的搜索，但是降低了求解質(zhì)量并增加了禁忌搜索階段的求解時間。

根據(jù)不同算例在不同組別中下降改進階段結(jié)束后的路徑長度繪制折線圖，如圖3所示。根據(jù)不同算例在不同組別中，實驗最好解的路徑長度繪制折線圖，如圖4所示。其中，數(shù)字1～6為各個算例的編號。

圖3 下降改進階段路徑長度

圖4 實驗最好解的路徑長度

在實驗中，算子的使用數(shù)量與實驗結(jié)果質(zhì)量呈現(xiàn)正相關(guān)性，在不嚴格限制求解時間的情況下，應(yīng)盡量同時使用3類算子。同時，求解質(zhì)量與算子順序相關(guān)度較大，結(jié)果表明解的質(zhì)量受順序方式影響不大，受逆序方式影響較大，尤其在數(shù)據(jù)規(guī)模較大時(如數(shù)據(jù)II和數(shù)據(jù)III的C2、C3組)，求解質(zhì)量會受到極大影響，為保證求解質(zhì)量，建議使用順序方式執(zhí)行算子。

4 結(jié)論

(1)甩掛運輸?shù)穆窂揭?guī)劃問題是更接近實際同時具備重要研究意義的一個NP-hard問題。筆者為研究鄰域算子對求解結(jié)果的影響方式，建立了基于禁忌搜索的兩階段算法對標準TTRP進行了求解，引入不同類型的鄰域算子，并針對算子的使用方式進行了對比研究。

(2)實驗結(jié)果表明：鄰域算子的使用數(shù)量與實驗結(jié)果的質(zhì)量呈正相關(guān)性，在更強調(diào)求解質(zhì)量的條件下，應(yīng)在各優(yōu)化階段使用引入的所有算子；算子的執(zhí)行順序?qū)λ惴ǖ倪\行有較大影響，應(yīng)采用順序執(zhí)行方式，盡量避免使用逆序執(zhí)行方式。

(3)筆者的研究內(nèi)容對解決現(xiàn)實中的甩掛運輸路徑規(guī)劃問題有一定的參考價值，對元啟發(fā)式算法下鄰域算子的使用方式也提供了一定的指導(dǎo)依據(jù)。不足之處在于算法的求解質(zhì)量和求解性能與目前最優(yōu)的算法仍有一定差距，可以作為日后優(yōu)化的方向。