金夢(mèng)圓，王勇暢，劉敬琪

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710129)

0 引言

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

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

1 問(wèn)題描述

某公司有五位快遞員C1～C5負(fù)責(zé)上門收貨，有八個(gè)倉(cāng)庫(kù)W1～W8用于臨時(shí)存放所收貨物，所收貨物位于200個(gè)收貨點(diǎn)R1～R200，倉(cāng)庫(kù)及收貨點(diǎn)位置如圖1所示?，F(xiàn)在公司有20 個(gè)任務(wù)單A1～A20，每個(gè)任務(wù)單包括收貨點(diǎn)編號(hào)，快遞員先到某個(gè)倉(cāng)庫(kù)領(lǐng)取任務(wù)單，然后到任務(wù)單上每件貨物對(duì)應(yīng)收貨點(diǎn)收取貨物，收完該任務(wù)對(duì)應(yīng)貨物后再到某個(gè)倉(cāng)庫(kù)交回收取的貨物，待完成該任務(wù)后才能領(lǐng)取下一任務(wù)。

圖1 倉(cāng)庫(kù)及收貨點(diǎn)位置

圖1 中紅色的圓圈代表倉(cāng)庫(kù)，藍(lán)色的點(diǎn)代表收貨點(diǎn)，倉(cāng)庫(kù)與倉(cāng)庫(kù)之間、倉(cāng)庫(kù)與收貨點(diǎn)之間、收貨點(diǎn)與收貨點(diǎn)之間的連線，表示兩點(diǎn)之間可以直接通達(dá)，否則表示不能直接通達(dá)。

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

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

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

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

對(duì)于這三個(gè)模型，本文利用Floyd 算法計(jì)算兩點(diǎn)之間最優(yōu)距離，用蟻群算法求解任務(wù)路徑最優(yōu)解。

2 算法簡(jiǎn)介

2.1 Floyd算法

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

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

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

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

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

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

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

2.2 蟻群算法

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

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

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

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

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

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

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

3 實(shí)驗(yàn)數(shù)據(jù)

針對(duì)前述模型一，取任務(wù)單號(hào)A1作為研究對(duì)象，其中的貨物收取點(diǎn)和所有倉(cāng)庫(kù)的位置關(guān)系如圖2所示。圖2 中的連線表示收貨點(diǎn)與收貨點(diǎn)、收貨點(diǎn)與倉(cāng)庫(kù)之間可以直接通達(dá)。

圖2 任務(wù)單號(hào)1收貨點(diǎn)及倉(cāng)庫(kù)位置圖

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)

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

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

4 結(jié)束語(yǔ)

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