蟻群算法在外賣配送路徑規劃中的應用

黃心++吳學群++袁清冽

摘要： 隨著我國經濟的快速發展，生活節奏的提高，外賣成為了年輕人生活的一部分，而快速有效的送貨速度成為了幾個外賣公司的競爭重點之一。外賣送貨人員如何能夠在有限的時間對外賣進行分配節約勞動成本根據的是送貨人員的經驗。本文通過蟻群算法對不同地址的收貨點進行路徑進行規劃，并利用MATLAB軟件，為送貨人員設計出了最短時間路徑規劃。

Abstract： With the rapid development of China's economy and the improvement of the pace of life， takeaway became a part of young people's lives. Fast and effective delivery speed has become one of the competitive priorities of several takeaway companies. How do the delivery personnel distribute the takeaways in a limited time to sell the labor cost is based on the experience of delivery personnel. In this paper， ant colony algorithm is used to carry out the path planning for different address receiving points， and the shortest path planning is designed for the delivery personnel by using MATLAB software.

關鍵詞： 外賣；送貨；蟻群算法；路徑規劃；MATLAB

Key words： takeaway；deliver goods；ant colony algorithm；path planning；MATLAB

中圖分類號：U116.2 文獻標識碼：A 文章編號：1006-4311（2017）05-0065-03

0 引言

近年來，外賣行業日趨火爆，百度外賣、餓了么、美團、大眾等幾大公司的競爭日趨激烈。外賣O2O的發展與消費者的快速收到外賣心態的矛盾越發明顯。“網站+送餐”的模式分為輕模式和重模式，區別在于配送團隊是第三方配送還是自建配送團隊。無論是輕模式還是重模式，配送團隊的重要性不言而喻。配送團隊的工作效率，服務的態度是各個公司考慮的幾個關鍵問題之一。與之相應，配送人員的工資也與配送單數有關，如何提高配送人員的工作效率，提高服務水平是目前較為熱點的問題。從商店出發到各個地址進行配送，再回到商店可以看作是一個經典NP難問題。關于此類的解決方法有很多種：蟻群算法、多尺度路徑算法、模擬退火法、粒子群算法等。考慮到蟻群算法的并行性、魯棒性且可以很早避免早熟收斂等問題。本文通過蟻群算法對外賣人員配送路徑進行規劃，并取得了較好的結果。

1 蟻群算法

人工蟻群算法（Ant Colony Algorithm）簡稱蟻群算法，由意大利學者Dorigo M提出。該算法通過模擬螞蟻覓食行為而設計[1]。1990 Deneubourg J.L等自發進行蟻群覓食的研究行動。通過實驗最后得出蟻群覓食的路徑選擇和信息素濃度有關系，通過對信息素濃度的感知而選擇路徑，一般情況下螞蟻會趨向于信息素高的地方移動。實驗表明，路徑越短的路徑，信息素濃度越高，因而這條路徑會逐漸逼近最優最短路徑[2]。

圖1是螞蟻覓食圖，如圖1（a）所示，螞蟻從巢穴出發尋找食物，有左右兩條路徑，從左右兩條路徑出發的螞蟻數量相同。在某個時刻，當往右邊路徑出發尋找食物的螞蟻尋找到食物時，左邊路徑上的螞蟻還未尋找到食物，如圖1（b）。當左邊路徑上的螞蟻尋找到食物時，右邊路徑上的螞蟻已經在返回巢穴的路上，如圖1（c）。我們可以推斷，在某個N個時間段后，右邊路徑上的信息素濃度比左邊路徑上的信息素濃度高，此時從巢穴出來的螞蟻會更趨向于右邊路徑。

2 蟻群算法實現

初始時刻，各條路徑上的信息素濃度相同，設tij（0）=C（C為常數）。螞蟻k（k=1，2，3，…，m）在運動過程中根據各條路徑上的信息素濃度決定方向。螞蟻系統所使用的狀態轉移規則被稱為隨機比例規則，它給出了位于位置i的螞蟻k轉移到位置j的概率。在t時刻，螞蟻k在位置i選擇位置j的轉移概率如公式（1）：

4 結語

綜上所述，本文借鑒國內外相關路徑優化的思想和理念，結合國內實際的配送的情況，將蟻群算法應用于配送路徑中，為配送人員設計了一種提高工作效率且符合現實的路徑，體現了配送路徑規劃的智能化和人性化。

參考文獻：

[1]Colorni A，Dorigo M and Maniezo V. Distributed optimization by ant colonies[A]. Proc of lst European Conf. Artificial Life.Pans，France：Elsevier，1991，134-142.

[2]Deneubourg J.L.，Aron S.，Goss S.，and Pasteels J.M.The self-organizing exploratory pattern of the argentine ant [J]，Journal of Insect Behavior，1990，3：159-168.

[3]李山，王慧，王崢，等.中國觀光旅游線路設計中的游時研究[J].人文地理，2005，20（2）：51-56.

[4]肇勇.改進蟻群算法的理論及方法研究[D].西南石油學院，2004.

[5]龔延成，郭曉汾，尤曉鈴，等.基于遺傳算法的物流配送車輛調度間題研究[J].數學的實踐與認識，2004，34（6）：93-97.

[6]Dantzig G，Ramser J，The trunk dispatching problem [J]. Management Science，1959（6）：80-91.

[7]吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學報，2001，24（12）：1328-1333.

[8]張紀會，徐心和.一種新的進化算法-蟻群算法[J].系統工程理論與實踐，1999（3）：84-87.