基于改進遺傳算法的校園外賣配送路徑規劃

范立南 呂鵬

摘? 要：隨著互聯網和智能手機的普及，校園外賣也取得了迅速的發展，而如何對校園內各個外賣配送地點進行配送路徑的規劃是當前校園外賣存在的一大問題。文章選取了沈陽大學北校區的24個外賣配送地點，利用遺傳算法和TSP問題的相關理論，通過對比傳統的遺傳算法與蟻群算法在實驗中的優劣，采用改進的自適應遺傳蟻群混合算法，對沈陽大學校園內外賣配送路線進行了合理的規劃，并通過MATLAB軟件對路徑做了仿真實驗。試驗結果表明，文章中算法能有效縮短校園外賣配送路徑長度，提供較為合理的優化路徑，能夠有效提升外賣員的配送效率，具有一定的應用價值。

關鍵詞：校園外賣;遺傳算法;TSP問題;蟻群算法

中圖分類號：U116??? 文獻標識碼：A

Abstract： With the popularity of the Internet and smartphones， campus takeaways have also achieved rapid development， and how to plan the distribution routes of various takeaway locations on campus is a major problem in campus takeaways. This paper selects 24 take-out delivery locations in the north campus of Shenyang University， uses genetic algorithm and related theories of TSP problem， and compared the advantages and disadvantages of traditional genetic algorithm and ant colony algorithm in the experiment， and adopted an improved adaptive genetic ant colony hybrid algorithm， reasonable planning of the take-out delivery route on the campus of Shenyang University， MATLAB software conducts simulation experiments on the path. The test results show that the algorithm can effectively shorten the length of campus takeaway delivery routes， provide a more reasonable optimized route， and can effectively improve the delivery efficiency of takeaways. It has certain application value.

Key words： campus take-out; genetic algorithm; TSP problem; colony algorithm

0? 引? 言

作為大學生群體聚集度高且消費水平強的大學校園，已經成為第三方平臺外賣配送的主要區域，而在校園內錯綜復雜的配送線路是外賣員進行配送需要常常考慮的問題[1]。減少外賣員的配送距離能有效提高外賣員的工作效率并降低配送成本，而外賣配送實際上就是TSP問題[2]。王荃菲[3]基于城市內的復雜道路交通流量對外賣配送尋優路徑問題展開了研究。馬江濤[4]針對醫藥產品的物流配送路徑采用遺傳算法進行了路徑尋優。郭豐林[5]針對景區旅游路徑規劃問題，將所要前往的旅游景點網絡抽象成TSP問題，通過傳統的遺傳算法實現對旅游路徑的規劃。徐坤[6]選擇物流快遞配送路線的尋優問題作為研究案例，把配送問題抽象成求解車輛路徑規劃模型，運用蟻群算法求解該問題并對配送路徑進行優化，獲得了較好的配送路徑。馬駿[7]針對旅行商問題，基于遺傳算法并通過MATLAB軟件編寫的程序，得到了較好的優化結果。

本文正是針對校園外賣配送路徑展開研究，將沈陽大學北校區的多個地點構成的外賣配送目的地網絡作為研究對象，將配送路徑規劃問題抽象成旅行商問題，利用傳統的遺傳算法與蟻群算法對此類問題進行求解及討論，并通過遺傳算法的相關設計及改進，借助MATLAB軟件對校園內外賣的配送路徑進行仿真實驗獲取最優配送路徑，從而實現對校園內外賣配送路徑的規劃。

1? TSP問題與傳統算法

1.1? TSP問題描述

TSP問題可以簡單的理解為：一個人想要去往n個目標地點，他需要挑選一條將要出發的路線，而路線的挑選必須嚴格遵守任一目標地點只能尋歷一次的規則，尋歷結束后最終要回到剛開始出發的地點。路線的選擇所要達到的目標是要求使得行走路線的總距離為所有路線之中的最小值。它是一個復雜程度高且密集的非確定性問題，隨著此類問題規模的不斷增大，對TSP問題進行求解，在近些年的研究中，國內外一些優秀學者運用的算法主要包括遺傳算法[8]、模擬退火算法[9]、蟻群算法[10]、禁忌搜索算法[11]、粒子群算法[12]等。

1.2? 遺傳算法的基本原理

遺傳算法是一種隨機檢索方法，它沿用了生物世界的進化定律（適者生存，優勝劣汰）。它的主要特點是可以直接對種群空間中的多個解進行搜索，對函數的求導及其連續性的判定沒有約束，具有良好的魯棒性和更全面的全局搜索尋優能力[13]。使用遺傳算法來處理尋優問題時，過程中每個可能出現的解決方案都可以被編碼成一個“染色體”，也就是一個個體，而多個個體相互之間組成了一個群組（所有可能的解決方案）。因此，遺傳算法可以看成多個可能出現的解決方案所構成的一個群組從始到末的演化過程。遺傳算法主要過程及流程圖如圖1所示。

1.3? 蟻群算法的基本原理

蟻群算法最開始是根據對螞蟻種群的觀察，分析螞蟻種群行為信息特點，從中得到啟發而設計的算法。在蟻群整個的移動路徑中，它們會在其經過的路徑上釋放僅適用于蟻群之間信息共享和通信的信息素。在蟻群移動過程中，它們能夠察覺到釋放的物質并以此來追蹤這一物質，在后面的移動中，繼續產生信息素。一條道路上的信息素蹤跡越密，其他螞蟻沿著該路徑行進的可能性就越高，因此該路徑上的信息素蹤跡將得到加強。螞蟻種群利用蟻群個體之間的間接信息溝通渠道來達到協同遍歷搜索最短路徑的目的。蟻群算法這種啟發式算法的出現，解決了組合爆炸的問題，其可以在合理的時間范圍內找到可接受的最優解[14]。

2? 算法設計

2.1? 問題描述

本文選取了沈陽大學北校區24個外賣配送地點，依次進行編號為1至24號。對外賣配送地點坐標的選取，本文則通過百度地圖生成校園內各個地點的經緯度坐標，由于在地圖上各點的經緯度相近，為了更加直觀的顯示仿真運算結果，對經緯度進行如下處理：（a）只保留經度的小數點后的3、4位生成十位數字坐標;（b）只保留緯度的小數點后的2、3、4位生成百位數字坐標。如1號教學樓的經緯度坐標為（123.464988，41.830611），本文選取坐標為（49，306）。設定完畢的外賣配送地點坐標，如表1所示。

百度地圖上外賣配送地點的地址如圖2所示。

經上述操作后，本文研究的校園外賣配送的路徑規劃問題可表示為以沈陽大學北校區的24個配送地點為研究對象，設置1號教學樓為出發地點，求歷經其余23個配送地點后，最后回到1號教學樓的一條最短路徑的TSP類規劃問題。

2.2? 遺傳算法實現

（1）順序式編碼。在遺傳算法的編碼過程中，通常使用二進制作為編碼方式，但在本文求解最優配送路徑問題時，采用的是按節點順序進行編碼的編碼方式。例如，對于遍歷7個城市的一條旅行路徑5-4-2-6-1-3-7可簡單表示為向量5426137，表示從城市5出發依次經歷城市4，2，6，1，3，7然后返回城市5的一條路徑。

（2）初始化種群。設定遺傳進化的代數計數器t=0，進化的最大代數為T，并隨機產生一定數量的染色體（個體），從所有的個體集中選擇出M個個體當作初始種群P0。

（3）適應度函數設計。TSP的目標是路徑總長度為最短，在進行選擇時適應度值越大則被遺傳到下一代的概率越大，為使適應度值最大，故采用路徑總長度的倒數值作為TSP的適應度值：

fx=????????????????????????????????????????????? （1）

其中：

disV=dV，V+dV，V???????????????????????????????????? （2）

（4）選擇運算。遺傳選擇的目的是對于適應度較大的個體能夠有機會直接遺傳到下一代或者利用交叉配對的形式生成全新的個體再遺傳到下一代。本文采用的是錦標賽選擇的方法，即從當代種群中隨機選擇一定數量的個體，并將所有個體中適應性最強的個體遺傳給下一代群體[15]。在本文中，從父代種群中隨機選擇4個路徑個體，通過比較它們各自的適應度值，挑選出當中適應度值最大的一個個體進化到下一代，種群規模popsize=300，也就是說選擇運算重復300次，最終得到新一代的種群。

（5）交叉操作。遺傳交叉操作中尤為重要的就是交叉算子的設計。本文采用次序雜交OX來設計交叉算子，從父代A中隨機挑選任一個編碼片段，在子代B的對應位置處插入，而子代B的其他位置由父代A中的編碼（去除從父代A中已經選取的編碼）按順序填充。子代B也采用相同的形式獲取。求解過程如圖3所示。

（6）變異操作。因為TSP問題的限定是旅行路徑中的每個地點只能尋訪一次，故不能采用傳統遺傳算法中常用的二進制編碼的變異操作方法，不能由簡單變量通過翻轉操作來實現變異。本文中對種群進行變異操作時采用的是染色體兩點交換變異算子，將外賣配送地點的編碼序列作為父代染色體，從中隨機抽取兩個地點作為發生交換變異的對象，然后將這兩個地點的位置進行交換，通過交換變異可以得到新一代的染色體[16]，這樣就完成了個體的遺傳變異操作。

（7）終止條件判斷。當t=T時，則將進化過程中產生的適應度值最大的個體當作遺傳尋優結果輸出，停止計算過程。

2.3? 蟻群算法實現

采用基于信息素的蟻周模型處理TSP問題的傳統蟻群算法的操作步驟為：

（1）初始化蟻群各項基本參數以及各條配送路徑上的信息素，設置螞蟻的種群數量為m，n表示為校園內配送地點的數量，每一只螞蟻隨機挑選n個校園內配送地點中的任一配送地點作為出發地。

（2）往復迭代。在每一次的路徑循環中，k只螞蟻根據每條配送路徑上的信息素量來判斷其接下來的移動方向。使用禁忌表的記錄形式來記錄當前k只螞蟻所遍歷過的校園內的配送地點。隨著螞蟻種群的不斷搜索，螞蟻種群會依照每條配送路徑上的信息素量跟當前配送路徑上滯留的啟發信息來求解當前狀態轉移概率。pt表示的是在t時刻，螞蟻k從校園內的配送地點i移動到下一階段所要前往的配送地點j的狀態轉移概率[17]：

P=????????????????????????????????? （3）

其中：allowed=C-tabuk=1，2，…，m用來代表螞蟻k下一階段所被允許挑選移動的配送地點。α是一種信息啟發式因子，代表著移動路徑的相對權重，體現了蟻群在其移動路徑上所積攢的信息對在蟻群轉移時所起到的作用。α通常取值為0，5。β是一種期望值啟發式因子，代表著路徑能見度的相對權重，體現了蟻群在其移動路徑上啟發信息為蟻群挑選下一階段路徑時所起到的作用。β通常取值范圍為0，5。

τt表示t時刻路徑i，j上信息素的強度，i表示為從校園內出發的配送地點，j表示為所要到達的下一個配送地點。

ηt表示啟發函數，通常取值為。d表示經過路徑i，j的距離。

（3）求解每只螞蟻遍歷過的所有校園內配送地點的路徑長度，設定螞蟻的數量為k，而配送路徑長度用L來表示，并保存當前的最短路徑。

（4）更新信息素。利用式（4）更新配送路徑上的信息素，其中，ρ表示移動路徑的持久性，即配送路徑上信息素的衰減度，1-ρ表示消失程度。經過n個時刻，螞蟻完成一次遍歷循環，各配送路徑上的信息素按照式（5）進行調整[18]。

τt+n=1-ρτt+Δτt+n?????????????????????????????????????? （4）

Δτt+n=Δτt+n?????????????????????????????????????????? （5）

其中：Δτt+n代表的是當前遍歷中路徑i，j上的信息素的增量，Δτt+n代表的是第k只螞蟻在當前遍歷中釋放在路徑i，j上的信息素，其計算方式如式（6）所示。

Δτt+n=????????????????????????????? （6）

（5）對螞蟻種群的迭代次數進行判斷看其是否滿足迭代終止條件，通常當螞蟻種群迭代次數達到最大即判定為終止條件，若滿足條件則跳轉到下面步驟（6），反之跳轉到上述步驟（2）。

（6）輸出當代最優路徑。

2.4? 算法改進

本文將傳統的遺傳算法與蟻群算法進行融合，將蟻群算法遍歷得到的尋優路徑結果當作遺傳算法的種群初始值，使得遺傳算法的尋優迭代次數大大降低，同時引入自適應交叉算子及變異算子對交叉、變異操作進行改進，使得遺傳算法的收斂速度得以大幅提高。與單一的遺傳算法和蟻群算法相比，改進后的算法從整體上提高了算法的執行效率。

本文在遺傳算法的基礎上，通過構建一個指標來對種群的收斂程度進行評價，選取f-作為種群收斂程度的指標。在遺傳算法中，若種群收斂程度趨于相同，則該算法可以收斂于全局最優解，也可以收斂于局部最優解，此時f-的值將減小，所以同時應該增加遺傳操作的交叉概率p和變異概率p，擴大種群范圍及多樣性，以便種群能夠不局限于局部最優的區域，并可以檢索其他的區域。

在任一代的種群中，任何一個個體其對應的p、p都是不同的，為了盡可能地保留較好的個體，此時p、p應該較小，差的個體應該盡可能地進行交叉變異而產生新的個體，此時的p、p應該足夠大。所以p、p的計算方法與f-以及每個個體的適應度值都有關。故提出下式計算方法：

p=kf-f/f-， k≤1??????????????????????????????????????? （7）

p=kf-f/f-， k≤1??????????? ????????????????????????????（8）

其中：為當代所有個體適應度值的平均值，f為要即將變異的當代個體的適應度值。

對于適應度值最大的個體，p、p的值應該為零，即最優的個體應該被保留下來，當個體的適應度值在種群平均適應度值以下的時候，根據上面的公式，p、p的值可能會大于1，所以需要進行如下處理：

p=???????????????????????????????????? （9）

p=???????????????????????????????????? （10）

其中：k，k，k，k≤1。

將改進后得到的自適應交叉算子和變異算子引入到蟻群算法與遺傳算法融合后的交叉及變異操作中，直至迭代結束。

改進后的自適應遺傳蟻群混合算法求解本文對象的計算流程如下：（1）配送地點信息及蟻群算法的參數初始化。（2）初始化螞蟻位置，將m只螞蟻隨機分配到n個配送地點中。（3）根據式（2）計算螞蟻k的當前狀態移動概率，挑選下一階段所要到達的配送地點。（4）將新加入移動路線的配送地點轉移到螞蟻k的禁忌表中，對禁忌表進行更新。（5）重復步驟（3）、（4），分別求出每一只螞蟻的一次遍歷路徑。（6）經步驟（1）到（5）處理獲得的m只螞蟻的所有遍歷路徑當作遺傳算法的初始種群，初始化遺傳算法參數。此時種群的大小popsize=m，根據自適應交叉算子與變異算子來決定交叉概率p及變異概率

p，以及最大迭代次數maxGEN的值。（7）對初始種群進行編碼，將蟻群算法得到的配送地點按照訪問順序依次排列組成編碼。（8）確定遺傳種群適應度函數，按照TSP理論重新計算種群中每個個體的適應度值fx。（9）選擇操作。根據式（8）計算得到的適應度值，按照適應度函數值的大小通過輪盤賭的方式挑選種群下一代的染色體。（10）執行交叉算子，采用前述自適應交叉算子，生成新的子代個體。（11）執行變異算子，利用自適應變異算子得到新的個體。（12）對遺傳算法進行終止條件判斷。如果i>maxGEN，則結束循環，對每次循環得到的最短路徑進行比較，得到算法的最終解即最優路徑。

3? 實驗結果分析

3.1? 實驗參數選擇

在本文中，對傳統的遺傳算法進行運行參數的選擇：種群規模popsize=300，交叉概率和變異概率分別取p=0.95和p

=0.33，最大迭代次數maxGEN=500;蟻群參數包括蟻群最大迭代代數iter_max=100，螞蟻種群個數m=30，信息素蒸發系數ρ

=0.8，軌跡的重要性α=1，能見度的重要性β=5，迭代計數器nC=1。

3.2? 遺傳算法與蟻群算法效果測試

根據以上針對遺傳算法與蟻群算法運行參數的設定，借助MATLAB軟件對校園內的外賣配送路線進行仿真實驗，通過對比傳統的遺傳算法與蟻群算法，得到的優化配送結果如圖4和圖5所示。圖4中橫縱坐標分別代表的是處于遺傳算法與蟻群算法中經處理變換后得到的校園內外賣配送地點的經緯度坐標。

圖5中橫坐標表示的是遺傳算法的種群代數以及蟻群算法的迭代次數，縱坐標表示的是兩種算法所搜索計算的校園內外賣配送路線的最短路徑長度。由圖5所見，蟻群算法的收斂性明顯快于遺傳算法，遺傳算法雖收斂速度慢，但搜尋到的外賣配送的最短路徑長度要優于蟻群算法。

3.3? 改進算法效果測試

經遺傳算法與蟻群算法融合改進后，引入自適應交叉算子及變異算子，能夠以較快的速度提高每一代種群的整體質量，算法的尋優性能得到了快速改善，出現最優解的代數明顯縮短。改進算法后得到的優化配送結果如圖6和圖7所示。迭代次數52，優化路徑長度223.60，最優配送路徑為：1-2-7-6-8-10-15-14-11-12-13-21-17-20-16-24-23-22-19-18-9-5-4-3-1。

利用本文的三種算法對校園內外賣配送路徑規劃問題數據進行仿真求解，得到的實驗對比結果如表2所示。

通過實驗對比結果發現，傳統的蟻群算法盡管收斂速度快，但是容易陷入局部最優，無法得到較好的全局優化結果，而傳統的遺傳算法雖然具有較好的全局尋優路徑長度，但收斂速度過慢，而改進后的自適應遺傳蟻群混合算法，算法的收斂速度明顯提高，大大降低了尋優路徑長度，在第52代就找到最優路徑長度223.60，因此，改進后的算法在搜索效率跟尋優能力上都能夠有較好的效果。

4? 總結與展望

本文基于改進的自適應遺傳蟻群混合算法來求解校園外賣配送類的TSP問題，有效地解決了校園內外賣配送的線路規劃問題，具有較好的應用價值。但本研究結果仍存在許多尚待改進的地方，比如交叉概率、變異概率以及種群規模大小的選取都會影響遺傳算法得出的路徑規劃結果，而且考慮校園內行人行走的不規范性、外賣配送車輛的行駛速度、配送車輛的裝載空間等因素也可以影響到路徑規劃的結果。此外求解TSP問題的相關算法還有很多，將遺傳算法和其他算法相互結合從而求解出更加優化的結果，是有待進一步研究的內容。

參考文獻：

[1] 秦正雨. 高校校園外賣第三方物流配送問題研究[J]. 商業故事，2016（26）：98-99.

[2] 程榮. 遺傳算法求解旅行商問題[J]. 科技風，2017，16（37）：40-51.

[3] 王荃菲. 快餐外賣配送路徑方案研究[D]. 北京：北京交通大學（碩士學位論文），2017.

[4] 馬江濤. 基于遺傳算法的醫藥配送路徑規劃[J]. 電腦知識與技術，2010，6（11）：2717-2718.

[5] 郭豐林. 基于遺傳算法的旅游線路規劃研究[J]. 現代營銷（經營版），2019（1）：134.

[6] 徐坤. 基于改進蟻群算法的小區快遞配送路徑規劃研究[D]. 烏魯木齊：新疆大學（碩士學位論文），2019.

[7] 馬駿. 遺傳算法TSP的matlab求解分析[J]. 科技視界，2018（16）：37-38.

[8] 趙鐵軍，羅羽梟. 基于改進自適應遺傳算法的點焊機器人TSP路徑規劃[J]. 機械工程師，2019（10）：7-9.

[9] 汪強. 基于模擬退火算法的超市物流配送路徑優化研究[J]. 集美大學航海學院，2019，27（3）：39-41.

[10] 熊沂鋮，王棟. 基于蟻群算法的車輛路徑問題研究[J]. 信息技術，2019，43（7）：15-17.

[11] 肖馳. 禁忌搜索求解TSP問題[J]. 福建電腦，2011（9）：110-111.

[12] 蔣冬梅. 粒子群算法在TSP中的應用及其LabVIEW實現[J]. 信息化研究，2018，44（4）：24-26.

[13] 劉飛. 遺傳算法實現過程詳解[J]. 福建電腦，2010，23（1）：37，49.

[14] 徐暢，張浩漩. 基于蟻群算法的TPS問題求解策略研究[J]. 科學咨詢（教育科研），2020（3）：34-35.

[15] 朱云飛，蔡自興，袁琦釗，等. 求解多目標旅行商問題的混合遺傳算法[J]. 計算機工程與應用，2011，44（7）：53-54.

[16] 李勇. 基于訂單數據的庫位優化研究[D]. 杭州：浙江工商大學（碩士學位論文），2015.

[17] 于瑩瑩，陳燕，李桃迎. 改進的蟻群遺傳算法求解旅行商問題[J]. 計算機仿真，2013，30（11）：317-320.

[18] 陶麗華，馬振楠，史朋濤，等. 基于TSP問題的動態蟻群遺傳算法[J]. 機械設計與制造，2019，37（12）：147-149.