考慮同時取送貨的車機協同路徑優(yōu)化問題

摘要：考慮到傳統(tǒng)同時取送貨問題模式單一，無法應對復雜多變情況的現實需要，研究了一種考慮同時取送貨的路徑優(yōu)化問題（vehicleroutingproblemwithdronesforsimultaneouspickupanddelivery，VRPD-SPD）。首先，以車輛與無人機總成本最小為優(yōu)化目標，建立了考慮無人機單架次訪問順序約束的混合整數線性規(guī)劃模型。其次，提出了一種基于遺傳思想的兩階段啟發(fā)式算法（two-stageheuristicalgorithmbasedgenetic，TSHAG），第一階段結合貪婪算法和節(jié)約算法生成初始解，第二階段通過改進的遺傳算法優(yōu)化初始解，設計了多元組編碼方式來提高解碼效率，改進了交叉算子來增加鄰域解的搜索空間，設計了新的變異算子來提高算法全局尋優(yōu)性能。最后，算例實驗結果表明了TSHAG算法能夠有效地解決VRPD-SPD問題。

關鍵詞：車機協同；同時取送貨；兩階段啟發(fā)式算法；遺傳算法

中圖分類號：U116;TP18文獻標志碼：A文章編號：1001-3695（2023）05-008-1335-06doi：10.19734/j.issn.1001-3695.2022.10.0542

在包裹配送［1］、商品退貨［2］、廢舊回收［3］等城市末端物流系統(tǒng)中，取貨/送貨是物流方向相反的兩種基本服務形式，對取貨路徑和送貨路徑進行優(yōu)化是末端物流的研究重點。由于需要同時考慮兩種服務形式的配送需求，同時取送貨問題是一類更加復雜的車輛路徑衍生問題，但可能形成比單一的取貨/送貨路徑規(guī)劃問題成本更優(yōu)、重箱率更高的調度方案，因而引起了國內外學者的廣泛關注。

同時取送貨問題是在滿足相關約束條件的前提下，同時考慮用戶的取送貨需求，通過構造合適的取送貨路線使得配送成本最小的一類組合優(yōu)化問題。該問題最早由Min［4］提出，用于解決圖書配送—回收路徑規(guī)劃問題。文獻［5～9］進一步考慮了時間窗約束，研究了帶時間窗的同時取送貨問題，并通過遺傳算法、模擬退火算法來求解問題。文獻［10～13］將同時取送貨問題抽象成兩級車輛路徑問題，并通過節(jié)約算法、遺傳算法來求解問題。隨著無人機在物流領域的推廣應用，無人機同時取送貨問題成為該領域新的研究熱點［14，15］。文獻［16，17］研究無人機同時取送貨問題，建立了相應的數學模型。文獻［18］研究應急情形下帶時間窗的無人機同時取送貨問題，提出改進遺傳算法進行求解。由于車輛與無人機在實際配送環(huán)境中均存在各種限制，部分學者開始探索車機互補進行配送的模式［19］。其中文獻［20］將無人機抽象成一類特殊車輛，對車機獨立配送模式下的同時取送貨問題進行了研究，建立了相應的數學模型。文獻［21］進一步研究了車機獨立配送模式下帶時間窗的同時取送貨問題，建立了相應的數學模型，并通過遺傳算法進行求解。然而，上述研究未涉及車機協同模式的同時取送貨問題，且未見相應的求解算法。

綜上所述，同時取送貨問題現有研究主要聚焦于單一工具配送或車機獨立配送模式，難以滿足路況限制、無接觸收取等情形下的配送需要。本文研究了考慮同時取送貨的車機協同路徑優(yōu)化問題，建立了以最小化總成本為目標的混合整數線性規(guī)劃模型，提出了一種基于遺傳思想的兩階段啟發(fā)式算法進行求解，通過改進算法編碼方式和交叉、變異算子提升了求解性能。

1問題描述及建模

1.1問題描述

在VRPD-SPD問題中，用戶點是能夠提供全天候服務的自提、自寄點，令車輛搭載無人機為用戶提供取送貨服務，即無人機從車輛裝載貨物后起飛為用戶送貨，或從用戶處取貨后降落回車輛進行卸貨，所有用戶均由無人機進行服務，且無人機每次只能攜帶一個包裹，車輛僅提供貨物中轉及無人機起降、充換電等功能。問題旨在構造合理的車輛行駛路線與無人機飛行路線，使得在滿足各類資源約束條件下，完成全部用戶取送貨需求的總成本最小，如圖1所示。

這里做如下合理假設：a）假定車輛、無人機均為同質的；b）假定車輛與無人機的行駛距離為歐氏距離；c）假定無人機的負載量滿足任一單個用戶的需求；d）假定無人機有最大續(xù)航里程限制；e）假定無人機的行駛速度遠大于車輛的行駛速度；f）假定無人機僅能在特定節(jié)點（錨點）處起降，且起降位置為同一節(jié)點。

1.2數學建模

建模所需符號及其含義如表1所示。

目標函數式（1）表示最小化總成本，總成本等于車輛使用成本、無人機使用成本、車輛與無人機總行駛距離之和；約束式（2）確保車輛出入倉庫流量平衡，任一車輛從倉庫出站就必須返回倉庫；約束式（3）保障車輛訪問錨點唯一性及出入度平衡；約束式（4）確保車輛經過的任一錨點至少有一個無人機架次；約束式（5）確保無人機只從車輛經過的錨點起降；約束式（6）（7）確保每一個顧客必須被無人機訪問，且無人機在顧客點的流量平衡；約束式（8）保障無人機起降點流量平衡；約束式（9）確保任一架次無人機訪問顧客不允許出現先取后送的情況；約束式（10）（11）確保每架次至多含一對取送貨顧客；約束式（12）～（14）是車輛容積約束；約束式（15）是無人機架次續(xù)航約束；約束式（16）（17）表示決策變量的取值約束。

2兩階段啟發(fā)式算法

遺傳算法［22，23］為求解同時取送貨問題的常用方法之一，具有快速的隨機搜索能力和可擴展性。本文基于VPPD-SPD問題的特點，設計了一種基于遺傳思想的兩階段啟發(fā)式算法，第一階段結合貪婪和節(jié)約算法生成初始解，第二階段利用改進遺傳算法改進初始解。下面介紹算法的具體內容。

2.1初始解生成

貪婪算法［24］、節(jié)約算法［25］是同時取送貨問題常用的、效率較高的算法之一。故第一階段通過貪婪、節(jié)約算法分別生成無人機路徑和車輛路徑，得到初始解。首先，通過貪婪算法生成無人機路徑；其次，基于無人機路徑確定的錨點位置，通過節(jié)約算法生成車輛路徑。

2.1.1基于貪婪思想的無人機路徑規(guī)劃算法

基于貪婪思想和無人機訪問順序規(guī)則，確定錨點位置并構造無人機飛行路線，具體步驟如圖2所示。

2.1.2基于節(jié)約思想的車輛路徑規(guī)劃算法

基于無人機路徑已確定的錨點，通過串行節(jié)約里程法構造車輛行駛路線，具體步驟如圖3所示。

2.2改進遺傳算法

第二階段改進了遺傳算法的編碼方式、交叉及變異算子用于優(yōu)化初始解，具體內容如下。

2.2.1染色體編碼

每個基因位對應一個多元組〈X1，X2，X3，X4，X5，X6，X7〉，其中X1表示節(jié)點編號，X2表示節(jié)點屬性，X3表示需求量，X4表示到達該節(jié)點載重，X5表示離開該節(jié)點載重，X6表示對應站點/錨點，X7表示架次編號。解碼時可以根據多元組信息確定車輛路徑和無人機路徑，如圖4所示。

2.2.2交叉算子

本文提出了三類交叉算子：顧客節(jié)點交叉（customer-change）算子，用于對無人機訪問的同類型顧客節(jié)點之間進行交換；錨點交叉（anchor-change）算子，用于車輛訪問錨點內部之間進行交換；架次交叉（vehicle-change）算子，用于對車輛訪問錨點及其所含的架次進行調整。

1）customer-change算子

customer-change算子通過從不同無人機路徑中隨機選擇兩個同種類型的顧客節(jié)點進行交換來生成鄰域解，如圖5所示。

2）anchor-change算子

anchor-change算子通過從車輛路徑中隨機選擇兩個錨點進行交換來生成鄰域解，如圖6所示。

3）vehicle-change算子

vehicle-change算子從車輛路徑中隨機選擇兩個不同的錨點，再將錨點及錨點所在的架次組合進行交換得到鄰域解，如圖7所示。

2.2.3變異算子

本文提出了兩種變異算子：錨點替換（anchor-swap）算子，用于對車輛訪問節(jié)點與未訪問節(jié)點進行交換；顧客合并（customer-merge）算子，用于合并單送貨點和單取貨點無人機路徑。

1）anchor-swap算子

anchor-swap算子隨機選擇一對已訪問錨點和未訪問錨點，將兩者進行交換得到鄰域解，如圖8所示。

2）customer-merge算子

customer-merge算子首先在個體解內查詢是否存在單送貨點和單取貨點的無人機路徑，若存在，則將送貨點與取貨點合并在同一路徑內，若調整后存在空無人機路徑的錨點，則刪除后得到鄰域解，如圖9所示。

2.3算法整體流程

兩階段算法整體流程如圖10所示。

3數值分析實驗

3.1實驗環(huán)境

Liamp;Lim實例集（Liamp;Limbenchmark（sintef.no））［26，27］是取送貨問題常用的數據集，其中包含聚類分布lc類型、隨機分布lr類型、隨機聚類分布lrc類型。由于缺少VRPD-SPD問題的標準測試集，本文基于Liamp;Lim實例集的數據類型進行構造，具體構造方式如下：

a）保留原車輛和客戶信息，車輛容積Q=200。

b）增加錨點信息，錨點數量設置比例約為顧客點數量的1/3，即顧客點C=10時，錨點數量Va=3；C=20時，Va=6；C=30時，Va=10；C=50時，Va=16；C=100時，Va=30。

c）增加無人機信息，無人機的續(xù)航距離為30，同一錨點處無人機最大架次數量為3。

d）50個用戶以下測試集從原測試集各類型中共選取12組數據，并從中隨機選取指定數量節(jié)點形成，如lr-10是指從隨機分布lr類數據集中隨機選取了10個用戶。

e）100以上用戶測試集從原測試集各類型中共選取15組數據形成。

本文算法在PC計算機（IntelCorei102.9GHz、8GB內存）上利用Java語言，基于IDEA2021環(huán)境編程實現。

3.2參數敏感性分析

TSHAG中種群規(guī)模、迭代次數、選擇概率是算法主要參數，為了分析參數取值對算法性能的影響，基于數據集lc101、lr101、lrc101進行參數敏感性分析，種群規(guī)模設置為60、80、100、120；迭代次數設置為20、30、50；選擇概率設置為70%、80%、90%，并記錄最優(yōu)解和求解時間，結果如圖11所示。

由圖11（a）可知，種群規(guī)模為60～100時，最優(yōu)解隨著種群規(guī)模的增大而減少，當種群規(guī)模為100～120時，最優(yōu)解趨于收斂；由圖11（b）可知，最優(yōu)解在迭代次數接近30時趨于收斂；由圖11（c）可知，選擇概率為70%～80%時，最優(yōu)解隨著選擇概率的增大而減小，當選擇概率為80%、90%時，最優(yōu)解趨于收斂，且求解時間隨著各類參數值的增大而增大。綜上所述，本文算法的參數設置為：種群規(guī)模100，最大迭代次數30，選擇概率80%。

3.3模型與算法驗證分析

為驗證兩階段啟發(fā)式算法TSHAG的準確性與時效性，基于50個用戶以下的12組測試集進行實驗，每組數據上運行算法10次，對比算法與CPLEX求解的最優(yōu)解、平均解、求解時間如圖12所示。

由圖12（a）可知，在10、20、30個顧客點的算例集中，本文算法與CPLEX在求解質量上基本相等，10次運行的平均解與CPLEX的結果平均誤差為0.75%，最優(yōu)解與CPLEX的結果誤差為0；在50個顧客點的算例集中，CPLEX受時間限制較大，無法在有效時間內求得最優(yōu)解。由圖12（b）可知，本文算法在求解時間上明顯優(yōu)于CPLEX，在10、20、30個顧客點的算例集中，本文算法約6s內可以求解，而CPLEX求解時間長達7200s；在50個顧客點的算例集中，本文算法約13s內可以求解，CPLEX無法在有效時間內求得最優(yōu)解，本文算法相比于CPLEX平均計算時間節(jié)省了80%。

3.4較大規(guī)模算例的實驗分析

對于100以上用戶的測試集，CPLEX無法在有效時間內求得最優(yōu)解，因此將本文算法與基于遺傳思想的自適應算法（AAGM）［28］和混合禁忌模擬退火算法（SA-TS）［29］的最優(yōu)解、求解時間進行比較，并求出相應的GAP值，如表2所示。其中：C表示顧客數量；A表示最優(yōu)解使用的錨點數；R表示最優(yōu)解使用的架次數量；P表示最優(yōu)解使用的車輛；Obest表示TSHAG最優(yōu)解；Ebest表示AAGA最優(yōu)解；Sbest表示SA-TS最優(yōu)解；GAPOG表示TSHAG最優(yōu)解與AAGA最優(yōu)解的相對誤差；GAPOS表示TSHAG最優(yōu)解與SA-TS最優(yōu)解的相對誤差；TCPU表示算法得到最優(yōu)值時需要的求解時間。

由表2中第9、12列可知，本文算法在絕大多數算例集上的最優(yōu)解優(yōu)于對比算法AAGM、SA-TS，平均差距分別為-189%、-241%；從第7、10、13列可知，本文算法在求解速度上明顯占優(yōu)，能夠在約21s內求得最優(yōu)解，相比算法AAGM的平均求解時間節(jié)省了46%，對比算法SA-TS的求解時間超過了2min。為驗證兩階段啟發(fā)式算法的穩(wěn)定性，記錄每個算例集10次獨立運行的解與最優(yōu)解的對比情況，并計算相對標準偏差，如圖13所示。

圖13（a）～（c）展示了在lc、lr、lrc類數據集下本文算法運行結果的波動情況，各類型數據集總體波動較小，并且15組算例集10次獨立運行的相對標準偏差均在1%以內。

綜上所述，根據與CPLEX對比實驗，驗證了TSHAG算法求解VRPD-SPD問題的準確性；根據與遺傳、模擬退火對比實驗，驗證了TSHAG算法求解VRPD-SPD問題的有效性以及穩(wěn)定性。

4結束語

本文研究了考慮同時取送貨的車機協同路徑優(yōu)化問題，建立了混合整數線性規(guī)劃模型，設計了一種基于遺傳思想的兩階段啟發(fā)式算法。首先結合貪婪算法和節(jié)約算法生成初始解，其次改進了編碼方式提高解碼效率，并設計了三種交叉算子、兩種新的變異算子提升算法求解質量。通過對比實驗表明了本文所提出的兩階段啟發(fā)式算法TSHAG解決VRPD-SPD問題的有效性。

在本文的基礎上，未來的研究工作可以從以下方面進行展開：a）由于實際需求的多樣性，當要解決以時效性為目標的應急任務時，考慮帶時間窗的無人機不同位置起降、跨車?？康能嚈C協同同時取送貨問題；b）在本文算法的基礎上研究更高效的算法框架或算法策略，可以結合松弛定界等策略提高鄰域解的搜索效率，并結合實際案例情況展開計算實驗。

參考文獻：

［1］WenXupeng，WuGuohua.Heterogeneousmulti-droneroutingpro-blemforparceldelivery［J］.TransportationResearchPartC：EmergingTechnologies，2022，141：103763.

［2］王新杰，陳淮莉.多中心聯合取送貨車輛路徑優(yōu)化與利潤分配［J］.計算機工程與應用，2023，59（3）：300-307.（WangXinjie，ChenHuaili.Vehicleroutingoptimizationandprofitdistributionformulti-centerjointpick-upanddelivery［J］.ComputerEngineeringandApplications，2023，59（3）：300-307.）

［3］CaoSiqi，LiaoWenzhu，HuangYuqi.Heterogeneousfleetrecyclablescollectionroutingoptimizationinatwo-echeloncollaborativereverselogisticsnetworkfromcirculareconomicandenvironmentalperspective［J］.ScienceoftheTotalEnvironment，2021，758：144062.

［4］MinH.Themultiplevehicleroutingproblemwithsimultaneousdeliveryandpickuppoints［J］.TransportationResearchA，1989，23（5）：377-386.

［5］劉建勝，蔡祥，黃紀繪，等.考慮同時取送和時間窗的車輛路徑及求解算法［J/OL］.計算機工程與應用.（2022-07-15）.http：//kns.cnki.net/kcms/detail/11.2127.TP.20220714.1157.005.html.（LiuJiansheng，CaiXiang，HuangJihui，etal.Thesolutionalgorithmforvehicleroutingproblemconsideringsimultaneouspickup-deliveryandtimewindows［J/OL］.ComputerEngineeringandApplications.（2022-07-15）.http：//kns.cnki.net/kcms/detail/11.2127.TP.20220714.1157.005.html.）

［6］ZhangMengdi，PratapS，ZhaoZhiheng，etal.ForwardandreverselogisticsvehicleroutingproblemswithtimehorizonsinB2Ce-commercelogistics［J］.InternationalJournalofProductionResearch，2021，59（20）：6291-6310.

［7］ZhangQinghua，WuGuangpu.Modelingandmemeticalgorithmforvehicleroutingproblemwithsimultaneouspickup-deliveryandtimewindows［J］.JournalPaper，2020，40（4）：1097-1103.

［8］AmaliaIS，BakhtiarT，Jaharuddin.MinimizingthehandlingtimeinVRPwithpickup-and-deliveryandtimewindows［J］.JournalofPhysics：ConferenceSeries，2021，1863（1）：12002.

［9］ZhangShaoqing，MuDong，WangChao.Asolutionforthefull-loadcollectionvehicleroutingproblemwithmultipletripsanddemands：anapplicationinBeijing［J］.IEEEAccess，2020，8：89381-89394.

［10］YildizEA，KaraoglanI，AltiparmakF.Amixedintegermathematicalmodelandaheuristicapproachfortwoechelonlocationroutingpro-blemwithsimultaneouspickupanddelivery［J］.JournaloftheFa-cultyofEngineeringandArchitectureofGaziUniversity，2021，36（2）：807-822.

［11］BelginO，KaraoglanI，AltiparmakF.Mathematicalprogrammingbasedheuristicapproachfortwo-echelonvehicleroutingproblemwithsimultaneouspickupanddelivery［J］.JournaloftheFacultyofEngineeringandArchitectureofGaziUniversity，2021，36（3）：1566-1579.

［12］FanHouming，WuJiaxin，LiXin，etal.Presentingamulti-starthybridheuristicforsolvingtheproblemoftwo-echelonlocation-routingpro-blemwithsimultaneouspickupanddelivery（2E-LRPSPD）［J］.JournalofAdvancedTransportation，2020，2020：1-24.

［13］MartinsLDC，HirschP，JuanAA.Agileoptimizationofatwo-echelonvehicleroutingproblemwithpickupanddelivery［J］.InternationalTransinOperationalResearch，2021，28（1）：201-221.

［14］JiangHong，RenXinhui.Comparativeanalysisofdronesandridersinon-demandmealdeliverybasedonprospecttheory［J］.DiscreteDynamicsinNatureandSociety，2020，2020：1-13.

［15］Ko，LaporteG，

Tükenmez.Areviewofvehicleroutingwithsimul-taneouspickupanddelivery［J］.Computersamp;OperationsResearch，2020，122：104987.

［16］SeonJK，GinoJL，JaeyoungC，etal.Drone-aidedhealthcareservicesforpatientswithchronicdiseasesinruralareas［J］.JournalofIntelligentamp;RoboticSystems，2017，88（1）：163-180.

［17］PachayappanM，SudhakarV.Asolutiontodroneroutingproblemsusingdockingstationsforpickupanddeliveryservices［J］.TransportationResearchRecord，2021，2675（12）：1056-1074.

［18］KhoufiI，LaouitiA，AdjihC，etal.UAVstrajectoryoptimizationfordatapickupanddeliverywithtimewindow［J］.Drones，2021，5（2）：1-22.

［19］MurrayCC，ChuAG.Theflyingsidekicktravelingsalesmanpro-blem：optimizationofdrone-assistedparceldelivery［J］.TransportationResearchPartC：EmergingTechnologies，2015，54：86-109.

［20］HamAM.Integratedschedulingofm-truck，m-drone，andm-depotconstrainedbytime-window，drop-pickup，andm-visitusingconstraintprogramming［J］.TransportationResearch：PartC，EmergingTechnologies，2018，91：1-14.

［21］褚衍昌，王雪婷，張娜.貨車聯合無人機的農村電商物流運輸路徑規(guī)劃［J］.物流技術，2020，39（9）：82-88，133.（ChuYanchang，WangXueting，ZhangNa.Rurale-commercelogisticstransportpathplanningwithtruck-UAVcombineddeliveryandpick-up［J］.LogisticsTechnology，2020，39（9）：82-88，133.）

［22］EuchiJ，SadokA.Hybridgenetic-sweepalgorithmtosolvethevehicleroutingproblemwithdrones［J］.PhysicalCommunication，2021，44：101236.

［23］BerahhouA，BenadadaY.Dynamicvehicleroutingproblemwithsimultaneousdeliveryandpickup：formulationandresolution［C］//Procofthe5thInternationalConferenceonLogisticsOperationsMa-nagement.Piscataway，NJ：IEEEPress，2020：1-8.

［24］WangXiaowei.Researchonhybridimmunealgorithmforsolvingthelocation-routingproblemwithsimultaneouspickupanddelivery［J］.JournalofCasesonInformationTechnology，2022，24（5）：1-17.

［25］郭放，黃志紅，黃衛(wèi)來.考慮前置倉選址與服務策略的同時取送貨車輛路徑問題研究［J］.系統(tǒng)工程理論與實踐，2021，41（4）：962-978.（GuoFang，HuangZhihong，HuangWeilai.Integratedsustainableplanningoffast-pickareanetworkandvehicleroutingwithsimultaneousdeliveryandpick-up［J］.SystemsEngineering-Theoryamp;Practice，2021，41（4）：962-978.）

［26］LiHaibing，LimA.Ametaheuristicforthepickupanddeliverypro-blemwithtimewindows［J］.InternationalJournalonArtificialIntelligenceTools，2003，12（2）：173-186.

［27］吳廷映，陶新月，孟婷.“卡車+無人機”模式下帶時間窗的取送貨車輛路徑問題［J/OL］.計算機集成制造系統(tǒng).（2022-05-17）.http：//kns.cnki.net/kcms/detail/11.5946.TP.20220517.1108.016.html.（WuTingying，TaoXinyue，MengTing.Pickupanddeli-veryproblemwithtimewindowsinthemodeof“truck+drone”［J/OL］.ComputerIntegratedManufacturingSystems.（2022-05-17）.http：//kns.cnki.net/kcms/detail/11.5946.TP.20220517.1108.016.html.）

［28］馬華偉，馬凱，郭君.考慮多投遞的帶無人機車輛路徑規(guī)劃問題研究［J］.計算機工程，2022，48（8）：299-305.（MaHuawei，MaKai，GuoJun.Researchonvehicleroutingproblemwithdronesconsideringmulti-delivery［J］.ComputerEngineering，2022，48（8）：299-305.）

［29］LiuYao，LiuZhong，ShiJianmai，etal.Two-echelonroutingproblemforparceldeliverybycooperatedtruckanddrone［J］.IEEETransonSystems，Man，andCybernetics：Systems，2020，51：7450-7465.