帶時間窗的車輛路徑問題的混合粒子群優化算法

吳鈞皓，戚遠航，羅浩宇，鐘日雄，柯炳明，4

（1.廣東工業大學自動化學院，廣東廣州 510006；2.電子科技大學中山學院計算機學院，廣東中山 528402；3.廣深鐵路股份有限公司廣州車輛段技術科，廣東廣州 510000；4.深圳大學物理與光電工程學院，廣東深圳 518060）

帶時間窗的車輛路徑問題（Vehicle Routing Problems With Time Windows，VRPTW）是經典的車輛路徑問題，具體描述為：在滿足時間窗和載重量約束下，配送中心合理地安排車輛對客戶進行服務，使得總路徑長度最小[1]。VRPTW 是一個組合優化問題[2]，面對這類問題，精確算法[3]和智能算法[4]均能進行求解。但面對大算例時，精確算法的運行時間會非常長，而智能算法卻常常能在合理的時間內求解出較優解[5]，因此成為了學者們的研究熱點[6-8]。

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

1 VRPTW的數學模型

在無向圖G(V,E)中，定義V={v0,v1,…,vn}為圖的頂點集，E={(vi,vj):vi,vj∈V}為V中頂點構成的弧集。設vo為配送中心，剩下的頂點為待服務客戶，n為客戶數量，同時定義在E上的加權C=(cij),cij表示從vi到vj的距離成本，單位為km[14]。現設變量及參數如下：

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

該模型以車輛的總旅行距離最短為目標，如式（1）所示:

同時，該模型需要滿足以下約束條件：

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

2 求解算法

2.1 混合粒子群優化算法

HPSO 把種群劃分為精英子群和跟隨子群，不同子群負責不同的搜索任務。同時，對于精英子群，設計一種交叉學習策略來增強全局搜索的能力；對于跟隨子群，引入隨機例子學習策略來提高算法的局部搜索能力。

2.1.1 子種群的劃分

精英子群和跟隨子群的劃分方法為：根據適應度，從小到大進行排序所有粒子，并根據預設的群體比率λγ來確定兩種子群的大小。

2.1.2 學習策略

1）基于交叉的綜合學習策略

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

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

2）隨機粒子學習策略

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

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

2.2 編解碼策略

2.2.1 編碼策略

設計的粒子位置包含了客戶序列信息、路徑分段信息以及路徑數三部分。假定客戶數為n，總車輛數量為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 解碼策略

解碼策略與編碼策略對應，如圖2 的例子進行闡述。在圖2中，n=10，M=3，最大車輛數Mmax=5，粒子的維度為10+3=13。

圖2 解碼例子示意圖

解碼策略分為以下四個步驟：

1）獲取客戶點的配送順序

xi,1,…,xi,n的維度分別代表客戶1 至客戶n的序號。將xi,1,…,xi,n的值按照從小到大排序，得到排序序列，對應序號順序，得到客戶序列。

2）獲取車輛數

xi,n+M用于獲取車輛數，車輛數M由下式計算得出：

3）獲取每輛車的訪問客戶數

當M=1 時，表示只有一臺車輛負責訪問所有客戶點，此時路徑也只有一條。當M＞1 時，令M′=n-M，則每輛車訪問的客戶數qτ（1 ≤τ≤M）可分兩種情況進行計算：當1 ≤τ≤M-1 時，qτ可表示為：

4）獲取具體路徑信息

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

2.3 適應度

因為VRPTW 受到時間窗和載重量的約束，算法會得到不可行解。因此，適應度將在式(1)中加入時間窗懲罰和容量懲罰[15]。

2.4 局部搜索策略

為進一步增強局部搜索能力，HPSO 采用單點插入策略以及雙點交換策略。

1）單點插入策略：隨機選擇一個客戶a 插入到客戶點b 的前面，從而得到一個新的配送方案。如果新方案更優，則替代舊方案。

2）雙點交換策略：隨機選擇兩個客戶c 和d，將這兩個客戶交換，從而得到一個新的配送方案。如果新方案更優，則替代舊方案。

2.5 算法流程

求解VRPTW 問題的HPSO 算法如下：

步驟一：初始化粒子種群，計算每個粒子的適應度值FIT，初始化全局最優解pg。

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

步驟三：對精英子群中的粒子執行基于交叉的綜合學習策略。

步驟四：對跟隨子群中的粒子執行隨機例子學習策略。

步驟五：計算更新后每個粒子的適應度值FIT，并更新全局最優解pg。

步驟六：對全局最優解pg執行局部搜索策略。

步驟七：若滿足終止條件，則輸出全局最優解，否則，跳轉至步驟二繼續執行。

3 實驗與分析

3.1 實驗算例與相關參數

實驗數據集采用solomon-50 標準數據集中的C101 到C109 算例[16]。其中HPSO 算法的參數設置如下：種群數量100，迭代方式為連續100 代不更新則 停止，w=0.5，c1=2.0，c2=2.0，λγ=0.5，λc=0.5，λm=0.5。

3.2 實驗結果與分析

HPSO 獨立求解C101 算例10 次后得到的最優解如表1 所示，其中配送中心一共派出了5 臺車，即車輛數為5，路徑長度為362.4 km。從表中可以看出，配送中心一共派出了5 臺車，而每個客戶有且只有被訪問一次。“具體配送信息”中每個客戶vi(ti,li,表示車輛到達客戶vi的時刻為ti，而客戶vi時間窗為，如車輛1 到達客戶20 的時刻為10 min，而其時間窗[10 min,73 min]；誤差的計算方式：當前解與已知最優解的差，再除以已知最優解后，得到的結果的百分比。

表1中，HPSO求解C101得到最優解為362.4 km，車輛數為5。其中，每個客戶有且只有被某一車輛訪問一次，符合式（2）、式（3）的約束。而每臺車輛的實際載重量均小于或等于車輛的最大載重量200 kg，滿足式（4）的約束。其次，在配送的過程中，車輛均在客戶要求的時間窗前或者時間窗內到達客戶點，符合式（5）和式（6）的約束條件。由此可見，HPSO 能夠有效地解決VRPTW。

表1 HPSO求解C101的最優解具體信息

為了驗證HPSO 的性能，該實驗結合了傳統的PSO 以及提出的局部搜索策略，得到一個新的算法PSO-LS，并比較其與HPSO 和PSO-LS 對C101 到C109 算例分別求解10 次得到的結果，如表2 所示。

表2 HPSO和PSO-LS求解C101到C109算例的實驗結果

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

4 結論

該文提出了一種HPSO 算法來解決VRPTW。該算法以HPSO 為框架，設計了一種面向VRPTW 的編解碼策略，同時提出了由單點插入策略以及雙點交換策略組成的局部搜索策略。最后，通過solomon-50標準數據集中的九個算例進行仿真實驗。實驗結果表明了HPSO 的有效性和穩定性。而HPSO 在C101、C102、C105、C106 和C107 均能找到已知最優解，尋優能力較強。