李妍峰，李 佳，向 婷

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

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

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

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

1 問題描述及模型建立

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

圖1 問題示例Figure 1 Example of problem

1.2 符號說明

1.3 模型建立

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

2 算法設(shè)計

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

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

2.1 預(yù)處理

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

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

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

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

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

Step 2 初始化：k=1。

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

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

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

2.3 鄰域算子及算法框架

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

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

2.3.1 鄰域算子

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

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

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

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

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

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

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

2) 卡車兩點(diǎn)交換(如圖3(b))：分別在兩條搭載不同卡車的無人機(jī)路徑中選擇一點(diǎn)，交換位置，相關(guān)聯(lián)的無人機(jī)訪問的顧客點(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)生過程中，由無人機(jī)訪問的顧客點(diǎn)安排在卡車訪問路徑中相鄰的兩點(diǎn)間插入，且在2.3節(jié)中設(shè)計的鄰域算子中也保持這一特點(diǎn)。為了進(jìn)一步優(yōu)化路徑，設(shè)計一個起止點(diǎn)延伸的算子，若無人機(jī)航行起點(diǎn)與終點(diǎn)不相鄰時能使降低成本，則執(zhí)行該操作。另外，在鄰域搜索的過程中，因?yàn)榈?類顧客點(diǎn)只能采用無人機(jī)進(jìn)行訪問，所以優(yōu)先滿足第2類顧客點(diǎn)使用無人機(jī)訪問，第1類顧客點(diǎn)則全部由卡車訪問。事實(shí)上，針對第1類顧客點(diǎn)，采用無人機(jī)訪問方式很大程度能減少成本，因此設(shè)計卡車點(diǎn)改為無人機(jī)點(diǎn)這一算子。兩種算子操作如下。

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

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

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

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

以下3.1節(jié)通過小規(guī)模算例對問題特性進(jìn)行分析(采用ILOG Cplex12.9對模型進(jìn)行求解)，3.2節(jié)對構(gòu)造的不同規(guī)模算例進(jìn)行數(shù)值實(shí)驗(yàn)，通過與Cplex的求解結(jié)果對比，對改進(jìn)的變鄰域算法的效率進(jìn)行驗(yàn)證。算法采用C#語言進(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個第1類顧客點(diǎn)和3個第2類顧客點(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 元/輛。通過對卡車載重C、無人機(jī)載重C′和無人機(jī)運(yùn)輸成本cD的靈敏度分析對問題特性進(jìn)行分析。顧客點(diǎn)的坐標(biāo)及需求量如表4所示。

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

3.1.1 卡車載重C分析

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

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

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

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

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

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

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

3.2 算法性能分析

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

由于尚無針對本問題的標(biāo)準(zhǔn)算例，本文采用隨機(jī)方式生成顧客位置，算例規(guī)模表示為|N|(|N1|+|N2|)?；趩栴}特性，具體產(chǎn)生方式如下。在二維平面上構(gòu)造兩個中心相同的正方形，邊長分別為20 km和10 km，兩正方形的重疊部分為區(qū)域1，未重疊部分為區(qū)域2。在區(qū)域1內(nèi)隨機(jī)生成|N1|+1個點(diǎn)，第1個點(diǎn)作為配送中心，其余點(diǎn)作為第1類顧客點(diǎn)；在區(qū)域2隨機(jī)生成 |N2|個點(diǎn)作為第2類顧客點(diǎn)。顧客需求同樣采用隨機(jī)生成方式，第1類顧客點(diǎn)設(shè)置為[0, 40]的1位小數(shù)，第2類點(diǎn)設(shè)置為[0, 15]的1位小數(shù)。參考文獻(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 元/輛。

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

為測試本文所設(shè)計改進(jìn)變鄰域搜索算法的求解質(zhì)量，本節(jié)將改進(jìn)變鄰域搜索算法結(jié)果與精確算法進(jìn)行對比。令無人機(jī)載重量C′為5 kg，無人機(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ī)模算例下使用的卡車數(shù)目以及Cplex的求解結(jié)果，包括下界(LB)、上界(UB)以及上下界間的偏差值(Gap%)。求解中設(shè)置最大求解時間為7 200 s。同時表8還給出改進(jìn)變領(lǐng)域搜索算法的求解結(jié)果，包括計算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%)以及平均求解時間(Time)。另外，表8還給出改進(jìn)變鄰域搜索算法的相對偏差值(Related Gap%=(Avg.obj-Best.obj)/Best.obj×100%)，用來衡量改進(jìn)變鄰域搜索算法求解的穩(wěn)定性。

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

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

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

4 結(jié)論

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