吳鈞皓，戚遠(yuǎn)航，羅浩宇，鐘日雄，柯炳明，4

（1.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣東廣州 510006；2.電子科技大學(xué)中山學(xué)院計(jì)算機(jī)學(xué)院，廣東中山 528402；3.廣深鐵路股份有限公司廣州車(chē)輛段技術(shù)科，廣東廣州 510000；4.深圳大學(xué)物理與光電工程學(xué)院，廣東深圳 518060）

帶時(shí)間窗的車(chē)輛路徑問(wèn)題（Vehicle Routing Problems With Time Windows，VRPTW）是經(jīng)典的車(chē)輛路徑問(wèn)題，具體描述為：在滿(mǎn)足時(shí)間窗和載重量約束下，配送中心合理地安排車(chē)輛對(duì)客戶(hù)進(jìn)行服務(wù)，使得總路徑長(zhǎng)度最小[1]。VRPTW 是一個(gè)組合優(yōu)化問(wèn)題[2]，面對(duì)這類(lèi)問(wèn)題，精確算法[3]和智能算法[4]均能進(jìn)行求解。但面對(duì)大算例時(shí)，精確算法的運(yùn)行時(shí)間會(huì)非常長(zhǎng)，而智能算法卻常常能在合理的時(shí)間內(nèi)求解出較優(yōu)解[5]，因此成為了學(xué)者們的研究熱點(diǎn)[6-8]。

粒子群算法是求解組合優(yōu)化問(wèn)題的一種經(jīng)典智能算法[9-11]，但傳統(tǒng)的粒子更新規(guī)則容易使粒子群陷入局部最優(yōu)，難以求解復(fù)雜的組合優(yōu)化問(wèn)題[12]。為解決上述問(wèn)題，Liang 于2021 年提出了一種混合粒子群算法（Hybrid Particle Swarm Optimization，HPSO）[13]。HPSO 通過(guò)把種群劃分為精英子群和跟隨子群來(lái)平衡算法的局部搜索和全局搜索能力。然而，該算法無(wú)法直接對(duì)VRPTW 進(jìn)行求解，因此，該文基于HPSO 設(shè)計(jì)了一種有效的編解碼策略，并設(shè)計(jì)了相應(yīng)的局部搜索策略，通過(guò)實(shí)驗(yàn)證明了所提出算法的有效性。

1 VRPTW的數(shù)學(xué)模型

在無(wú)向圖G(V,E)中，定義V={v0,v1,…,vn}為圖的頂點(diǎn)集，E={(vi,vj):vi,vj∈V}為V中頂點(diǎn)構(gòu)成的弧集。設(shè)vo為配送中心，剩下的頂點(diǎn)為待服務(wù)客戶(hù)，n為客戶(hù)數(shù)量，同時(shí)定義在E上的加權(quán)C=(cij),cij表示從vi到vj的距離成本，單位為km[14]?，F(xiàn)設(shè)變量及參數(shù)如下：

M表示車(chē)輛數(shù)；m表示第m輛車(chē)；P表示車(chē)的容量限制，單位為kg；ui表示客戶(hù)vi的需求量，單位為kg；vi表示第i個(gè)客戶(hù)；tij表示車(chē)輛從vi到vj的行駛時(shí)間，單位為min；表示vi的可服務(wù)時(shí)間窗，單位為min；si表示在vi的服務(wù)時(shí)間，單位為min；ti表示到達(dá)vi的時(shí)間，單位為min；wi表示在vi等待的時(shí)間，單位為min；αijm={ }1,0 表示從vi到vj由第m輛車(chē)服務(wù)時(shí)為1，否則為0；βim={1,0}，vi由第m輛車(chē)服務(wù)時(shí)為1，否則為0。

該模型以車(chē)輛的總旅行距離最短為目標(biāo)，如式（1）所示:

同時(shí)，該模型需要滿(mǎn)足以下約束條件：

其中，式（2）和式（3）確保所有客戶(hù)必須有且只能被某一車(chē)輛訪問(wèn)一次；式（4）約束了車(chē)輛的最大載重量；式（5）表示從vi到vj的時(shí)間約束；式（6）表示客戶(hù)的時(shí)間窗約束。

2 求解算法

2.1 混合粒子群優(yōu)化算法

HPSO 把種群劃分為精英子群和跟隨子群，不同子群負(fù)責(zé)不同的搜索任務(wù)。同時(shí)，對(duì)于精英子群，設(shè)計(jì)一種交叉學(xué)習(xí)策略來(lái)增強(qiáng)全局搜索的能力；對(duì)于跟隨子群，引入隨機(jī)例子學(xué)習(xí)策略來(lái)提高算法的局部搜索能力。

2.1.1 子種群的劃分

精英子群和跟隨子群的劃分方法為：根據(jù)適應(yīng)度，從小到大進(jìn)行排序所有粒子，并根據(jù)預(yù)設(shè)的群體比率λγ來(lái)確定兩種子群的大小。

2.1.2 學(xué)習(xí)策略

1）基于交叉的綜合學(xué)習(xí)策略

針對(duì)精英種群，設(shè)計(jì)一種水平交叉算子，在兩個(gè)不同粒子的個(gè)體最優(yōu)位置之間進(jìn)行相同維度的交叉操作。同時(shí)，為了控制搜索空間的大小，設(shè)計(jì)一種垂直交叉算子，對(duì)同一個(gè)體最優(yōu)位置的不同維度進(jìn)行交叉操作，使停滯于局部最優(yōu)的粒子有機(jī)會(huì)跳出，如式（7）-（8）所示：

其中，xi=是粒子i的位置；hi=是粒子i的速度；D是xi和hi的最大維度；d、d1是xi和hi的任意維度，且d≠d1；pg代表全局最優(yōu)個(gè)體位置；pi代表粒子xi的個(gè)體最優(yōu)位置；pj代表粒子xj的個(gè)體最優(yōu)位置；w是慣性權(quán)值；c1和c2是加速度系數(shù)；c是在[-1,1]之間均勻分布的隨機(jī)值；r1、r2、γ1、λc為[0,1]之間的隨機(jī)值。

2）隨機(jī)粒子學(xué)習(xí)策略

根據(jù)適應(yīng)度排序所有粒子，假設(shè)粒子xi排在第i位，則前i-1 個(gè)粒子將成為粒子xi對(duì)應(yīng)的學(xué)習(xí)樣例{x1,…,xi-1}。接著，從學(xué)習(xí)樣例池{x1,…,xi-1}中隨機(jī)選擇一個(gè)較好粒子xk作為學(xué)習(xí)樣例，與該粒子xi進(jìn)行交叉運(yùn)算，生成一個(gè)速度矢量，如式（9）所示。最后，基于該速度矢量，引導(dǎo)較差粒子去挖掘較好粒子探索過(guò)的空間，得到一個(gè)新的粒子位置，如式（10）所示：

其中，xi=是粒子i的位置；hi=是粒子i的速度；D是xi和hi的最大維度；d是xi和hi的任一一個(gè)維度；k從樣例池{x1,…,xi-1} 中隨機(jī)選取的序號(hào)；pg代表最優(yōu)個(gè)體位置；pi代表粒子xi的個(gè)體最優(yōu)位置；pk是較好粒子xk的個(gè)體最優(yōu)位置；w是慣性權(quán)值；c1和c2為加速度系數(shù)；r1、r2、γ2、λm是在[0,1] 之間的隨機(jī)值。

2.2 編解碼策略

2.2.1 編碼策略

設(shè)計(jì)的粒子位置包含了客戶(hù)序列信息、路徑分段信息以及路徑數(shù)三部分。假定客戶(hù)數(shù)為n，總車(chē)輛數(shù)量為M，則粒子i位置xi=(xi,1,xi,2,…,xi,n+M)，xi,j∈[-100,100]，j=1,2,…,n+M，如圖1所示。

圖1 粒子i 位置編碼示意圖

2.2.2 解碼策略

解碼策略與編碼策略對(duì)應(yīng)，如圖2 的例子進(jìn)行闡述。在圖2中，n=10，M=3，最大車(chē)輛數(shù)Mmax=5，粒子的維度為10+3=13。

圖2 解碼例子示意圖

解碼策略分為以下四個(gè)步驟：

1）獲取客戶(hù)點(diǎn)的配送順序

xi,1,…,xi,n的維度分別代表客戶(hù)1 至客戶(hù)n的序號(hào)。將xi,1,…,xi,n的值按照從小到大排序，得到排序序列，對(duì)應(yīng)序號(hào)順序，得到客戶(hù)序列。

2）獲取車(chē)輛數(shù)

xi,n+M用于獲取車(chē)輛數(shù)，車(chē)輛數(shù)M由下式計(jì)算得出：

3）獲取每輛車(chē)的訪問(wèn)客戶(hù)數(shù)

當(dāng)M=1 時(shí)，表示只有一臺(tái)車(chē)輛負(fù)責(zé)訪問(wèn)所有客戶(hù)點(diǎn)，此時(shí)路徑也只有一條。當(dāng)M＞1 時(shí)，令M′=n-M，則每輛車(chē)訪問(wèn)的客戶(hù)數(shù)qτ（1 ≤τ≤M）可分兩種情況進(jìn)行計(jì)算：當(dāng)1 ≤τ≤M-1 時(shí)，qτ可表示為：

4）獲取具體路徑信息

根據(jù)上述步驟得到q1、q2、K、qτ四個(gè)值，從左到右來(lái)劃分客戶(hù)序列，得到客戶(hù)分段信息。由于所有的車(chē)輛都是從配送中心出發(fā)然后返回到配送中心，因此可以在每段客戶(hù)分段信息的首尾加上配送中心“0”，則可以得到具體路徑信息。

2.3 適應(yīng)度

因?yàn)閂RPTW 受到時(shí)間窗和載重量的約束，算法會(huì)得到不可行解。因此，適應(yīng)度將在式(1)中加入時(shí)間窗懲罰和容量懲罰[15]。

2.4 局部搜索策略

為進(jìn)一步增強(qiáng)局部搜索能力，HPSO 采用單點(diǎn)插入策略以及雙點(diǎn)交換策略。

1）單點(diǎn)插入策略：隨機(jī)選擇一個(gè)客戶(hù)a 插入到客戶(hù)點(diǎn)b 的前面，從而得到一個(gè)新的配送方案。如果新方案更優(yōu)，則替代舊方案。

2）雙點(diǎn)交換策略：隨機(jī)選擇兩個(gè)客戶(hù)c 和d，將這兩個(gè)客戶(hù)交換，從而得到一個(gè)新的配送方案。如果新方案更優(yōu)，則替代舊方案。

2.5 算法流程

求解VRPTW 問(wèn)題的HPSO 算法如下：

步驟一：初始化粒子種群，計(jì)算每個(gè)粒子的適應(yīng)度值FIT，初始化全局最優(yōu)解pg。

步驟二：將種群分為精英子群和跟隨子群。

步驟三：對(duì)精英子群中的粒子執(zhí)行基于交叉的綜合學(xué)習(xí)策略。

步驟四：對(duì)跟隨子群中的粒子執(zhí)行隨機(jī)例子學(xué)習(xí)策略。

步驟五：計(jì)算更新后每個(gè)粒子的適應(yīng)度值FIT，并更新全局最優(yōu)解pg。

步驟六：對(duì)全局最優(yōu)解pg執(zhí)行局部搜索策略。

步驟七：若滿(mǎn)足終止條件，則輸出全局最優(yōu)解，否則，跳轉(zhuǎn)至步驟二繼續(xù)執(zhí)行。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)算例與相關(guān)參數(shù)

實(shí)驗(yàn)數(shù)據(jù)集采用solomon-50 標(biāo)準(zhǔn)數(shù)據(jù)集中的C101 到C109 算例[16]。其中HPSO 算法的參數(shù)設(shè)置如下：種群數(shù)量100，迭代方式為連續(xù)100 代不更新則 停止，w=0.5，c1=2.0，c2=2.0，λγ=0.5，λc=0.5，λm=0.5。

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

HPSO 獨(dú)立求解C101 算例10 次后得到的最優(yōu)解如表1 所示，其中配送中心一共派出了5 臺(tái)車(chē)，即車(chē)輛數(shù)為5，路徑長(zhǎng)度為362.4 km。從表中可以看出，配送中心一共派出了5 臺(tái)車(chē)，而每個(gè)客戶(hù)有且只有被訪問(wèn)一次?！熬唧w配送信息”中每個(gè)客戶(hù)vi(ti,li,表示車(chē)輛到達(dá)客戶(hù)vi的時(shí)刻為ti，而客戶(hù)vi時(shí)間窗為，如車(chē)輛1 到達(dá)客戶(hù)20 的時(shí)刻為10 min，而其時(shí)間窗[10 min,73 min]；誤差的計(jì)算方式：當(dāng)前解與已知最優(yōu)解的差，再除以已知最優(yōu)解后，得到的結(jié)果的百分比。

表1中，HPSO求解C101得到最優(yōu)解為362.4 km，車(chē)輛數(shù)為5。其中，每個(gè)客戶(hù)有且只有被某一車(chē)輛訪問(wèn)一次，符合式（2）、式（3）的約束。而每臺(tái)車(chē)輛的實(shí)際載重量均小于或等于車(chē)輛的最大載重量200 kg，滿(mǎn)足式（4）的約束。其次，在配送的過(guò)程中，車(chē)輛均在客戶(hù)要求的時(shí)間窗前或者時(shí)間窗內(nèi)到達(dá)客戶(hù)點(diǎn)，符合式（5）和式（6）的約束條件。由此可見(jiàn)，HPSO 能夠有效地解決VRPTW。

表1 HPSO求解C101的最優(yōu)解具體信息

為了驗(yàn)證HPSO 的性能，該實(shí)驗(yàn)結(jié)合了傳統(tǒng)的PSO 以及提出的局部搜索策略，得到一個(gè)新的算法PSO-LS，并比較其與HPSO 和PSO-LS 對(duì)C101 到C109 算例分別求解10 次得到的結(jié)果，如表2 所示。

表2 HPSO和PSO-LS求解C101到C109算例的實(shí)驗(yàn)結(jié)果

從表2 可以看出，無(wú)論最優(yōu)解、平均解或者最差解，HPSO 都優(yōu)于PSO-LS。其 中，HPSO 在C101、C102、C105、C106 和C107 五個(gè)算例中可以找到已知最優(yōu)解。在C102，PSO-LS 求得的最優(yōu)解為499.9 km，最優(yōu)解的誤差為38.32%，而HPSO 的最優(yōu)解為362.4 km，誤差為0，比PSO-LS 降低了38.32%。由此可見(jiàn)，HPSO 的尋優(yōu)能力以及穩(wěn)定性均優(yōu)于PSOLS。此外，值得注意的是，當(dāng)兩種算法均以“連續(xù)100 代不更新”作為算法停止條件時(shí)，HPSO 的整體運(yùn)行時(shí)間均多于PSO-LS，這表明了HPSO 更容易跳出局部最優(yōu)而進(jìn)行更多更有效的解搜索。

4 結(jié)論

該文提出了一種HPSO 算法來(lái)解決VRPTW。該算法以HPSO 為框架，設(shè)計(jì)了一種面向VRPTW 的編解碼策略，同時(shí)提出了由單點(diǎn)插入策略以及雙點(diǎn)交換策略組成的局部搜索策略。最后，通過(guò)solomon-50標(biāo)準(zhǔn)數(shù)據(jù)集中的九個(gè)算例進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明了HPSO 的有效性和穩(wěn)定性。而HPSO 在C101、C102、C105、C106 和C107 均能找到已知最優(yōu)解，尋優(yōu)能力較強(qiáng)。