王 茜，吉清凱, ，胡祥培

?

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

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

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

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

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

0 引言

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

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

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

1文獻(xiàn)綜述

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

1.1多車槽車輛路徑問(wèn)題及其算法綜述

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

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

1.2多車型車輛路徑問(wèn)題及其算法綜述

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

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

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

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

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

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

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

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

s.t.

(2)

,,(4)

(5)

,(7)

(8)

,,(10)

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

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

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

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

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

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

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

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

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

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

(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問(wèn)題的復(fù)雜性，即使是亞啟發(fā)式算法在求解中-大規(guī)模問(wèn)題時(shí)，尋求鄰域最優(yōu)解也需要巨大的計(jì)算量,耗時(shí)較長(zhǎng)。學(xué)者們利用“鄰域范圍縮減策略”，過(guò)濾掉一些被認(rèn)為潛在價(jià)值相對(duì)較小的鄰域解，將計(jì)算集中在某些合意的鄰域以減少計(jì)算量。本文在鄰域搜索中允許一個(gè)非禁忌的操作當(dāng)且僅當(dāng)該操作連接的邊滿足訂單對(duì)應(yīng)的客戶是訂單對(duì)應(yīng)的客戶的鄰居的條件，即

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

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

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

(19)

(20)

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

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

else

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

參數(shù) 含義

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

else

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

啟動(dòng)程序1 獲取初始解。

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

啟動(dòng)程序 2。

啟動(dòng)程序 3。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 HFFMCVRP算例集

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

表 1 TC-8算例屬性

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

表 3 不同導(dǎo)引機(jī)制求解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)引機(jī)制可相輔相成。上文提過(guò)HFFVRP的可行解可看作HFFMCVRP的可行解，故HFFVRP最優(yōu)解可視為HFFMCVRP解的下界。

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

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

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

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

abcd

5 結(jié)論

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

[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ùn)車輛優(yōu)化調(diào)度[J].系統(tǒng)工程學(xué)報(bào)，1992，7（1）：111-117.

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

[18] 袁慶達(dá)，杜文，周再玲. 帶軟時(shí)間窗的混合車隊(duì)車輛路線問(wèn)題的模型和算法研究[J].西南交通大學(xué)學(xué)報(bào)，2001，36（4）：401-406.

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

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

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

[22] 戴錫，葉耀華，吳勤旻，等. 油品配送車輛路徑問(wèn)題的交互式求解方法[J]. 系統(tǒng)工程學(xué)報(bào)，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.

中文編輯：杜 ??；英文編輯：Charlie C. Chen

U16

A

1004-6062(2016)03-0179-09

10.13587/j.cnki.jieem.2016.03.022

2013-09-28

2015-12-22

國(guó)家自然科學(xué)基金資助項(xiàng)目（70971141）；國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（71431007）

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