基于改進蟻群算法的外賣配送路徑規劃研究

摘要：從外賣配送員角度出發提出一種改進蟻群算法（Improved Ant Colony Optimization，IACO），在此基礎上進行外賣配送路徑規劃研究．首先通過蟻群算法（Ant Colony Optimization，ACO）求解得到初始規劃路徑，然后通過大規模鄰域搜索算法（Large Neighborhood Search，LNS）優化初始規劃路徑，通過將ACO和LNS算法結合，提高求解質量．為了驗證方法的有效性，對外賣配送過程進行仿真，并且選用不同訂單數量場景進行對照分析．根據最優配送方案路線圖和目標罰函數的最優值可以得出，IACO算法是有效的，且可以提高外賣配送員外賣配送的效率．IACO算法不但能夠提升配送的智能化水平，還從外賣配送員的角度提出一種更為人性化的配送方法，支持網絡互聯外賣平臺派送系統的可持續化發展．

關鍵詞：改進蟻群算法;大規模鄰域搜索算法;外賣配送;配送方案

中圖分類號F252;TP18

文獻標志碼A

0引言

隨著科技的快速發展，人們的生活變得更加便利．外賣行業蓬勃發展，使得人們能夠在互聯網上購買自己想要和需要的物品．外賣行業在日常生活中顯得越來越重要，同時對于外賣配送服務的要求也越來越高．外賣配送服務的流程是客戶在第三方平臺購物下單，商家接受訂單后，平臺的外賣配送員根據訂單信息進行外賣配送服務．在正常情況下一位外賣配送員在同一時間段中所需要配送的外賣可能會有多個，在外賣配送過程中會因為配送路線安排不合理導致訂單無法及時送達等問題．在外賣平臺系統的設置中，配送超時是不被允許的，一旦出現配送超時的問題，客戶對外賣配送員的評價可能為差評，將造成外賣配送員收入降低、獎金被扣等負面影響［1-3］．

外賣配送問題，可以簡化為帶有時間窗和容量限制的車輛路徑問題［4］．針對車輛路徑問題（VRP），常見的求解方法有遺傳算法［5］、蟻群算法［6］、禁忌搜索［7］等智能算法．遺傳算法是通過模擬生物進化適者生存的過程，在解決組合優化問題時使用選擇、交叉、變異操作找出全局最優解．遺傳算法的操作較簡單，在不同的鄰域可以表現出很好的兼容性，但是在解決具有針對性，并且要求一定精度的問題時，算法所得到的解在局部表現得不令人滿意［8］．禁忌搜索算法需要對每個可能的解進行檢查，因此搜索效率較低．蟻群算法（Ant Colony Optimization，ACO）的基本思想是模擬螞蟻尋找食物的過程，當得到一條有效路徑時會釋放一定的信息素標記該路徑，對其他螞蟻起到引導作用，從而加速整個搜索過程［9］．蟻群算法可以處理大規模的解空間，并且自適應地調整搜索范圍，因此蟻群算法對多種組合優化和運輸調度問題具有較好效果．近年來，國內外學者們針對基本蟻群算法易陷入局部最優解和收斂速度慢的缺點，進行了大量的改進研究．Zhang等［10］將鄰近啟發式算法與蟻群算法結合，提高了算法的性能和求解的質量;王曉東等［11］引入節約矩陣U引導螞蟻搜索，通過不同搜索時段采用不同的信息素揮發因子，平衡優化蟻群算法中權重的分配，提高算法的性能;Donati等［12］使用多蟻群系統（MACS-VRPTW）算法求解VRPTW問題，通過設計多個蟻群系統對多目標進行優化，提高求解速度和解的質量;Kalayci等［13］基于蟻群系統（ACS）和可變鄰域搜索（VNS）的混合算法，防止算法求解陷入局部最優解，提高算法的性能和解的質量;李琳等［14］將蟻群系統（ACS）與最大最小螞蟻系統（MMAS）結合，并且設計在算法不同階段采用不同的信息素蒸發策略防止陷入局部最優，用2-opt和2-opt*方法對每次迭代所得最優解進行局部優化，提高算法性能．針對傳統智能算法易出現局部最優解情況，Blum等［15］提出進化算法（EA）與大規模鄰域搜索算法（Large Neighborhood Search，LNS）結合可以提高進化算法生成解的質量，從而提高算法的性能;徐倩等［16］提出一種自適應大規模鄰域搜索算法求解外賣配送車輛調度問題，提高了外賣配送效率．

為了解決外賣配送路徑規劃問題，本文提出一種改進蟻群算法（Improved Ant Colony Optimization，IACO），綜合考慮外賣配送員在進行外賣配送過程中的實際情況，對外賣配送路徑進行規劃．外賣配送過程中不僅有時間窗要求，對配送數量同樣有要求，并且要求配送總路徑盡可能短．因此，本文所研究的外賣配送過程可以簡化為有時間窗約束和車載容量約束的車輛路徑問題（CVRPTW）．引入外賣配送過程中以費用最小為目標的罰函數，建立外賣配送的數學模型，結合蟻群算法和大規模鄰域搜索算法（LNS）對所建立的數學模型進行分析求解，并通過仿真實驗對模型和所提出的改進蟻群算法進行驗證分析．

本文的貢獻為：1）從外賣配送員的角度出發，在外賣配送過程中考慮到時間窗約束、容量約束和最短總路徑，所設計的算法更加貼近實際;2）根據外賣配送員配送過程的實際情況設計合理的外賣配送數學模型，以配送過程中的費用最小為目標設計罰函數，充分考慮到對于配送員的最優方案的設計;3）將蟻群算法和大規模鄰域搜索算法結合，提高單一算法的求解質量，并且合理運用在本文所設計的外賣配送方案模型中，通過仿真結果驗證了所提出算法的有效性，從而提高外賣配送效率．

1外賣配送問題描述

本文研究的問題是針對一個外賣配送中心向多位顧客配送外賣或在一個緊湊的商業區向多位顧客進行外賣配送的場景．因此，該外賣配送路徑規劃問題可以描述為在滿足配送員車載容量約束和送餐時間窗約束的前提下，對配送員的外賣配送路徑進行合理規劃，以提高配送效率并滿足約束條件．整體規劃出的路徑需要使車輛的使用數目、配送員行駛總距離和違反約束條件的懲罰函數的各項成本之和達到最小．對本文所研究的問題可以簡化為帶有時間窗約束和車載容量約束的車輛路徑問題（CVRPTW）［17］．因此，對研究的CVRPTW問題提出如下假設：

1）外賣配送員配送起點和終點都為配送中心;

2）所有外賣車輛的車載容量相同，配送容量不能超過車載容量;

3）每位顧客的外賣只能由一位外賣配送員進行配送;

4）每位顧客的外賣質量已知，并且提供送餐時間窗．

數學模型描述如下：

設K為外賣配送中心配送員總數的集合;N為需要配送服務的n個顧客點的集合，N=｛1，2，3，…，n｝;V=｛0｝∪N．

min∑k∈K∑i∈Vk∑j∈Vk｛i｝Cijxij|k， （1）

s.t.∑j∈Vk｛i｝xij|k=yi|k，∑i∈Vk｛j｝xij|k=yi|k，i∈V，j∈V，k∈K，（2）

∑j∈Vkqiyi|k≤Q，k∈K，（3）

∑j∈Nx0j|k=∑i∈Nxi0|k=1，k∈K，（4）

∑k∈Kyi|k=1，i∈N，（5）

∑i，j∈Vkxij|k≤|Vk|-1，k∈K，（6）

TE，i≤ai≤TL，i，i∈N.（7）

其中：0為配送中心;Vk為車輛訪問顧客的集合;i，j表示顧客編號;xij|k表示配送員k對顧客i的外賣配送結束后是否需要配送顧客j;yi|k表示配送員k是否完成了對顧客i的外賣配送;Q表示配送員配送外賣容量的約束;qi表示顧客i的外賣需求量;Cij為配送員從i點駛向j點的運輸成本;TE，i為顧客i允許的最早外賣配送到達時間;TL，i為顧客i允許的最遲外賣配送到達時間;ai為配送員到達顧客i的時間．xi|k，yi|k為決策變量，當配送員k對顧客i的外賣配送完成后對顧客j進行外賣配送，xij|k=1，否則xij|k=0;當顧客i由配送員k進行外賣配送時，yi|k=1，否則yi|k=0．

式（1）表示配送員外賣配送過程中費用最小的目標罰函數;式（2）表示配送員k在配送完顧客i后只配送顧客j，配送員k在配送顧客j之前只配送顧客i;式（3）表示每個配送員配送外賣的總容量不能超過車載總容量;式（4）表示每個配送員從配送中心出發，送完最后一個顧客后返回配送中心;式（5）表示每位顧客只能有一位配送員進行外賣配送;式（6）表示避免配送過程中產生子回路;式（7）表示配送員給每位顧客配送外賣到達時間應該在規定的時間窗范圍內．

2改進蟻群算法設計

2.1蟻群算法原理

蟻群算法是一種源于自然界的放生進化算法，主要思想是螞蟻在覓食的過程中會在經過的路徑留下信息素從而引導整個蟻群的搜索過程，人類通過計算機模擬自然界中蟻群覓食的行為進行蟻群算法的開發．每只螞蟻都會進行覓食行為，并且在覓食的路徑上留下一種特有物質——信息素，其他螞蟻在經過該路徑時，可以感應到該信息素，并以此引導其他螞蟻覓食．一般情況下，螞蟻離開巢穴，會選擇一條通往目的地的路徑，在路徑的每一個交叉點上都會將前一只螞蟻所釋放的信息素作為標記來選擇接下來前進的路徑，以此進行多次迭代可以得到最優路徑．

2.2配送路徑生成

配送員k從顧客i所在地方出發到顧客j所在地方那一刻時間為aj，根據式（7）要求aj的范圍，如果aj小于顧客j時間窗的左邊界，會導致配送員需等待顧客所設定的外賣最早到達時間，影響外賣的配送效率，配送成本增加;如果aj大于顧客j時間窗的右邊界，會導致配送員配送外賣超時，極易引起顧客差評等不滿評價，導致配送員利益受損．因此，在配送員配送外賣的到達時間必須在規定的時間窗范圍內，所規劃出的路徑對于配送員來說比較合理，需要在狀態轉移過程中加入等待時間的影響因素．當TE，j≤aj≤TL，j時，配送員k外賣配送到顧客j的等待時間tw，j=0，將tw，j取一個很小的正數;當aj≤TE，j時，tw，j=TE，j-aj;當aj≥TL，j時，tw，j=aj-TL，j．同時，配送員對顧客配送外賣的時間窗跨度也會影響對配送路徑規劃，在配送時間窗開始時刻一樣的顧客j1和顧客j2時，如果顧客j1的時間窗跨度小于顧客j2，則顧客j1對于外賣的配送要求更加緊急，對于配送員來說超時的可能性會越大，因此會優先顧客j1的外賣配送．在狀態轉移過程中加入時間窗跨度影響因素fwidth，j=TL，j-TE，j．

狀態轉移概率Pij|k（t）表示在第t次迭代時，螞蟻k從節點i移動到節點j的概率，移動規則如下所示：

j= maxj∈Ni|k｛［τij（t）］α［ηij（t）］β［1／fwidth，j］γ［1／tw，j］δ｝，

r≤r0；

Pij|k（t），rgt;r0.（8）

其中：Pij|k（t）為使用輪盤賭法選擇點j的概率，可表示為［τij（t）］α［ηij（t）］β［1／fwidth，j］γ［1／tw，j］δ∑j∈Ni|k（［τij（t）］α［ηij（t）］β［1／fwidth，j］γ［1／tw，j］δ）;Ni|k是未被蟻群訪問過的節點集合，可以通過概率值選擇下一個節點;τij（t）表示在第t次迭代時，節點i與節點j形成的邊上的信息素的量;α表示信息素對蟻群搜索的影響大小;ηij（t）表示形成的邊對螞蟻的可見度大小，ηij（t）=1／dij，dij為節點i到節點j的距離，如果兩個節點距離越遠，表示螞蟻的可見度越小;β是可見性對蟻群搜索的影響，β越大，蟻群更有可能會采取可見度高的路徑;γ表示時間窗跨度因素導致螞蟻對節點選擇影響的大小;δ表示等待時間因素導致螞蟻對節點選擇影響的大小;r為［0，1］上服從均勻分布的隨機變量;r0為控制轉移規則的參數，并且0≤r0≤1．

螞蟻在訪問完該條路徑后，會在該路徑上留下信息素，對其他螞蟻起引導作用．每次迭代后，螞蟻會重復經過該路徑，會使得信息素更新，信息素的表達式為

τij（t+1）=（1-ρ）τij（t）+∑nk=1Δτij|k（t），（9）

Δτij，k（t）= Q／Lk，j∈V；0，其他.（10）

其中：ρ為信息素揮發因子，大小為0lt;ρlt;1;Δτij|k（t）表示為第t次迭代的第k只螞蟻經過路徑留下的信息素，初始Δτij|k（0）設為1;Lk表示第k只螞蟻從配送中心出發到回到配送中心訪問的總路徑長度;Q為設定的常數，本文實驗給定為5．

令一組螞蟻從配送中心出發，每一只螞蟻按照式（8）規則選擇下一訪問節點j，當根據規則找不到合理的下一節點j時，螞蟻返回配送中心，則該只螞蟻對應的配送路徑規劃完成，一組螞蟻全部遍歷完節點后，即生成規劃的外賣的配送路徑．

2.3大規模鄰域搜索算法（LNS）

大規模鄰域搜索算法從蟻群算法所得出的初始解進行優化，通過算法中的“破壞”和“修復”兩個階段對初始解進行優化操作，從而得到最優解．假設通過蟻群算法得到的配送路徑為S0，設定最優解Sbest=S0，即記錄當前路徑;將路徑Sbest中的顧客隨機抽出，即進行破壞操作，記錄當前的路徑為Sd;對路徑Sd進行顧客插入的操作，即進行修復操作，記錄當前的路徑為Sr．比較路徑Sr罰函數的值與最優解路徑Sbest罰函數的值大小：如果路徑Sr罰函數的值小于最優解路徑Sbest罰函數的值，則認為破壞、修復后的路徑Sr優于路徑Sbest，于是有Sbest=Sr，實現更新最優解，否則重新進行破壞、修復兩個操作．當滿足終止條件的罰函數值時，即輸出最優路徑Sbest，其流程如圖1所示．

2.4改進蟻群算法流程

將蟻群算法和大規模鄰域搜索算法結合，使用大規模鄰域搜索算法對蟻群算法所求得的初始解進行優化操作．大規模鄰域搜索算法優化初始解的實質是通過將蟻群所遍歷路徑進行破壞和重新修復操作，防止蟻群陷入局部最優解，從而改善初始解，得到優質解．解決帶載重約束和時間窗約束的外賣配送算法原理如圖2所示．

2.5改進蟻群算法步驟

改進蟻群算法的偽代碼如表1所示．

3仿真分析

在MATLAB平臺進行仿真實驗，對本文所提出的改進蟻群算法、未改進的蟻群算法和遺傳算法，針對不同數量的顧客進行外賣配送仿真分析．根據外賣配送實際情況，模擬外賣訂單的低峰期和高峰期兩個場景，驗證本文所提出的改進蟻群算法的有效性．設定外賣訂單的低峰期和高峰期顧客人數分別為25和110，配送員由配送中心出發，在規定的時間窗范圍內進行外賣配送，最后返回配送中心．設定迭代次數T=50，配送員的最大載貨容量設定為15．

3.1訂單數量較少場景仿真分析

表2為25位顧客和配送中心的信息數據，使用MATLAB軟件進行模擬配送員進行外賣配送的場景，分別使用未改進的蟻群算法、遺傳算法和本文提出的改進蟻群算法進行配送員的配送路徑規劃，配送路線和罰函數最優值變化曲線分別如圖3、圖4和圖5所示，詳細配送路徑分別如表3、表4和表5所示．

由圖3—5可知：使用蟻群算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為8 180;使用遺傳算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為6 886;本文設計的改進蟻群算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為6 615．因此，可以求得改進蟻群算法在訂單數量較少的場景下，與蟻群算法相比提升性能為19.13％，與遺傳算法相比提升性能為3.94％．

3.2訂單數量較多場景下的仿真分析

表6為110位顧客和配送中心的信息數據，使用MATLAB模擬配送員進行外賣配送的場景．分別使用未改進的蟻群算法、遺傳算法和本文提出的改進蟻群算法進行配送路徑規劃．配送路線圖和罰函數最優值變化曲線如圖6、圖7和圖8所示，詳細配送路徑如表7、表8和表9所示．

由圖6—8可知：使用蟻群算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為3.945×104;使用遺傳算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為4.413×104;改進蟻群算法在迭代50次后，所得到外賣配送路徑的罰函數最優值為2.215×104．本文提出的改進蟻群算法在訂單數量較多的場景下，與蟻群算法相比，性能提升為43.85％，與遺傳算法相比性能提升為49.81％．

3.3仿真結果分析

由仿真結果可知，當訂單數量較少時，蟻群算法、遺傳算法和本文所提出的改進蟻群算法都可以根據顧客信息進行合理的外賣配送路徑規劃，并且最后所得到的路徑均未出現違反時間窗等情況．整個外賣配送過程中的一個綜合判定，表現為所設定罰函數的最優值大小：最優值越小，說明配送過程中違反約束的情況越少，并且綜合配送成本越低，反之則違反約束情況多，并且配送成本高．蟻群算法、遺傳算法和本文所提出的改進蟻群算法，進行外賣配送路徑規劃的罰函數最優值比較，結果如表10所示．根據表10中罰函數的最優值結果分析可得：顧客數量較少時，改進后蟻群算法的性能相比蟻群算法和遺傳算法分別提升19.13％和3.94％;顧客數量較多時，改進后蟻群算法的性能相比蟻群算法和遺傳算法分別提升43.85％和49.81％．結果表明，本文提出的改進蟻群算法所求解的外賣配送路徑的性能有較大提升，說明所提出的算法是有效的，可以合理運用在訂單數量較多的場景．

4結論

本文研究了有時間窗約束和車載容量約束的VRP問題，提出了一種改進蟻群算法，既有蟻群算法快速尋找解的優點，又有大規模鄰域算法優化解質量的優點．結合MATLAB仿真平臺進行驗證，選取顧客訂單數量較少和較多的兩個場景，選用蟻群算法、遺傳算法和本文所提出的改進蟻群算法進行對照仿真，根據所得到的最優配送方案路線和罰函數的最優值可以得出，本文提出的改進蟻群算法，可以較好地規劃外賣配送路徑，滿足約束要求，合理提升外賣配送效率．

參考文獻

References

［1］初良勇，閆淼，胡美麗，等.生鮮產品物流配送路徑優化研究綜述及展望［J］.物流研究，2021，3（1）：5-13

CHU Liangyong，YAN Miao，HU Meili，et al.Review and prospect of fresh product logistics distribution route optimization［J］.Logistics Research，2021，3（1）：5-13

［2］趙金龍，蔣忠中，萬明重，等.考慮配送截止時間的“貨到人”訂單揀選優化問題研究［J／OL］.中國管理科學：1-12［2022-12-08］.https：／／doi.org／10.16381／j.cnki.issn1003-207x.2022.1049

ZHAO Jinlong，JIANG Zhongzhong，WAN Mingzhong，et al.Optimization of parts-to-picker order picking with due dates［J／OL］.China Management Science：1-12［2022-12-08］.https：／／doi.org／10.16381／j.cnki.issn1003-207x.2022.1049

［3］周成昊，呂博軒，周翰宇，等.以商圈為中心的O2O動態外賣配送路徑優化模型與算法［J］.運籌學學報，2022，26（3）：17-30

ZHOU Chenghao，L Boxuan，ZHOU Hanyu，et al.Optimization model and algorithm for online to offline dynamic take-out delivery routing problem centered on business districts［J］.Operations Research Transactions，2022，26（3）：17-30

［4］劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述［J］.管理工程學報，2005，19（1）：124-130

LIU Yunzhong，XUAN Huiyu.Summarizing research on models and algorithms for vehicle routing problem［J］.Journal of Industrial Engineering and Engineering Management，2005，19（1）：124-130

［5］畢華玲，趙亞風，盧福強，等.考慮客戶風險偏好的第四方物流路徑問題研究［J／OL］.南京信息工程大學學報（自然科學版）：1-12［2022-06-16］.http：／／kns.cnki.net／kcms／detail／32.1801.N.20220615.1221.002.html

BI Hualing，ZHAO Yafeng，LU Fuqiang，et al.Research on 4PL routing problem considering customer risk preference［J／OL］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition）：1-12［2022-06-16］.http：／／kns.cnki.net／kcms／detail／32.1801.N.20220615.1221.002.html

［6］蘇濤，韓慶田，李文強，等.VRP問題蟻群算法研究［J］.計算機與現代化，2012（11）：18-21，25

SU Tao，HAN Qingtian，LI Wenqiang，et al.Research on VRP problem based on ant colony algorithm［J］.Computer and Modernization，2012（11）：18-21，25

［7］賀琪，官禮和，崔煥煥.硬時間窗VRP的混合變鄰域禁忌搜索算法［J］.計算機工程與應用，2023，59（13）：82-91

HE Qi，GUAN Lihe，CUI Huanhuan.Hybrid variable neighborhood tabu search algorithm for vehicle routing problem with hard time window［J］.Computer Engineering and Application，2023，59（13）：82-91

［8］王東.改進多種群遺傳算法的研究及其在車輛路徑優化的應用［D］.南寧：廣西大學，2016

WANG Dong.Research on improved multi-population genetic algorithm and its application in vehicle routing optimization［D］.Nanning：Guangxi University，2016

［9］董平先，郭放，陳晨，等.基于優化蟻群算法的電纜敷設路徑規劃［J］.南京信息工程大學學報（自然科學版），2023，15（2）：210-217

DONG Pingxian，GUO Fang，CHEN Chen，et al.Cable laying path planning based on optimized ant colony algorithm［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2023，15（2）：210-217

［10］Zhang X，Wang J Q.Hybrid ant algorithm and applications for vehicle routing problem［J］.Physics Procedia，2012，25：1892-1899

［11］王曉東，張永強，薛紅.基于改進蟻群算法對VRP線路優化［J］.吉林大學學報（信息科學版），2017，35（2）：198-203

WANG Xiaodong，ZHANG Yongqiang，XUE Hong.Improved ant colony algorithm for VRP［J］.Journal of Jilin University （Information Science Edition），2017，35（2）：198-203

［12］Donati A V，Montemanni R，Casagrande N，et al.Time dependent vehicle routing problem with a multi ant colony system［J］.European Journal of Operational Research，2008，185（3）：1174-1191

［13］Kalayci C B，Can K Y.An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery［J］.Expert Systems with Applications，2016，66：163-175

［14］李琳，劉士新，唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題［J］.控制與決策，2010，25（9）：1379-1383

LI Lin，LIU Shixin，TANG Jiafu.Improved ant colony algorithm for solving vehicle routing problem with time windows［J］.Control and Decision，2010，25（9）：1379-1383

［15］Blum C，Eremeev A，Zakharova Y.Hybridizations of evolutionary algorithms with large neighborhood search［J］.Computer Science Review，2022，46：100512

［16］徐倩，熊俊，楊珍花，等.基于自適應大鄰域搜索算法的外賣配送車輛路徑優化［J］.工業工程與管理，2021，26（3）：115-122

XU Qian，XIONG Jun，YANG Zhenhua，et al.Based on an adaptive large neighborhood search algorithm for take-out delivery vehicle routing optimization［J］.Journal of Industrial Engineering and Management，2021，26 （3）：115-122

［17］Natalia C，Triyanti V，Setiawan G，et al.Completion of capacitated vehicle routing problem （CVRP） and capacitated vehicle routing problem with time windows （CVRPTW） using bee algorithm approach to optimize waste picking transportation problem［J］.Journal of Modern Manufacturing Systems and Technology，2021，5（2）：69-77

Takeout delivery path planning based on improved ant

colony optimization algorithm

TANG Chuanyin1ZHANG Mingli1LI Jinghong2，3YUAN Ying4Wei Meirong1

1School of Mechanical Engineering and Automation，Northeastern University，Shenyang 110819，China

2School of Mechanical Engineering，Shanghai Dianji University，Shanghai 201306，China

3School of Mechanical Engineering，Zhejiang Sci-Tech University，Hangzhou 310018，China

4School of Business Administration，Northeastern University，Shenyang 110167，China

AbstractIt is impossible for takeaway delivery staff to plan the takeout delivery route balancing rationality and efficiency.To address this problem，an Improved Ant Colony Optimization （IACO） algorithm is proposed.The initial routes are obtained using the Ant Colony Optimization （ACO） algorithm and then optimized using Large Neighborhood Search （LNS） algorithm.The solution quality is improved by combining the ACO algorithm with the LNS algorithm.The proposed algorithm is verified by simulating the delivery routes for different number of takeout orders.Comparative analysis shows that the proposed IACO algorithm can increase the takeout delivery efficiency，according to the optimal distribution plan and the ideal value of the objective penalty function.The proposed strategy can enhance the intelligence and promote the long-term growth of the delivery system of Internet-connected takeout platforms.

Key wordsimproved ant colony optimization （IACO）;large neighborhood search （LNS）;takeout delivery;distribution schemes