李妍峰，李 佳，向 婷

(西南交通大學(xué) 1.經(jīng)濟(jì)管理學(xué)院；2.服務(wù)科學(xué)與創(chuàng)新四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610031)

隨著科技的進(jìn)步與發(fā)展，無(wú)人機(jī)不僅應(yīng)用在軍事方面，在民用物流服務(wù)方面也得到廣泛應(yīng)用。無(wú)人機(jī)靈活、快速的特點(diǎn)為提升物流效率帶來(lái)很大空間。許多電商及物流企業(yè)相繼展開(kāi)了無(wú)人機(jī)項(xiàng)目，如順豐、亞馬遜、谷歌、DHL等[1]。但同時(shí)無(wú)人機(jī)也具有載重能力小、續(xù)航時(shí)間短等缺點(diǎn)，在實(shí)際配送中往往需要與卡車(chē)協(xié)同配送，發(fā)揮二者的優(yōu)勢(shì)。

近幾年來(lái)，無(wú)人機(jī)與卡車(chē)協(xié)同配送路徑優(yōu)化問(wèn)題引起國(guó)內(nèi)外學(xué)者的廣泛研究。不同于經(jīng)典車(chē)輛路徑問(wèn)題(vehicle routing problem，VRP)，引入無(wú)人機(jī)后，兩種訪問(wèn)方式結(jié)合的復(fù)雜路徑關(guān)系使問(wèn)題建模與求解的難度增大[2]。Murray等[1]最早提出無(wú)人機(jī)協(xié)助包裹遞送的旅行商問(wèn)題(the flying sidekick traveling salesman problem，F(xiàn)STSP)，引起學(xué)者們的關(guān)注。隨后研究從載有無(wú)人機(jī)的旅行商問(wèn)題(traveling salesman problem with drone，TSPD)[1-7]進(jìn)一步拓展到載有無(wú)人機(jī)的車(chē)輛路徑問(wèn)題(vehicle routing problem with drone，VRPD)[8-14]。目前文獻(xiàn)對(duì)于VRPD問(wèn)題研究主要從以下幾個(gè)方面考慮。在問(wèn)題優(yōu)化目標(biāo)的設(shè)置上，大多數(shù)研究以最小化完成配送的時(shí)間為目標(biāo)[1,3-4,6,9-10,12,14]。Chang等[7]則將目標(biāo)函數(shù)設(shè)置為最小化總配送時(shí)間。Wang等[8]、Schermer等[11]和Pugliese等[13]提出最小化卡車(chē)與無(wú)人機(jī)運(yùn)輸成本。Ha等[2]提出以最小化運(yùn)輸成本和等待成本為目標(biāo)。在無(wú)人機(jī)單次可訪問(wèn)顧客的數(shù)量設(shè)置方面，由于無(wú)人機(jī)載重量較小，大多數(shù)文獻(xiàn)考慮無(wú)人機(jī)一次只能訪問(wèn)一個(gè)顧客點(diǎn)，只有Wang等[8]和Ham[14]考慮在不超過(guò)載重的情形下，無(wú)人機(jī)單次可訪問(wèn)多個(gè)顧客點(diǎn)。在可供使用的卡車(chē)與無(wú)人機(jī)數(shù)目方面，針對(duì)TSPD問(wèn)題，Murray等[1]、Ha等[2]、Yurek等[3]及Ponza[4]提出一輛卡車(chē)只能攜載一架無(wú)人機(jī)；Carlsson等[5]、Boysen等[6]與Chang等[7]考慮一輛卡車(chē)可攜載多架無(wú)人機(jī)的情形。針對(duì)VRPD問(wèn)題，可同時(shí)使用多輛卡車(chē)用于配送，卡車(chē)的承載力又分為每輛車(chē)只攜載一架無(wú)人機(jī)[9,12-13]及每輛卡車(chē)可載多架無(wú)人機(jī)[8,10-11,14]的情形。在求解算法方面，除Wang等[8]設(shè)計(jì)精確算法求解外，其余文獻(xiàn)均設(shè)計(jì)啟發(fā)式算法，在生成初始解后采取一些優(yōu)化策略進(jìn)一步提升解的質(zhì)量。

目前在VRPD的研究中，未從顧客點(diǎn)的分布特征考慮。例如在一些邊遠(yuǎn)地區(qū)，顧客點(diǎn)分布相對(duì)稀疏，交通不便和卡車(chē)較大的平均運(yùn)輸成本為卡車(chē)配送服務(wù)帶來(lái)困難。京東曾指出無(wú)人機(jī)快遞服務(wù)可用于解決農(nóng)村地區(qū)的快遞配送問(wèn)題[15]?；诖吮尘埃疚母鶕?jù)顧客點(diǎn)的分布特征將顧客點(diǎn)分為僅由無(wú)人機(jī)配送和由卡車(chē)與無(wú)人機(jī)協(xié)同配送兩類(lèi)。另外，已有研究均僅考慮每個(gè)顧客由一架無(wú)人機(jī)訪問(wèn)的情形[1-14]，而在實(shí)際中，由于無(wú)人機(jī)的載重量較小，單架無(wú)人機(jī)的載重量很難完全滿(mǎn)足顧客需要，因此本文考慮顧客需求可拆分屬性，當(dāng)需求量大于無(wú)人機(jī)載重時(shí)，允許包裹拆分，且每個(gè)顧客可被無(wú)人機(jī)訪問(wèn)多次。在上述問(wèn)題特性的基礎(chǔ)上，以最小化運(yùn)輸成本和使用卡車(chē)的人力成本為目標(biāo)，考慮卡車(chē)載重量、無(wú)人機(jī)載重量和續(xù)航時(shí)間、需求拆分比例和路徑可行性等約束，建立混合整數(shù)規(guī)劃模型，并根據(jù)問(wèn)題屬性設(shè)計(jì)一種改進(jìn)變鄰域搜索算法，對(duì)不同算例規(guī)模下的問(wèn)題進(jìn)行數(shù)值實(shí)驗(yàn)驗(yàn)證算法的求解性能。

1 問(wèn)題描述及模型建立

1.1 問(wèn)題描述

本文考慮基于顧客點(diǎn)的分布特征的無(wú)人機(jī)與卡車(chē)分區(qū)域協(xié)同配送問(wèn)題。根據(jù)客戶(hù)需求的分布，將配送區(qū)域分為需求稀疏區(qū)域和需求密集區(qū)域。需求稀疏區(qū)域的客戶(hù)由于距離配送中心較遠(yuǎn)且運(yùn)輸成本較大，安排無(wú)人機(jī)進(jìn)行服務(wù)。而在需求密集地區(qū)，無(wú)人機(jī)與卡車(chē)兩種配送方式均可采用。對(duì)應(yīng)的顧客點(diǎn)也可分為兩類(lèi)：卡車(chē)與無(wú)人機(jī)二者均可訪問(wèn)的顧客點(diǎn)(第1類(lèi)顧客點(diǎn))；只能由無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)(第2類(lèi)顧客點(diǎn))。

卡車(chē)攜載無(wú)人機(jī)從配送中心出發(fā)去服務(wù)兩類(lèi)顧客點(diǎn)，配送任務(wù)結(jié)束后回到中心，且在途中承擔(dān)發(fā)送和接收無(wú)人機(jī)的服務(wù)。由于無(wú)人機(jī)載重量較小，當(dāng)需求超出無(wú)人機(jī)載重時(shí)，允許拆分包裹，多次訪問(wèn)該顧客。其中，對(duì)于第1類(lèi)顧客點(diǎn)：當(dāng)需求重量不超過(guò)無(wú)人機(jī)載重量時(shí)，采用兩種配送方式中的任意一種；當(dāng)需求重量超過(guò)無(wú)人機(jī)載重量時(shí)，或不拆分采用卡車(chē)配送，或拆分后采用無(wú)人機(jī)多次配送。對(duì)于第2類(lèi)顧客點(diǎn)，只采用無(wú)人機(jī)配送方式，當(dāng)需求量超出無(wú)人機(jī)載重，則拆分后配送。本文提出的需求可拆分的無(wú)人機(jī)與車(chē)輛協(xié)同路徑問(wèn)題(split delivery vehicle routing problem with drone, SDVRPD)還具有如下特點(diǎn)。

1) 要求所有顧客點(diǎn)均被訪問(wèn)；

2) 每輛車(chē)最多承載一架無(wú)人機(jī)；

3) 無(wú)人機(jī)一次只能訪問(wèn)一個(gè)顧客，但每架無(wú)人機(jī)可以多次訪問(wèn)顧客；

4) 在運(yùn)輸過(guò)程中，隨車(chē)無(wú)人機(jī)只能從其搭載車(chē)輛出發(fā)并回到該車(chē)輛；

5) 無(wú)人機(jī)的起飛點(diǎn)與著陸點(diǎn)不同；

6) 在無(wú)人機(jī)訪問(wèn)顧客時(shí)，允許拆分包裹，多次服務(wù)，無(wú)人機(jī)每次攜帶的包裹重量不能超過(guò)其載重；

7) 每個(gè)顧客的需求只能由卡車(chē)與無(wú)人機(jī)其中一種配送方式服務(wù)。

圖1是本文卡車(chē)與無(wú)人機(jī)協(xié)同配送問(wèn)題的示例，共有3輛卡車(chē)提供服務(wù)。0點(diǎn)表示配送中心，1 ～6，9 ～ 12，15 ～ 17點(diǎn)表示第1類(lèi)點(diǎn)，其中1 ～ 5，9 ～12，15 ～ 17點(diǎn)由卡車(chē)訪問(wèn)，6、13點(diǎn)由無(wú)人機(jī)訪問(wèn)；7 ～ 8、14、18點(diǎn)表示第2類(lèi)點(diǎn)，7、14點(diǎn)無(wú)人機(jī)單次配送即可滿(mǎn)足，8、18點(diǎn)需求拆分，無(wú)人機(jī)兩次訪問(wèn)滿(mǎn)足。

圖1 問(wèn)題示例Figure 1 Example of problem

1.2 符號(hào)說(shuō)明

1.3 模型建立

目標(biāo)函數(shù)(1)是最小化總成本，包括使用卡車(chē)的人力成本以及卡車(chē)與無(wú)人機(jī)的行駛成本；約束(2)表示對(duì)于車(chē)輛不可達(dá)的客戶(hù)點(diǎn)，只能由無(wú)人機(jī)進(jìn)行配送；約束(3)表示對(duì)配送方式無(wú)要求的顧客，車(chē)輛與無(wú)人機(jī)送貨均可；約束(4)表示每輛卡車(chē)訪問(wèn)顧客的需求量與其承載無(wú)人機(jī)的訪問(wèn)顧客需求量之和不能超過(guò)卡車(chē)最大載重量；約束(5)表示無(wú)人機(jī)每次服務(wù)顧客攜帶的包裹重量不超過(guò)無(wú)人機(jī)的載重量；約束(6)表示無(wú)人機(jī)飛行時(shí)長(zhǎng)不能超過(guò)其最大續(xù)航時(shí)間；約束(7)表示對(duì)第1類(lèi)顧客點(diǎn)而言，若卡車(chē)訪問(wèn)該點(diǎn)，則必須從該點(diǎn)離開(kāi)到達(dá)其他點(diǎn)；約束(8)和(9)表示卡車(chē)從配送中心出發(fā)，服務(wù)后返回配送中心；約束(10)和(11)表示無(wú)人機(jī)離開(kāi)與返回卡車(chē)的點(diǎn)必須有卡車(chē)訪問(wèn)以發(fā)送和接收無(wú)人機(jī)；約束(12)表示若第1類(lèi)點(diǎn)由卡車(chē)訪問(wèn)，則無(wú)需無(wú)人機(jī)訪問(wèn)；約束(13)表示只有使用卡車(chē)，對(duì)應(yīng)搭載的無(wú)人機(jī)才可能有訪問(wèn)路線；約束(14)表示若攜載無(wú)人機(jī)則必有航行路徑，無(wú)攜載無(wú)人機(jī)則沒(méi)有；約束(15) ～ (18)為卡車(chē)路徑的避免子環(huán)約束，由于配送中心既作為出發(fā)點(diǎn)又作為終止點(diǎn)，本文沒(méi)有設(shè)置兩個(gè)集合分別表示出發(fā)與到達(dá)[1-11]，而將0點(diǎn)單獨(dú)考慮；約束(19)和(20)為兩變量的轉(zhuǎn)換關(guān)系；約束(21)保證在卡車(chē)訪問(wèn)順序中訪問(wèn)無(wú)人機(jī)起飛點(diǎn)要先于著陸點(diǎn)；約束(22)和(23)表示無(wú)人機(jī)訪問(wèn)的先后順序，不可交叉進(jìn)行：針對(duì)同一架無(wú)人機(jī)的兩次訪問(wèn)，若一次訪問(wèn)的起飛點(diǎn)訪問(wèn)次序后于另一次訪問(wèn)的起飛點(diǎn)，則其訪問(wèn)次序也后于另一次訪問(wèn)的著陸點(diǎn)；約束(24) ～ (26)表示無(wú)人機(jī)攜帶重量比例的關(guān)系：針對(duì)所有由無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)，分配比例之和為1；約束(27) ～ (30)表示變量為0-1決策變量。

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

Murray等[1]指出FSTSP是NP-hard問(wèn)題，本文所提出的SDVRPD是該問(wèn)題的擴(kuò)展，因此也是NP-hard問(wèn)題。精確算法只能求解小規(guī)模問(wèn)題，對(duì)于大規(guī)模問(wèn)題求解非常困難。因此，本文設(shè)計(jì)一種改進(jìn)的變鄰域搜索算法(improved variable neighborhood search,IVNS)來(lái)求解本問(wèn)題。在已有文獻(xiàn)中，變鄰域搜索對(duì)于求解路徑優(yōu)化問(wèn)題表現(xiàn)出很好的性能[16-19]。結(jié)合問(wèn)題特性，在初始解產(chǎn)生上，首先針對(duì)無(wú)人機(jī)載重量超出顧客需求的第2類(lèi)顧客點(diǎn)進(jìn)行拆分，構(gòu)造虛擬顧客點(diǎn)，然后安排所有顧客點(diǎn)由卡車(chē)訪問(wèn)，采用貪心策略將第2類(lèi)顧客點(diǎn)改為由無(wú)人機(jī)訪問(wèn)，從而得到變鄰域搜索的初始解；根據(jù)模型特征，本文設(shè)計(jì)6種適用于問(wèn)題的鄰域算子用于鄰域搜索和擾動(dòng)；最后，設(shè)計(jì)兩種改進(jìn)算子進(jìn)一步提升解的質(zhì)量。本文所設(shè)計(jì)算法的框架如表1所示。

表1 改進(jìn)變鄰域搜索算法的整體框架Table 1 The overall framework of IVNS

2.1 預(yù)處理

在本問(wèn)題中，由于第2類(lèi)顧客只能采用無(wú)人機(jī)方式進(jìn)行配送且無(wú)人機(jī)載重量較小，因此允許拆分配送。針對(duì)這一特性，編碼前首先進(jìn)行預(yù)處理。將第2類(lèi)顧客點(diǎn)中超出無(wú)人機(jī)載重量的顧客拆分為n個(gè)顧客(n是采用無(wú)人機(jī)訪問(wèn)方式下客戶(hù)需求的最小拆分?jǐn)?shù))，即虛擬n-1個(gè)顧客點(diǎn)，虛擬顧客點(diǎn)的坐標(biāo)與原坐標(biāo)相同。在需求的分配上，根據(jù)模型中的隨機(jī)化設(shè)置，將總需求量隨機(jī)分配給這n個(gè)顧客，各自的需求都不超過(guò)最大載重量。具體步驟如表2所示。

表2 預(yù)處理的操作步驟Table 2 Operation steps of encoding preprocessing

2.2 初始解的構(gòu)造

在Kitjacharoenchai等[9]的研究中，所有顧客均可采用卡車(chē)和無(wú)人機(jī)兩種方式訪問(wèn)，初始解通過(guò)安排所有顧客由卡車(chē)訪問(wèn)來(lái)產(chǎn)生，由于本問(wèn)題要求第2類(lèi)點(diǎn)必須由無(wú)人機(jī)進(jìn)行訪問(wèn)，這種方式并不完全適用。結(jié)合問(wèn)題特征，設(shè)計(jì)新的初始解產(chǎn)生方式，具體流程如下。

Step 1 所有顧客均由車(chē)輛訪問(wèn)，隨機(jī)生成路徑序列，若卡車(chē)載重量無(wú)法滿(mǎn)足則使用下一輛車(chē)，設(shè)使用車(chē)數(shù)為K，每輛車(chē)的路徑為Rk(k=1-K)。

Step 2 初始化：k=1。

Step 3 將Rk中第2類(lèi)顧客點(diǎn)從中剔除，放入集合Fk中，剩余包括第1類(lèi)點(diǎn)的序列Rk′。

Step 4 將集合Fk中的顧客點(diǎn)依次插入序列Rk′中，插入方法采用貪心策略：每點(diǎn)優(yōu)先被插入到運(yùn)輸成本最低的位置，同時(shí)需考慮該種插入方式是否超出無(wú)人機(jī)續(xù)航時(shí)間，若超出則選擇成本次低位置，重新考慮續(xù)航約束，直至Fk中的所有點(diǎn)被插入完成，k=k+1。

Step 5 若k≤K，轉(zhuǎn)向Step 3；否則結(jié)束，從而得到初始解。

2.3 鄰域算子及算法框架

變鄰域搜索利用不同的鄰域結(jié)構(gòu)進(jìn)行交替搜索，在集中性和疏散性之間達(dá)到很好的平衡。鄰域算子用來(lái)從當(dāng)前解中產(chǎn)生新解，本文設(shè)計(jì)多種滿(mǎn)足問(wèn)題特性的鄰域結(jié)構(gòu)用于變鄰域搜索。在執(zhí)行所有的鄰域操作時(shí)，都要考慮執(zhí)行操作后，更改訪問(wèn)路徑的無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)是否超出無(wú)人機(jī)續(xù)航時(shí)間，若超出則不執(zhí)行該操作，從而避免不可行情況。在下降算法部分共采用6種鄰域結(jié)構(gòu)提升解的質(zhì)量，包括4種線路內(nèi)鄰域算子(見(jiàn)圖2)和2種線路間鄰域算子(見(jiàn)圖3)。擾動(dòng)部分采用5種鄰域結(jié)構(gòu)，包括更換無(wú)人機(jī)起止點(diǎn)、子序列逆序、無(wú)人機(jī)兩點(diǎn)交換以及將卡車(chē)兩點(diǎn)交換拆分為相鄰兩點(diǎn)交換和不相鄰交換。

圖3 線路間鄰域算子Figure 3 Neighborhood operator between lines

2.3.1 鄰域算子

線路內(nèi)鄰域算子如下所示。

1) 更換無(wú)人機(jī)起止點(diǎn)(如圖2(a))：改變無(wú)人機(jī)的原插入位置到新的位置。

2) 子序列逆序(如圖2(b))：在卡車(chē)路徑中隨機(jī)選擇一條子路徑，將該序列逆序，子序列兩端相關(guān)聯(lián)的由無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)更改斷開(kāi)的單側(cè)起飛點(diǎn)或著陸點(diǎn)，內(nèi)側(cè)無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)更換起止點(diǎn)的前后關(guān)系。

3) 無(wú)人機(jī)兩點(diǎn)交換（如圖2(c))：隨機(jī)選擇兩個(gè)無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)，交換位置。

4) 卡車(chē)兩點(diǎn)交換（如圖2(d))：隨機(jī)選擇兩卡車(chē)訪問(wèn)的顧客點(diǎn)交換位置，相關(guān)聯(lián)的無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)的起止點(diǎn)隨之改變。

線路間鄰域算子如下所示。

1) 無(wú)人機(jī)兩點(diǎn)交換(如圖3(a))：分別在兩條不同卡車(chē)路徑中選擇一點(diǎn)，交換位置。

2) 卡車(chē)兩點(diǎn)交換(如圖3(b))：分別在兩條搭載不同卡車(chē)的無(wú)人機(jī)路徑中選擇一點(diǎn)，交換位置，相關(guān)聯(lián)的無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)的起止點(diǎn)隨之改變。

2.3.2 鄰域搜索算法框架

鄰域搜索算法框架如表3所示。

表3 鄰域搜索算法框架Table 3 The flow of the neighborhood search algorithm

2.4 進(jìn)一步改進(jìn)

在初始解產(chǎn)生過(guò)程中，由無(wú)人機(jī)訪問(wèn)的顧客點(diǎn)安排在卡車(chē)訪問(wèn)路徑中相鄰的兩點(diǎn)間插入，且在2.3節(jié)中設(shè)計(jì)的鄰域算子中也保持這一特點(diǎn)。為了進(jìn)一步優(yōu)化路徑，設(shè)計(jì)一個(gè)起止點(diǎn)延伸的算子，若無(wú)人機(jī)航行起點(diǎn)與終點(diǎn)不相鄰時(shí)能使降低成本，則執(zhí)行該操作。另外，在鄰域搜索的過(guò)程中，因?yàn)榈?類(lèi)顧客點(diǎn)只能采用無(wú)人機(jī)進(jìn)行訪問(wèn)，所以?xún)?yōu)先滿(mǎn)足第2類(lèi)顧客點(diǎn)使用無(wú)人機(jī)訪問(wèn)，第1類(lèi)顧客點(diǎn)則全部由卡車(chē)訪問(wèn)。事實(shí)上，針對(duì)第1類(lèi)顧客點(diǎn)，采用無(wú)人機(jī)訪問(wèn)方式很大程度能減少成本，因此設(shè)計(jì)卡車(chē)點(diǎn)改為無(wú)人機(jī)點(diǎn)這一算子。兩種算子操作如下。

1)起止點(diǎn)延伸(如圖4(a))：將無(wú)人機(jī)所訪問(wèn)顧客點(diǎn)的出發(fā)點(diǎn)或著陸點(diǎn)向外延伸，跨點(diǎn)訪問(wèn)。

2)卡車(chē)點(diǎn)改為無(wú)人機(jī)點(diǎn)(如圖4(b))：將由卡車(chē)訪問(wèn)的顧客點(diǎn)改為由無(wú)人機(jī)訪問(wèn)，將該點(diǎn)從原卡車(chē)路徑中刪除，若需求量小于無(wú)人機(jī)載重，尋找成本最小位置插入；若需求量大于無(wú)人機(jī)載重，將該點(diǎn)拆分后分別尋找成本最小位置插入。

圖4 改進(jìn)鄰域算子Figure 4 Improved neighborhood operator

3 數(shù)值實(shí)驗(yàn)

以下3.1節(jié)通過(guò)小規(guī)模算例對(duì)問(wèn)題特性進(jìn)行分析(采用ILOG Cplex12.9對(duì)模型進(jìn)行求解)，3.2節(jié)對(duì)構(gòu)造的不同規(guī)模算例進(jìn)行數(shù)值實(shí)驗(yàn)，通過(guò)與Cplex的求解結(jié)果對(duì)比，對(duì)改進(jìn)的變鄰域算法的效率進(jìn)行驗(yàn)證。算法采用C#語(yǔ)言進(jìn)行編程實(shí)現(xiàn)，實(shí)驗(yàn)均在i5-5250CPU，主頻1.6 GHz，內(nèi)存4 G的PC上進(jìn)行。

3.1 參數(shù)分析

本節(jié)構(gòu)造包含7個(gè)第1類(lèi)顧客點(diǎn)和3個(gè)第2類(lèi)顧客點(diǎn)的算例。參考文獻(xiàn)[12]的數(shù)據(jù)，參數(shù)設(shè)置如下。C=1 300 kg，C′= 5 kg，v= 50 km/h，T= 1，cT= 0.6 元/km，cD= 10%·cT= 0.06 元/km，cF= 50 元/輛。通過(guò)對(duì)卡車(chē)載重C、無(wú)人機(jī)載重C′和無(wú)人機(jī)運(yùn)輸成本cD的靈敏度分析對(duì)問(wèn)題特性進(jìn)行分析。顧客點(diǎn)的坐標(biāo)及需求量如表4所示。

表4 顧客點(diǎn)信息Table 4 Customer information

3.1.1 卡車(chē)載重C分析

表5給出C=30，60，90時(shí)，傳統(tǒng)的卡車(chē)單獨(dú)送貨(VRP)和無(wú)人機(jī)與卡車(chē)協(xié)同送貨(SDVRPD)兩種情況下求解的目標(biāo)函數(shù)值、使用卡車(chē)數(shù)和訪問(wèn)路徑，以及SDVRPD相比VRP目標(biāo)函數(shù)值的節(jié)省比(%)。兩種情況下的顧客點(diǎn)信息均采用表1數(shù)據(jù)，其中，VRP不區(qū)分顧客點(diǎn)類(lèi)別，1 ～ 10點(diǎn)全部由卡車(chē)訪問(wèn)。

表5 不同C 下的求解結(jié)果Table 5 Solution results under different C

從表5中可以看出，在不同的卡車(chē)載重量下，SDVRPD和VRP所用車(chē)數(shù)相同，但訪問(wèn)路徑不同，甚至每條路徑的顧客分配也不同，這主要由于無(wú)人機(jī)與卡車(chē)單位運(yùn)輸成本差異較大，不同路徑下無(wú)人機(jī)訪問(wèn)節(jié)省的成本更大，可以在抵消卡車(chē)更換路徑增加的成本后仍使成本減少。另外，隨著卡車(chē)載重量的增大，使用卡車(chē)數(shù)目逐漸減少，目標(biāo)函數(shù)值隨之減少，節(jié)省比例逐漸增加，從4.82%增加到9.5%。

3.1.2 無(wú)人機(jī)載重C′分析

表6給出了C′=3, 4, 5, 6, 7, 8時(shí)的目標(biāo)函數(shù)值、第2類(lèi)顧客點(diǎn)的拆分點(diǎn)數(shù)、訪問(wèn)路徑以及相比VRP目標(biāo)函數(shù)值的節(jié)省比(%)。圖5給出了目標(biāo)函數(shù)值隨無(wú)人機(jī)載重C′的變化曲線。

由表6可知，在不同載重下，卡車(chē)訪問(wèn)路徑的順序變化不大，主要影響的是無(wú)人機(jī)的訪問(wèn)路徑。隨著C′的增大，無(wú)人機(jī)在單次訪問(wèn)過(guò)程中能夠滿(mǎn)足更大需求量，第2類(lèi)顧客點(diǎn)中需拆分的顧客數(shù)隨之減少，并且拆分點(diǎn)生成的虛擬顧客個(gè)數(shù)也會(huì)減少，從而減少訪問(wèn)第2類(lèi)顧客的運(yùn)輸成本；另外，增大無(wú)人機(jī)載重量使原來(lái)無(wú)法由無(wú)人機(jī)訪問(wèn)的第1類(lèi)顧客可被訪問(wèn)，減少卡車(chē)訪問(wèn)第1類(lèi)顧客的運(yùn)輸成本。以上兩方面導(dǎo)致目標(biāo)函數(shù)值的減少，從而使相比VRP的節(jié)省比例逐漸增大，從C′=3對(duì)應(yīng)的0.64%增長(zhǎng)到C′=8情形下的11.42% (如圖5所示)。結(jié)果表明，無(wú)人機(jī)的載重量越大，節(jié)省的運(yùn)輸成本越大，將無(wú)人機(jī)引入配送越有利。

圖5 C′=3, 4, 5, 6, 7, 8的相關(guān)折線圖Figure 5 Related line chart of differentC′

表6 不同C ′下的求解結(jié)果Table 6 Solution results under differentC′

3.1.3 無(wú)人機(jī)單位運(yùn)輸成本cD分析

表7給出了無(wú)人機(jī)單位運(yùn)輸成本cD取不同值時(shí)的目標(biāo)函數(shù)值、第1類(lèi)顧客點(diǎn)中由無(wú)人機(jī)訪問(wèn)的數(shù)目、訪問(wèn)路徑以及相比VRP目標(biāo)函數(shù)值的節(jié)省比(%)。圖6給出了目標(biāo)函數(shù)值和節(jié)省比隨cD的變化曲線。

表7 不同c D下的求解結(jié)果Table 7 Solution results under differentcD

圖6 cD=0.06, 0.1, 0.2, 0.3的相關(guān)折線圖Figure 6 Related line chart of different cD

如表7所示，當(dāng)cD=0.06，0.1時(shí)，訪問(wèn)路徑完全相同，此時(shí)有2個(gè)第1類(lèi)顧客點(diǎn)由無(wú)人機(jī)訪問(wèn)，目標(biāo)函數(shù)的不同主要由無(wú)人機(jī)單位運(yùn)輸成本所致。隨著cD逐漸增大，原本由無(wú)人機(jī)訪問(wèn)的第1類(lèi)顧客點(diǎn)變?yōu)橛煽ㄜ?chē)訪問(wèn)，因?yàn)闊o(wú)人機(jī)成本的增大導(dǎo)致采用無(wú)人機(jī)訪問(wèn)方式已經(jīng)無(wú)法節(jié)省成本，并且目標(biāo)函數(shù)值逐漸增大，相比VRP的節(jié)省比例為負(fù)值(如圖6)，表明在較大無(wú)人機(jī)單位運(yùn)輸成本下，在VRP基礎(chǔ)上引入無(wú)人機(jī)反而會(huì)增加總成本。相應(yīng)地，在無(wú)人機(jī)技術(shù)中進(jìn)一步減小無(wú)人機(jī)單位運(yùn)輸成本對(duì)降低物流成本有很大意義。

3.2 算法性能分析

3.2.1 算例產(chǎn)生及參數(shù)設(shè)置

由于尚無(wú)針對(duì)本問(wèn)題的標(biāo)準(zhǔn)算例，本文采用隨機(jī)方式生成顧客位置，算例規(guī)模表示為|N|(|N1|+|N2|)?；趩?wèn)題特性，具體產(chǎn)生方式如下。在二維平面上構(gòu)造兩個(gè)中心相同的正方形，邊長(zhǎng)分別為20 km和10 km，兩正方形的重疊部分為區(qū)域1，未重疊部分為區(qū)域2。在區(qū)域1內(nèi)隨機(jī)生成|N1|+1個(gè)點(diǎn)，第1個(gè)點(diǎn)作為配送中心，其余點(diǎn)作為第1類(lèi)顧客點(diǎn)；在區(qū)域2隨機(jī)生成 |N2|個(gè)點(diǎn)作為第2類(lèi)顧客點(diǎn)。顧客需求同樣采用隨機(jī)生成方式，第1類(lèi)顧客點(diǎn)設(shè)置為[0, 40]的1位小數(shù)，第2類(lèi)點(diǎn)設(shè)置為[0, 15]的1位小數(shù)。參考文獻(xiàn)[12]數(shù)據(jù)，問(wèn)題參數(shù)設(shè)置為C= 1 300 kg，C′ = 5 kg，v= 50 km/h，T= 1，cT= 0.6 元/km，cD= 10%·cT=0.06 元/km，cF= 50 元/輛。

3.2.2 算例測(cè)試及結(jié)果

為測(cè)試本文所設(shè)計(jì)改進(jìn)變鄰域搜索算法的求解質(zhì)量，本節(jié)將改進(jìn)變鄰域搜索算法結(jié)果與精確算法進(jìn)行對(duì)比。令無(wú)人機(jī)載重量C′為5 kg，無(wú)人機(jī)的單位運(yùn)輸成本cD為0.06元。設(shè)置目標(biāo)數(shù)目|N|(|N1|+|N2|)分別為10(7+3)、20(14+6)、30(20+10)、50(35+15)、100(70+30)、200(140+60)等幾種規(guī)模進(jìn)行求解，為表明一般性，同等規(guī)模下，選取5組算例。表5給出不同規(guī)模算例下使用的卡車(chē)數(shù)目以及Cplex的求解結(jié)果，包括下界(LB)、上界(UB)以及上下界間的偏差值(Gap%)。求解中設(shè)置最大求解時(shí)間為7 200 s。同時(shí)表8還給出改進(jìn)變領(lǐng)域搜索算法的求解結(jié)果，包括計(jì)算20次的平均目標(biāo)函數(shù)值(Avg.obj)、平均gap值(Avg.Gap%=(Avg.obj-LB)/LB×100%)、最好解的目標(biāo)函數(shù)值(Best.obj)、最好解的gap值(Best.Gap%=(Best.obj-LB)/LB×100%)以及平均求解時(shí)間(Time)。另外，表8還給出改進(jìn)變鄰域搜索算法的相對(duì)偏差值(Related Gap%=(Avg.obj-Best.obj)/Best.obj×100%)，用來(lái)衡量改進(jìn)變鄰域搜索算法求解的穩(wěn)定性。

從表8中可以看出，當(dāng)|N|=10時(shí)，Cplex在3 s內(nèi)即可求得最優(yōu)解；當(dāng)|N|=20時(shí)，在210 s內(nèi)可以得到最優(yōu)解。隨著問(wèn)題規(guī)模擴(kuò)大，當(dāng)|N|=30時(shí)，只有一組算例用時(shí)4 870 s求得最優(yōu)解，其余4組在7 200 s內(nèi)只能求得可行解，且Gap值較大(30%左右)。隨著問(wèn)題規(guī)模進(jìn)一步擴(kuò)大，當(dāng)|N|=50乃至更大數(shù)值時(shí)，Cplex在7 200 s內(nèi)無(wú)法獲得可行解。以上結(jié)果表明，精確算法能夠較快地求解到小規(guī)模算例的最優(yōu)解，但求解較大規(guī)模問(wèn)題時(shí)存在很大局限性。

表8 改進(jìn)變鄰域搜索算法性能比較Table 8 Performance comparison of improved variable neighborhood search algorithm

由表8還可知，本文設(shè)計(jì)的改進(jìn)變鄰域搜索算法在本節(jié)設(shè)置的所有算例規(guī)模下的求解時(shí)間均在1 s內(nèi)，在時(shí)間上相比Cplex具有很大優(yōu)勢(shì)，當(dāng)|N|=10, 20時(shí)，除第10組算例外，改進(jìn)變鄰域搜索算法求得的最好解的目標(biāo)函數(shù)值(Best.obj)均與精確算法的求解結(jié)果相同。當(dāng)|N|=30時(shí)，改進(jìn)變鄰域搜索算法在極短時(shí)間內(nèi)求得解的Gap值在4%以?xún)?nèi)，說(shuō)明改進(jìn)變鄰域搜索算法求解效果很好，在不到1 s的時(shí)間內(nèi)求解結(jié)果優(yōu)于Cplex在7 200 s內(nèi)求解的結(jié)果。當(dāng)|N|=50, 100,200時(shí)，Cplex在7 200 s內(nèi)已無(wú)法求得可行解，而改進(jìn)變鄰域搜索算法在1 s內(nèi)求得可行解。另一方面，改進(jìn)變鄰域搜索算法在不同算例規(guī)模下的最好解與平均解的相對(duì)誤差值(related gap)都比較小，在|N|=10, 20, 30等算例規(guī)模下相對(duì)誤差值小于2%，在更大規(guī)模下相對(duì)誤差值也穩(wěn)定在3%內(nèi)，充分說(shuō)明改進(jìn)變鄰域搜索算法求解的穩(wěn)定性。

4 結(jié)論

本文研究了一類(lèi)需求可拆分的無(wú)人機(jī)與卡車(chē)協(xié)同路徑優(yōu)化問(wèn)題?？紤]到需求稀疏地區(qū)交通不便和卡車(chē)較大的平均運(yùn)輸成本，結(jié)合需求客戶(hù)點(diǎn)的分布特征將配送方式分為兩部分：需求密集地區(qū)的客戶(hù)由卡車(chē)和無(wú)人機(jī)兩種方式協(xié)同配送；需求稀疏地區(qū)的客戶(hù)只能由無(wú)人機(jī)進(jìn)行配送。另外，由于無(wú)人機(jī)載重小，引入需求可拆分特性，允許顧客多次訪問(wèn)。結(jié)合上述問(wèn)題特性，考慮卡車(chē)載重量、無(wú)人機(jī)載重量和續(xù)航時(shí)間、需求拆分比例和路徑可行性等約束，以最小化運(yùn)輸成本和使用卡車(chē)的人力成本建立混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種改進(jìn)變鄰域搜索算法進(jìn)行求解。小規(guī)模算例下分析問(wèn)題特性得出：提高無(wú)人機(jī)載重量可有效減少需要拆分包裹的顧客數(shù)以及單顧客點(diǎn)的拆分次數(shù)，從而很大程度減少運(yùn)輸成本；降低無(wú)人機(jī)單位運(yùn)輸成本可以進(jìn)一步增大卡車(chē)與無(wú)人機(jī)的成本差異，提高無(wú)人機(jī)服務(wù)率，進(jìn)而降低物流成本。在多個(gè)不同算例規(guī)模的數(shù)值實(shí)驗(yàn)中，測(cè)試了改進(jìn)變鄰域搜索算法的性能。結(jié)果表明，在極短的時(shí)間內(nèi)改進(jìn)變鄰域搜索算法能夠求解更大規(guī)模的問(wèn)題，并且求解質(zhì)量較好，算法穩(wěn)定性很高。后續(xù)研究可考慮動(dòng)態(tài)需求下的路徑優(yōu)化問(wèn)題。