基于蟻群算法的物流多任務分配中路徑規(guī)劃研究＊

金夢圓，王勇暢，劉敬琪

(西北工業(yè)大學計算機學院，陜西 西安 710129)

0 引言

自2013年以來，國家大力推進“一帶一路”發(fā)展理念，不斷加大電商業(yè)務發(fā)展的支持力度[1]，且隨著社會分工和服務的不斷精細化，“懶人經(jīng)濟”成為消費升級的衍生產(chǎn)物[2]。在電商與懶人經(jīng)濟的雙重推動作用下，我國快遞行業(yè)的業(yè)務量呈逐年上升的趨勢，從2013 年的1441.7 億元上升至2021 年的10332.3 億元[3]。2019～2021 年分別為7497.8 億元、8795.4 億元、10332.3 億元。同期全國GDP 數(shù)據(jù)分別為98.65 萬億、101.36 萬億、114.37 萬億。由此可以計算出快遞業(yè)務量分別占GDP 總量的0.76%、0.87%和0.90%，占比呈上升趨勢。可見快遞業(yè)務對于方便人們生活的重要性。因此，如何設計好上門收貨的最短路線問題對于快遞行業(yè)的發(fā)展、提升社會生產(chǎn)效率有著重要意義。

事實上，路徑優(yōu)化許多學者已經(jīng)做了大量的研究工作[4-9]，不過已有的工作未能考慮到多任務下可能出現(xiàn)在某一任務中存在孤立點的情況。孤立點的存在使得路徑的計算更加復雜，本文試圖借助其他任務中的收貨點使得路徑計算變得簡單一些。

1 問題描述

某公司有五位快遞員C1～C5負責上門收貨，有八個倉庫W1～W8用于臨時存放所收貨物，所收貨物位于200個收貨點R1～R200，倉庫及收貨點位置如圖1所示?，F(xiàn)在公司有20 個任務單A1～A20，每個任務單包括收貨點編號，快遞員先到某個倉庫領取任務單，然后到任務單上每件貨物對應收貨點收取貨物，收完該任務對應貨物后再到某個倉庫交回收取的貨物，待完成該任務后才能領取下一任務。

圖1 倉庫及收貨點位置

圖1 中紅色的圓圈代表倉庫，藍色的點代表收貨點，倉庫與倉庫之間、倉庫與收貨點之間、收貨點與收貨點之間的連線，表示兩點之間可以直接通達，否則表示不能直接通達。

為了解決上述問題，我們建立如下數(shù)學模型：

模型一若快遞員C1從倉庫W1領取任務單A1，完成任務A1后可回到任意一個倉庫交貨，建立模型求解最優(yōu)路線；

模型二若W1～W4四個倉庫可使用，快遞員C1需要完成任務A1～A4共四個任務，并自行確定每次領取任務的倉庫和交貨的倉庫，在模型一的基礎上求解最優(yōu)路線；

模型三若八個倉庫W1～W8都可使用，快遞員C1～C5共需要完成任務A1～A20共20 個任務，在模型二的基礎上求解最優(yōu)路線。

對于這三個模型，本文利用Floyd 算法計算兩點之間最優(yōu)距離，用蟻群算法求解任務路徑最優(yōu)解。

2 算法簡介

2.1 Floyd算法

Floyd 算法是在給定的加權圖中計算多個源點之間最短路徑[10]。本文利用Floyd算法進行數(shù)據(jù)預處理，求出模型一的任務單A1中的收貨點和m 個倉庫所有位置點中任一兩點之間的最短路徑，為后續(xù)利用蟻群算法求解任務最優(yōu)解決方案提供基礎。

文中使用Dis(i,j)表示收貨點i 到收貨點j 的最短路徑的距離。計算任意兩個收貨點i、（ji≠j）的之間的距離有以下兩種可能。

⑴直接計算兩個收貨點之間的歐幾里得距離。如果收貨點i 可以直接到達收貨點j，則可以利用兩點位置坐標關系進行計算；如果收貨點i 不能直接到達收貨點j，則可以定義Dis(i,j)=∞。

⑵間接計算。從收貨點i經(jīng)過若干個其他收貨點k（k≠i,j,k∈S，其中S為不包括收貨點i、j 的所有收貨點集合）到達收貨點j，此種情況，需要分別計算Dis(i,k)和Dis(k,j)，判斷

是否成立，如果不成立，證明收貨點i 直接到達收貨點j之間的距離為最優(yōu)距離；否則，令

表明從收貨點i 經(jīng)收貨點k 再到收貨點j 的路徑比從收貨點i直接到收貨點j的路徑更優(yōu)。每執(zhí)行一次式⑴的判斷，則將k從S中刪除，當S為空時，則Dis(i,j)的值便是收貨點i和收貨點j兩點之間的最優(yōu)距離。

通過Floyd 算法可算得模型一中任一兩收貨點之間和收貨點與倉庫之間存在的最短路徑，通過蟻群算法可得到遍歷所有收貨點的最短總距離。由于所有收貨點以及倉庫點之間有連線的距離為這兩點的歐幾里得距離，故可根據(jù)兩位置點的橫縱坐標表示兩點之間的距離：

2.2 蟻群算法

蟻群算法在求解旅行商問題、指派問題、調(diào)度問題、圖著色問題和網(wǎng)絡路由問題等方面獲得廣泛的應用。實踐證明,蟻群算法具有魯棒性強、收斂性好等特點，是解決上述問題的一種非常實用的優(yōu)化算法[11]。

蟻群算法模擬螞蟻在尋找食物源時，會在沿途釋放一種分泌物——信息素，同時能夠感知其他螞蟻在附近釋放的信息素。路徑的遠近可以通過信息素的濃度值來表示，信息素濃度越高，表示螞蟻離信息素源越近，即對應的路徑越短。通常，螞蟻會以較大的概率選擇信息素濃度較高的路徑，同時，為了使其他螞蟻也最大可能選擇同樣的路徑，該螞蟻會釋放一定量的信息素以增強該路徑上的信息素濃度。另外，信息素濃度也會隨著時間的流逝而逐漸減少。

不失一般性，設整個螞蟻群體中螞蟻的數(shù)量為m，收貨點的數(shù)量為n，收貨點i 與收貨點j 之間的距離Dis(i,j)（i,j=1,2,3,…,n），t時刻，用τij(t)來表示收貨點i與收貨點j 之間的信息素濃度。任務開始時刻，假設各個收貨點（包括倉庫點）間連接路徑上的信息素濃度相同，設τij(0)=τ0。

t 時刻，螞蟻（即快遞員）k（k=1,2,…,m）選擇下一個收貨點，是根據(jù)該時刻路徑上的信息素濃度來決定的，設(t)表示t 時刻螞蟻k 從收貨點i 轉(zhuǎn)移到收貨點j的概率[12]，其計算公式為：

其中，ηij(t)為啟發(fā)函數(shù)，（其中Dij根據(jù)式⑶計算）表示螞蟻從收貨點i轉(zhuǎn)移到收貨點j的期望程度；allowk（k=1,2,…,n）為螞蟻k待訪問收貨點的集合，開始時，allowk中有(n-1)個元素，即包括除了螞蟻k出發(fā)站點的其他所有站點，隨著任務進度的推進，allowk中的收貨點不斷減少。當所有收貨點均訪問完畢時，allowk為空；α為信息素重要程度因子，其值越大，表示信息素的濃度在轉(zhuǎn)移中起的作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即螞蟻會以較大的概率轉(zhuǎn)移到距離短的收貨點。

由蟻群算法思想可知，在螞蟻釋放信息素的同時，各個收貨點間連接路徑上的信息素也在逐漸消失，設參數(shù)ρ(0＜ρ＜1) 表示信息素的揮發(fā)程度。因此，當所有螞蟻完成一次循環(huán)后，各個收貨點間連接路徑上的信息素濃度需進行實時更新。

其中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量，Lk為第k個快遞員經(jīng)過路徑的長度。

3 實驗數(shù)據(jù)

針對前述模型一，取任務單號A1作為研究對象，其中的貨物收取點和所有倉庫的位置關系如圖2所示。圖2 中的連線表示收貨點與收貨點、收貨點與倉庫之間可以直接通達。

圖2 任務單號1收貨點及倉庫位置圖

由圖2可以看出，在任務A1存在許多孤立點，這是和其他學者研究的不同之處。由圖1 可以看出，這些孤立點可以借助該任務之外其他收貨點間接到達任務A1中的其他收貨點。所求得路徑和路徑長度如表1所示。

針對模型二，在模型一的基礎上進一步對模型二進行求解。由于模型二中的出發(fā)點和終止點在本研究中未做要求，故在模型一的基礎上結合動態(tài)規(guī)劃進行一定的修改，可求得執(zhí)行第i 個任務（i=1,2,3,4）的最短路徑。

模型二中的任務單號、任務單對應的收貨點編號、路徑和路徑長度如表1 所示。表1 中路徑中涉及到其他收貨點，是由于存在收貨點之間不能直接到達，借助于其他收貨點間接到達。模型二中快遞員C1接到4 個任務單，按照A4-A3-A2-A1順序執(zhí)行收貨任務，可以縮短所走路徑。

表1 實驗數(shù)據(jù)

針對模型三，在模型二的基礎上拓展至八個倉庫可用，且需要五個快遞員同時完成20個任務。對模型二進一步分析可知，快遞員C1分配得到任務A1～A4即可得出領取任務的倉庫點和交接貨物的倉庫點，以及執(zhí)行任務的先后順序，從而得出遍歷所有收貨點的路線圖。其他快遞員領取到對應的任務單后，以同樣方法根據(jù)模型二進行處理，可以得出每個快遞員的任務執(zhí)行順序和路線。

因篇幅所限，本文只給出了模型一、模型二中的實驗數(shù)據(jù)，模型三數(shù)據(jù)與模型二類似。

4 結束語

實驗數(shù)據(jù)表明，結合Floyd 算法和蟻群算法，可以快速有效地解決在多任務分配情況下的路徑選擇問題，為快遞員提供最優(yōu)的路徑選擇決策方案。此方法同樣可以應用于機器人配送、無人機配送中路徑選擇決策場景中。