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

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

0 引言

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 解碼過程

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

步驟1：按照S 鏈進(jìn)行不減排序，然后將S 鏈替換為標(biāo)號，并對N鏈進(jìn)行向下取整；

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

步驟3：如果當(dāng)前指針超出編碼鏈長度或者當(dāng)前載客量為0且歷史載質(zhì)量不為0，則程序結(jié)束；如果當(dāng)前指針?biāo)冈氐哪康牡匾呀?jīng)在集合L中，則i=i+ 1，返回步驟3；如果上面條件都不符合則判斷指針?biāo)傅某丝忘c(diǎn)編號是否位于集合L中，如果位于集合L中，則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟5；

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

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

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

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

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

圖3 解碼過程示意

2.3 評價(jià)規(guī)則

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

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

2.4 群體智能算法

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

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

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

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

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

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

選擇概率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)者的全局限制計(jì)數(shù)設(shè)置為0，否則增加1。

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

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

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

3.3 結(jié)果與分析

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

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

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

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

圖8 車輛路徑可視化

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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