基于群體智能算法的通勤車輛路徑優化問題*

劉 婷，王孫康宏，陳壯耿，魏麗軍

（廣東工業大學機電工程學院，廣州 510006）

0 引言

通勤服務企業或大型企業自身的通勤服務團隊為員工提供統一接送服務，通勤團隊首先設定多個乘車點，乘客可就近選擇上下車站點，每個站點會有前往多個目的地或廠區的乘客，通勤團隊需合理進行車輛、車型和運行路線規劃，保證把乘客送達目的地，在保障運營工作的同時實現運營企業全年運營成本最優。

大型企業為員工提供統一接送通勤服務相當于多目的地多車型車輛路徑規劃問題，是取送貨車輛路徑規劃問題（Pickup and Delivery Problem，PDP）的延伸，擴展了PDP 的應用場景。近年來，國內外學者針對不同的業務場景和用戶規模進行了大量的研究和實踐，提出了諸多策略，已取得顯著成果。王科峰等[1]從精確算法、并行算法、構造型啟發式算法和現代啟發式算法4 個方面對同時取送貨車輛路徑問題進行了詳細的評述。徐寧等[2]為提高大規模同時取送貨車輛路徑優化問題的求解效率和精度，基于先分解-再求解的解決思路，提出了兩階段混合算法RPCHVNS 求解該類問題。裴頌文等[3]在逆向物流的路徑規劃問題上展開了研究，針對逆向物流需求的不確定性提出了KMG 模型，該模型融合了帶權值的拓展性k-means++聚類算法和遺傳算法，有效解決了包含逆向物流的無人機調度問題。吳騰宇等[4]面向外賣的及時配送需求，將配送車輛返回原點取貨的約束融入在線旅行商問題中，基于固定取貨點的思想設計了TAIB算法和IGNORE算法對該問題進行求解。陳雪等[5]以最小化碳排放成本為優化目標，提出了一種學習型蟻群優化算法LACO，用于求解帶同時取送貨的綠色兩級車輛路徑問題，通過仿真實驗對比，驗證LACO 算法的有效性。包勝男等[6]基于同城速運背景，考慮訂單的時間窗要求構建VRPSPDTW 模型，采用改進的遺傳算法求解了車輛最優配送路徑。李博威等[7]基于軟時間窗和同時取送貨的雙重需求，同時考慮行駛里程、車輛數目、客戶滿意度等因素構建了MINLP 模型，采用理想點法對多目標優化問題進行簡化求解。李志濤等[8]采用基于硬時間窗約束對需要二次清運的回收車輛路徑問題進行研究，構建硬時間窗約束的VRP模型對問題進行求解。Belgin等[9]研究了同時取送貨的兩級車輛路徑問題，開發了一種基于可變領域下降和局部搜索的混合啟發式算法求解此問題，并有效解決了中大規模配送問題。Majidi 等[10]針對同時取送貨的車輛排污路徑問題，構建了一種非線性混合整數規劃模型，提出用自適應大鄰域搜索算法求解此問題，通過對比兩類基準實例驗證算法的有效性。Lagos等[11]考慮時間窗口約束，采用改進的粒子群優化算法求解了同時取送貨和時間窗的車輛路徑問題。Chentli 等[12]研究了固定數量同時取送貨的車輛路徑問題，提出用自適應大鄰域搜索算法求解最優行駛路線，構建了多個算例驗證算法有效性。Qiu 等[13]面向逆向物流中生產工藝路線問題，提出了一種分支定界引導搜索算法的求解方法，此算法在求解大規模算例時具有良好的性能。Zhao 等[14]對同時取送貨的選址與路徑問題展開了研究，提出了一種超啟發式算法框架對其進行優化求解，并開發了4 種選擇機制和5 種激活策略檢驗框架的性能。Ma 等[15]針對考慮帶時間窗和多決策者的同時取送貨的車輛路徑問題，設計了一種混合優先級遺傳算法對此問題進行求解，并通過多個不同規模的算例驗證算法的適用性。Afra 等[16]研究了考慮啟動成本和環保因素的取送貨的車輛路徑問題，采用了拉格朗日松弛算法求解此問題。Park 等[17]針對同時取送貨車輛路徑問題提出一種等待策略，并開發了一種遺傳算法解決大規模問題。

綜上所述，國內外學者們針對PDP 延伸問題的研究，主要集中在搭建問題求解模型和算法框架，并通過大量實例驗證算法的有效性，為本文研究的多目的地多車型車輛路徑規劃問題的求解提供了參考。本文考慮實際應用場景，以通勤服務企業運營成本最小為目標，依據實際約束搭建了相應的數學模型，并采用群體智能算法對問題進行優化處理，通過不同規模的算例驗證算法的有效性。

1 多目的地多車型車輛路徑規劃問題描述與數學模型

1.1 問題描述

對于運營服務企業而言，運營成本與車輛數量、車型、行駛路徑有關，因此需要通過計算獲取不同車型車輛數量和不同車輛的運行路線，使車輛數量盡可能少且總里程盡可能短，保障運營成本總能耗最小。

本文的假設條件如下：（1）通勤團隊設定多個乘車點，所有站點位置信息已知（包含車輛統一停靠區域、目的地、上下車站點）；（2）每個乘車點有前往多個目的地的乘客，且每個乘車點對應的不同目的地的乘客數量已知；（3）里程用歐氏距離表示；（4）只考慮單程，即車輛返回統一放置點的路程不考慮；（5）不同類型車輛的最大乘客承運量已知，車輛運營過程中不得超載；（6）不考慮運營車輛數不足和車輛需要充電、加油的情況；（7）車輛第2次空車后不允許再搭載乘客（第1次空車是出發時）。

多目的地多車型車輛路徑規劃問題的最終目標為找出一個路徑集合，對于每個路徑的每個站點需要安排多少車輛搭載多少數量的乘客、搭載去往什么目的地的乘客，并為每個路徑分配合適的車型，使得路徑集合的總能耗最低。

1.2 數學模型

多目的地多車型車輛路徑規劃問題的特點是每個站點的搭載乘客數是變量，搭載乘客的類型也是變量（以目的地區分乘客類型），問題的變量較多，比較復雜。基于多目的地多車型車輛路徑規劃問題與PDP 相似，利用求解PDP 的一些算法來對該問題進行啟發式求解。建立PD（Pickup and Delivery，PD）模型求解多目的地多車型車輛路徑規劃問題，下面是對PD模型的介紹。

設0 為車輛統一放置中心；T為車型數目；Qk為車型k的最大載客量；pj為第j個站點的乘客數量；ckij為第k種車型從站點i行駛至站點j的能耗（ckij=ck j）i；dij為站點i到站點j的歐氏距離；δk為第k種車型的單位能耗；yij為站點i到站點j的的乘客裝載量。此外，決策變量取值規則如下。

綜上，具體數學模型可表示如下。

其中，目標函數（2）表示最小化總能耗；約束（3）和（4）保證車輛到達目的地后乘客的下車；約束（5）表示乘客的移動，確保每個乘客都能被送往目的地；約束（6）確保車輛在行駛過程中搭載的乘客數量不超過其最大載客量；約束（7）表示如果沒有車輛從站點i行駛至站點j，則從站點i到站點j就沒有人員流動。

PD 模型支持一輛汽車在到達站點時搭載任意數量的乘客（小于等于車輛的最大乘客承運量即可），并且支持一條路徑內包含多目的地，有概率得到更好的解；缺點是解的搜索空間巨大，需要搜索很久才能夠得到較好的解。

2 群體智能算法求解PD模型

Kachitvichyanukul等[18]提出了兩種求解具有多取多送的廣義多車輛段車輛路徑問題（GVRP-MDMPDR）的求解方法，該方法可以與GLNPSO 結合使用，初步結果表明，他們所提出的方法能夠為大多數測試問題提供良好的解決方案。基于此，針對多目的地多車型車輛路徑規劃問題開發了一種基于S-N 鏈的解表示方法、解碼過程和評價規則，可以很好地結合群體智能算法框架對本問題進行求解。群體智能算法求解PD模型流程如圖1所示。

圖1 群體智能算法求解PD模型流程

2.1 基于S-N鏈的解表示方法

群體智能算法的核心是智能體，每一個智能體都有一定維度數的自變量數組，解的表示方法就是基于自變量數組的表示方法。

為表示解，本文給每個智能體定義了兩條自變量編碼鏈（S-N 鏈），一條用來控制站點訪問順序，稱之為S鏈，位于S鏈中的自變量定義域為[0，1]；另一條用來控制每個站點的接送人數，稱之為N 鏈，位于N 鏈的自變量的定義域為[0，pj+ 1），pj為第j個位置元素對應乘車點及對應目的地的乘客人數。假設只有3個乘客點和3個目的地，則基于S-N鏈的解表示方法如圖2所示。

2.2 解碼過程

解碼過程即根據S-N 鏈的信息，通過一定規則獲取一個可行路徑的過程，具體為以下7個步驟。

步驟1：按照S 鏈進行不減排序，然后將S 鏈替換為標號，并對N鏈進行向下取整；

步驟2：初始化人數記錄數組P，當前載客量N=0，歷史載質量N′ = 0，當前指針i=1，路徑記錄集合L={S}；

步驟3：如果當前指針超出編碼鏈長度或者當前載客量為0且歷史載質量不為0，則程序結束；如果當前指針所指元素的目的地已經在集合L中，則i=i+ 1，返回步驟3；如果上面條件都不符合則判斷指針所指的乘客點編號是否位于集合L中，如果位于集合L中，則轉步驟4，否則轉步驟5；

步驟4：判斷不等式pIi+N′≤Q是否成立，如果成立，則轉步驟6，否則轉步驟7；

步驟5：判斷不等式pIi+N≤Q是否成立，如果成立，則將當前指針對應乘客點編號加入集合L，轉步驟6，否則轉步驟7；

步驟6：按照當前指針對應目的地更新人數記錄數組PIi=PIi+pIi，更新當前載客量和歷史載質量N=N+pIi,N′=N′+pIi,i=i+ 1轉步驟3；

步驟7：設集合L的最后一個非目的地且乘客數非0的元素J，則選擇與乘客點J最接近的且不存在于集合L中的目的地M加入集合L，更新人數記錄數組和當前載客量PIi=PIi-pIi,N=N-pIi,?i∈目的地M，i=i+ 1轉步驟3。

假設此路徑車輛的最大載客量為15，基于所提S-N鏈的解碼過程如圖3所示。

圖3 解碼過程示意

2.3 評價規則

如圖3 所示，最終解碼得到的一條可行路徑為S→2→3→A→C→B，其中在乘車點2 上車人數為[0，1，0]，在乘車點3 上車人數為[7，0，5]，這條路徑的總載客量T=1+7+5=13。設L為該路徑總長度，設C為當前車型的百公里能耗，則該可行路徑的評價值可以由式（11）表示。

同樣的S 鏈和N 鏈，采用不同車型解碼得到的路徑都不一定相同，故在評價時，需要遍歷每一種車型解碼，獲得k個評價值Z和k條可行路徑，從中選取Z值最小的可行路徑作為最終解碼的結果返回。

2.4 群體智能算法

蜘蛛猴優化算法（Spider Monkey Optimization algorithm，SMO）是一種元啟發式算法，是Bansal 等[19]根據自然界中蜘蛛猴的智能覓食行為提出的一種新型群體智能算法。SMO 算法主要通過6 個階段實現優化問題的解決，具體如下。

（1）初始化階段：隨機在D維優化求解空間中生成一個由N個蜘蛛猴構成的均勻分布的初始種群，Esm,i為種群中的第i個蜘蛛猴，每個Esm,i進行初始化公式為：

式中：Esm,minj、Esm,maxj分別為搜索空間中第j維的下限和上限；U（0，1）為（0，1）中的隨機數。

（2）局部領導者階段：種群中的蜘蛛猴基于其局部領導者和小組成員的經驗對自己的位置進行更新，并在更新位置計算其適應度，若適應度值低于其原位置，則不更新，否則更新。蜘蛛猴位置更新的適應度公式為：

式中：Esm,ij為第i個蜘蛛猴的第j維變量；LL,kj為第k組局部領導者的第j維變量；Esm,rj為從第r組中隨機選擇的蜘蛛猴的第j維變量（r≠i）；U（-1，1）為（-1，1）中的隨機數。

（3）全局領導者階段：種群中的蜘蛛猴基于其全局領導者和局部小組成員的經驗對自己的位置進行更新，同時基于某一選擇概率進行位置的更新。第i個蜘蛛猴適應度值Fi可依據目標函數fi進行計算。

選擇概率Pi基于輪盤賭選擇確定，蜘蛛猴在全局領導者階段被選中的概率為：

則全局領導者階段蜘蛛猴位置更新方程為：

式中：GL,j為全局領導者在第j維上的位置。

（4）全局領導者學習階段：尋找群體中的最優解，被選中的蜘蛛猴代表群體的全局領導者。檢查全局領導者的位置，若位置更新，則將全局領導者的全局限制計數設置為0，否則增加1。

（5）局部領導者學習階段：依次對每組成員進行貪婪選擇，確定每組局部領導者的位置。檢查局部領導者的位置，若位置更新，則將局部領導者的局部限制計數設置為0，否則增加1。

（6）局部領導者決策階段：若局部限制計數達到了局部領導限制，即在初始迭代次數內局部領導者的位置未更新，則該組成員采用隨機初始化方式或式（16）重新進行位置更新。

（7）全局領導者決策階段：若全局限制計數達到了全局領導限制，即在初始迭代次數內全局領導者的位置未更新，則對群體重新進行分組。

群體中的蜘蛛猴通過以上步驟不斷更新位置，直至達到其最優位置和最優函數值時終止算法。SMO 算法的主要參數及其作用如表1所示。

表1 蜘蛛猴優化算法的主要參數與作用

3 實驗結果與分析

3.1 實驗環境

本文所有實驗均在配備Intel（R）Core（TM）i7-9750H 2.60 GHz 處理器和16 GB RAM 的筆記本計算機上進行。該PC 的操作系統為64 位Windows 10。代碼均以Java語言編寫。

3.2 SMO算法參數分析

由于最大探索次數、迭代次數、蜘蛛猴數量和局部搜索次數這4 個參數通常來說是越大越好的，故初步暫定它們的值分別為50、10、200和200。接下來，本文對剩余的LLDP_PR、LLP_PR和最大組數這3個參數進行實驗分析。

首先固定LLP_PR 為0.8，最大組數為10，對LLDP_PR 進行最佳取值搜索，結果如圖4所示。由圖可知，LLDP_PR的最佳取值搜索值為0.5。

圖4 LLDP_PR的取值結果

圖5 LLP_PR的取值結果

因此，固定LLDP_PR 為0.5，最大組數為10，然后對LLP_PR 進行最佳取值搜索，結果如圖5所示。由圖可知，LLP_PR的最佳取值搜索值為0.8。

同理，對最大組數進行最佳取值搜索，結果如圖6 所示。由圖可知，當最大組數為2 時，目標函數值較小，又由于最大組數對目標值的影響和迭代次數緊密相連，最終決定設置最大組數為迭代次數的1∕5，即最大組數為2。

圖6 最大組數的取值結果

3.3 結果與分析

本文測試數據來源于2022 年數字汽車大賽創新組賽題一，詳細數據可在大賽官網下載。本文對求解PD模型的不同方法分別進行了測試，并得到了不同求解時間下，不同算法得到的結果，結果如表2 所示。由于大部分方法屬于隨機算法，具有隨機性，本文取10 次實驗結果的平均值作為表3的數據來源。為驗證SMO算法的有效性，將其與粒子群優化算法（Particle Swarm Optimization，PSO）算法進行比較，并采用較大規模的算例進行測試。其中，PSO算法主要參數設定為：慣性權重ω=0.6、個體學習 因 子c1=0.5、社 會 學 習 因子c2=0.4。由 表2 可 得，SMO 算法的求解結果都比PSO 算法的求解結果好，說明SMO算法在求解該問題時具有更好的性能。

表2 比賽測試數據結果10-5m·kW·h

不同卡時不同算法求解結果如圖7 所示。由圖可知，當求解時間從60 s變為600 s時，求解結果的下降最為明顯，而后即使將時間增加至10 800 s，下降也沒有60～600 s 這一階段明顯，說明群體智能算法在600 s 左右時即可求得較優解。

圖7 不同卡時不同算法求解測試數據結果對比柱狀圖

圖8 車輛路徑可視化

當算法運行時間為10 800 s 時，SMO 算法求解PD 模型的結果如表3所示，車輛路徑可視化結果如圖8所示。

3.4 隨機測試數據結果與分析

為了進一步測試和驗證算法的可移植性，構造了17組不同站點數、不同目的地數的隨機測試案例，每個隨機案例的特征取值范圍依據3.3節比賽測試數據中對應特征的最大和最小值所確定。表4 所示為比賽測試數據的描述性信息，包括每個特征的平均值Avg、最小值Min、最大值Max、標準差Std。

為了更簡潔地表達隨機案例的屬性，將隨機案例命名為PX-Y，其中X為隨機案例中的站點數（包含目的地和車輛統一停靠區域），Y為目的地數。例如P60-2 表示一個擁有60 個站點和2個目的地的隨機案例。針對17 組隨機構造的測試案例，進行了卡時300 s 的測試，表5 所示為17 組隨機案例的測試結果。由表可知，300 s 內求解17 組隨機測試案例的最佳結果有14 組來自SMO 算法，說明SMO 算法在大部分案例中都可以在較短時間內求得較好解；也有3組最佳結果來自PSO 算法，3組案例都是較大規模和較多目的地的隨機案例，說明PSO 算法在一定時間內對大規模的多目的地多車型車輛路徑規劃問題可能有更好的求解效果。圖9 所示為卡時300 s 不同算法求解不同隨機案例的結果對比柱狀圖。

4 結束語

本文研究了多目的地和多車型的車輛路徑規劃問題，根據通勤車輛接送員工上下班實際運營情況，構建相應的數學模型對此過程進行完整刻畫。設計了一種基于SN 鏈的解表示方法以及對應的解碼過程和評價準則，采用蜘蛛猴優化算法對問題進行求解。通過對多組算例進行測試，驗證了所提數學模型和蜘蛛猴優化算法能夠有效解決多目的地和多車型的車輛路徑問題。

本文提出的PD 模型和SMO 算法在求解多目的地∕小規模問題時有更好的效果，在未來研究中，會進一步考慮求解少目的地∕大規模問題。其中，在問題模型上，對PD 模型進行簡化，減少決策變量和提升求解速度；在求解算法上，探索啟發式-精確兩階段算法此問題進行求解，從而提高算法的精確度。

表3 蜘蛛猴優化算法求解PD模型結果示例

表4 比賽測試數據的描述性統計結果

表5 17組隨機案列測試數據結果10-5m·kW·h

圖9 卡時300 s不同算法求解不同隨機案例的結果對比