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

（廣東工業(yè)大學(xué)機電工程學(xué)院，廣州 510006）

0 引言

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

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

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

1 多目的地多車型車輛路徑規(guī)劃問題描述與數(shù)學(xué)模型

1.1 問題描述

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

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

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

1.2 數(shù)學(xué)模型

多目的地多車型車輛路徑規(guī)劃問題的特點是每個站點的搭載乘客數(shù)是變量，搭載乘客的類型也是變量（以目的地區(qū)分乘客類型），問題的變量較多，比較復(fù)雜?；诙嗄康牡囟嘬囆蛙囕v路徑規(guī)劃問題與PDP 相似，利用求解PDP 的一些算法來對該問題進行啟發(fā)式求解。建立PD（Pickup and Delivery，PD）模型求解多目的地多車型車輛路徑規(guī)劃問題，下面是對PD模型的介紹。

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

綜上，具體數(shù)學(xué)模型可表示如下。

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

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

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

Kachitvichyanukul等[18]提出了兩種求解具有多取多送的廣義多車輛段車輛路徑問題（GVRP-MDMPDR）的求解方法，該方法可以與GLNPSO 結(jié)合使用，初步結(jié)果表明，他們所提出的方法能夠為大多數(shù)測試問題提供良好的解決方案?；诖耍槍Χ嗄康牡囟嘬囆蛙囕v路徑規(guī)劃問題開發(fā)了一種基于S-N 鏈的解表示方法、解碼過程和評價規(guī)則，可以很好地結(jié)合群體智能算法框架對本問題進行求解。群體智能算法求解PD模型流程如圖1所示。

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

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

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

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

2.2 解碼過程

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

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

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

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

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

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

步驟6：按照當前指針對應(yīng)目的地更新人數(shù)記錄數(shù)組PIi=PIi+pIi，更新當前載客量和歷史載質(zhì)量N=N+pIi,N′=N′+pIi,i=i+ 1轉(zhuǎn)步驟3；

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

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

圖3 解碼過程示意

2.3 評價規(guī)則

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

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

2.4 群體智能算法

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

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

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

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

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

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

選擇概率Pi基于輪盤賭選擇確定，蜘蛛猴在全局領(lǐng)導(dǎo)者階段被選中的概率為：

則全局領(lǐng)導(dǎo)者階段蜘蛛猴位置更新方程為：

式中：GL,j為全局領(lǐng)導(dǎo)者在第j維上的位置。

（4）全局領(lǐng)導(dǎo)者學(xué)習(xí)階段：尋找群體中的最優(yōu)解，被選中的蜘蛛猴代表群體的全局領(lǐng)導(dǎo)者。檢查全局領(lǐng)導(dǎo)者的位置，若位置更新，則將全局領(lǐng)導(dǎo)者的全局限制計數(shù)設(shè)置為0，否則增加1。

（5）局部領(lǐng)導(dǎo)者學(xué)習(xí)階段：依次對每組成員進行貪婪選擇，確定每組局部領(lǐng)導(dǎo)者的位置。檢查局部領(lǐng)導(dǎo)者的位置，若位置更新，則將局部領(lǐng)導(dǎo)者的局部限制計數(shù)設(shè)置為0，否則增加1。

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

（7）全局領(lǐng)導(dǎo)者決策階段：若全局限制計數(shù)達到了全局領(lǐng)導(dǎo)限制，即在初始迭代次數(shù)內(nèi)全局領(lǐng)導(dǎo)者的位置未更新，則對群體重新進行分組。

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

表1 蜘蛛猴優(yōu)化算法的主要參數(shù)與作用

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

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

3.2 SMO算法參數(shù)分析

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

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

圖4 LLDP_PR的取值結(jié)果

圖5 LLP_PR的取值結(jié)果

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

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

圖6 最大組數(shù)的取值結(jié)果

3.3 結(jié)果與分析

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

表2 比賽測試數(shù)據(jù)結(jié)果10-5m·kW·h

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

圖7 不同卡時不同算法求解測試數(shù)據(jù)結(jié)果對比柱狀圖

圖8 車輛路徑可視化

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

3.4 隨機測試數(shù)據(jù)結(jié)果與分析

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

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

4 結(jié)束語

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

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

表3 蜘蛛猴優(yōu)化算法求解PD模型結(jié)果示例

表4 比賽測試數(shù)據(jù)的描述性統(tǒng)計結(jié)果

表5 17組隨機案列測試數(shù)據(jù)結(jié)果10-5m·kW·h

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