基于驢與走私者算法的物流配送車輛路徑優(yōu)化研究

王 迪 金 輝

(遼寧工業(yè)大學汽車與交通工程學院 遼寧 錦州 121001)

0 引 言

物流配送車輛路徑優(yōu)化作為物流運輸系統(tǒng)的核心問題[1]，也是提高物流配送效率和降低物流成本重要途徑，一直以來受到各方的重點研究[2]。物流配送車輛路徑問題主要是指物流車輛從配送中心出發(fā)，將貨物送到各個配送點最后返回配送中心，并且在滿足各種約束條件下形成的最優(yōu)車輛配送路線方案[3]。車輛路徑優(yōu)化問題(VRP)是廣泛存在于實際生活與工程中的經(jīng)典離散組合優(yōu)化問題，已被證明為NP-hard問題[4]，找不到一個多項式時間算法來精確地求解其最優(yōu)解[5]。因此利用智能優(yōu)化算法求解VRP問題，已經(jīng)成為該領域的研究熱點。常用的求解VRP問題的智能算法包括遺傳算法[6](GA)、蟻群算法[7](ACO)、粒子群算法[8](PSO)、模擬退火算法[9](SAA)、布谷鳥算法[10](CS)等。上面提到的群體智能算法都是受到各種動物和昆蟲的不同社會行為的啟發(fā)，以解決各種優(yōu)化問題。然而，沒有任何一種群體智能算法可以解決所有優(yōu)化問題。在上述提到的算法中，ACO非常受歡迎，它設計目的是為了解決組合優(yōu)化問題，主要通過搜索成本最低或距離最短來解決問題。但是，它有一些局限性，如理論分析不容易，概率的分布會隨著迭代次數(shù)的改變而改變，并且收斂的時間不確定。

因此，本文將采用一種新興的智能算法——驢與走私者算法[11]對VRP問題進行求解研究。驢與走私者算法是Shamsaldin等[11]在2019年提出的一種新型路徑查找的協(xié)作工作方法，并在理論上證明此算法可以用于求解旅行商問題(TSP)、數(shù)據(jù)包路徑(PR)和救護車路徑規(guī)劃問題(AR)等，且取得了不錯的效果。因此，本文將DSO算法運用到求解物流配送車輛路徑優(yōu)化中，具有實際的研究意義。

DSO算法是受到驢的搜索行為的啟發(fā)，通過在走私過程中模擬驢的運輸行為，從而建立兩種模式(非自適應和自適應)來實現(xiàn)算法中的搜索行為和路徑選擇。DSO算法是基于種群的算法，這里的種群是指在算法的自適應部分中使用的解決方案組。在其他基于種群的算法中，例如遺傳算法，是通過不斷在不同的解決方案中進行交叉和變異操作，從而獲取最佳解決方案。但是，在DSO算法中，由于走私者會探索所有解決方案并計算其適用值大小，因此無需進行此類處理。再將這些解決方案放入一個總體中，并從總體中確定最佳解決方案。在算法的自適應(驢)部分中，將繼續(xù)維持第一部分中求解的最佳方案，如果其適應性發(fā)生變化，那么將繼續(xù)評估種群并根據(jù)算法程序更新最佳解決方案。

1 基本車輛路徑優(yōu)化問題(VRP)

VRP可以描述為：有n多個需求點，各個需求點之間的距離已知，因此企業(yè)需要提前安排規(guī)劃，通過安排合理的配送路線，將貨物配送到每一個顧客的手中，然后再返回到出發(fā)點。在此過程中要保證配送過程中路徑距離最短或配送成本最低[12]。

模型假設：客戶點的數(shù)量為n，節(jié)點i與節(jié)點j之間的距離設為dij，則VRP問題的目標函數(shù)和約束條件分別為：

(1)

(2)

(3)

(4)

(5)

(6)

式(1)表示配送路徑距離最短；式(2)表示當xij=1時訪問節(jié)點i后訪問節(jié)點j，xij=0時則相反；式(3)表示每次配送過程中車輛都要從起點出發(fā)；式(4)表示配送車輛在完成配送任務后返回出發(fā)點；式(5)表示車輛在進行貨物配送過程中，所有的客戶點都會被服務到；式(6)表示在配送服務過程中，每個客戶點都會有一輛配送車輛進行服務，而且僅能被服務一次[13]。

2 驢與走私者算法

2.1 驢的社會行為

驢具有一系列的社會行為，在一定程度上可以將它們與其他動物區(qū)分開來，例如具有良好的記憶力和快速輕松學習的能力?！扼H保護區(qū)》[14]指出，驢的學習能力可以與狗或海豚一樣強。這些特征使驢成為多年來國內(nèi)和國際走私活動中的第一大走私動物。Diaz[15]指出，走私者使用馬、騾子和驢子開展走私業(yè)務，如圖1所示。

圖1 走私者利用驢進行汽油走私

正如Diaz[15]指出的那樣，走私者騎著馬，用驢或騾子裝載了他們想要走私的物品。他還強調(diào)，在熟悉的道路上，驢和騾子可以獨立地進行走私活動，而無需走私者的指導。在《阿拉伯新聞》[16]的一篇新聞中寫道，驢被用來在也門和沙特阿拉伯之間走私雜草，驢是經(jīng)過馴養(yǎng)者訓練的，它們在也門的村莊進行培訓，走私者在村莊里穿上沙特邊境警察的制服，并開始用石子來攻擊驢，從而使驢可以識別這些制服并避開這些制服，即驢會改變方向或一旦識別出這些制服便逃離。

而且，驢還具有較高的地域特征，它們通常單獨生活或兩個一組生活[14]。每當驢子感受到危險時，逃離并非總是生存的最佳選擇，它們的戰(zhàn)斗和防御行為將會被觸發(fā)，從而來保護自己。還有區(qū)別驢的另一種行為是自殺，Pubby[17]顯示，當驢遭受主人的殘酷和殘忍的虐待時會選擇自殺。

此外，驢子還表現(xiàn)出相互支持的行為。美國廣播公司新聞[14]顯示，如圖2所示，一頭驢試圖越過柵欄，但它無法跨越，因此它從另一頭驢那里得到了幫助，后者摘下一塊木頭來幫助驢群穿過柵欄。

圖2 驢群在同伴的幫助下跨越柵欄

總而言之，驢具有的社會行為可以總結為：

(1) 逃避過去能使它們痛苦的人或經(jīng)歷事件。

(2) 在它們感到危險時戰(zhàn)斗或防御機制將會被觸發(fā)。

(3) 當遇到困難或需要幫助時會互相支持。

(4) 當情況達到驢再也無法忍受的程度時將會自殺。

2.2 DSO算法

根據(jù)2.1節(jié)，驢的行為可以歸納為以下幾點：逃離、面對和支持、面對和自殺。

驢與走私者算法就是通過模擬驢和走私者的行為，利用“走私者”和“驢”的一些行為構造了一個由兩部分組成的算法，可以尋找到最佳解決方案并且能夠?qū)θ魏伟l(fā)生變化的情況作出反應以維持最佳解決方案。

2.2.1 非自適應(走私者)

“走私者”部分是DSO算法的非自適應部分，這表示此部分不適應任何更改。在這一部分中，走私者將檢查從源頭到目的地的所有可能路線，然后根據(jù)某些度量(例如時間、路線的安全性和狀況等)來決定要采取的最佳路線以及用此路線來進行驢的走私活動。

首先要確定每個解決方案的參數(shù)，然后再利用式(7)計算每個可能解的適用度值，并根據(jù)每個可能解的適應度值將所有可能解進行分組。最后選擇其中適應度最小的作為最佳的解決方案，并根據(jù)該解決方案來發(fā)送驢。

(7)

式中：xij是可能的解;i是可能解的數(shù)量;j表示的是與每個可能解的參數(shù)的數(shù)量成正比;z表示與每個可能解的參數(shù)的數(shù)量成反比。分子包含與比例成正比的參數(shù)，分母包含與比例成反比的參數(shù)。

2.2.2 自適應(驢)

在自適應(驢)部分中，決策基于當前網(wǎng)絡狀態(tài)，即拓撲和流量的測量或估計。如果流量和拓撲都發(fā)生變化，或者其中一種發(fā)生變化，則會作出反應以避免路徑丟失或避免延遲。此反應將基于驢的行為。

首先，使用走私者部分確定的最佳解決方案。其次根據(jù)適應性評估當前解決方案(在適應性發(fā)生變化的情況下，將繼續(xù)利用適應性函數(shù)以找到更好的解決方案)。接著判斷當前解決方案是否有擁塞現(xiàn)象，如果有則需要采取以下步驟：

(1) 逃離：重新評估可能的解決方案總體的適用性并更新最佳解決方案。此行為是將當前路徑更改為另一個最佳路徑(最佳解決方案)，即當在算法的非自適應部分中確定的最佳解決方案不再是最佳解決方案時，它將被丟棄，并根據(jù)新變化設置新的最佳解決方案。

(2) 面對和自殺：修復當前正在使用的最佳路徑(優(yōu)化最佳路徑)。同時，刪除當前路徑并使用另一種最佳解決方案，修復被阻止的可能解決方案，對可能的解決方案總體的適用性不必進行重新計算。

如果由于影響算法適應性的任何更改而在算法的第一部分中設置的最佳解決方案不再是最優(yōu)解決方案時，那么我們先保留該解決方案。然后將該解決方案放回其原來狀態(tài)，直到可以利用解決方案集中第二優(yōu)的解決方案為止。

最佳解決方案的適應度值是解決方案總數(shù)中最小的。因此，我們將所有可能的解決方案適應度值減去最佳解決方案的適應度值，將差異最小的可能解決方案視為新的最佳解決方案。通過式(8)，我們可以在其他解決方案中的第二優(yōu)的解決方案作為最佳解決方案。對于其他可能的解決方案總體的適合性不需要進行重新評估。

bestSuicid Solution=f(xi)-f(bestSolution)

(8)

式中：i是可能解決方案的數(shù)量。

(3) 面對和支持：當走私者設定的最佳解決方案中開始出現(xiàn)擁塞或超載的跡象時，我們可以通過在解決方案集中分配次優(yōu)解決方案來執(zhí)行相同的任務，從而避免丟棄該解決方案，直到擁塞或超載的跡象都消失。即我們可以使用兩個通道來減少擁塞或過載，而不是使用一個通道來發(fā)送和接收數(shù)據(jù)。

當最佳解決方案的路線出現(xiàn)過載時，利用第二優(yōu)的解決方案進行替代，直到原始的最佳解決方案恢復到正常狀態(tài)為止。其中不需要對可能的解決方案總體的適用性進行重新評估。

secondbestSolution=f(bestSolution)-f(xi)

(9)

bestSupport Solution=bestSolution+secondbestSolution

(10)

式(9)表示通過從最佳解決方案的適用度值中減去可能解決方案的適用度值來確定哪個解決方案將用作第二優(yōu)的解決方案。然后，通過式(10)將最佳解決方案與次優(yōu)解決方案結合起來，以生成使用兩條路徑來執(zhí)行同一項任務的最佳支持解決方案。

2.3 DSO算法流程

DSO算法的求解步驟如下：

第一部分：非自適應(走私者)。

(1) 確定每個解決方案的參數(shù)。

(2) 利用式(7)計算每個可能解的適應度值。

(3) 選擇最佳解決方案并用此方案發(fā)送驢。

第二部分：自適應(驢)。

(1) 使用第一部分選擇的最佳解決方案。

(2) 利用式(7)評估當前解決方案的適應度值，如果其適應值發(fā)生變化，則繼續(xù)利用適應度函數(shù)功能尋找最優(yōu)的解決方案。

(3) 判斷當前最優(yōu)解決方案是否有擁塞現(xiàn)象，如果存在，則需要執(zhí)行以下步驟之一：

① 逃離：利用式(7)重新評估可能解決方案的適應度值，選擇適應度值最低的可能解決方案作為最佳解決方案。

② 面對和自殺：利用式(8)可以在所有可能解中選擇第二優(yōu)的解決方案作為最佳方案。

③ 面對和支持：當最佳方案出現(xiàn)過載時，利用式(9)在可能方案集中選擇第二優(yōu)的解決方案來支持最佳解決方案。然后利用式(10)將最優(yōu)解決方案和次優(yōu)解決方案結合起來，生成使用兩條路徑執(zhí)行同一任務的最佳支持解決方案。

DSO算法的執(zhí)行流程如圖3所示。

圖3 算法的執(zhí)行流程圖

3 實例研究

3.1 問題描述

京東“211限時達”(俗稱“當日達”)，即當日上午11點前提交的現(xiàn)貨訂單(以訂單進入出庫狀態(tài)時間點開始計算)當日送達；夜晚11點前提交的現(xiàn)貨訂單第二天送達。京東開展此業(yè)務的目的是為了打通和擴展地區(qū)物流配送能力，提高物流配送效率，同時讓當?shù)叵M者能夠享受京東提供的優(yōu)質(zhì)電商體驗。對于遼西地區(qū)來說，京東的“211限時達”業(yè)務服務范圍已經(jīng)擴大到錦州、葫蘆島、盤錦、阜新、遼陽、赤峰、朝陽、凌海等縣市區(qū)。圖4為遼西主要城市地理位置圖，表1為各個城市之間的距離，其中序號1到8分別代表錦州、葫蘆島、盤錦、阜新、遼陽、赤峰、朝陽、凌海。

圖4 配送城市區(qū)域圖

為了保證貨物及時準確地送到各個城市點，京東送貨員在接到物流配送任務后，先要制定相應的配送計劃和合理的車輛行駛路線，然后按照制定好的行車路線進行配送。送貨員需要對其負責的遼西區(qū)域很熟悉，如果遇到異常情況，如交通堵塞或者限行，可及時調(diào)整行車路線[20]。

表1 各個城市點之間的距離 km

3.2 實例應用

利用DSO算法求解上述問題。對于DSO算法的第一次迭代，在算法的第一部分走私者檢查兩個城市之間的所有距離，并根據(jù)他的經(jīng)驗，確定從每個城市出發(fā)的最短路徑。每次迭代都重復此步驟，以確定從不同城市開始訪問其他所有城市的最短路徑。算法的第二部分中，在指出出發(fā)節(jié)點和要訪問所有城市點的最短路徑后，搜索并建議新的可能路徑，以防止第一部分確定的最短路徑不再可用。

算法的第一部分將每個城市點視為一次出發(fā)點，并執(zhí)行了所有迭代以找出所有可能路線及其距離以及要遵循的最短路徑。圖5為DSO算法第一部分(走私者)求得的最佳路線圖。

圖5 從每個出發(fā)點訪問其他客戶點的最短路徑

其中，第一部分執(zhí)行時間為0.059 395秒，下面列出了從各個出發(fā)點經(jīng)過的最短路線和其最短距離(單位：km)。

從城市1出發(fā)：1 4 5 2 7 3 8 6 1 距離：256

從城市2出發(fā)：2 5 4 1 6 8 3 7 2 距離：256

從城市3出發(fā)：3 8 6 1 4 5 2 7 3 距離：256

從城市4出發(fā)：4 1 2 5 6 8 3 7 4 距離：295

從城市5出發(fā)：5 2 1 4 8 6 7 3 5 距離：284

從城市6出發(fā)：6 1 4 5 2 7 3 8 6 距離：256

從城市7出發(fā)：7 3 8 6 1 4 5 2 7 距離：256

從城市8出發(fā)：8 6 1 4 5 2 7 3 8 距離：256

算法的第二部分是在第一部分中選擇的最短路徑不再可用的情況下，維護通往所有城市點的路線。這一部分中，確定出發(fā)節(jié)點并確定最短路徑后，該算法將掃描整個數(shù)據(jù)集，并計算出從該節(jié)點訪問集合中所有城市點的所有其他可能路徑及其距離，如圖6所示。

圖6 從節(jié)點1出發(fā)的所有可能路徑及距離

第二部分的執(zhí)行時間為0.025 490秒，下面列出了從城市點“1”出發(fā)的可能路線和其經(jīng)過的距離。

從城市1出發(fā)：1 2 5 4 8 6 7 3 1 距離：286

從城市1出發(fā)：1 3 8 6 2 5 4 7 1 距離：323

從城市1出發(fā)：1 4 5 2 6 8 3 7 1 距離：281

從城市1出發(fā)：1 5 2 6 8 3 7 4 1 距離：300

從城市1出發(fā)：1 6 2 5 4 8 3 7 1 距離：292

從城市1出發(fā)：1 7 2 5 4 8 6 3 1 距離：315

從城市1出發(fā)：1 8 6 2 5 4 3 7 1 距離：316

為了比較算法的性能，本文利用ACO算法獨立運行求解20次，運行結果如表2所示。

表2 ACO算法運行20次結果

3.3 結果分析

DSO算法的第一部分求解了從每個城市點出發(fā)的最佳路徑，從城市點1、2、3、6、7、8出發(fā)的最佳路徑的距離相同，都為256，因此我們可以在算法的第二部分中選擇點1、2、3、6、7、8作為出發(fā)點。在ACO算法運行20次的結果中，所有路線的最短距離相同，但是起始點卻不相同，在20次執(zhí)行結果中，起始點為1、3、6、8的點出現(xiàn)4次，起始點為2的出現(xiàn)3次，起始點為7的出現(xiàn)1次。

因此，我們可以在DSO算法的第二部分中，選擇城市點1、3、6、8作為起始點，DSO以其中一點為起始點計算出所有其他可能的路徑。如果選擇城市點1作為起始點，則其他可能路徑為：

從城市1出發(fā)：1 2 5 4 8 6 7 3 1 距離：286

從城市1出發(fā)：1 3 8 6 2 5 4 7 1 距離：323

從城市1出發(fā)：1 4 5 2 6 8 3 7 1 距離：281

從城市1出發(fā)：1 5 2 6 8 3 7 4 1 距離：300

從城市1出發(fā)：1 6 2 5 4 8 3 7 1 距離：292

從城市1出發(fā)：1 7 2 5 4 8 6 3 1 距離：315

從城市1出發(fā)：1 8 6 2 5 4 3 7 1 距離：316

如果選擇點3作為起始點，則其他可能路徑為：

從城市3出發(fā)：3 1 4 5 2 6 8 7 3 距離：269

從城市3出發(fā)：3 2 1 4 5 6 8 7 3 距離：280

從城市3出發(fā)：3 4 1 2 5 6 8 7 3 距離：288

從城市3出發(fā)：3 5 2 1 4 8 6 7 3 距離：284

從城市3出發(fā)：3 6 1 4 5 2 7 8 3 距離：284

從城市3出發(fā)：3 7 2 1 4 5 6 8 3 距離：263

從城市3出發(fā)：3 8 1 4 5 2 6 7 3 距離：278

DSO每執(zhí)行一次所需時間為0.084 885秒，而ACO每次運行的時間大概在0.110 0～0.190 0秒之間。同時，DSO算法在求出從每個城市點出發(fā)的最優(yōu)路徑后，算法的自適應部分提供了從該城市點出發(fā)的其他可供選擇的次優(yōu)路線解。而ACO算法只能得到從可能城市點出發(fā)的最優(yōu)路線，假如在其求解的最優(yōu)路線發(fā)生其他變化的情況下，其無法提供可供選擇的其他次優(yōu)路線解。因此從以上分析可以得出結論，與ACO算法相比，DSO可以在更短時間內(nèi)提供更多和穩(wěn)定的路線選項。

4 結 語

DSO具有用于實現(xiàn)搜索和選擇路徑的兩種模式——走私者(非自適應)和驢(自適應)。在走私者模式下，DSO能夠發(fā)現(xiàn)所有可能路徑和最短路徑，而在驢模式下，可利用驢的探索行為來尋找最佳路線以防止第一部分求出的最佳路徑不再適應。DSO算法是一種路徑協(xié)同優(yōu)化算法，在求解物流車輛配送路線問題上，與ACO算法相比，DSO算法能夠在更短時間內(nèi)提供更多的路徑選擇和更加穩(wěn)定的選項。