多車型多車槽VRP的混合導(dǎo)引反應(yīng)式禁忌搜索算法

王 茜，吉清凱, ，胡祥培

?

多車型多車槽VRP的混合導(dǎo)引反應(yīng)式禁忌搜索算法

王 茜1，吉清凱1, 2，胡祥培2

（1.中山大學管理學院，廣東廣州，510275；2.大連理工大學系統(tǒng)工程研究所，遼寧大連，116023）

多車槽多車型VRP問題在燃油、食品等行業(yè)的應(yīng)用變得越來越普遍。本文充分考慮多車槽多車型雙重屬性，在構(gòu)建HFFMCVRP的三下標流數(shù)學模型基礎(chǔ)上，將反應(yīng)機制與導(dǎo)引機制有機結(jié)合，提出一種混合的導(dǎo)引反應(yīng)式禁忌搜索算法予以求解。該算法不僅利用反應(yīng)機制有效增加禁忌搜索的靈活性，而且改進的導(dǎo)引機制可修正尋優(yōu)過程中潛在的“誤導(dǎo)”性。實驗結(jié)果表明，該算法可通過反應(yīng)機制與導(dǎo)引機制動態(tài)調(diào)整算法深度搜索與多樣搜索的平衡，從而有效地求解HFFMCVRP問題。

多車槽；多車型；導(dǎo)引機制；反應(yīng)機制；禁忌搜索

0 引言

車輛路徑問題(Vehicle Routing Problems，VRP)[1]是實現(xiàn)物流配送系統(tǒng)高效、低成本運作的難點和熱點問題，自1959年由Dantzig和Ramser提出后備受學術(shù)界關(guān)注。隨著VRP自身理論與現(xiàn)代物流業(yè)的高速發(fā)展，實際應(yīng)用中的VRP呈現(xiàn)出復(fù)雜形態(tài)，即所謂的“復(fù)雜VRP(rich VRP)”，從而衍生出諸多側(cè)重研究不同因素的VRP模型。

在物流配送中，為滿足排斥性貨物低成本準時送達到客戶，多車槽車輛路徑問題(Multi-Compartment Vehicle Routing Problems, MCVRP)的應(yīng)用較為常見，如牲畜飼料配送中，對病毒極其敏感的兔子飼料不能使用曾經(jīng)裝載過牛科動物飼料的車槽裝載，以免發(fā)生感染；同樣，為滿足各類生鮮冷熱、易腐、易溶食品對不同溫度、濕度的需求，便利店的食品配送中也需要提供不同環(huán)境的獨立車槽(或某種可移動、封閉的容器)；此外，還有可回收垃圾運輸以及不同燃油配送等。多車槽車輛除能滿足不同情況下貨物“隔離”的要求外，在節(jié)約配送成本上相對于獨立運輸也有較為明顯的優(yōu)勢[2-3]。而物流配送企業(yè)往往會在不同時期購買不同的車型以滿足自身發(fā)展、靈活響應(yīng)不同的運輸需求，從而形成了配送車隊車型的異質(zhì)屬性，即車隊中有多種型號的車輛。因此，現(xiàn)實的物流配送中，尤其對于燃油類、食品類、環(huán)衛(wèi)部門等企業(yè)，多車型與多車槽兩種屬性共存的車輛路徑問題，即多車型多車槽的車輛路徑問題(Heterogeneous Fixed Fleet Multi- Compartment Vehicle Routing Problem, HFFMCVRP)越來越普遍。

而目前的VRP研究中，往往側(cè)重于多車槽[2-4]或多車隊[5-17]某一方面的研究，較少綜合考慮二者在實際物流運輸中關(guān)聯(lián)性的研究，相關(guān)企業(yè)難以找到運營決策的理論依據(jù)。本文綜合考慮多車型與多車槽雙屬性的VRP問題，提出了求解HFFMCVRP問題的混合的禁忌搜索算法。本文研究成果在一定程度上擴展了VRP的研究，具有一定的理論價值；也為燃油、食品運輸?shù)葘嶋HHFFMCVRP應(yīng)用企業(yè)提供了運營決策支持，提高物流企業(yè)運營效率，改善顧客服務(wù)質(zhì)量具有廣泛的現(xiàn)實意義。

1文獻綜述

近年來，學者們對經(jīng)典VRP 進行了大量卓有成效的研究工作。本文主要對“多車槽”與“多車型”國內(nèi)外學者的研究進展進行了梳理與歸納。

1.1多車槽車輛路徑問題及其算法綜述

盡管早在80年代就有研究者對燃油配送中的“多車槽”運輸進行了研究，但直至2008年多車槽車輛路徑問題(MCVRP)才由El-Fallahi等[3]正式提出。在MCVRP研究中，客戶可以有多種貨物需求，而車輛有多個負責裝載不同貨物的車槽。車輛的裝貨車柜由隔離壁(Separator)分隔為多個車槽。針對車槽數(shù)的VRPC問題，F(xiàn)allahi等采用等分和隨機分割兩種方式，將CVRP經(jīng)典算例中的客戶需求一分為二，而獲得所需算例，并將MCVRP按貨物種類數(shù)分解為個經(jīng)典VRP問題,通過C-W節(jié)約法求解得個VRP初始解，從而獲得MCVRP的初始解；同時并用迷因算法(Memetic Algorithm，MA)與禁忌搜索（Tabu Search, TS）兩種算法分別對其進行優(yōu)化；最后，通過比較同一客戶的可分開運輸與必須同時運輸兩種訂單的運輸成本，結(jié)果發(fā)現(xiàn)前者比后者成本更小。盡管El-Fallahi等提出的“分解、組裝”策略較好地解決了MCVRP的“多車槽”約束，但其過程略顯費解與耗時。Muyldermans等[2]于2010年根據(jù)MCVRP的“多需求多車槽”特性，引入一個客戶及訂單的組合結(jié)點方法，改進了El-Fallahi提出的“分解、組裝”的步驟，直接應(yīng)用經(jīng)典VRP的改進算法，將鄰域表標記(Neighbor Lists and Marking)以及導(dǎo)引式局部搜索算法(Guided Local Search)結(jié)合，前者用于提高搜索速度，后者用于提高搜索質(zhì)量；求解相同算例的結(jié)果表明，其GLS比El-Fallahi等的MA與TS更快，解的質(zhì)量也有1%-2%的提高；這一研究成果成功被應(yīng)用于城市垃圾回收過程的“共同回收 (co-collection) ”，有效節(jié)約回收成本。此外，Muyldermans等學者的研究還發(fā)現(xiàn)，在貨物種類更多、車載量增加、更多客戶有多種貨物需求等情況下“共同回收”帶來的成本節(jié)約更顯著。2010年，Derigs等[4]基于前人的研究，提出較完善的、可方便擴展的MCVRP數(shù)學模型。該模型首次考慮車槽與貨物的排斥性與車槽結(jié)構(gòu)，將訂單而非客戶作為MCVRP中的最小操作單元，將多種算法模塊，如大鄰域搜索(Large Neighborhood Search)、局部搜索與亞啟發(fā)式算法——包括基于屬性的爬山算法(Attribute Based Hill Climber)、大洪水法(Great Deluge Algorithm) 、紀錄更新算法（Record-to-Record Travel algorithm）、模擬退火算法(Simulated Anealing)——進行組合實驗，尋求最佳的算法模塊組合。與El-Fallahi等、Muyldermans等的算法相比，Derigs等的算法求得的結(jié)果平均約有1%的提高。

上述文獻中使用的MCVRP算例有部分是通過對VRP算例進行需求二等分獲得的，即VRP算例的解空間包含了相應(yīng)MCVRP算例的解空間。但是，由于多車槽的約束，上述針對MCVRP提出的算法在求解相應(yīng)的VRP算例時，均無法全部求得VRP的已知最優(yōu)解（Best Known Solution, BKS），而求解MCVRP的結(jié)果相對于VRP的BKS則有更大的偏差，這也表明了MCVRP的求解質(zhì)量仍有提高的空間。目前國內(nèi)學者暫無有關(guān)MCVRP方面的研究。

1.2多車型車輛路徑問題及其算法綜述

在實際的物流配送中，配送中心車隊可能由多種運輸成本和裝載量不同的車型組成，稱為混合車隊車輛路徑問題(Mixed Fleet VRP, MFVRP)或多車型車輛路徑問題(Heterogeneous Fleet VRP，HVRP)[5]。HVRP一般根據(jù)車隊規(guī)模分為規(guī)模固定的多車型車輛路徑問題 (Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP) 與車隊規(guī)模與組合車輛路徑問題(Fleet Size and Mix Vehicle Routing Problem, FSMVRP)兩類。Taillard[6]于1999年首次研究HFFVRP問題。HFFVRP中車隊的異構(gòu)表現(xiàn)為裝載量、固定成本與可變成本、速度、最大旅行時間與可用性等多方面，而目前的研究主要是裝載量與成本方面的異構(gòu)。在實際應(yīng)用中，F(xiàn)SMVRP適用于戰(zhàn)略決策支持，即配送中心購買何種組成結(jié)構(gòu)的車隊最實惠；而HFFVRP適用于戰(zhàn)術(shù)層和操作層的決策支持，即如何高效地調(diào)用已有規(guī)模固定多車型車隊。Taillard對HFFVRP的“拆分、組合”的處理思路與Fallahi等對VRPC的處理思路相似，而二者都是對新問題的首次研究。然而，這種處理方式因為比較復(fù)雜，所以在后續(xù)研究中研究者都較少使用。

Tarantilis是研究HFFVRP較深入的學者之一。其最初應(yīng)用可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting algorithm, BATA)[7,8]求解HFFVRP。與傳統(tǒng)門檻接受算法不同，在BATA算法中，門檻值不單可以逐漸下降，當門檻接受條件一次都不滿足時它還可以上升，或稱回溯。在回溯過程中，上升值必須比回溯執(zhí)行前的那一個門檻值小。相對傳統(tǒng)門檻接受算法，BATA更靈活而且更有效地向全局最優(yōu)收斂，在解的質(zhì)量上平均提高了0.31%?；诹斜淼拈T檻接受法(List Based Threshold Accepting algorithm, LBTA)是Tarantilis等[9]提出的求解HFFVRP的第二種算法，是對傳統(tǒng)門檻接受算法的另一種改進。LBTA在局部搜索的過程中，利用解的信息不斷更新門檻值列表，并依此列表更新門檻值。在使用相同的鄰域結(jié)構(gòu)的情況下，BATA比LBTA求解效果更優(yōu)，前者能夠求得T-8算例6個較優(yōu)解。在實際物流配送中，Tarantilis等[10]提出一種混合算法用以求解鮮奶配送與預(yù)混混凝土運輸中的HFFVRP問題。該算法使用禁忌搜索改進，由GEROCA (Generalized Route Construction Algorithm)構(gòu)造初始解，并利用AMP組合優(yōu)秀解特性形成不完全解，再用GEROCA補充得完整解。該算法對實際案例的求解優(yōu)于LBTA和BATA。但關(guān)于T-8算例，該文獻中并沒有相關(guān)求解結(jié)果。Tarantilis等[11]人提出導(dǎo)引式禁忌搜索(Guided TS, GTS)是目前求得T-8算例最優(yōu)解的算法之一。GTS的初始解構(gòu)造方法與LBTA、BATA相同，Tarantilis等先將其模擬成裝箱問題，即逐個計算尚未被服務(wù)客戶的需求與各車輛空余裝載量的差值，并將最小差值所對應(yīng)的客戶分派給相應(yīng)的車輛，直到所有客戶都被服務(wù)。這種初始解構(gòu)造法能構(gòu)造出T-8算例的初始可行解。此外，除了經(jīng)典的2-opt外，GTS還應(yīng)用了新穎的鄰域結(jié)構(gòu)——對每一對路徑，交換兩條路徑中的客戶結(jié)點序列(Bone，從長度可從0至整條路徑)。通過為候選解中的每條邊定義一個客戶結(jié)點到各連接結(jié)點的距離平均值改進效用函數(shù)，重新定義“不被期望的長邊”并通過懲罰這些邊以摒棄非期望解的特性，對TS進行引導(dǎo)。

2007年，Li等[12]提出的紀錄更新算法(其簡稱HRTR)，亦是目前求解T-8算例效果最佳的算法之一。HRTR將Relocate、Swap、2-opt與Or-opt四種鄰域結(jié)構(gòu)分別以紀錄更新(record-to-record travel)與下坡(downhill)兩種方式執(zhí)行，并針對HFFVRP復(fù)雜的解空間，在傳統(tǒng)紀錄更新算法基礎(chǔ)上增加全局紀錄與全局偏差量，用以接受擾動解，增強算法跳出局部最優(yōu)解的性能，并能求出T-8算例的7個所知最優(yōu)解。Li等[13]于2010年應(yīng)用一種混合路徑重連(path re-linking，PR)算法的“多重啟動”的適應(yīng)性記憶規(guī)劃法(multi-start adaptive memory programming, MAMP)來求解HFFVRP。其中，MAMP每一次迭代構(gòu)造多個有潛力的初始解，進而由禁忌搜索進行改進；PR算法則作為強化搜索的策略融入MAMP中，以增強其構(gòu)造優(yōu)質(zhì)解的能力。在求解T-8算例的表現(xiàn)上，該算法求得的可變成本比GTS、HRTR稍差，只求得5個可變成本的所知最優(yōu)解，但在總成本方面較GTS、HRTR稍強(平均約0.3%的成本降低)。

HFFVRP除了有重要的理論研究意義外，還有廣泛的實際應(yīng)用價值，其研究成果往往作為核心模塊被嵌入DSS中，以支持企業(yè)配送中心的運營管理。如Prindezis等[14]于2005年為雅典中心食物市場公司開發(fā)了一個基于網(wǎng)頁瀏覽器的物流管理系統(tǒng)，其核心是禁忌搜索求解HFFVRP；Tütüncü[15]于2010年提出基于一種新的貪婪式隨機自適應(yīng)記憶規(guī)劃搜索算法(Greedy Randomized Adaptive Memory Programming Search)的可視化交互方法，并將其嵌在ADVISER的決策支持系統(tǒng)的應(yīng)用中。

國內(nèi)最早由郭耀煌等[16]于1992年對HFVRP進行研究，并同時考慮了多車場的屬性，其工作主要是圍繞如何將HFVRP按“優(yōu)先分配裝載量大的車輛”原則并用里程控制方法將HFVRP化簡為多個單一車型VRP，然后分別進行求解。2001年，李嘉等人[17]針對城市貨運出租公司車輛分派管理、搬家公司搬運車輛分派管理等領(lǐng)域展開研究。研究中車輛有統(tǒng)一的最大允許工作時間限制，各個客戶也有時間窗等要求。且每個客戶單次可能需要不只一輛車為其服務(wù)且對車型有所限制。針對此特殊問題，他們提出了兩階段方法，即第一階段采用枚舉的辦法用啟發(fā)式每次生成一個車隊模式；第二階段在“車隊+客戶”的組合染色體編碼結(jié)構(gòu)下，用一種混合算法(TS對GA產(chǎn)生的后代進行預(yù)改進)求解。同時，袁慶達等[18]研究了帶軟時間窗的HFFVRP(HFFVRP with Soft Time Windows)。其先用GENIUS(GENeralized Insertion & Unstring and String)算法按加入時間坐標的三維距離來構(gòu)造初始路徑，然后為每條初始路徑構(gòu)造一個輔助圖，在中確定每段邊使用何種車型服務(wù)能獲得的最小服務(wù)成本和求解的最短路，確定所對應(yīng)初始路徑的最優(yōu)車輛組合，用TS算法進行優(yōu)化，使用按均勻獨立分布生成的算例對算法進行驗證。2008年，李建等人[19]研究第三方物流中的帶硬時間窗的HFFVRP(HFFVRP with Hard Time Windows，HFFVRPHTW)。鑒于第三方物流的復(fù)雜性與“優(yōu)先分配裝載量大的車型”的原則，其在研究中沒有考慮到車輛的運輸可變成本，而優(yōu)先滿足最小費用車型策略來分配車輛，再用融合SA的混合GA來對車輛的再分配和路徑優(yōu)化，最后使用隨機生成的算例驗證其算法與車輛分配策略的合理性。

由于國內(nèi)最先提出HFVRP時是伴隨著多車場屬性提出，因此國內(nèi)學者對多車場HFFVRP(Multi-Depot HFFVRP，MDHFFVRP)關(guān)注頗多。在MDHFFVRP研究中，對于“多車場”的處理，普遍采用啟發(fā)式算法與一定分配原則相結(jié)合，將多車場問題轉(zhuǎn)化為單車場問題的策略。如鄭麗英[20]等于2009年使用隸屬度變異全局搜索聚類算法，針對染色體結(jié)構(gòu)中客戶排程與車輛安排兩部分設(shè)計了5類交叉算子，并用GA求解。鐘石泉等人認為，盡管簡單的“化多為一”的作法可行，但卻都沒有從整體上來考慮多個車場，而且其使用的劃分規(guī)則在約束比較多的情況下對車輛調(diào)度的全局優(yōu)化有很大影響。因此，他提出了多車場同時優(yōu)化的方法，而以隨機分派的方式對多車型約束進行處理，并使用帶局部禁忌表與全局禁忌表的改進TS優(yōu)化求解。2009年，王曉博等[21]人針對多車場、多車型裝卸一體化車輛路徑問題(MDHFFVRP with Backhauls，MDHFFVRPB)研究。他們也認為由于MDHFFVRPB的特殊性，簡單地“化多為一”容易導(dǎo)致配送和集貨這兩個因素權(quán)衡分析不充分，造成車輛資源的浪費、增加運輸成本，并容易陷入局部最優(yōu)解。因此他們提出符號和自然數(shù)混合的編碼形式從整體上考慮MDHFFVRPB，并提出一種利用TS對GA的精英種群改進搜索的混合算法。實驗結(jié)果表明其混合算法優(yōu)于前人的多階段啟發(fā)式算法，并得出“多車場多車型”比“多車場單車型”運營策略更有效的結(jié)論。與本文研究內(nèi)容較相近的是國內(nèi)學者戴錫等[22]對油品配送的研究。其研究問題具有多車場、多倉庫、多商品、多艙位（即車槽）、多車型、時間窗等諸多特性與約束，為應(yīng)對其復(fù)雜性并提高應(yīng)用開發(fā)的適用性，其以兩階段啟發(fā)式算法為基礎(chǔ)，給出了人機交互式的求解方法。戴錫等的研究深入說明了本文的現(xiàn)實意義，本文亦為相關(guān)的現(xiàn)實應(yīng)用開發(fā)提供了理論基礎(chǔ)。

2 數(shù)學定義與模型

HFFMCVRP問題的求解目標是在滿足以下約束的情況下找到最小總成本的車輛分配與行車路線，其數(shù)學模型如下：

s.t.

(2)

,,(4)

(5)

,(7)

(8)

,,(10)

,,(11),,(12),,(13),(14),,(15)

式(1)為模型的目標函數(shù)，表示所使用車的可變成本之和最小。表示車輛從客戶直接到達客戶，否則為0。式(2)表示每輛車最多只從配送中心出發(fā)一次。式(3)表示車進入結(jié)點，必然也從離開。式(2)和式(3)表明若車被分派任務(wù)，則必須從配送中心出發(fā)并最終回到配送中心。式(4)表示若車從駛到，則的“位置”比的“位置”高，即在車行駛路徑中的位置。式(5) 將配送中心設(shè)在所有路徑首端，以消除結(jié)點次序不同但實質(zhì)相同的重復(fù)路徑。式(4) 和式(5)用于共同消除子路徑。式(6) 表示各種車型使用的車輛數(shù)不超過限制。是車輛關(guān)于車型的特征函數(shù)，若車輛，則，否則為0。（7）式表示車輛車槽裝載貨物量不能超過其限載量。表明訂單由車的車槽運輸，否則為0。式(8)表示每個訂單只由某一輛車的某一個車槽為其服務(wù)。式(9)表示，若客戶的某些或全部訂單由車輛服務(wù)，則車輛必定訪問客戶。式(10)表示若某些或全部所訂貨物為的訂單，由車輛的車槽負責運輸，則貨物由車輛的車槽負責運輸，即。式(11)和式(12)描述貨物不兼容的約束條件，式(13)~式(16)則定義模型的決策變量。

上述模型較完整地對HFFMCVRP進行了描述，但在實際物流運輸中，存在不同的應(yīng)用，從而模型的目標函數(shù)與約束條件均會發(fā)生細微變化。比如，在實際物流運輸中，經(jīng)常出現(xiàn)運力不足的情況。此時，需要決定哪些訂單需求應(yīng)優(yōu)先處理，哪些訂單暫時不處理。為此，可引入新的決策變量，表示訂單暫時不處理，表示訂單優(yōu)先處理。若訂單未被服務(wù)，則產(chǎn)生一個懲罰成本，與訂單的需求量相關(guān)，或者可根據(jù)實際情況另外定義。此時，目標函數(shù)將發(fā)生變化，式(1)變?yōu)?/p>

又如，在實際物流運輸中，對需求、裝載量的衡量可能有多個維度，比如不僅考慮重量還考慮體積約束。此時，無需添加新的決策變量，而只需增加類似式(7)的約束條件即可。此外，上述模型中不允許對一個訂單進行切割，即每個訂單只由一輛車一次性完成服務(wù)。但在實際物流運輸中，存在將訂單進行切割并分別在多個車槽或多輛車中完成運輸?shù)那闆r，則需定義一個訂單的切割方式，即是任意切割為多個小訂單還是按某種規(guī)則進行切割。此類擴展需定義更多的決策變量與約束條件。

3 算法設(shè)計

3.1初始解構(gòu)造及鄰域搜索

對于HFFMCVRP問題需要同時考慮多車型與多車槽的雙重屬性，與多車槽屬性對應(yīng)的是客戶的多訂單屬性，客戶的不同訂單對應(yīng)不同的貨物。某客戶的一個訂單只能由一輛車一次完成服務(wù)，但一個客戶的不同訂單可以由同一輛車也可由不同的車服務(wù)。因此，HFFMCVRP中的最小服務(wù)單元應(yīng)是訂單結(jié)點而不應(yīng)是客戶結(jié)點。本文在Tarantilils等人[11]提出初始解構(gòu)造法基礎(chǔ)上，結(jié)合HFFMCVRP雙屬性特征，將HFFMCVRP模擬成一個裝箱問題，為每一客戶定義一個表示所有從某結(jié)點出發(fā)邊的平均長度；然后對每一訂單與符合裝載約束車槽間計算“匹配度”，每次將最大“匹配度”對應(yīng)的訂單分派給相應(yīng)的車槽，重復(fù)此操作，直至所有訂單均被服務(wù)。在初始解的構(gòu)造過程中，不僅考慮了車槽裝載量與訂單需求量間的匹配，而且能顧及到已服務(wù)訂單與沒有服務(wù)訂單間的“匹配”。該改進的初始解構(gòu)造法能快速構(gòu)建HFFMCVRP的初始可行解。HFFMCVRP中的車隊為異質(zhì)且規(guī)模固定，現(xiàn)考慮一支由3輛A型、2輛B型的車輛組成的車隊。首先，對應(yīng)每一輛車，生成一條空路徑，即生成“A, A, A, B, B”五條帶有A型車、B型車特征的路徑。然后按程序1生成可行初始解。具體如下：

程序1 初始解構(gòu)造

(1)根據(jù)需求量大小將訂單按升序排列；

(3)在保持可行性的條件下，使用最小成本插入法依次將未服務(wù)訂單逐個插入中；

(4)更新各車槽剩余裝載量，重復(fù)步驟(2)與(3)，直到所有的訂單被服務(wù)。

確定初始解之后，需搜索解的鄰域以尋求更優(yōu)解。本文采用了2-1 move, 1-1 move, 1-0 move, 和 2-opt*以及swap, relocate 和 2-opt等經(jīng)典的鄰域結(jié)構(gòu)。由于VPR問題的復(fù)雜性，即使是亞啟發(fā)式算法在求解中-大規(guī)模問題時，尋求鄰域最優(yōu)解也需要巨大的計算量,耗時較長。學者們利用“鄰域范圍縮減策略”，過濾掉一些被認為潛在價值相對較小的鄰域解，將計算集中在某些合意的鄰域以減少計算量。本文在鄰域搜索中允許一個非禁忌的操作當且僅當該操作連接的邊滿足訂單對應(yīng)的客戶是訂單對應(yīng)的客戶的鄰居的條件，即

3.2導(dǎo)引反應(yīng)式禁忌搜索算法

導(dǎo)引機制是一種依據(jù)設(shè)定效用函數(shù)識別并懲罰不良屬性邊，以導(dǎo)引搜索進入未開拓解空間搜索方法，其效用函數(shù)及懲罰參數(shù)設(shè)計不同，會存在誤選或懲罰“過度”或“過輕”的問題。本文在Tarantilis[11]提出的引導(dǎo)機制的基礎(chǔ)上，引入矩陣記錄邊在優(yōu)良解中出現(xiàn)的頻率，利用搜索過程的歷史信息修正引導(dǎo)機制尋優(yōu)過程中潛在的盲目性；同時將動態(tài)控制禁忌周期的反應(yīng)機制與導(dǎo)引機制相結(jié)合，提出一種混合的導(dǎo)引反應(yīng)式禁忌搜索算法。該算法利用反應(yīng)機制直接調(diào)整鄰域范圍參數(shù)以有效引導(dǎo)禁忌搜索的方向；若TS連續(xù)表現(xiàn)良好，則調(diào)整該參數(shù)縮小鄰域范圍以深化搜索；反之調(diào)整該參數(shù)擴大鄰域范圍以放寬搜索，從而動態(tài)調(diào)整算法深度搜索與多樣搜索的平衡，增強了算法的尋優(yōu)能力。

在調(diào)度問題或VRP的求解中，長距離的邊往往被認為具有不良屬性并進行懲罰，從而在未來搜索中該邊極有可能被避開。Tarantilis等人[11]對傳統(tǒng)導(dǎo)引機制做了延伸，成功應(yīng)用于HFFVRP問題。其效用函數(shù)為，不僅考慮了邊的距離和懲罰次數(shù)，還考慮了結(jié)點和相對其它結(jié)點的平均距離，從而使邊的選取更加科學。傳統(tǒng)導(dǎo)引機制中，雖然效用函數(shù)使用、和等參數(shù)使邊的選取更準確，但由于和兩個參數(shù)是問題本身固有屬性，也只是關(guān)于導(dǎo)引機制中懲罰操作的信息，其并未包含關(guān)于搜索過程的歷史信息。而對歷史信息的有效利用能夠提高未來搜索的性能[23]。為有效利用歷史信息，本文引入一個矩陣來記錄邊在優(yōu)良解中出現(xiàn)的頻率，根據(jù)搜索的歷史信息來進行邊的選取的效用函數(shù)。每個元素初始值為1，每次搜索到最優(yōu)鄰域解時，對中的每條邊更新其對應(yīng)的，即當時，，否則令, 其中是當前所發(fā)現(xiàn)的歷史最優(yōu)解。在程序3的步驟2中，當搜索被認為陷入循環(huán)時，被設(shè)置為其缺省狀態(tài)，即全部元素為1的矩陣。這樣做可進一步給予算法一定的自我改正功能。這一步驟亦是連接導(dǎo)引機制與反應(yīng)機制的重要一步。

(19)

(20)

式(18), (19), 和 (20)定義了三個效用函數(shù)，無論在哪個效用函數(shù)中，若邊多次出現(xiàn)在優(yōu)良解中，其值就越高，從而越低，被選中進行懲罰的可能性就越低。

程序 2 導(dǎo)引機制

else

而反應(yīng)式的禁忌搜索(Reactive TS，RTS)是Battiti與Tecchiolli[24]受動力系統(tǒng)理論啟發(fā)后提出的一種禁忌搜索算法。本文根據(jù)搜索過程調(diào)整禁忌表長度以將搜索軌跡放寬，從而不受限于搜索空間的局部區(qū)域，其魯棒性及參數(shù)變動對其性能的微弱影響已得到證明[25-28]。在本文中，反應(yīng)機制除了動態(tài)調(diào)整禁忌表長度外，還調(diào)整鄰域范圍；當搜索陷入局部最優(yōu)時，還通過開/關(guān)鄰域范圍縮減策略和缺省化導(dǎo)引機制中的矩陣來使搜索跳出局部最優(yōu)。(見程序3中的步驟(2))。RTS流程及其參數(shù)描述如下：

參數(shù) 含義

程序3反應(yīng)機制

else

當求解過程陷入混亂時，Battiti等人提出的反應(yīng)機制中，逃脫程序?qū)嵸|(zhì)上是一系列的隨機搜索。而本文使用另一個較長含有歷史最優(yōu)解目標值的“禁忌表”來檢測重復(fù)，即當在中時，則目標值的重復(fù)被檢測。除了禁忌表長度動態(tài)調(diào)整外，本文用這個開關(guān)來開啟/關(guān)閉鄰域范圍縮減策略。當搜索被認為是陷入混亂時，關(guān)閉鄰域范圍縮減策略，從而使搜索范圍擴大以幫助搜索“逃脫”；若下次迭代未檢測到重復(fù)，則重新開啟鄰域范圍縮減策略，從而動態(tài)調(diào)整搜索深度與廣度?，F(xiàn)在給出算法 RGTS的整體框架：

啟動程序1 獲取初始解。

: 依次使用路線間操作,,改進當前解，再依次使用路線內(nèi)操作,和改進當前解。每個操作后都更新當前解。最終返回一個未禁忌的鄰域最優(yōu)解。

啟動程序 2。

啟動程序 3。

4 實驗設(shè)計與分析

4.1 HFFMCVRP算例集

由于現(xiàn)有研究中尚無HFFVRPC的國際標準算例，本文根據(jù)Taillard[6]的HFFVRP標準算例，采用如文獻[2][3]的算例生成方法，將HFFVRP的國際標準算例T-8做“二等切分”變換，即將車輛裝載量與各個客戶需求二等分，使每輛車有二個裝載量相等的車槽，每個客戶有兩種數(shù)量相等的需求，而第個車槽只能裝載第種需求，如此生成算例TC-8，詳見表1。

表 1 TC-8算例屬性

TC-8算例的復(fù)雜性不僅在于多車槽、多訂單的約束，而且在結(jié)點規(guī)模上亦是T-8算例的兩倍。將有個客戶結(jié)點、條邊的HFFVRP算例二等分后，生成一個有個訂單結(jié)點、條邊的HFFMCVRP 算例，如的情形如圖1所示，其中正方形表示客戶結(jié)點，圓形表示配送中心，三角形表示客戶結(jié)點的訂單。這意味著HFFMCVRP將會擁有更大的搜索空間與更多的局部最優(yōu)解。同時，由于T-8算例將同一客戶的兩個需求同時派送，所以T-8的可行解也可認為是TC-8的可行解。TC-8算例解空間是將T-8算例解空間的多重細分，T-8算例中的每一個可行解在TC-8中可能以多種形態(tài)出現(xiàn)。

圖1 HFFVRP算例與HFFVRPC算例的關(guān)系

4.2 實驗結(jié)果與分析

算法RGTS在Windows XP系統(tǒng)下、Visual Studio 2008 C#編程環(huán)境中實現(xiàn)，并在配有主頻為1.32GHz的Intel 奔騰雙核T4300 處理器與1GB DDRII內(nèi)存的筆記本電腦上運行。

4.2. 1參數(shù)設(shè)置

表 2 RGTS的參數(shù)設(shè)置

與許多亞啟發(fā)式算法相似，RGTS需要對其參數(shù)進行調(diào)試以求計算量與求解質(zhì)量間的平衡。由于反應(yīng)機制多次成功應(yīng)用于[25-28]文獻中，因此本文反應(yīng)機制參數(shù)設(shè)置基本參考上述文獻參數(shù)設(shè)置。為避免早期迭代時過度頻繁的禁忌表長度調(diào)整，本文經(jīng)過測試將的初始值設(shè)為而不是 標準RTS中的“1”。關(guān)于導(dǎo)引機制的參數(shù)設(shè)置，本文生成5個隨機算例，變動各個導(dǎo)引機制的參數(shù)，在中變動，在中變動，并記錄其對應(yīng)的求解質(zhì)量，最后得到較優(yōu)的參數(shù)組合。對于其它參數(shù)和亦在多次試驗后確定參數(shù)值，具體如表2所示。

4.2. 2有無導(dǎo)引機制的TS求解TC-8算例的比較分析

為進一步了解導(dǎo)引機制的作用與效能（擴大算法的搜索廣度），圖2展示了標準TS（圖中灰色）與有導(dǎo)引機制的TS（圖中黑色）在求解TC-8中的問題19時的搜索迭代曲線。

圖2 導(dǎo)引機制的擴大算法搜索廣度的能力展示

可見，由于沒有導(dǎo)引機制的引導(dǎo)，標準TS很容易就困在局部最優(yōu)解中無法逃離（為了讓其運行足夠久，標準TS下的設(shè)為100），與之形成鮮明對比的是，有導(dǎo)引機制的TS能有效避免過早地陷入局部最優(yōu)解而將搜索引導(dǎo)到更寬廣的空間，從而最終獲得更優(yōu)的解。在求解其它TC-8的問題時亦發(fā)現(xiàn)類似的鮮明對比。

4.2. 3不同效用函數(shù)對導(dǎo)引機制的影響

本文根據(jù)導(dǎo)引機制對固有屬性信息與搜索歷史信息的利用程度不同，定義了三種不同的效用函數(shù)“U1”, “U2”與“U3”。表3為在沒有反應(yīng)機制的前提下，不同效用函數(shù)對導(dǎo)引機制的影響，其均使用標準的懲罰方式。除效用函數(shù)與懲罰方式外，其它如初始解構(gòu)造、鄰域搜索與算法流程都與上文定義一致。表3中“OV”表示算法所能求得的最優(yōu)解的目標值，“CPU”指其所需時間。

4.2. 4反應(yīng)機制與導(dǎo)引機制求解TC-8算例的比較分析

由于HFFMCVRP的復(fù)雜性，即使是有“U2”導(dǎo)引機制的TS亦很難求得與HFFVRP已知最優(yōu)解(BKS)足夠接近的TC-8的解。因此，本文為檢驗兩種機制是互相補充還是互相排斥，分別對RGTS、TS、有導(dǎo)引無反應(yīng)機制的TS-G、有反應(yīng)無導(dǎo)引機制的TS-R在求解TC-8問題進行比較。具體如表4所示。

表 3 不同導(dǎo)引機制求解TC-8的比較

autility functionsbutility functionsTarantilis et al. (2008)

表 4 RGTS與TS-G及 TS-R 求解TC-8的比較

比率(%)：=100%*(OVi-OV1)/OV1

表4中RGTS求解效果最佳，表明反應(yīng)與導(dǎo)引機制可相輔相成。上文提過HFFVRP的可行解可看作HFFMCVRP的可行解，故HFFVRP最優(yōu)解可視為HFFMCVRP解的下界。

4.2. 5 RGTS與HFFVRP算法求解T-8的比較

與HFFVRP的標準算例T-8的已知最優(yōu)解（BKS）相比，RGTS求得TC-8的解有一定距離，比率為4.06%，如表5所示。盡管這并非很小的比率，但由于TC-8算例遠比T-8算例復(fù)雜，而且T-8的BKS是歷經(jīng)前人多次研究、通過精心編制的多種算法才獲得的，所以比率屬于可接受范圍。

盡管RGTS并非針對HFFVRP設(shè)計的算法，但為進一步檢驗其魯棒性，將其應(yīng)用于求解T-8，并與HFFVRP的四個算法進行比較。根據(jù)表5的結(jié)果，RGTS具有一定的魯棒性，因為它求得的最優(yōu)解與T-8的BKS只有2.06%，等于(解-BKS)/BKS的距離。El- Fallahi 等[3]將其MCVRP算法應(yīng)用于經(jīng)典VRP時，其求得的最優(yōu)解與經(jīng)典VRP的BKS亦有1.02%的距離。他們認為使用 MCVRP算法求解VRP問題有一個困難，即在MCVRP框架下，VRP問題中虛擬的兩個訂單必須同時派送，這可能導(dǎo)致MCVRP算法在求解VRP問題時效率低下。從問題的繼承性與困難度來看，本文中HFFMCVRP可對應(yīng)MCVRP，而HFFVRP則對應(yīng)經(jīng)典VRP，因此El Fallahi 等[3]的解釋亦適用于本文的情況。

表 5 RGTS與HFFVRP算法求解T-8的比較

abcd

5 結(jié)論

本文圍繞HFFMCVRP問題，提出一種混合的導(dǎo)引反應(yīng)式禁忌搜索算法。為增強算法的尋優(yōu)能力，該算法在求解過程中利用反應(yīng)機制調(diào)整鄰域范圍參數(shù)以有效引導(dǎo)禁忌搜索的方向；同時改進的導(dǎo)引機制利用搜索過程的歷史信息修正尋優(yōu)過程中潛在的誤導(dǎo)性。實驗比較結(jié)果表明，本文提出的算法求解效果較優(yōu)，在一定程度上實現(xiàn)深入搜索與多樣搜索平衡。該研究成果在一定程度上擴展了VRP的理論研究，而且為燃油類、食品運輸?shù)葘嶋HHFFMCVRP應(yīng)用企業(yè)的運營決策支持提供參考，具有理論與現(xiàn)實意義。

[1] Dantzig GB，Ramser JH. The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[2] Muyldermans L，Pang G. On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm[J]. European Journal of Operational Research，2010，206：93-103.

[3] El-Fallahi A，Prins C，Calvo RW. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research，2008，35：1725-1741.

[4] Derigs U，Gottlieb J，Kalkoff J et al. Vehicle routing with compartments: applications, modeling and heuristics[J]. OR Spectrum，2011，33（4）：885-914.

[5] Baldacci R，Battarra M，Vigo D. Routing a Heterogeneous Fleet of Vehicles[A].In： Golden BL，Raghavan S，Wasil EA. The Vehicle Routing Problem: Latest Advances and New Challenges [C]. New York：Springer，2008. 3-27.

[6] Taillard ED. A heuristic column generation method for the heterogeneous vehicle routing problem[J]. RAIRO，1999，33：1~14.

[7] Tarantilis CD，Kiranoudis CT. A meta-heuristic algorithm for the efficient distribution of perishable foods[J]. Journal of Food Engineering，2001，50：1-9.

[8] Tarantilis CD，Kiranoudis CT，Vassiliadis VS. A threshold accepting meta-heuristic for the heterogeneous fixed fleet vehicle routing problem[J]. European Journal of Operational Research，2004，152：148-158.

[9] Tarantilis CD，Kiranoudis CT. A List Based Threshold Accepting Meta-heuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem[J]. The Journal of the Operational Research Society，2003，54（1）：65-71.

[10] Tarantilis CD，Kiranoudis CT. A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector[J]. European Journal of Operational Research，2007，179：806-822.

[11] Tarantilis CD，Zachariadis EE，Kiranoudis CT. A guided tabu search for the heterogeneous vehicle routing problem[J]. Journal of the Operational Research Society，2008，59：1659-1673.

[12] Li F，Golden B，Wasil E. A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem[J].Computers & Operations Research，2007，34：2734-2742.

[13] Li X，Tian P，Aneja YP. An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review，2010，46（6）：1111-1127.

[14] Prindezis N，Kiranoudis CT. An internet-based logistics management system for enterprise chains[J]. Journal of Food Engineering，2005，70：373-381.

[15] Tütüncü GY. An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls[J]. European Journal of Operational Research，2010，201（2）：593-600.

[16] 郭耀煌，范莉莉，童淑惠. 多車型貨運車輛優(yōu)化調(diào)度[J].系統(tǒng)工程學報，1992，7（1）：111-117.

[17] 李嘉，王夢光，唐立新，等.一類特殊車輛路徑問題(VRP)[J].東北大學學報(自然科學版)，2001，22（3）：245-248.

[18] 袁慶達，杜文，周再玲. 帶軟時間窗的混合車隊車輛路線問題的模型和算法研究[J].西南交通大學學報，2001，36（4）：401-406.

[19] 李建，張永，達慶利.第三方物流多車型硬時間窗路線問題研究[J].系統(tǒng)工程學報，2008，23（1）：74-80.

[20] 鄭麗英，賈海鵬.全局搜索聚類的多車場多車型調(diào)度算法研究[J].蘭州交通大學學報，2009，28（6）：19-22.

[21] 王曉博，李一軍.多車場多車型裝卸混合車輛路徑問題研究[J].控制與決策，2009，24（12）：1769-1774.

[22] 戴錫，葉耀華，吳勤旻，等. 油品配送車輛路徑問題的交互式求解方法[J]. 系統(tǒng)工程學報，2009，24（6）：749-753.

[23] Glover F，Kochenberger GA，Alidaee B. Adaptive Memory Tabu Search for Binary Quadratic Programs[J]. Management Science，1998，44（3）：336-345.

[24] Battiti R，Tecchiolli G. The reactive tabu search[J]. ORSA Journal on Computing，1994，6：126-140.

[25] Osman IH，Wassan NA. A reactive tabu search meta-heuristic for the vehicle routing problem with backhauls[J]. Journal of Scheduling，2002，5：263-285.

[26] Wassan NA，Osman IH. Tabu search variants for the mix fleet vehicle routing problem[J]. The Journal of the Operational Research Society，2002，53：768-782.

[27] Wassan NA. A reactive tabu search for the vehicle routing problem[J]. The Journal of the Operational Research Society，2006，57：111-116.

[28] Wassan NA，Wassan AH，Nagy G. A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries[J]. Journal of Combinatorial Optimization，2008，15：368-386.

A Hybrid Guided Reactive Tabu Search for Heterogeneous Fixed Fleet Multi-compartment Vehicle Routing Problem

WANG Qian1, JI Qing-kai2,1, HU Xiang-pei2

(1. Sun Yat-sen Business School, Sun Yat-sen University, Guangzhou 510275, China;2. Institute of System Engineering, Dalian University of Technology, Dalian 510275, China)

Heterogeneous fixed fleet multi-compartment vehicle routing problem (HFFMCVRP) prevails in industries such as oil and food industries. Such real life problems have not been well studied by scholars. In this paper, we propose a three-index mathematical model that can well characterize the features of multi-compartment and heterogeneous fleet. We then incorporate the reactive mechanism and guiding mechanism when designing the hybrid guided reactive tabu search (RGTS) to solve HFFMCVRP. By adapting the tabu list size and the neighborhood size according to search performance (i.e., generally speaking, shortening the tabu list size and increasing the neighborhood size when the search returns a series of new solutions, while lengthening the tabu list size and reducing the neighborhood size while the search returns many repetitions), the RGTS successfully utilize the upgraded reactive mechanism to increase the tabu search’s flexibility. More importantly, to decrease the chance of “misleading” during the classic guided search, an enhanced guiding mechanism is introduced into RGTS by efficiently applying history information of the search. More specifically, the utility function of our guiding mechanism is based on a continuously-updated matrix which records the appearance of edges in good solutions returned by the search. As a result, the selection of edge according to the utility function for penalization is more reasonable. Several well-known neighborhood operators including 2-1 move, 1-1 move, 1-0 move, 2-opt*, swap, relocate and 2-opt, are applied in the search. As for experimentation, since there is no public HFFMCVRP instance set, we derive instance set TC-8 by besetting the benchmark instance set T-8 of the heterogeneous fixed fleet vehicle routing problem (HFFVRP). Vehicles and orders in T-8 are “bisected” so that there are two compartments for each vehicle and two orders for each customer in TC-8. The first/second order of each customer can only be carried in the first/second compartment of vehicles. Firstly, three different guiding mechanisms characterized by different utility functions are numerically compared to assess their effectiveness. Our guiding mechanism with the utilization of search history information dominates others with only predetermined information (i.e. distances of edges). Secondly, the tabu search, the tabu search with reactive mechanism, the tabu search with guding mechanism and the tabu search with both mechanisms (i.e. RGTS) are compared to justify these two hybrid mechanisms. RGTS outperforms others by producing better solutions. Thirdly, in order to test the robustness of RGTS, we apply it to solve the heterogeneous fixed fleet vehicle routing problem (HFFVRP), even though RGTS is not specifically designed for HFFVRP. The results indicate that RGTS can produce solutions of an average gap 2.06% compared to the best-known solution of HFFVRP benchmark instances, which is acceptable since HFFMCVRP is much harder than HFFVRP. In summary, experiments demonstrate that our heuristic can dynamically balance the intensification and diversification of the search through the reactive mechanism and guiding mechanism in order to efficiently solve the complex HFFMCVRP.

multi-compartment; heterogeneous fleet; guiding mechanism; reactive mechanism; tabu search.

中文編輯：杜 ?。挥⑽木庉嫞篊harlie C. Chen

U16

A

1004-6062(2016)03-0179-09

10.13587/j.cnki.jieem.2016.03.022

2013-09-28

2015-12-22

國家自然科學基金資助項目（70971141）；國家自然科學基金重點資助項目（71431007）

王茜（1971—），女，遼寧丹東人；中山大學管理學院教授，博士生導(dǎo)師，研究方向：電子商務(wù)，網(wǎng)絡(luò)信息戰(zhàn)略，物流管理。