黃心++吳學(xué)群++袁清冽

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

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.

關(guān)鍵詞： 外賣；送貨；蟻群算法；路徑規(guī)劃；MATLAB

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

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

0 引言

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

1 蟻群算法

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

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

2 蟻群算法實現(xiàn)

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

4 結(jié)語

綜上所述，本文借鑒國內(nèi)外相關(guān)路徑優(yōu)化的思想和理念，結(jié)合國內(nèi)實際的配送的情況，將蟻群算法應(yīng)用于配送路徑中，為配送人員設(shè)計了一種提高工作效率且符合現(xiàn)實的路徑，體現(xiàn)了配送路徑規(guī)劃的智能化和人性化。

參考文獻：

[1]Colorni A，Dorigo M and Maniezo V. Distributed optimization by ant colonies[A]. Proc of lst European Conf. Artificial Life.Pans，F(xiàn)rance：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]李山，王慧，王崢，等.中國觀光旅游線路設(shè)計中的游時研究[J].人文地理，2005，20（2）：51-56.

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

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

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

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

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