兩級(jí)車(chē)輛路徑問(wèn)題的多起始點(diǎn)變鄰域下降算法

曾正洋，許維勝，徐志宇，倪嘉呈

（同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海201804）

隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展和人民生活水平的不斷提高，物流活動(dòng)與日常生活的聯(lián)系也越來(lái)越緊密.物資運(yùn)輸中傳統(tǒng)的車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP）一般假設(shè)單級(jí)配送物資，即由中心倉(cāng)庫(kù)（depot）直接向需求點(diǎn)（customers）配送物資.但由于物流運(yùn)輸車(chē)輛體積大、起步慢，降低了城市道路的通行能力，易加劇城市交通擁堵、噪音和尾氣污染，為保護(hù)城市環(huán)境，很多城市對(duì)這類(lèi)車(chē)輛采取限行措施：物資必須首先由大型車(chē)輛配送至位于郊區(qū)的各個(gè)中轉(zhuǎn)站（satellites），再通過(guò)小型車(chē)輛轉(zhuǎn)運(yùn)至市內(nèi)的各個(gè)需求點(diǎn)，這就形成兩級(jí)車(chē)輛路徑問(wèn)題（twoechelon vehicle routing problem，2E-VRP［1-6］），如圖1所示［7］.圖中，s1，s2，s3為中轉(zhuǎn)站，c1，…，c9為 需求點(diǎn)，兩級(jí)路徑用不同的箭頭區(qū)分.

圖1 2E-VRP示例Fig.1 An example of 2E-VRP

現(xiàn)有文獻(xiàn)對(duì)2E-VRP的研究較為有限，求解方法主要分為精確算法和啟發(fā)式算法兩類(lèi).Perboli等［1］提出2E-VRP的商品流模型，并采用分支切割精確算法求解，由于計(jì)算時(shí)間較長(zhǎng)，并未給出算法的全部運(yùn)行時(shí)間.Jepsen等［2］提出一種特殊的分支切割精確算法，采用特殊的分支過(guò)程來(lái)獲得可行解.Perboli等［1，3］提出一些有效的不等式，增強(qiáng)對(duì)分支切割法中商品流模型的連續(xù)松弛.Baldacci等［4］提出了一種新的2E-VRP模型，用于獲得有效的下界，然后將2E-VRP解耦為多個(gè)帶邊界約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題（multi-depot vehicle routing problem，MDVRP）后，再用精確算法求解，求解結(jié)果好于已有的精確算法.由于2E-VRP是NP難問(wèn)題［6］，在問(wèn)題規(guī)模較大時(shí)，精確算法求解過(guò)程需要相當(dāng)長(zhǎng)的時(shí)間.啟發(fā)式算法有多起始點(diǎn)啟發(fā)式方法（multi-start［5］）、自適應(yīng)大鄰域搜索（adaptive large neighborhood search，ALNS［6］）算法以及Memetic算法［7］.Crainic［5］首先按與中轉(zhuǎn)站距離將需求點(diǎn)分配至中轉(zhuǎn)站，然后在此基礎(chǔ)上搜索改進(jìn)，由于算法局部開(kāi)發(fā)的程度不足，求解時(shí)間較長(zhǎng)，且精度較差.ALNS［6］算法用輪盤(pán)賭的方法將需求點(diǎn)分配至中轉(zhuǎn)站，再通過(guò)擾動(dòng)―修復(fù)―局部搜索的過(guò)程持續(xù)對(duì)當(dāng)前解進(jìn)行搜索，該方法求解質(zhì)量較高，計(jì)算速度較快，明顯優(yōu)于Crainic等［5］的多起始點(diǎn)方法，但采用的算子種類(lèi)、數(shù)目過(guò)多，實(shí)現(xiàn)過(guò)程較為復(fù)雜.許維勝等［7］設(shè)計(jì)的Memetic算法將遺傳算法與局部搜索合理組合，平衡了求解質(zhì)量與效率.此外，Crainic等［8］研究了中心倉(cāng)庫(kù)、中轉(zhuǎn)站以及需求點(diǎn)之間的相對(duì)位置關(guān)系對(duì)總成本的影響；Crainic等［9］研究了廣義的配送成本（固定成本、運(yùn)作成本、環(huán)境成本等）對(duì)2E-VRP的中轉(zhuǎn)站布局的影響.

變鄰域下降算法（variable neighborhood descent，VND［10-11］）是變鄰域搜索算法（variable neighborhood search，VNS［10-11］）的一種.VNS最早于文獻(xiàn)［11］中提出，其核心思想為對(duì)一組鄰域進(jìn)行系統(tǒng)的切換，一方面通過(guò)目標(biāo)值下降的過(guò)程找到局部最優(yōu)，另一方面通過(guò)對(duì)該局部最優(yōu)進(jìn)行擾動(dòng)以跳出局部最優(yōu)，獲得新的搜索起始點(diǎn).VND去除了VNS的擾動(dòng)過(guò)程，雖優(yōu)化效率較高，但由于缺少擾動(dòng)過(guò)程，易于陷入局部最優(yōu).

在求解困難的組合優(yōu)化問(wèn)題時(shí)，啟發(fā)式方法需要一定多樣性以搜索到全局最優(yōu).多起始點(diǎn)方法（multi-start methods［12-13］）在搜索到局部最優(yōu)時(shí)，通過(guò)生成全新的初始解進(jìn)行搜索改進(jìn)，以增加算法的多樣性，避免在改進(jìn)希望較小的解周?chē)磸?fù)無(wú)效搜索.多起始點(diǎn)方法的每次迭代均產(chǎn)生一個(gè)局部最優(yōu)值，迭代過(guò)程中最好的局部最優(yōu)值為最終的輸出.多起始點(diǎn)方法的局部開(kāi)發(fā)能力需要適當(dāng)強(qiáng)化.多起始點(diǎn)方法與變鄰域下降算法的組合已成功解決旅行維修員問(wèn)題（traveling repairman problem，TRP［14］）、卡車(chē)帶拖車(chē)路徑問(wèn)題（truck and trailer routing problem，TTRP［15］）、校車(chē)路徑問(wèn)題（school bus routing problem，SBRP［16］）等 NP難題，不僅獲得了較好的結(jié)果，而且由于實(shí)現(xiàn)過(guò)程較為簡(jiǎn)單，便于實(shí)際應(yīng)用.由于城市物流優(yōu)化需要通過(guò)易于實(shí)現(xiàn)與調(diào)整參數(shù)的算法快速給出較好的配送方案，受上述研究成果的啟發(fā)，本文選擇合適的局部搜索算子并結(jié)合多起始點(diǎn)方法，設(shè)計(jì)一種易于實(shí)現(xiàn)的多起始點(diǎn)變鄰域下降算法（multi-start variable neighborhood descent，MS-VND）求解2E-VRP，以達(dá)到求解質(zhì)量和計(jì)算時(shí)間的平衡，輔助城市物流的優(yōu)化決策.

1 2E-VRP問(wèn)題描述

2E-VRP可由節(jié)點(diǎn)（中心倉(cāng)庫(kù)、中轉(zhuǎn)站、需求點(diǎn)）集合V和邊的集合A組成的有向圖G來(lái)表示［1-6］，G=（V，A）.集合V中包含三類(lèi)節(jié)點(diǎn)：中心倉(cāng)庫(kù)V0，ns個(gè)中轉(zhuǎn)站組成的集合Vs，以及nc個(gè)需求點(diǎn)組成的集合Vc.節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離用D（i，j）表示.每個(gè)需求點(diǎn)ci的需求量為Q（ci）.每個(gè)需求點(diǎn)只能配送一次，且不允許由中心倉(cāng)庫(kù)直接配送.中轉(zhuǎn)站可由第一級(jí)車(chē)輛多次配送.同級(jí)的車(chē)輛具有相同的運(yùn)載容量約束，第一級(jí)和第二級(jí)的車(chē)輛最大容量分別為W1和W2，可用車(chē)輛數(shù)分別為K1和K2.

由于存在多個(gè)中轉(zhuǎn)站和多個(gè)需求不可分割的需求點(diǎn)，2E-VRP的第二級(jí)可看成一個(gè)MDVRP；由于中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量可能超過(guò)第一級(jí)車(chē)容量W1，進(jìn)而需要多次配送，故2E-VRP的第一級(jí)可看成需求可分割車(chē)輛路徑問(wèn)題（split-delivery vehicle routing problem，SDVRP［2］）.2E-VRP首先追求兩級(jí)使用的車(chē)輛數(shù)最少，其次兩級(jí)總配送路徑最短.2E-VRP不同于VRP：改變?nèi)我恍枨簏c(diǎn)所屬的中轉(zhuǎn)站可能影響第一級(jí)總距離；改變中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量也可能影響第二級(jí)配送方案.由于兩級(jí)的配送方案之間存在這樣相互耦合的關(guān)系［2］，因此2E-VRP的求解必須綜合考慮兩級(jí)的配送.

2 多起始點(diǎn)變鄰域下降算法

2.1 求解思路

考慮兩級(jí)問(wèn)題各自特性，為易于獲得初始可行解，自底向上求解2E-VRP［7］.在獲得第二級(jí)MDVRP的可行配送方案后，計(jì)算各個(gè)中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量，據(jù)此求解第一級(jí)的SDVRP，獲得完整的隨機(jī)初始可行解，然后通過(guò)變鄰域下降算法改進(jìn)；當(dāng)使用的幾種局部搜索算子均無(wú)法改進(jìn)時(shí)，采用多起始點(diǎn)技術(shù)重新生成隨機(jī)的初始可行解，重復(fù)變鄰域下降算法的改進(jìn)過(guò)程.到達(dá)最大迭代次數(shù)后，終止搜索過(guò)程，輸出已搜索到的最佳配送方案.

2.2 初始可行解的構(gòu)建

為增加搜索過(guò)程的多樣性，第二級(jí)的初始分配方案通過(guò)對(duì)由所有需求點(diǎn)構(gòu)成的隨機(jī)排列進(jìn)行合理的分割實(shí)現(xiàn).通過(guò)對(duì)文獻(xiàn)［7，17］的Split算法進(jìn)行改進(jìn)，考慮中轉(zhuǎn)站與中心倉(cāng)庫(kù)的距離遠(yuǎn)近，同時(shí)以優(yōu)先考慮車(chē)輛數(shù)最少，其次總路徑長(zhǎng)度最短的原則按隨機(jī)排列中的順序?qū)⑿枨簏c(diǎn)合理分配至各個(gè)中轉(zhuǎn)站，獲得第二級(jí)的配送方案.Split算法最早由Beasley［18］提出，由Prins［19］給出了詳細(xì)的實(shí)現(xiàn)過(guò)程.基本的Split算法只適用于單車(chē)場(chǎng)、單級(jí)的VRP，不適用于2E-VRP；文獻(xiàn)［7，17］中改進(jìn)的Split算法雖考慮了多個(gè)車(chē)場(chǎng)，但只針對(duì)單級(jí)情形進(jìn)行討論，并未拓展至兩級(jí)情形.除文獻(xiàn)［7］外，已有的Split算法只考慮分割距離最短單一目標(biāo)，并未考慮最小化所使用車(chē)輛數(shù).針對(duì)當(dāng)前Split算法求解2E-VRP存在的不足，并綜合考慮2E-VRP的中轉(zhuǎn)站—需求點(diǎn)之間以及中心倉(cāng)庫(kù)—中轉(zhuǎn)站之間的距離關(guān)系，改進(jìn)文獻(xiàn)［7］中的Split算法，改進(jìn)后算法的流程圖如圖2所示.

圖2中改進(jìn)的Split算法作用對(duì)象為由所有需求點(diǎn)構(gòu)成的隨機(jī)排列T，0號(hào)點(diǎn)為虛擬的起始點(diǎn)，i為當(dāng)前搜索起始點(diǎn)，j為以i為起點(diǎn)的可行弧的終點(diǎn)［7］；Ni為排列T中前i個(gè)需求點(diǎn)所需要的第二級(jí)車(chē)輛數(shù)，Li為對(duì)應(yīng)的綜合成本；為考慮中轉(zhuǎn)站與中心倉(cāng)庫(kù)之間的距離，在每條可行弧的成本中增加其所屬中轉(zhuǎn)站至中心倉(cāng)庫(kù)的距離這一懲罰項(xiàng)，從而獲得綜合成本.計(jì)算完畢后，Nnc為第二級(jí)方案所需的車(chē)輛數(shù)，Si記錄了T中第i個(gè)需求點(diǎn)所屬的中轉(zhuǎn)站，pi記錄了以第i個(gè)需求點(diǎn)為終點(diǎn)的單條路徑的起始節(jié)點(diǎn).利用Pi和Si，逆向復(fù)現(xiàn)第二級(jí)配送方案［7，17］.

獲得第二級(jí)初始可行的配送方案后，計(jì)算各個(gè)中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量，然后優(yōu)先處理轉(zhuǎn)運(yùn)量超過(guò)W1的中轉(zhuǎn)站，滿載的第一級(jí)車(chē)輛從中心倉(cāng)庫(kù)直接配送這些中轉(zhuǎn)站，同時(shí)減少其相應(yīng)的轉(zhuǎn)運(yùn)量，直至每個(gè)中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量均小于W1，將第一級(jí)的SDVRP轉(zhuǎn)化為VRP［6，20］，處理完畢后轉(zhuǎn)運(yùn)量大于零的中轉(zhuǎn)站組成第一級(jí)的排列，按照貪婪原則分配車(chē)輛，并通過(guò)局部搜索進(jìn)一步改進(jìn)［6-7］，再結(jié)合中心倉(cāng)庫(kù)與中轉(zhuǎn)站之間的直達(dá)路徑，得到第一級(jí)的配送方案；兩級(jí)的配送方案相結(jié)合，得到2E-VRP完整的初始可行解.

圖2 改進(jìn)的Split算法流程圖Fig.2 Flowchart of the improved Split algorithm

2.3 變鄰域下降算法中局部搜索算子的選擇

局部搜索分別針對(duì)第一級(jí)和第二級(jí)配送方案進(jìn)行.由于處理后的第一級(jí)是一個(gè)規(guī)模較小的VRP，采用swap和move算子［6］對(duì)第一級(jí)方案進(jìn)行搜索改進(jìn)，限定swap算子交換兩個(gè)中轉(zhuǎn)站的位置；move算子將一個(gè)中轉(zhuǎn)站移動(dòng)到另一條第一級(jí)路徑中.第一級(jí)的局部搜索僅在計(jì)算第一級(jí)總距離時(shí)執(zhí)行.

第二級(jí)問(wèn)題規(guī)模較大，所使用的局部搜索算子分為路徑內(nèi)部和路徑之間兩種.第二級(jí)路徑內(nèi)部搜索改進(jìn)采用2-Opt，Intra-swap和Intra-move算子［6］.2-Opt算子通過(guò)左右翻轉(zhuǎn)路徑內(nèi)部的一段連續(xù)的節(jié)點(diǎn)來(lái)進(jìn)行搜索改進(jìn)；Intra-swap算子將單個(gè)節(jié)點(diǎn)與單個(gè)或連續(xù)兩個(gè)節(jié)點(diǎn)交換位置來(lái)搜索改進(jìn)；Intra-move算子將單個(gè)或連續(xù)兩個(gè)節(jié)點(diǎn)前后移動(dòng)位置，移動(dòng)范圍包括一條路徑的中轉(zhuǎn)站.

第二級(jí)路徑之間算子采用2-Opt＊、Inter-swap以及Inter-move算子［6］，并針對(duì)2E-VRP擴(kuò)大了Inter-swap和Inter-move算子的搜索范圍.2-Opt＊算子分別去除兩條第二級(jí)路徑中的一條邊，再重組為兩條新路徑；Inter-swap算子交換兩條第二級(jí)路徑中的節(jié)點(diǎn)，每條路徑最多交換三個(gè)連續(xù)節(jié)點(diǎn)；當(dāng)兩條路徑分別屬于不同的中轉(zhuǎn)站時(shí)，Inter-swap算子包含這兩條路徑所屬中轉(zhuǎn)站的交換；Inter-move算子將一條第二級(jí)路徑中的需求點(diǎn)移動(dòng)到另一條中，最多允許移動(dòng)連續(xù)三個(gè)需求點(diǎn)；此外，Inter-move算子可重新分配單條第二級(jí)路徑所屬的中轉(zhuǎn)站來(lái)擴(kuò)大搜索范圍.為增強(qiáng)搜索的效能，當(dāng)路徑之間算子產(chǎn)生的新路徑均滿足第二級(jí)車(chē)容量約束時(shí)，采用路徑內(nèi)部搜索算子進(jìn)一步優(yōu)化［7］.

所有的局部搜索算子均采用First-Accept策略［6-7］以減小計(jì)算量：當(dāng)鄰域中搜索到更優(yōu)解時(shí)，立即替換當(dāng)前解，并繼續(xù)局部搜索過(guò)程.每次生成一個(gè)可行的初始解后，局部搜索算子按給定順序循環(huán)執(zhí)行，直至所有算子均無(wú)法獲得改進(jìn).由于第二級(jí)路徑內(nèi)部搜索改進(jìn)算子執(zhí)行次數(shù)較多，其與路徑之間算子結(jié)合使用時(shí)，僅順序優(yōu)化路徑之間算子鄰域中的可行解；在路徑之間算子作用之前，對(duì)當(dāng)前解的每條第二級(jí)路徑使用路徑內(nèi)部的三種算子循環(huán)優(yōu)化以徹底改進(jìn).第二級(jí)路徑之間搜索時(shí)，若兩條路徑屬于相同的中轉(zhuǎn)站，對(duì)這兩條路徑改進(jìn)時(shí)不改變中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量，故不必計(jì)算第一級(jí)總距離；若兩條路徑屬于不同的中轉(zhuǎn)站，由于改變了中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量，則必須進(jìn)一步計(jì)算第一級(jí)總距離；Inter-move算子重新分配一條第二級(jí)路徑所屬的中轉(zhuǎn)站時(shí)，由于改變了中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量，也必須進(jìn)一步計(jì)算第一級(jí)總距離［7］.

2.4 求解2E-VRP的MS-VND算法流程圖

本文的MS-VND算法流程圖可用圖3簡(jiǎn)要表述，其中參數(shù)i為當(dāng)前迭代次數(shù)，Imax為算法設(shè)定的最大迭代次數(shù)；Improve指示迭代過(guò)程中是否出現(xiàn)改進(jìn)；判定“Trips可行”是指判定其是否滿足第二級(jí)可用車(chē)輛數(shù)約束.“路徑內(nèi)部算子循環(huán)優(yōu)化S”是指對(duì)利用2-Opt，Intra-swap和Intra-move三種路徑內(nèi)部搜索算子循環(huán)改進(jìn)當(dāng)前解S的每條第二級(jí)路徑.圖中第二級(jí)路徑之間的2-Opt＊，Inter-swap以及Inter-move算子搜索過(guò)程已經(jīng)包含中轉(zhuǎn)站轉(zhuǎn)運(yùn)量變化時(shí)對(duì)第一級(jí)總距離的重新計(jì)算.由于第一級(jí)總距離的計(jì)算相對(duì)簡(jiǎn)單，且在上述三種算子的執(zhí)行過(guò)程中反復(fù)調(diào)用，故圖3并未突出顯示.

圖3 MS-VND算法流程圖Fig.3 Flowchart of MS-VND

3 仿真與分析

3.1 算例描述

本文算例取自文獻(xiàn)［8］，這些算例包含一個(gè)中心倉(cāng)庫(kù)、5個(gè)中轉(zhuǎn)站以及50個(gè)需求點(diǎn)，并采用了不同的需求點(diǎn)分布與中轉(zhuǎn)站位置組合.需求點(diǎn)有隨機(jī)分布（random）、重心分布（centroids）、象限分布（quadrants）三種分布類(lèi)型：隨機(jī)分布中需求點(diǎn)的x，y坐標(biāo)均服從［0，100］內(nèi)的均勻分布；重心分布模擬大城市中的市區(qū)和郊區(qū)，中心40×40的方塊代表市中心，市中心外圍的4個(gè)20×20的方塊代表郊區(qū)，中心方塊中有6個(gè)需求點(diǎn)群，而周?chē)總€(gè)郊區(qū)方塊中各有一個(gè)需求點(diǎn)群；象限分布模擬圍繞河流、主干道、山谷等分布的城鎮(zhèn)，需求點(diǎn)集中分布在四個(gè)象限內(nèi).中轉(zhuǎn)站有三種分布類(lèi)型：隨機(jī)分布（random），切片分布（sliced）、禁區(qū)限制（forbidden zone）：隨機(jī)分布表示沒(méi)有任何限制，中轉(zhuǎn)站可分布在城市周?chē)娜魏挝恢?；切片分布是指將城市周?chē)譃閚s塊，每塊隨機(jī)放置一個(gè)中轉(zhuǎn)站；禁區(qū)限制模擬需求點(diǎn)靠近海邊或者山脈分布的情形，有些地點(diǎn)無(wú)法設(shè)置中轉(zhuǎn)站，中轉(zhuǎn)站需要設(shè)置在這些禁區(qū)外.

3.2 實(shí)驗(yàn)設(shè)置

在主頻為2.8GHz的Intel奔騰雙核E5500處理器（只使用單核心）、內(nèi)存為2GB的硬件平臺(tái)上通過(guò)Microsoft Visual C++6.0實(shí)現(xiàn)本文求解2EVRP的MS-VND算法.設(shè)置最大迭代次數(shù)為1 000，為便于和ALNS［6］對(duì)比，每個(gè)算例均進(jìn)行了5輪獨(dú)立的計(jì)算.

3.3 實(shí)驗(yàn)結(jié)果與對(duì)比分析

針對(duì)18個(gè)標(biāo)準(zhǔn)算例的測(cè)試結(jié)果如表1所示，除時(shí)間外，表中的數(shù)值均未設(shè)定單位，可表示車(chē)輛行駛的總里程，也可表示車(chē)輛行駛的總時(shí)間.ALNS［6］算法在主頻為2.2GHz的AMD Opteron CPU上通過(guò)C++實(shí)現(xiàn)，每個(gè)算例均進(jìn)行5輪的獨(dú)立計(jì)算；MA為Memetic算法［7］在本文的軟硬件環(huán)境下的測(cè)試結(jié)果，除5輪獨(dú)立計(jì)算外，均使用文獻(xiàn)［7］中原有的參數(shù)配置；MS-VND為本文提出的多起始點(diǎn)變鄰域下降算法的測(cè)試結(jié)果.考慮到ALNS算法實(shí)現(xiàn)的硬件平臺(tái)差異，為公平比較算法的時(shí)間，從文獻(xiàn)［21］中獲得兩種CPU的性能得分（分別為1 234和1 658），在此基礎(chǔ)上對(duì)計(jì)算時(shí)間進(jìn)行比例縮放［5］：以ALNS算法的計(jì)算時(shí)間為基準(zhǔn)，MA和MS-VND的計(jì)算時(shí)間在原有基礎(chǔ)上乘以1 658再除以1 234.表1中給出了三種算法公平化之后最好結(jié)果首次出現(xiàn)的平均時(shí)間.表1中，加粗的數(shù)值表明MS-VND算法的結(jié)果優(yōu)于其他兩種算法，加下劃線的數(shù)值表明其結(jié)果不如其他兩種算法.

表1 2E-VRP標(biāo)準(zhǔn)算例測(cè)試結(jié)果比較Tab.1 Computational results comparison for 2E-VRP benchmark instances

表1分別進(jìn)行了算法求解質(zhì)量與計(jì)算時(shí)間的比較分析.MA無(wú)論是最好結(jié)果還是平均結(jié)果都不如ALNS與MS-VND，且差距較為明顯，故單獨(dú)比較ALNS與MS-VND.從算法獲得的最好結(jié)果來(lái)說(shuō)，MS-VND在每個(gè)算例下的最好結(jié)果均達(dá)到或優(yōu)于ALNS，特別地，Instance50-s5-45和Instance50-s5-47這兩個(gè)算例的最好結(jié)果優(yōu)于ALNS；此外，MS-VND均獲得了這幾個(gè)算例當(dāng)前已知的最好結(jié)果［4］.從算法5次獨(dú)立計(jì)算獲得的平均結(jié)果來(lái)說(shuō)，除了算例Instance50-s5-37的平均值略次于ALNS外，MSVND在其他算例下的運(yùn)行結(jié)果的平均值均達(dá)到或優(yōu)于ALNS算法，且有9個(gè)算例的平均值優(yōu)于ALNS.綜合評(píng)價(jià)計(jì)算結(jié)果質(zhì)量，可知MS-VND算法優(yōu)于ALNS算法與Memetic算法.

從三種算法最好解出現(xiàn)的平均時(shí)間考察算法的計(jì)算效率.由于三種算法時(shí)間均已考慮硬件配置進(jìn)行公平化處理，故可直接比較.從表1可見(jiàn)，這三種算法的計(jì)算時(shí)間均不超過(guò)2min，較為合理；由于ALNS與MS-VND的計(jì)算結(jié)果質(zhì)量明顯優(yōu)于MA，故先比較ALNS與MS-VND的計(jì)算時(shí)間，MS-VND在5個(gè)算例下計(jì)算時(shí)間慢于ALNS，其余13個(gè)算例下計(jì)算時(shí)間均快于ALNS；ALNS有4個(gè)算例的計(jì)算時(shí)間達(dá)到或超過(guò)1min，而 MS-VND只有1個(gè).MA的計(jì)算時(shí)間均在1min之內(nèi)，計(jì)算速度較快，但由其較差的求解質(zhì)量可知，由于局部開(kāi)發(fā)的程度不夠，算法陷入早熟收斂.從計(jì)算時(shí)間角度看，MSVND優(yōu)于ALNS算法，且與Memetic算法接近.

再結(jié)合算法實(shí)現(xiàn)過(guò)程與參數(shù)調(diào)節(jié)的難易程度進(jìn)行比較，ALNS需要實(shí)現(xiàn)的算子與需要調(diào)節(jié)的參數(shù)數(shù)目均最為復(fù)雜，MA其次，而本文的MS-VND只需要實(shí)現(xiàn)1種改進(jìn)的Split算法、6種簡(jiǎn)單的局部搜索算子，并設(shè)置1個(gè)最大迭代次數(shù)即可，實(shí)現(xiàn)過(guò)程最為容易，更有利于實(shí)際應(yīng)用.

綜合考查算法的結(jié)果質(zhì)量、計(jì)算時(shí)間以及實(shí)現(xiàn)與參數(shù)調(diào)節(jié)的難易程度這幾方面的因素，可知本文提出的MS-VND算法優(yōu)于ALNS算法與Memetic算法，更便于在城市物流優(yōu)化決策中應(yīng)用.

4 結(jié)論

本文針對(duì)城市物流中新出現(xiàn)的兩級(jí)車(chē)輛路徑問(wèn)題（2E-VRP），設(shè)計(jì)了一種多起始點(diǎn)變鄰域下降算法（MS-VND）進(jìn)行求解，針對(duì)2E-VRP改進(jìn)了已有的Split算法以獲得隨機(jī)的初始可行解，并擴(kuò)展了VND中幾種局部搜索算子的搜索范圍.標(biāo)準(zhǔn)算例的實(shí)驗(yàn)結(jié)果表明，所提算法平衡了求解質(zhì)量與計(jì)算時(shí)間，性能優(yōu)于當(dāng)前求解2E-VRP最好的兩種啟發(fā)式算法.此外，由于算法的實(shí)現(xiàn)過(guò)程與參數(shù)調(diào)節(jié)較為簡(jiǎn)單，在城市物流優(yōu)化決策過(guò)程中更有實(shí)際意義.

下一步的工作將結(jié)合城市物流的實(shí)際情形提出更為精細(xì)的模型，并改進(jìn)本文的算法進(jìn)行求解.

［1］ Perboli G，Tadei R，Vigo D.The two-echelon capacitated vehicle routing problem：models and math-based heuristics［J］.Transportation Science，2011，45（3）：364.

［2］ Jepsen M，Spoorendonk S，Ropke S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem［J］.Transportation Science，2013，47（1）：23.

［3］ Perboli G，Tadei R.New families of valid inequalities for the two-echelon vehicle routing problem［J］.Electronic Notes in Discrete Mathematics，2010，36：639.

［4］ Baldacci R，Mingozzi A，Roberti R，etal.An exact algorithm for the two-echelon capacitated vehicle routing problem［J］.Operations Research，2013，61（2）：298.

［5］ Crainic T G，Mancini S，Perboli G，etal.Multi-start heuristics for the two-echelon vehicle routing problem［J］.Lecture Notes in Computer Science，2011，6622：179.

［6］ Hemmelmayr V C，Cordeau J F，Crainic T G.An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics［J］.Computers &Operations Research，2012，39（12）：3215.

［7］ 許維勝，曾正洋，徐志宇.一種求解兩級(jí)車(chē)輛路徑問(wèn)題的Memetic算法［J］.控制與決策，2013，28（10）：1587.XU Weisheng，ZENG Zhengyang，XU Zhiyu.A memetic algorithm for solving the two-echelon vehicle routing problem［J］.Control and Decision，2013，28（10）：1587.

［8］ Crainic T G，Perboli G，Mancini S，etal.The two-echelon vehicle routing problem：a satellite location analysis［J］.Procedia Social and Behavioral Science，2010，2（3）：5944.

［9］ Crainic T G，Mancini S，Perboli G，etal.Impact of generalized travel costs on satellite location in the two-echelon vehicle routing problem［J］.Procedia Social and Behavioral Science，2012，39：195.

［10］ Hansen P， Mladenovic N，Brimberg J，etal.Variable neighborhood search［C］//Handbook of Metaheuristics.New York：Spring Science Business Media，2010：61-86.

［11］ Mladenovic N，Hansen P.Variable neighborhood search［J］.Computers &Operations Research，1997，24（11）：1097.

［12］ MartíR，Moreno-VegaJ M，Duarte A.Advanced multi-start methods［C］//Handbook of Metaheuristics.New York：Spring Science Business Media，2010：265-281.

［13］ MartíR，Resende M G C，Ribeiro C C.Multi-start methods for combinatorial optimization ［J］.European Journal of Operational Research，2013，226（1）：1.

［14］ Salehipour A，Sorensen K，Goos P，etal.Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem ［J］.4OR—A Quarterly Journal of Operations Research，2011，9（2）：189.

［15］ Villegas J G，Prins C，Prodhon C，etal.GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots［J］.Engineering Applications of Artificial Intelligence，2010，23（5）：780.

［16］ Schittekat P，Kinable J，S?rensen K，etal.A metaheuristic for the school bus routing problem with bus stop selection［J］.European Journal of Operational Research，2013，229（2）：518.

［17］ Nguyen V P，Prins C，Prodhon C.Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking［J］.European Journal of Operational Research，2012，216（1）：113.

［18］ Beasley J E.Route first-cluster second methods for vehicle routing［J］.Omega，1983，11（4）：403.

［19］ Prins C.A simple and effective evolutionary algorithm for the vehicle routing problem［J］.Computers &Operations Research，2004，31（12）：1985.

［20］ Archetti C，Speranza M G，Hertz A.A tabu search algorithm for the split delivery vehicle routing problem ［J］.Transportation Science，2006，40（1）：64.

［21］ Prins C.CPU benchmarks［EB/OL］.［2014-07-02］.http：//www.cpubenchmark.net/cpu＿list.php.