基于模擬退火算法的無人機聯(lián)合配送路徑優(yōu)化模型

基于模擬退火算法的無人機聯(lián)合配送路徑優(yōu)化模型

0基于雙向異性的聯(lián)合配送模型近年來，電子商務(wù)蓬勃發(fā)展。在一些特殊地區(qū)，如農(nóng)村地區(qū)和山地城市地區(qū)，由于地形復(fù)雜，交通條件差，物流往往受到山川的影響。民用無人機的興起，為此類問題提供了新的解決方案由于無人機和車輛各自配送存在諸多限制，兩者的結(jié)合，需要互相協(xié)作，這有別于有容量限制車輛路徑問題CVRP(CapacitatedVehicleRoutingProblem)和多車型車輛路徑問題MTVRP(MultitypesVehicleRoutineProblem)，屬于兼具兩者特點的聯(lián)合配送問題。對于此類特殊的路徑問題，研究者在進行模型設(shè)計時，出發(fā)點分為兩類。一類是從TSP出發(fā)，例如，MURRAY等另一類是從VRP出發(fā)，例如，WANG等以往研究通常以時間或成本最小為目標，而無人機飛行速度快，車輛配送中加入無人機，相當于增加了更快速的配送工具，總配送時間應(yīng)低于傳統(tǒng)配送本文基于農(nóng)村地區(qū)的聯(lián)合配送，考慮了無人機載重量和飛行距離限制，提出車輛不用在固定點等待無人機，無人機單次可以服務(wù)多個顧客節(jié)點，并構(gòu)建了一種雙層規(guī)劃模型，通過修改部分參數(shù)，模型能同時適用于多種場景；基于掃描法的思想，設(shè)計了一種帶末端優(yōu)化的模擬退火算法求解模型，并對考慮的無人機限制因素進行靈敏度分析，以提高滿載率和續(xù)航利用率，充分利用無人機的配送能力。1數(shù)學模型1.1單無人機單次配送模式對于特殊地形區(qū)域，例如，農(nóng)村地區(qū)、山地城市等，因道路彎曲、坡度大、高低起伏等原因，傳統(tǒng)車輛配送十分不便，在部分農(nóng)田和池塘環(huán)繞無路駛?cè)氲牡貐^(qū)，車輛根本無法進行配送，而無人機配送能無視地面環(huán)境，極大的縮短配送距離，且在山水相阻車輛不能進入的農(nóng)村地區(qū)，為實現(xiàn)“最后一公里”配送，無人機有著極大的優(yōu)勢。聯(lián)合配送一般指無人機需從車輛上進行取貨，送貨結(jié)束后需返回車輛，車輛可攜帶無人機進行配送，也可在無人機取貨后同步進行其他顧客點的配送，兩者依據(jù)顧客點的具體特征，協(xié)作完成所有顧客點的配送；相對的獨立配送，即非聯(lián)合配送，車輛和無人機無協(xié)作，獨立完成各自的配送任務(wù)。本文設(shè)計的兩種單無人機、單車輛配送的簡易模式如圖1所示。圖1(a)中無人機和車輛可分別運載貨物離開配送中心，也可由車輛攜帶無人機一起回到配送中心；車輛在無人機進行配送時，不用原地停留等待，也可同步進行顧客點的配送，無人機單次配送可以同時服務(wù)多個顧客點。圖1(b)中無人機和車輛分別獨立進行配送，中途無交互協(xié)作，無人機在一定的限制范圍內(nèi)，可以服務(wù)多個客戶點，但每次配送結(jié)束必須返回配送中心，車輛負責其余節(jié)點的配送。圖1中標記了超過無人機最大飛行距離的超遠點和超過無人機最大載重量的超重點，超遠顧客點因無人機無法長距離往返，僅可由車輛完成配送；超重顧客點因無人機無法負載貨物，也僅可由車輛完成配送，但聯(lián)合配送中無人機可在超重點進行發(fā)射或者接收?；谏鲜鰡栴}，本文做如下假設(shè)：(1)配送中心和顧客點的位置和需求量已知，且配送中心需求量為0;(2)所有顧客點都必須得到服務(wù)，不考慮顧客點的時間窗限制；(3)無人機的最大載重量和最大續(xù)航里程已知；(4)在滿足限制條件下，無人機一次可服務(wù)多個顧客點；(5)不考慮車輛的載重限制和續(xù)航限制；(6)車輛必須先于無人機到達停靠點，無人機不能在?？奎c懸停飛行；(7)無人機每次配送結(jié)束后，需返回車輛取貨，并進行電池更換；(8)不考慮顧客點的服務(wù)時間和無人機的取貨、電池更換時間；(9)車輛上攜帶足夠的無人機電源。1.2cccppk—參數(shù)說明模型建立過程中使用的參數(shù)如下：SSSLLCCCCPPK——配送總次數(shù)，K={1,2,?,k}；nndD——無人機的最大飛行距離；ZZZ——配送完所有節(jié)點的路徑距離總和；1.3單次路徑規(guī)劃車輛路徑問題研究，較多結(jié)合節(jié)約法和聚類分析，但這兩種方法不能很好地拓展到多車型間需要動態(tài)合作，且有載重限制的問題。為使無人機單次可服務(wù)多個節(jié)點，本文基于掃描法的思想，以總配送距離最小為目標，按以下步驟求解。Step1標記特殊點。對于所有顧客需求點，車輛均可以進行配送。由于無人機單次飛行有最大載重限制和最大飛行距離限制，因此，將所有顧客需求點中超過無人機最大載重限制的節(jié)點標記為L式(1)和式(2)保證標記點必定被車輛配送；式(3)和式(4)表示標記為LStep2單次路徑規(guī)劃。因無人機的電量限制，在無人機最遠可達的飛行距離半徑內(nèi)，且滿足無人機最大載重限制的條件下，盡可能多的給無人機分配顧客需求點，以提高無人機的滿載率和續(xù)航利用率。對于給定飛行半徑內(nèi)，無人機單次配送最多可服務(wù)的顧客點是有限的，每次分配完成后記錄下單次到達的終點。無人機配送一次后需要補充電量，為安全考慮，不能在停靠點做懸停等待，所以，車輛必須在無人機到達之前到達。以無人機單次路徑規(guī)劃記錄的終點為車輛此次配送的終點，在滿足提前到達的前提下，盡可能多的給車輛分配顧客需求點。因配送時間限制，車輛單次配送最多可服務(wù)的顧客點是有限的。式(9)是最大化單次無人機和車輛服務(wù)的顧客節(jié)點數(shù)；式(10)保證單次無人機攜帶的貨物重量不超過無人機最大載重量；式(11)保證單次無人機配送總距離不超過無人機最大飛行距離；式(12)和式(13)表示在所有未被服務(wù)的顧客節(jié)點中，無人機進出該節(jié)點不超過1次；式(14)保證車輛必定在無人機降落前到達；式(15)和式(16)表示在所有未被服務(wù)的顧客節(jié)點中，車輛進出該節(jié)點不超過1次；式(17)保證每次分配完單次服務(wù)的顧客節(jié)點后，將其從前1次未服務(wù)顧客節(jié)點集合中除去。Step3整體路徑優(yōu)化。以單次配送路徑記錄的終點為下次配送路徑的起點，重復(fù)Step2，直到所有顧客需求點全部配送完畢。將車輛和無人機的配送距離相加，以總配送距離最短為目標函數(shù)，優(yōu)化每次配送的路徑選擇。目標函數(shù)式(18)為最小化無人機和車輛的總配送距離；式(19)和式(20)表示所有非?？康念櫩凸?jié)點僅被無人機或車輛配送一次；式(21)和式(22)表示無人機收發(fā)節(jié)點車輛僅進出一次；式(23)表示無人機發(fā)射節(jié)點無人機僅飛出一次；式(24)表示無人機回收節(jié)點無人機僅降落一次；式(25)和式(26)保證所有節(jié)點全部分配完畢，無人機的發(fā)射和回收點可為同一節(jié)點；式(27)保證無人機對于非?？奎c出入流量守恒；式(28)確保車輛對于所有節(jié)點出入流量守恒；式(29)和式(30)給出了參數(shù)的取值范圍。式(6)、式(7)、式(21)～式(24)共同給出了當配送中心作為無人機收發(fā)點或非?？奎c時的進出規(guī)則，無人機可從配送中心發(fā)射回收，也可由車輛攜帶進出，中途無人機和車輛均不會再次訪問配送中心。2算法在較短區(qū)域的應(yīng)用由于設(shè)計的聯(lián)合配送模型屬于NP-hard問題，問題會隨節(jié)點的增多而成指數(shù)級增長，當節(jié)點超過10個時，使用精確算法需要花費大量時間，還無法求解出結(jié)果，而啟發(fā)式算法能在較短時間內(nèi)求解出很好的結(jié)果。所以本文針對聯(lián)合配送案例特征，采用啟發(fā)式算法求解問題。2.1求解算法模擬退火算法通過設(shè)置不同的控制參數(shù)，能有效求解本文所提問題。(1)降溫速率的設(shè)置通過設(shè)置不同的控制參數(shù)，可以控制模型的降溫速率，更好地逼近全局最優(yōu)解。需要設(shè)置的主要控制參數(shù)：降溫速率q=0.9；鏈長L=2000；初始溫度T(2)不同雙創(chuàng)配送路徑組合采用整數(shù)排列的編碼方法，隨機生成由1～n個整數(shù)構(gòu)成的初始解，每個整數(shù)對應(yīng)1～n個顧客需求點，配送中心為n+1。初始解可劃分為幾個不同的部分，每個部分，即不同配送趟次的無人機和車輛路徑集合。各數(shù)字的排列順序決定對應(yīng)節(jié)點的配送順序，從配送中心開始，按排列順序依次將各節(jié)點加入到無人機和車輛的配送路徑，每加入1個節(jié)點，計算是否滿足約束條件，未超出條件，則繼續(xù)加入下1個節(jié)點，直到超出約束范圍，進入下一趟次的顧客點分配。重復(fù)分配k次，得到所有趟次的配送路徑，每趟次配送路徑的順序結(jié)合，即總的配送路徑。結(jié)合式(9)～式(17)，單次路徑規(guī)劃的偽代碼如算法1所示。(3)單體交叉與2-opt通過對當前解進行變換，生成新的路徑組合，更新當前解。本文主要采用交換規(guī)則有單點交叉和2-opt變換。單點交叉即隨機產(chǎn)生[1,n]區(qū)間內(nèi)的兩個整數(shù)，將當前解中兩個整數(shù)對應(yīng)位置的節(jié)點進行對換。2-opt即隨機產(chǎn)生[1,n]區(qū)間內(nèi)的兩個整數(shù)，將當前解中兩個整數(shù)對應(yīng)位置中間部分的節(jié)點進行轉(zhuǎn)置。以1～10為例，假設(shè)隨機產(chǎn)生的兩個整數(shù)為4和7，單點交叉和2-opt的交換示意如圖2所示。(4)ropolus準則對于目標函數(shù)Z，假設(shè)當前解aMetropolis準則為如果Z′<0，則以概率1接受新的路徑；否則，以概率exp(-Z′T)接受新的路徑。(5)單次路徑距離以總配送路徑距離最小為目標函數(shù)，考慮到車輛不用在原地等待無人機返回，可以對部分聯(lián)合配送路徑進行末端優(yōu)化。為減少不必要的回路，結(jié)合式(33)，當無人機負責配送1個及以上節(jié)點，而車輛僅配送1個節(jié)點(此節(jié)點為無人機回收節(jié)點，可包括配送中心)，其2種路徑方案如圖3所示。為使路徑距離最小，無人機單次路徑距離計算如式(34)所示，車輛單次路徑距離計算如式(35)所示。當(Z偽代碼如算法2所示。(6)降身距利用降溫速率q按照進行降溫，若當前溫度T小于結(jié)束溫度，則停止迭代，并輸出當前最優(yōu)解的結(jié)果；否則，繼續(xù)迭代。2.2基于模擬退火算法的優(yōu)化設(shè)計場景求解為驗證所提出路徑優(yōu)化模型的有效性，設(shè)計了車輛單獨配送、無人機-車輛獨立配送和無人機-車輛聯(lián)合配送3種場景，并結(jié)合模擬退火算法(SA)和末端優(yōu)化對設(shè)計的場景進行求解。(1)顧客點配送中心即傳統(tǒng)配送問題(SA+TSP)，車輛無載重和續(xù)航能力限制，考慮道路阻抗的影響，車輛從配送中心出發(fā)，完成所有顧客需求點的配送后，再返回配送中心。為使模型能求解此問題，設(shè)置無人機最大載重量M=0，或無人機最大飛行距離D=0，限制無人機的配送，本文所設(shè)計的聯(lián)合配送模型即轉(zhuǎn)變?yōu)檐囕v單獨配送模型。(2)單次配送模式即帶容量限制的多車型路徑問題(SA+CVRP+MTVRP)，獨立配送為非聯(lián)合配送，屬于PDSTSP的變種問題，車輛和無人機負責各自的顧客點，沒有協(xié)作，無人機單次配送需返回配送中心進行取貨和更換電源。為使模型能求解此問題，將無人機的發(fā)射和接收點設(shè)置為P(3)場景中有三個無人機模型的聯(lián)合配送即本文所提的路徑優(yōu)化問題(SA+VRP-D)，無人機和車輛需要密切合作，共同完成所有顧客點的配送任務(wù)。3系統(tǒng)的實現(xiàn)和實現(xiàn)為求解本文設(shè)計的路徑優(yōu)化模型，使用MATLABR2019a編程，在一臺處理器為Intel(R)Core(TM)i7-8550U、8G內(nèi)存，操作系統(tǒng)為Win1064位的計算機上運行。模型各參數(shù)設(shè)置如表1所示。3.1仿真結(jié)果分析考慮到農(nóng)村地區(qū)的位置特點，依據(jù)Solomon實例數(shù)據(jù)集中RC208的數(shù)據(jù)，在50km×50km的空間范圍內(nèi)，隨機生成包含35個節(jié)點的仿真案例，修改部分顧客需求點的貨物需求量，加入2個超重點和2個超遠點，各節(jié)點的具體數(shù)據(jù)如表2所示。以路徑距離最小為目標，輸入數(shù)據(jù)參數(shù)，求解上述3個場景，統(tǒng)計運算結(jié)果。不同場景下的配送結(jié)果如圖4所示。車輛單獨配送的結(jié)果如圖4(a)所示，車輛從配送中心出發(fā)，順次完成所有顧客需求點的配送后返回配送中心；無人機-車輛獨立配送的結(jié)果如圖4(b)所示，無人機單次能服務(wù)多個顧客需求，但受無人機最大飛行距離限制，而農(nóng)村節(jié)點較為分散，且離配送中心相距很遠，無人機僅服務(wù)了4個顧客需求點，其余節(jié)點由車輛負責配送；無人機-車輛聯(lián)合配送的配送結(jié)果如圖4(c)所示，車輛和無人機分別從配送中心出發(fā)，無人機同樣服務(wù)多個顧客需求點，超重點和超遠點僅能由車輛進行配送，但超重點可以作為車輛配送的中間節(jié)點，也能作為無人機飛行的收、發(fā)節(jié)點，無人機和車輛相互協(xié)作，服務(wù)所有顧客需求點后共同回到配送中心。對每個場景獨立運行程序30次，每次的運行結(jié)果如圖5所示。不同場景下的統(tǒng)計結(jié)果，以及場景3相對其他場景的變動比例如表3所示。表3中，場景3的最小值在所有場景中結(jié)果最小，相對場景1下降2.81%，相對場景2下降1.91%，場景2的最小值結(jié)果也小于場景1。說明無人機和車輛的獨立配送和聯(lián)合配送均優(yōu)于車輛單獨配送，無人機的加入，可以減少總的配送距離，證明了本文設(shè)計模型的可行性，3種場景均可以視為設(shè)計模型在不同參數(shù)下的特例。此外，場景2、場景3的最大值均大于場景1，場景1的仿真結(jié)果差距最小。由圖5中可知，場景1中30次的運行結(jié)果波動幅度最平緩，另外2種場景的波動幅度較大，特別是場景2，由于無人機的發(fā)射和接收點均限制為配送中心，且受最大載重量和最大飛行距離限制，無人機能服務(wù)的顧客點十分有限，部分單一節(jié)點分配給無人機進行配送后，導致總配送距離增大。在3種場景中，場景3的結(jié)果均值依然最小，無人機和車輛的聯(lián)合配送有著更大優(yōu)勢，合理分配無人機和車輛的配送路徑，兩者相互協(xié)調(diào)，可以更高效地完成所有節(jié)點的配送任務(wù)。3.2無人機配送能力組合為驗證在不同載重和飛行距離限制下，無人機是否能很好地完成農(nóng)村地區(qū)的物流配送任務(wù)，使用表2的顧客點數(shù)據(jù)，對無人機最大載重和最大飛行距離進行靈敏度分析，其余參數(shù)保持不變，每組結(jié)果獨立運行20次后取最小值。保持無人機最大載重不變，不同飛行距離限制下，3種場景的配送結(jié)果如圖6所示。圖6中，場景1因為僅使用車輛進行配送，而車輛無配送距離限制，無人機最大飛行距離的變化，不會影響其配送結(jié)果。以場景1為參考，隨著無人機最大飛行距離的提高，無人機的運載能力得到充分發(fā)揮，場景2的配送距離逐漸低于場景1，在飛行距離取20km時達到最低，明顯優(yōu)于其他場景，但繼續(xù)增大無人機的最大飛行距離，場景2的配送距離反而增大，因為，此時無人機的飛行直徑已經(jīng)接近空間范圍的1/2，無人機存在遠距離往返，在每次完成配送后，需要折返回配送中心，導致配送距離增加。而場景3因為有車輛的支持，在較低飛行距離時，已經(jīng)能很好地發(fā)揮無人機的運載能力，其配送結(jié)果優(yōu)于另外2個場景，但隨著無人機飛行距離的增加，場景3的配送距離同樣在增大，這是受數(shù)據(jù)節(jié)點位置分散的影響，無人機在完成附近顧客點的配送時，還會飛往較遠顧客點，車輛也因此增大了行駛距離。保持無人機的最大飛行距離不變，不同載重量限制下，3種場景的配送結(jié)果如圖7所示。仍然以場景1為參照，由圖7可知，場景2中，無人機在較小載重量時，已優(yōu)于場景1，但因無人機最大飛行距離固定，無人機只能在配送中心一定范圍內(nèi)飛行，其最大載重量兩端(0kg和5kg)均無法很好地利用無人機的配送能力，結(jié)果陷入局部最優(yōu)。而場景3中，車輛可以攜帶無人機，無人機因此能夠前往更遠的節(jié)點，當周圍顧客需求點分布較為密集，無人機載重量越大，越能發(fā)揮其配送優(yōu)勢，減少總的配送距離。值得注意的是，當無人機最大載重量超過4kg時，節(jié)點中已經(jīng)不存在超重點，在可達的情況下，無人機能配送所有節(jié)點，但無法同時配送超重點和其他節(jié)點，無人機的配送能力受到限制。為進一步了解無人機的特性，取無人機最大載重1～3kg、最大飛行距離9～21km，構(gòu)成25組配送能力組合，運算結(jié)果如表4所示。表4中，隨著無人機配送能力的上升，無人機配送的節(jié)點數(shù)不斷增多，有利于發(fā)揮無人機無視路況、速度快的優(yōu)勢。而僅提升一項能力，雖然可以增加無人機配送節(jié)點，但因需要同時提高滿載率和續(xù)航利用率，總配送距離會有所上升。從配送距離在310km以下的幾組(編號為：7、12、18、24)可以發(fā)現(xiàn)，無人機的最大載重量和飛行距離以一定比例同步提升，能更好地發(fā)揮無人機的配送能力，在配送距離上更優(yōu)。3.3配送距離比較以湖南省瀏陽市為例，隨機選取下屬5個鄉(xiāng)鎮(zhèn)范圍內(nèi)的30個節(jié)點，使用百度地圖標記各點，無人機飛行距離取兩點間歐式距離，車輛行駛距離取推薦的最短車行距離。道路阻抗系數(shù)取1，假設(shè)道路情況良好，車輛可以送達所有包裹，無人機最大載重量為2kg，最大飛行距離10km，平均飛行速