基于區域—負載均衡策略的兩級車輛路徑優化研究

摘 要：為提升由城市倉庫—前置倉庫—消費者組成的多階段物流運輸效益，提出基于區域—負載均衡的優化方法。首先，基于K-means聚類設計區域劃分策略；其次，構建基于距離準則的聚類中心—前置倉庫最佳匹配機制，從成本最小化視角給出負載均衡策略；然后，構建兩級車輛路徑優化模型，基于禁忌搜索算法設計多層求解策略；最后，通過數值實驗與靈敏度分析驗證所構模型及方法的有效性，通過對照實驗分析僅考慮區域劃分、同時考慮區域—負載均衡、不考慮區域—負載均衡三種情景下優化結果。研究成果揭示了區域—負載均衡與路徑結果的內在關系，可為實現多階段物流運輸效率與成本的雙重優化提供理論及方法支撐。

關鍵詞：物流規劃； 區域劃分； 負載均衡； 車輛路徑； 智能算法

中圖分類號：U116.2

文獻標志碼：A

文章編號：1001-3695（2023）07-011-1991-07

doi：10.19734/j.issn.1001-3695.2022.11.0769

Research on two-level vehicle routing optimization based onregion load balancing strategy

Wang Jianxin^1?， Sun Wenyuan²， Yao Xilong¹， Li Jizu¹

（1.College of Economics amp; Management， Taiyuan University of Technology， Taiyuan 030002， China; 2.College of Politics amp; Public Management， Guangxi Minzu University， Nanning 530000， China）

Abstract：To improve the efficiency of multi-stage logistics transportation composed of urban warehouse， front-end warehouse and consumer， this paper proposed an optimization method based on region load balance. Firstly， this paper designed the region division strategy based on K-means clustering. Secondly， this paper constructed the optimal matching mechanism between cluster center and front-end warehouse based on distance criterion， and gave the load balancing strategy from the perspective of cost mi-nimization. Then， this paper constructed a two-level vehicle routing optimization model， and designed a multi-layer solution stra-tegy based on tabu search algorithm. Finally， this paper verified the validity of the model and method by numerical experiments and sensitivity analysis and analyzed the optimization results under the three scenarios of only considering region division， simultaneously considering region load balancing， and not considering region load balancing by comparison experiments. The research results reveal the internal relationship between region load balance and route results， which can provide theoretical and technical support for the realization of dual optimization of multi-phase logistics transportation efficiency and cost.

Key words：logistics planning; regional division; load balancing; vehicle routing; intelligent algorithm

0 引言

在全球經濟格局不斷演化、國家物流樞紐快速發展、及物流市場競爭持續加劇的背景下，提升物流企業對客戶的高效響應，是提升物流樞紐競爭力和運輸效益的重要途徑。而受中重型貨車12/24 h交通管制影響，由倉庫出發的大型貨車難以直接進入城市內部進行配送，需經前置倉庫中轉，致使物流網絡多呈現以前置倉庫為分界的多階段特征。此外，工作人員對區域是否熟悉、前置倉庫間負載是否均衡、能否滿足消費者對時間窗的要求均是影響運輸效益的關鍵因素，進一步增加了多階段運輸問題求解的復雜性。而如何快速生成最佳車輛路徑方案，對于提升運輸效益具有重要的現實與理論價值^［1，2］。鑒于此，進一步催生了對基于區域—負載均衡的兩階段帶時間窗的車輛路徑問題（two-echelon vehicle routing problem with time windows based on area-load balancing，2E-VRPTWALB）的研究。

2E-VRPTWALB是兩階段帶時間窗約束的車輛路徑問題（two-echelon vehicle routing problem with time windows，2E-VRPTW）與區域劃分方法、負載均衡方法的深度融合。第一階段節點由城市倉庫與前置倉庫構成，第二階段節點由前置倉庫與消費者構成。2E-VRPTWALB的優勢在于通過區域劃分避免工作人員跨區域執行任務、通過負載均衡實現車輛使用數量成本的降低，通過車輛行駛距離成本的最小化實現物流成本的降低，最終通過兩階段運輸，將消費者所需的產品由城市倉庫經前置倉庫中轉派遣至消費者指定目的地。

針對2E-VRPTW問題，Li等人^［3］研究了帶時間窗口和移動衛星的2E-VRPTW，并設計了用于求解該問題的自適應

大鄰域啟發式搜索算法，但該研究并沒有考慮車輛速度因素。Yu等人^［4］從速度對成本的影響角度研究了2E-VRP問題，設計了用于求解該問題的構造啟發式和帶回溯的混合元啟發式算法，通過對車速組合的敏感性分析，得出提高小型自動駕駛汽車速度對成本的影響非常有限這一結論。為解決應急物流問題，楊楓等人^［5］研究了突發事件情境下，交通路網動態變化時的應急車輛路徑選擇問題，提出應急車輛動態路徑選擇的兩階段調度優化模型。王付宇等人^［6］采用聚合優化算法對災區進行應急救援區域劃分，建立了以總救援時間最短和相對綜合救援權重值最大為目標的救援車輛兩階段數學規劃模型，并設計用于求解該模型的離散型螢火蟲優化算法，該算法屬于啟發式范疇。針對精確式算法范疇，文獻［7］基于分支界定法研究了2E-VRPTW問題，并以5個衛星和100個客戶作為實例進行了驗證研究。針對求解2E-VRPTW問題的求解方法，主要分為以分支定界法^［8］、動態規劃法^［9］為代表的精確式算法，以及以禁忌搜索算法^［10］、遺傳算法^［11］、模擬退火算法^［12］、大鄰域搜索算法^［13］等為代表的啟發式算法。相比精確式算法，啟發式算法憑借求解速度快的優勢被廣泛應用，包括Wang等人^［14］基于可變鄰域搜索，研究了用于求解2E-VRP問題的元啟發式算法，以提升物流方案的生成效率；Akbay等人^［15］開發了用于求解2E-VRP的混合整數線性規劃公式，并設計了可變鄰域搜索元啟發式算法；文獻［16］研究了求解2E-VRP問題的自適應大鄰域搜索算法，并引入時間窗，設計了評估啟發式算法。

綜上所述，現有文獻已對2E-VRPTW問題展開了較為深入研究，并取得了豐富的成果，然而，還沒有文獻從區域劃分與負載均衡的視角對其展開深入的研究。因此，在借鑒現有文獻成果基礎上，提出基于K-means的區域劃分方法、以及基于節點平衡的車輛負載均衡機制，將其融入到2E-VRPTW中，構建2E-VRPTWALB模型及求解策略，旨在實現物流派遣效率、車輛行駛距離成本及使用數量成本的多重優化。

1 問題描述

2E-VRPTWALB主要針對涉及兩階段配送業務的企業，如擁有前置倉庫的電商企業。商家在距消費者較遠地方建立城市倉庫，在距離消費者較近地方建立前置倉庫。當消費者通過電商平臺下單后，由平臺指派車輛由城市倉庫出發，選擇最佳配送路線，將消費者所需產品快速配送至所在地，而前置倉庫的需求由城市倉庫負責滿足。由于作業人員只能在規定的服務窗口期內訪問并作業（如工作時間段），所以城市倉庫、前置倉庫及消費者均有時間窗約束要求；此外，從城市倉庫到前置倉庫與從前置倉庫到消費者的運量不同，因此不同階段需采用不同規格的車輛，但車輛的實際裝載量不能夠超過車輛的額定裝載量；前置倉庫及消費者均有需求約束；所有車輛完成運輸任務后均需返回城市倉庫或前置倉庫；不同的工作人員對不同區域具有熟悉度差異性，在同區域內執行任務的效率高于跨區域執行任務的效率，2E-VRPTWALB問題示意圖如圖1所示。

當不同消費者發出需求之后，先根據消費者及前置倉庫位置進行聚類，依據距離準則實現區域劃分與倉庫最佳匹配，然后安排大型車輛將消費者所需產品先從城市倉庫轉運至前置倉庫，再由小型車輛從前置倉庫派送至目的地。在區域劃分過程中，采用劉瀟等人^［17］對區域劃分的K-means聚類方法，以距離最小化為目標，根據消費者位置坐標及前置倉庫數量進行最佳區域聚類劃分；在進行中轉站間車輛負載均衡過程中，以車輛使用數量成本最小化為目標，對前置倉庫間車輛負載進行均衡。

2 模型構建

2.1 選址環節

a）基于K-means的消費者訂單區域劃分。以消費者與區域中心間距離最小化及每個消費者僅屬一個區域原則，設計訂單劃分機制。將n個消費者{c₁，c₂，…，c_n}隨機劃分為k個不同的初始區域{q₁，q₂，…，q_k}，1≤k≤n，每個消費者到每個區域中心的距離計算公式為

其中：c_i為第i個消費者；q_j為第j個區域中心；c_ix、c_iy為第i個消費者的x、y屬性；q_jx、q_jy為第j個區域中心的x、y屬性。根據式（1），依次計算每個消費者到每個區域中心的距離，將消費者分配到距離最近的區域中，得到k個新的區域{s₁，s₂，…，s_j，…，s_k}，各個區域中心的坐標值計算公式為

其中：s_j為第j個區域中心；s_j為第j個區域中所包含的消費者數量；c_i為第j個區域中第i個消費者，1≤i≤s_j。基于上述區域劃分機制，雖能實現對消費者的不同區域劃分，以避免跨區域執行任務，進而提升派遣效率，但并不能夠保證兩階段車輛路徑成本最小化。為實現效率與距離成本雙重最優化，以聚類數量作為變量，以消費者及城市倉庫與聚類區域中心距離最小化為目標，構建最佳區域劃分及區域中心選址模型，目標函數為

其中：c₀為城市倉庫，變量為聚類個數設置，取值范圍為不超過前置倉庫數量。

b）區域劃分與前置倉庫的最佳匹配。經過最佳區域劃分之后，易出現區域中心與前置倉庫位置不匹配的情景，需對新生成的區域中心與前置倉庫進行最佳匹配，以實現物資的最佳中轉。為此設計以所有聚類中心與前置倉庫組成的一一映射網絡距離最小化為優化目標的匹配機制，優化目標函數為

其中：w_i為前置倉庫、目標為區域中心與前置倉庫距離之和。

c）前置倉庫間車輛負載均衡策略。經過區域劃分之后，不同的前置倉庫所服務消費者需求量不同，易導致車輛在執行任務時出現負載不均的情況，進一步導致車輛使用數量成本增加，因此有必要對前置倉庫間車輛負載進行均衡。在均衡過程中，為兼顧車輛使用數量與行駛距離成本雙重最小化，設計距離非所屬前置倉庫越近，越優先被調節的機制，對客戶與前置倉庫間的隸屬關系進行微調，以實現在區域劃分的基礎上實現車輛間的負載均衡，提升車輛平均裝載率。前置倉庫間車輛負載均衡策略如圖2所示。

如圖2，假定每個客戶的需求量均為15 kg，車輛最大裝載量為100 kg，則前置倉庫A需要至少派遣2輛車方可完成任務，而前置倉庫B則至少需派遣1輛車方可完成任務，此時共需至少調度3輛車，車輛平均裝載率為60%。若依據距離非所屬前置倉庫越近越被有效調節的策略，消費者6被調節至前置倉庫B，前置倉庫A、B均至少需調度1輛車即可完成任務，此時車輛使用數量由3降低至2，平均裝載率由60%提升至90%。鑒于此，為兼顧車輛行駛距離成本最小化，以距離其他前置倉庫最小的消費者作為調節對象，將其隸屬關系對應至距離最小的前置倉庫，更新該前置倉庫服務消費者信息。若距離相同，則優先調節前置倉庫車輛裝載率小的消費者；當該前置倉庫車輛平均裝載率小數部分大于0.5時，則終止被移入，該前置倉庫完成車輛負載均衡，不再進行移入與移出操作。依次重復上述步驟，直至所有前置倉庫均被均衡為止。

2.2 路徑優化環節

借鑒文獻［7，18］構建的兩階段車輛路徑模型，以車輛行駛距離成本最小化作為優化目標，構建基于區域—負載均衡的2E-VRPTW模型，模型假設為：由城市倉庫到前置倉庫所采用車輛的額定裝載量為1 034，由前置倉庫到客戶所采用車輛的額定裝載量為70；城市倉庫與前置倉庫可使用車輛數量均為無限；選址費用與前置倉庫數量成正比，假定為單位值1；車輛訪問前置倉庫及客戶均需滿足時間窗要求；車輛實際裝載量不能夠超過額定裝載量。

所使用到的數學符號含義為：c¹_{［i］［j］［k］}為第一階段車輛k由節點i到j的單位距離成本；c²_{［i］［j］［k］}［m］為第二階段前置倉庫m中車輛k由節點i到j單位距離成本；d¹_{［i］［j］［k］}為第一階段中車輛k由節點i到j的距離；d²_{［i］［j］［k］}［m］為第二階段前置倉庫m中車輛k由節點i到j的距離；x¹_{［i］［j］［k］}為第一階段車輛k是否由節點i通往j的0-1變量；x²_{［i］［j］［k］}［m］為第二階段前置倉庫m中車輛k是否由節點i通往j的0-1變量；i，j，i′，j+∈N¹∪N²，k∈K¹∪K²_m為編號；N¹，N²為第一階段中前置倉庫集合和第二階段中消費者集合；K¹，K²_m為第一階段可用車輛數及第二階段前置倉庫m的可用車輛數；M²為第二階段前置倉庫集合；M為無窮大正數；w¹_{［i］［k］}為第一階段車輛k到達前置倉庫i的時間；w²_{［i］［k］}［m］為第二階段前置倉庫m中車輛k到消費者i的時間；s¹_［i］，s²_［i］為在前置倉庫i和消費者i處的服務時間；t¹_{［i］［j］［k］}為第一階段車輛k由i到j的行駛時間；t²_{［i］［j］［k］}［m］為第二階段前置倉庫m中車輛k由i到j的行駛時間；N¹，N²_m為集合中包含元素的個數；w¹_［k］，w²_［k］［m］為第一階段車輛k的實際裝載量，及第二階段前置倉庫m中車輛k的實際裝載量；Q¹，Q²_［m］為第一階段車輛k的額定裝載量，及第二階段前置倉庫m中車輛k的額定載量；L_{［j］［j+］［k］}為車輛k從節點j到j+的實際裝載量；q_i為前置倉庫或消費者的需求量；a¹_［i］，b¹_［i］為第一階段前置倉庫i的時間窗；a²_{［i］［m］}，b²_{［i］［m］}為第二階段前置倉庫m中消費者i的時間窗；E¹，L¹，E²，L²為第一、二階段中起點時間，模型目標函數與約束條件如式（5）～（24）。

式（6）（7）為流量守恒約束；式（8）（9）為由城市倉庫或第m個前置倉庫派出車輛數量需滿足可用數量；式（10）（11）為車輛服務前置倉庫或消費者的順序；式（12）（13）為任意前置倉庫或消費者i最多被訪問一次；式（14）（15）為消除第一、二階段子回路；式（16）（17）為車輛非超載約束；式（18）（19）為任意消費者均能在一次服務中得到滿足；式（20）（21）為時間窗約束；式（22）為訪問任意前置倉庫均需滿足城市倉庫時間窗；式（23）為訪問任意消費者均需滿足前置倉庫時間窗；式（24）為變量取值范圍。

3 基于禁忌搜索算法的多層求解策略

Glover^［19］于1986年提出禁忌搜索算法（tabu search algorithm，TSA），其核心為通過鄰域搜索不斷產生新的解，并通過禁忌表、禁忌長度、藐視準則保存與釋放局部解，最終通過適應度函數尋得全局較優解。TSA作為隨機啟發式算法，憑借其搜索速度快的優勢已被大量學者應用于VRP領域^［20］，而本文所解決的問題本質上屬于多個VRP問題的組合，鑒于此，在前期學者研究基礎上，繼續基于TSA設計用于求解基于區域—負載均衡的2E-VRPTW的算法偽代碼如下所示。

算法1 基于TSA的多層求解策略偽代碼

1 layer1

2 parameter initialication， generate feasible solution n（x）

based on neighborhood transformation criterion

3 openlist（x）=selection function（N（x））

4 while openlist（x）? and no optimal solution found， do

5

x=min{v（openlist（x））}

6

if x∈tabulist（x） then

7

openlist（x）=openlist（x）-{x}

8

else if y（x）＞y（x^*） then

9

x^*=x

10

end if

11

end if

12 end while

13 updata tabulist（x）

14 if the local optimal solution x is found， then

15 insert x into tabulist（x）

16 end if

17 end

18 layer1+

19 cycle 2～17 steps

20 until all nodes are traversed

21 end and output the optimal solution

偽代碼中，外層循環終止條件為所有經過區域—負載均衡的前置倉庫，以及消費者均得到滿足，內層循環終止條件為城市倉庫及前置倉庫尋得最優的車輛路徑方案，多層次求解核心思路為：首先基于區域及負載均衡結果，采用TSA求解由城市倉庫與前置倉庫組成的VRP問題；其次，采用TSA求解由前置倉庫與消費者組成的VRP問題；最后得出2E-VRPTWALB的優化解。在構造初始解過程中，基于隨機思想進行構造，具體為：首先，生成若干個開放的以城市倉庫或前置倉庫為起點和終點的路徑鏈；其次，在滿足時間窗約束下，隨機選取前置倉庫插入到由城市倉庫構成的路徑鏈，隨機選取消費者插入到由前置倉庫構成的路徑鏈，直到被插入的需求量之和超過車輛額定裝載量之前，關閉路徑鏈；最后，重復上述步驟，直至所有的前置倉庫及消費者均被插入完為止，生成初始可行解，其構造過程如式（25）所示。

其中：add random{i}為在滿足時間窗約束條件下，隨機選取非重復的前置倉庫或消費者的連續插入函數，更換路徑的條件為是否超過車輛的額定裝載量。在設計適應度函數時，以路徑鏈容量超載懲罰和車輛行駛距離之和作為指標，設置動態自適應適應度函數，以實現最大化地利用非可行解尋找全局最優解，自適應函數如式（26）所示。

其中：ΔQ為超出容量約束總量；ΔT為超出時間約束總量。在參數θ作用下，當路徑鏈容量滿足車輛容量約束時，適應度函數隨著懲罰系數的減小而減小；當路徑鏈容量偏離車輛容量約束時，適應度函數值隨著懲罰系數的增加而增加。在進行鄰域搜索時，設計基于2-opt的路徑間搜索擾動策略，如圖3所示。

如圖3中，{0，1，2，3，4，5，6，0}，{0，3，2，1，4，5，6，0}為兩個初始可行解，在經過任意兩個節點交換的2-opt操作之后，即可產生新的可行解{0，1，5，3，4，2，6，0}，{0，3，5，1，4，2，6，0}。禁忌表作為可行解的臨時儲存載體，對于提升解的質量具有重要作用。鑒于此，借鑒現有研究成果，采用先進先出的規則構造禁忌表。而在設計禁忌表時，當禁忌長度設置過短時，TSA容易因為搜索范圍變小而陷入局部搜索；相反當禁忌長度設置過長時，則容易造成搜索耗時的增加。因此，本文借鑒李國明等人^［21］指出的最優禁忌長度取值范圍，將禁忌長度設定在4n～10n，n表示所求解問題中節點的數量。

4 算例分析

4.1 算法性能分析

基于Solomon數據庫，選取不同分布特征的實例，對所構建TSA算法的有效性進行分析，數據下載地址為：http：//web.cba.neu.edu/～msolomon/。參數設置為：搜索迭代次數為5 000，禁忌步長為30，α=0.1，β=1.0，θ=0.8；測試環境為：Core i5，1.8 GHz CPU雙核，8 GB內存，512 GB SSD；Windows 10 64 bit，Java JDK-8u251編程環境。分散搜索（scatter Search，SS）最早在1977年由Glover 為解決整數規劃問題而提出，被廣泛應用于VRP領域，為此本文將所得結果與當前文獻已知最好解，以及文獻［22］設計的SS進行對比，結果如表1所示。

由表1可知，在測試過程中，TSA的表現性能整體較好，基本上達到了與文獻結果及已知最好解水平，就車輛行駛距離成本而言，TSA所求的RC102實例，相比已知最好解1 554.75，下降至1 504.68，優化率達到了3.22%。TSA所求的RC102的15條路徑分別為：No.1： 1 97 72 68 95 81 1；No.2： 1 91 1；No.3： 1 65 50 23 21 25 84 1；No.4： 1 46 6 4 2 9 8 7 47 5 3 101 1；No.5： 1 66 100 58 87 75 60 53 1；No.6： 1 62 82 69 56 1；No.7： 1 40 37 41 39 42 55 1；No.8： 1 64 34 29 31 33 35 94 1；No.9： 1 43 45 44 36 38 73 1；No.10： 1 83 12 16 17 88 98 76 59 1；No.11： 1 20 24 22 19 49 26 78 1；No.12： 1 70 99 89 54 10 11 14 18 13 1；No.13： 1 51 32 30 28 27 90 86 92 1；No.14： 1 15 48 74 80 79 61 71 1；No.15： 1 93 96 63 77 52 85 57 67 1。

接下來，將基于TSA的多層求解策略對2E-VRPTWALB進行案例仿真分析。為驗證所提基于區域—負載均衡的兩級車輛路徑優化策略，選取由1個城市倉庫、10個前置倉庫及200個消費者組成的案例進行驗證，車輛行駛單位距離成本設定為單位距離值。消費者需求分布（圖4（a））及城市倉庫、前置倉庫、消費者所在位置分布（圖4（b））如圖4所示。

4.2 基于區域—負載均衡的兩級車輛路徑優化

設置聚類數量初始值為1，依次遞增至與前置倉庫個數一致的值，對200個消費者進行區域劃分，統計不同聚類參數設置下兩階段網絡距離成本，分析不同聚類數量對距離成本的影響關系，其中，兩者之間的相關關系如圖5所示。

由圖5可知，隨著聚類數量的增加，兩階段網絡距離成本總體呈現出先減小后增加的特征，即表明存在最佳的中轉站數量設置，能夠使得兩階段車輛距離成本最小化，同樣也說明啟用全部前置倉庫并不一定能夠保證車輛距離最小化。而隨著聚類數量的增加，第一階段距離成本總體呈現出正相關性，第二階段距離成本整體呈現出負相關性。在不同聚類參數設計下各個聚類中心及距離成本信息如表2所示。

由表2結果可知，當聚類數量設置為7時，所得到的兩階段網絡距離成本值最小，即為1 615，此時第一階段網絡距離成本值為430，第二階段網絡距離成本值為1 186；其次為聚類數量設置為6時，距離成本值為1 668。在不同的聚類參數下，基于K-means的客戶區域劃分結果如圖6所示。

由圖6知，在不同參數設置下均能實現對客戶區域的劃分，可有效避免車輛跨區域執行任務，表明將K-means融入到區域劃分中的有效性。然而，在不同參數設置下，劃分結果不同，對應距離成本不同，這表明在進行區域劃分過程中，需確定最佳的中轉站數量及位置，以實現目標函數值最小化。

聚類中心與前置倉庫的最佳匹配。在聚類數量設置為7的條件下，網絡距離成本值取得最小化，因此在該條件下將7個聚類中心與10個前置倉庫進行匹配，以聚類中心與前置倉庫間距離之和最小化為目標，對中轉站與前置倉庫進行最佳匹配，以決策啟用最佳前置倉庫。其中，7個聚類中心與前置倉庫所構成的可達網絡如圖7所示。

圖7展示了7個聚類中心與10個前置倉庫所構成的可達網絡圖。由圖可知，同一聚類中心與不同的前置倉庫間距離存在較大差異性，而不同聚類中心與同一前置倉庫間距離同樣存在較大差異性，主要原因是由200個消費者需求分布的不確定性引起的。聚類中心與前置倉庫所構成的距離矩陣如式（27）所示。

基于匈牙利算法求解任務分配的規則，以距離和最小化為目標，對聚類中心與前置倉庫進行最佳匹配，匹配結果為：1-1，2-6，3-4，4-8，5-3，6-2，7-5。選擇1、6、4、8、3、2、5號前置倉庫作為最佳中轉站倉，并將消費者隸屬至對應前置倉庫。

前置倉庫間車輛負載均衡。以車輛使用數量成本最小化為目標，根據前述負載均衡策略，微調消費者與前置倉庫的隸屬關系，對最佳匹配后的前置倉庫進行負載均衡，負載均衡前后車輛使用數量及平均裝載率對比如表3所示。

由表3可知，經負載均衡之后，最小使用車數量由49降至45，車輛的平均裝載率由90.25%提升至97.90%，表明車輛負載均衡策略對于提升車輛使用效率具有顯著作用，其主要原因是隸屬于不同前置倉庫的消費者需求量不同，導致部分車輛間負荷不均衡，進一步致使車輛利用率不高。

基于區域—負載均衡的兩階段車輛路徑優化結果。在區域劃分及負載均衡的基礎上，采用禁忌搜索算法，對兩階段車輛路徑問題進行求解，所得一、二階段路徑圖如圖8所示。

由圖8的車輛路徑圖可知，在考慮區域劃分之后，可有效避免車輛跨區域執行任務，有助于提升配送效率。而之所以出現部分車輛跨區域執行任務的情況，是由于經過前置倉庫間負載均衡導致的，這表明經過負載均衡雖能夠降低車輛使用數量成本，但會以車輛跨區域執行任務作為代價。其中，基于區域—負載均衡的路徑優化結果如表4所示。

由表4可知，在第一階段共需4輛將消費者所需由城市倉庫中轉至前置倉庫，車輛行駛距離成本為490.92，在第二階段共需48輛車將消費者所需由前置倉庫派送至目的地，車輛行駛距離成本為1 460.75，總的車輛行駛距離成本為1 951.67。第一、二階段車輛的平均裝載率為74.98%、92.89%，這表明了在本文方案中車輛得到了較為有效的利用。

4.3 不同策略優化結果對比分析

情景1 不考慮區域—負載均衡下的車輛路徑優化結果。在不考慮區域劃分及負載均衡情景下，200個消費者需求首先由城市倉庫轉運至10個前置倉庫，再由前置倉庫轉運至消費者目的地，在整個派送過程中，僅以車輛行駛距離成本最小化為目標，此情景下的兩階段車輛路徑圖如圖9所示。

由圖9可知，在不考慮區域劃分及負載均衡的情境下，以車輛行駛距離成為作為路徑規劃的目標，所得到的結果中，車輛明顯存在跨區域執行任務情況，易導致派送效率降低；此外，10個前置倉庫均被啟用，易導致中轉成本增加。

情景2 僅考慮區域劃分，不考慮負載均衡。在對200個消費者進行區域劃分，及最佳前置倉庫匹配之后，以車輛行駛距離成本最小化為目標，所得兩階段車輛路徑如圖10所示。

由圖10可知，在僅考慮區域劃分，不考慮負載均衡情景下，所得到的結果中，車輛不存在明顯的跨區域執行任務情況，且呈現出了明顯的聚類特征，進一步表明了在兩階段車輛路徑問題中植入區域劃分機制，有助于提升車輛派遣效率。

接下來，對不同情景優化結果進行對比分析，設置考慮區域—負載均衡為情景3，車輛行駛距離成本、使用數量成本、車輛裝載率等作為運輸的關鍵指標，通常被企業所關注，為分析不同情景下的成本優劣性，對三種不同情境的優化結果展開分析，下第一階段車輛路徑優化結果對比如表5所示。

由表5可知，在第一階段，三種情景車輛使用成本均相同，均需要4輛裝載量為1 034的車輛即可完成任務，但三種情景下的車輛行駛距離成本及裝載率略有不同，情景1的車輛距離成本最大，情景2、3相同，表明在考慮區域劃分及負載均衡情景下的車輛行駛距離成本要優于不考慮情景；情景2、3的車輛行駛距離成本相同，但車輛裝載率不同，這表明了相同車輛行駛距離成本下對應的車輛行駛方案并不唯一。其中，不同情景下第二階段車輛路徑優化結果對比如表6所示。

由表6可知，在第二階段，三種情景對應的車輛行駛距離成本顯著不同，情景3最大，其次為情景2，最小的為情景1，主要是因為是否考慮區域劃分及負載均衡均直接作用于第二階段車輛路徑網絡。情景1對應的車輛行駛距離成本最小，表明了在考慮區域劃分及負載均衡之后，雖有助于避免出現跨區域執行任務的情況，但需要以犧牲距離成本作為代價。而情景1對應的車輛使用數量成本最大，表明了在考慮區域劃分及負載均衡后有助于降低車輛使用數量成本。此外，就車輛平均裝載率指標而言，情景2、3均優于情景1，這表明考慮區域劃分及負載均衡有助于提成車輛的裝載率。

4.4 敏感性分析

選擇合適的車型執行任務對于提升車輛利用率、降低車輛使用數量成本具有重要的作用，為探討車型變化與車輛行駛距離成本及平均裝載率之間的變化關系，在基于區域—負載均衡情景下，選擇服務消費者數量最多的前置倉庫7進行敏感性分析，結果如圖11所示。

由圖11可知，隨著車輛裝載量的增加，車輛行駛距離成本和使用數量成本均呈現出下降的趨勢，表明使用大型車輛能夠有效降低車輛行駛距離成本。在局部位置，隨著車輛裝載量的增加，車輛使用數量成本并不會發生變化，車輛行駛距離成本呈現下降趨勢，造成這一現象的原因為：消費需求總量在一定范圍內，大型車輛能夠訪問更多的消費者，進而實現行駛距離成本的節約，但并不會減少車輛使用數量。進一步表明選擇合適的車型，對于企業降低成本具有重要的實踐價值。

5 結束語

從區域劃分與負載均衡視角對兩階段車輛路徑問題進行了研究，首次針對2E-VRPTWALB問題進行了明確描述，構建了以避免跨區執行任務為目標的區域劃分機制，設計了以車輛使用數量成本最小化為目標的負載均衡策略，給出了2E-VRPTWALB的建模過程，以及基于TSA多層次求解策略。考慮到求解結果的可對比性，選擇通用數據庫Solomon、Perboli對所提方法進行了驗證，針對不同組合情景方案進行了詳細的對比分析，并進行了敏感性分析，通過本文研究得到的主要結論如下：

a）相比2E-VRPTW而言，考慮區域劃分能夠有效避免工作人員出現跨區域執行任務，基于K-means的區域劃分對提升派遣效率具有積極的作用。

b）以較高裝載率作為負載均衡目標時，并不利于降低車輛使用數量成本，相反可能因為違反時間窗約束導致車輛使用數量成本的增加。

c）車輛裝載量與行駛距離、使用數量成本呈現出非連續的負相關性，在消費者數量一定的情況下，車輛裝載量在局部范圍內變化并不會引起行駛距離與使用數量成本的增加。

成果可為后續研究提供基礎，如可以根據不同的物流運輸場景，增加或減少約束條件，更改求解策略及目標函數，形成2E-VRPTWALB的拓展性模型。從算法角度，還可以進一步研究更為高效的算法架構與求解策略，并結合更為廣泛實際的物流數據展開實證研究。

參考文獻：

［1］張穎鈺， 吳立云. 多中心半開放式送取需求可拆分的車輛路徑優化［J］. 計算機應用研究， 2022，39（8）：2316-2321. （Zhang Yingyu， Wu Liyun. Multi-depot half open vehicle routing problem with split deliveries and pickups［J］. Application Research of Computers， 2022，39（8）： 2316-2321.）

［2］閆芳， 鄧德萍， 柴福良. 基于智能垃圾桶的垃圾分類動態收運路徑優化問題研究［J］. 計算機應用研究， 2022，39（12）： 3620-3625. （Yan Fang， Deng Deping， Chai Fuliang. Research on optimization of dynamic collection and transportation route of garbage classification based on intelligent garbage cans［J］. Application Research of Computers， 2022，39（12）： 3620-3625.）

［3］Li Hongqi， Wang Haotian， Chen Jun， et al. Two-echelon vehicle routing problem with time windows and mobile satellites［J］. Transportation Research Part B： Methodological， 2020，138：179-201.

［4］Yu Shaohua， Puchinger J， Sun Shudong. Two-echelon urban delive-ries using autonomous vehicles［J］. Transportation Research Part E： Logistics and Transportation Review， 2020，141： 102018.

［5］楊楓， 種大雙. 應急車輛動態路徑選擇的兩階段優化模型［J］. 交通運輸系統工程與信息， 2022，22（3）： 84-92. （Yang Feng， Zhong Dashuang. Emergency vehicle dynamic path selection based on two-stage objective optimization model［J］. Journal of Transportation Systems Engineering and Information Technology， 2022，22（3）： 84-92.）

［6］王付宇， 葉春明， 王濤，等. 震后傷員救援車輛兩階段規劃模型及算法研究［J］. 管理科學學報， 2018，21（2）： 68-79. （Wang Fuyu， Ye Chunming， Wang Tao， et al. Research on two stage planning model and algorithm of wounded rescue vehicle after earthquake［J］. Journal of Management Sciences in China， 2018，21（2）： 68-79.）

［7］Nico D， Fardin D S， Tom V W， et al. Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows［J］. Transportation Science， 2019，53（2）： 463-479.

［8］Mads J， Simon S， Stefan R. A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem［J］. Transportation Science， 2013，47（1）： 23-37.

［9］Wang Yong， Peng Shouguo， Guan Xiangyang， et al. Collaborative logistics pickup and delivery problem with eco-packages based on time-space network［J］. Expert Systems with Applications， 2021，170： 114561.

［10］Zhou Hang， Qin Hu， Zhang Zizhen， et al. Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery［J］. Soft Computing， 2022，26（7）： 3345-3360.

［11］Leandro D C M， Patrick H， Angel A J. Agile optimization of a two-echelon vehicle routing problem with pickup and delivery［J］. International Transactions in Operational Research， 2021，28（1）： 201-221.

［12］Pichka K， Bajgiran A H， Petering M E H， et al. The two echelon open location routing problem： Mathematical model and hybrid heuristic［J］. Computers amp; Industrial Engineering， 2018，121（C）： 97-112.

［13］徐倩， 熊俊， 楊珍花， 等. 基于自適應大鄰域搜索算法的外賣配送車輛路徑優化［J］. 工業工程與管理， 2021，6（23）：115-122. （Xu Qian， Xiong Jun， Yang Zhenhua， et al. Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm［J］. Industrial Engineering and Management， 2021，6（23）： 115-122.）

［14］Wang Dan， Zhou Hong， Feng Ruxin. A two-echelon electric vehicle routing problem with time windows and battery swapping stations［J］. Applied Sciences， 2021，11（22）： 10779.

［15］Akbay M A， Kalayci C B， Blum C， et al. Variable neighborhood search for the two-echelon electric vehicle routing problem with time windows［J］. Applied Sciences， 2022，12（3）： 1014.

［16］Philippe G， Michel G， Fabien L， et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization［J］. European Journal of Operational Research， 2016，254（1）： 80-91.

［17］劉瀟， 王效俐. 基于K-means和鄰域粗糙集的航空客戶價值分類研究［J］. 運籌與管理， 2021，30（3）： 104-111. （Liu Xiao， Wang Xiaoli. Value segmentation of airline customers based on K-means and neighborhood rough set［J］. Operations Research and Ma-nagement Science， 2021，30（3）： 104-111.）

［18］Wang Kangzhou，Shao Yeming，Zhou Weihua. Matheuristic for a two-echelon capacitated vehicle routing problem with environmental consi-derations in city logistics service［J］. Transportation Research Part D： Transport and Environment， 2017，57： 262-276.

［19］Glover F. Tabu search： a tutorial［J］. Interfaces， 1990，20（4）： 74-94.

［20］孫麗君， 周雅嫻， 滕玥， 等. 多車艙車輛路徑問題的研究現狀與發展［J］. 系統工程理論與實踐， 2021，41（6）： 1535-1546. （Sun Lijun， Zhou Yaxian， Teng Yue， et al. Multi-compartment vehicle routing problem： status and perspectives［J］. Systems Enginee-ring： Theory amp; Practice， 2021，41（6）： 1535-1546.）

［21］李國明， 李軍華. 基于混合禁忌搜索算法的隨機車輛路徑問題研究［J］. 控制與決策， 2020，36（9）： 2161-2169. （Li Guoming， Li Junhua. Stochastic vehicle routing problem based on hybrid tabu search algorithm［J］. Control and Decision， 2020，36（9）： 2161-2169.）

［22］Patricia B， Hugo T Y. Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries［J］. Computers amp; Industrial Engineering， 2013，64（2）： 589-601.