蟻群算法在外賣配送路徑規(guī)劃中的應(yīng)用

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2017）05-0065-03

0 引言

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

1 蟻群算法

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]李山，王慧，王崢，等.中國(guó)觀光旅游線路設(shè)計(jì)中的游時(shí)研究[J].人文地理，2005，20（2）：51-56.

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

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

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

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

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