前幾期的推送已經(jīng)講解了整數(shù)規(guī)劃的基本知識(shí)、數(shù)學(xué)模型和相關(guān)算法，相信大家對(duì)整數(shù)規(guī)劃已經(jīng)有了充分的了解，這期小編將帶大家一起來(lái)讀一篇關(guān)于無(wú)人機(jī)車輛路徑問(wèn)題的文章。

1.文章信息

題目：Vehicle routing problem with drones

作者：Zheng Wang，Jiuh-Biing Sheu

來(lái)源：Transportation Research Part B: Methodological

出版信息：Volume 122，April 2019，Pages 350-364

網(wǎng)址：https://doi.org/10.1016/j.trb.2019.03.005

2.文章導(dǎo)讀

城市物流服務(wù)提供商一直在尋找更快、更經(jīng)濟(jì)的最后一公里配送方式，無(wú)人機(jī)則為城市物流從業(yè)者帶來(lái)了一個(gè)新的機(jī)會(huì)，與普通的送貨卡車相比，無(wú)人機(jī)具有避免道路擁堵、送貨更快、運(yùn)輸成本更低等優(yōu)勢(shì)。但由于大多數(shù)無(wú)人機(jī)都是電池供電的，因此裝載能力和飛行距離與卡車相比是有限的，并且無(wú)人機(jī)無(wú)法自行承擔(dān)所有可能的運(yùn)送任務(wù)。此外，卡車還可以攜帶更重的包裹，行駛更長(zhǎng)的距離，并攜帶無(wú)人機(jī)更接近客戶。因此使用卡車和無(wú)人機(jī)聯(lián)合運(yùn)輸成為一種有效的方式，可以最大限度地利用它們的優(yōu)勢(shì)。現(xiàn)如今，合理規(guī)劃無(wú)人機(jī)和卡車路徑在應(yīng)急管理工作與物流配送方面至關(guān)重要，尤其在新冠疫情形式下，無(wú)人機(jī)和卡車的協(xié)同配送在醫(yī)療物資運(yùn)輸方面的應(yīng)用愈發(fā)廣泛，這使得無(wú)人機(jī)車輛路徑問(wèn)題（Vehicle routing problem with drone，VRPD）逐漸成為一個(gè)備受關(guān)注的研究熱點(diǎn)。

3.摘要

VRPD問(wèn)題不僅使用卡車，而且使用無(wú)人機(jī)向客戶遞送包裹。其顯著特點(diǎn)是只要滿足飛行距離和裝載能力的限制，無(wú)人機(jī)就可以從其站點(diǎn)起飛為客戶服務(wù)，并降落在服務(wù)中心與另一輛卡車一起配送。不同于經(jīng)典的車輛路徑問(wèn)題，本文以集成的方式安排卡車和無(wú)人機(jī)，使該問(wèn)題更具挑戰(zhàn)性。為應(yīng)對(duì)該問(wèn)題，本文提出了一個(gè)混合整數(shù)規(guī)劃模型并開發(fā)分支定價(jià)算法進(jìn)行求解，并對(duì)隨機(jī)生成的實(shí)例進(jìn)行大量實(shí)驗(yàn)，結(jié)果表明該算法具有良好的計(jì)算性能。此外，本文還對(duì)可能影響解決方案總成本的關(guān)鍵因素進(jìn)行了敏感性分析。

4.主要內(nèi)容

VRPD中有兩種類型的車輛：無(wú)人機(jī)和卡車。無(wú)人機(jī)可能有多次飛行和著陸，每一次飛行和著陸都可能與不同的卡車相關(guān)聯(lián)；一輛卡車可以在不同的時(shí)間和地點(diǎn)發(fā)射和收集多架無(wú)人機(jī)。本文旨在解決如何將卡車和無(wú)人機(jī)一起調(diào)度以實(shí)現(xiàn)成本效益高的車輛路徑方案。

本文的無(wú)人機(jī)是與卡車聯(lián)合配送，首先由卡車將無(wú)人機(jī)攜帶到指定釋放點(diǎn)，無(wú)人機(jī)和卡車分別配送相應(yīng)的客戶包裹。在配送的路徑上會(huì)設(shè)置一些節(jié)點(diǎn)，該節(jié)點(diǎn)無(wú)人機(jī)與卡車都會(huì)經(jīng)過(guò)，卡車在該節(jié)點(diǎn)將包裹放下，由無(wú)人機(jī)對(duì)該包裹進(jìn)行配送，無(wú)人機(jī)在配送完所有包裹后自行返回倉(cāng)庫(kù)。本文VRPD的解決過(guò)程中需要確定卡車收集或發(fā)射無(wú)人機(jī)的地點(diǎn)，車輛行駛的路線以及無(wú)人機(jī)的路徑等問(wèn)題。如何在空間和容量限制下，以集成方式對(duì)卡車和無(wú)人機(jī)進(jìn)行布線，也是本文需要解決的最具挑戰(zhàn)性的問(wèn)題。

因?yàn)闊o(wú)人機(jī)是與卡車聯(lián)合配送，若無(wú)人機(jī)沒(méi)有匹配的卡車弧和卡車節(jié)點(diǎn)的路徑，則無(wú)人機(jī)路徑將不可行。為了解決這個(gè)問(wèn)題，文章提出兩個(gè)引理：

1、最終解決方案的無(wú)人機(jī)路徑中的任何卡車弧必須通過(guò)解決方案的卡車路徑行駛，否則沒(méi)有卡車通過(guò)弧運(yùn)輸無(wú)人機(jī)。

2、最終解決方案的無(wú)人機(jī)路徑中的任何停靠點(diǎn)和卡車節(jié)點(diǎn)必須由卡車經(jīng)過(guò)，否則沒(méi)有卡車向節(jié)點(diǎn)處的無(wú)人機(jī)提供客戶包裹。

由于無(wú)人機(jī)路徑取決于卡車的路徑僅有兩種情況：（1）無(wú)人機(jī)需要由卡車通過(guò)弧形運(yùn)輸?shù)侥骋还?jié)點(diǎn)；（2）無(wú)人機(jī)在某一節(jié)點(diǎn)運(yùn)送的客戶包裹需要由卡車運(yùn)輸?shù)皆摴?jié)點(diǎn)。引理1確保了情形（1）的可行性，引理2通過(guò)任何對(duì)接節(jié)點(diǎn)都有卡車經(jīng)過(guò)確保情形（2）的可行性，因?yàn)榍樾危?/span>2）只發(fā)生在無(wú)人機(jī)可以著陸的對(duì)接節(jié)點(diǎn)上。

如果任一服務(wù)站節(jié)點(diǎn)滿足引理1和引理2，則可以確保無(wú)人機(jī)路徑的可行性，從而構(gòu)造了基于路徑的VRPD模型（path-M）。

基于路徑的模型是一個(gè)混合整數(shù)規(guī)劃模型，其變量數(shù)目較多，而分支定價(jià)是組合優(yōu)化中的一種常見方法,其適用于求解大規(guī)?；旌险麛?shù)線性規(guī)劃問(wèn)題。故為了解決基于路徑的模型，本文開發(fā)了一個(gè)分支定價(jià)算法。該算法除了可以應(yīng)用于本文的車輛路徑問(wèn)題，其還可以應(yīng)用于廣義指派問(wèn)題和圖形多色問(wèn)題。該算法主要流程包括兩步，即主問(wèn)題的線性松弛和解決定價(jià)子問(wèn)題，其在解決定價(jià)子問(wèn)題中提出的改進(jìn)的pulse算法極大的提高了搜索速度。

在主問(wèn)題的線性松弛中，將客戶集首先分為兩個(gè)子集，一個(gè)子集包含無(wú)人機(jī)從倉(cāng)庫(kù)可以到達(dá)的客戶，另一個(gè)子集包含其他客戶。無(wú)人機(jī)和卡車分別用于為兩個(gè)子集的客戶提供服務(wù)，每一個(gè)子集只與一種車輛類型的路由問(wèn)題相關(guān)聯(lián)。利用經(jīng)典的節(jié)約啟發(fā)式算法，得到了每一個(gè)子集的解，并將兩個(gè)子集的解組合成一個(gè)初始解。

在定價(jià)子問(wèn)題中，設(shè)計(jì)了一個(gè)能夠區(qū)分不同類型路徑和節(jié)點(diǎn)的特殊網(wǎng)絡(luò)，并提出了一種改進(jìn)的pulse算法，通過(guò)定制的修剪和擴(kuò)展策略解決定價(jià)子問(wèn)題，這一改進(jìn)大大提高了搜索進(jìn)度。并且為了緩解列生成中緩慢收斂帶來(lái)的拖尾效應(yīng)，本文應(yīng)用了交替拉格朗日下界和列生成穩(wěn)定性。然后，利用一種基于約束的分支規(guī)則來(lái)處理受限主問(wèn)題的非整數(shù)解。該規(guī)則首先將基于路徑的模型的解轉(zhuǎn)化為基于弧的模型的等價(jià)解，然后識(shí)別部分弧流，最后在其中一個(gè)弧流上分支。利用這種分支方案，在分支后保留了定價(jià)子問(wèn)題的結(jié)構(gòu)。

最后對(duì)隨機(jī)生成的實(shí)例進(jìn)行大量實(shí)驗(yàn)，在不同參數(shù)設(shè)置下進(jìn)行敏感性分析，通過(guò)分支定價(jià)算法與Gurobi對(duì)比,驗(yàn)證了分支定價(jià)算法的良好計(jì)算性能。并將VRP解決方案與VRPD解決方案對(duì)比，證明了無(wú)人機(jī)配送的有效性。在敏感性分析中，觀測(cè)到將無(wú)人機(jī)飛行時(shí)間延長(zhǎng)一倍的先進(jìn)電池技術(shù)將使后勤成本降低近10%，這個(gè)結(jié)論將有助于后續(xù)研究。

圖3顯示了某一實(shí)例的路由方案。從圖中我們可以看到，卡車必須沿著地面上可能擁堵的道路行駛，但無(wú)人機(jī)可以飛越道路，從而大大縮短了一對(duì)節(jié)點(diǎn)的行駛時(shí)間。在該解決方案中，卡車依次通過(guò)節(jié)點(diǎn)6、5、10、8、1和2，以便能夠在節(jié)點(diǎn)6發(fā)射無(wú)人機(jī)并在兩個(gè)對(duì)接節(jié)點(diǎn)與無(wú)人機(jī)相遇。作為卡車的助手，無(wú)人機(jī)在其飛行范圍和裝載限制范圍內(nèi)運(yùn)送了四個(gè)客戶，包括最遠(yuǎn)的客戶3和客戶7、9和2。若沒(méi)有卡車的參與，無(wú)人機(jī)就無(wú)法為這些客戶提供服務(wù)。若沒(méi)有無(wú)人機(jī)，卡車必須花費(fèi)更多的成本為四個(gè)客戶服務(wù)，卡車與無(wú)人機(jī)的聯(lián)合配送實(shí)現(xiàn)了良好的協(xié)作。

5.結(jié)論

本文研究了無(wú)人機(jī)車輛路徑問(wèn)題（VRPD），其中卡車和無(wú)人機(jī)都用于配送交貨。本文首先提出了一種基于弧的VRPD整數(shù)規(guī)劃模型，但由于特殊的問(wèn)題結(jié)構(gòu)導(dǎo)致了大量的約束，將其重新表述為基于路徑的模型，并開發(fā)了分支定價(jià)算法。在主問(wèn)題中，利用經(jīng)典的節(jié)約啟發(fā)式算法，得到初始解。在定價(jià)子問(wèn)題中，設(shè)計(jì)了一個(gè)能夠區(qū)分不同類型路徑和節(jié)點(diǎn)的特殊網(wǎng)絡(luò)，并通過(guò)改進(jìn)的pulse算法進(jìn)行修剪和擴(kuò)展。最后，本文利用一種基于約束的分枝規(guī)則來(lái)處理受限主問(wèn)題的非整數(shù)解。本文研究得出的VRPD解決方案不僅有助于節(jié)省平均成本，而且將縮減配送交付時(shí)間。

6.貢獻(xiàn)

本文將VRPD問(wèn)題與現(xiàn)實(shí)實(shí)例相結(jié)合，首次研究了城市物流領(lǐng)域的VRPD問(wèn)題，并為該問(wèn)題開發(fā)了一個(gè)有效的算法—分支定價(jià)算法。其次，本文進(jìn)行的敏感性分析確立了可能影響解決方案總成本的關(guān)鍵因素。本文研究的內(nèi)容有助于解答決策者所面臨的兩類交通工具服務(wù)顧客的順序及車輛行駛的路線等問(wèn)題

7.展望

由于本文是第一批研究卡車和無(wú)人機(jī)混合使用的文章之一，因此有許多潛在的研究領(lǐng)域。引入對(duì)接樞紐有利于車輛的協(xié)調(diào)，但這需要投入大量的資源和管理，所以如何以最低成本定位、調(diào)整和配置服務(wù)站，以及如何預(yù)先在每個(gè)服務(wù)站處重新安置無(wú)人機(jī)，從而實(shí)現(xiàn)有效的卡車與無(wú)人機(jī)路線安排，仍然是一個(gè)重大問(wèn)題，這有望成為日后的研究重點(diǎn)。