多中心協同模式下動態的車輛路徑優化研究

文/柘佳怡

1.引言

隨著共享經濟的興起，作為物流配送優化系統中的關鍵環節，多中心協同的車輛路徑優化問題（Collaboration Multi-depots vehicle routing problem CMVRP）受到了廣泛關注。傳統的車輛路徑（VRP）問題中，在優化之前，客戶的地理位置、貨物需求、時間窗等配送信息都是已知的，且是相對穩定的，不隨著時間的推移產生變化，然后根據這些已知信息為配送中心的車輛進行路徑優化，這類問題統稱為靜態車輛路徑問題（Static SVRP），本文研究的多中心協同模式下車輛的動態路徑問題（Collaboration Multi-depots vehicle routing problem with dynamic demands CMDVRPDD）在傳統的VRP基礎點行，同時考慮了多個配送中心之間的合作和車輛的動態路徑優化，更加具有現實意義。

圍繞著具有動態需求客戶的配送網絡和多中心的車輛調度問題，國內外的學者展開了一系列研究。在多中心協作配送方面，Wang等[1]提出了一種基于改進的粒子群算法研究了考慮同時取貨和送貨的共同配送問題。文軍[2]研究了基于車輛共享的多配送中心車輛路徑問題，并應用2-opt局部優化算法的自適應多態蟻群算法求解模型。范厚明[3]設計了一種變鄰域搜索算法研究了多中心聯合配送模式下集貨需求隨機的同時配集車輛路徑問題。楊翔[4]運用兩階段禁忌搜索算法研究了多中心開放式模糊需求下的車輛路徑問題。張婷等[5]研究了四種動態事件下的配送線路實時優化問題，利用混合遺傳算法尋優。張文博等[6]研究了帶時間窗的動態車輛路徑問題，同時考慮了配送成本最小化和服務準時性最大化。Michal Okulewicz等[7]提出并分析了一種求解動態車輛路徑問題的兩階段多群粒子群優化算法。

綜上所述，學者們對多中心聯合配送以及DVRP研究較為豐富，但上述文獻在將多中心協同和動態車輛路徑優化的結合上還有待深入研究。本文研究了基于多中心協同模式下車輛的動態路徑規劃，將配送中心的工作時間劃分為多個周期，從而將DVRP轉化為一系列SVRP。首先建立以最小化物流總成本和最小化車輛數為目標建立了雙目標優化模型，其次，基于經典的SVRP模型，建立了初始優化階段和動態調整階段的兩階段優化模型，然后設計了一種改進的NSGA-Ⅱ算法進行求解，最后通過算例驗證文章模型和算法的有效性。

2.問題描述

2.1 問題描述。針對動態車輛路徑問題，采用多周期優化的策略將配送中心的工作時間劃分為多個周期，將本周期出現的動態客戶轉移到下一時間段進行延遲處理，從而將DVRP轉換為多個周期的SVRPs[8-9]，在單個周期內采用插入法將動態客戶點插入原有路徑中。因此，多中心協同模式下動態的車輛路徑問題可描述為：配送中心先根據已知客戶進行初始路徑規劃，在配送過程中根據客戶需求的改變，以總成本和車輛數最小為目標，對路徑進行動態調整。

2.2 問題分析及符號說明。假設配送中心D有l輛配送車輛，最大載重量為Q，對初始客戶C1以及動態客戶C2進行服務，配送中心和客戶的時間窗分別是[ETd，LTd]和[ETc，LTc]，違反時間窗的系數為pe和pl，每公里的車輛油耗為fv，汽油價格為AV，車輛的固定成本為Mv，客戶的需求量為qc。所有客戶點的集合為C，配送中心和客戶的集合為I，車輛到達配送中心和客戶的時間為ATig，正在進行配送任務的車輛集合為H，車輛剩余的貨物量為Qh，已經行駛的距離為Lh，任意兩節點之間的距離為dij，DTij是車輛從節點i到達節點j的時間，任意兩節點的行駛時間TTij，車輛在客戶點的等待時間為WTcg，|Nig|是車輛g所行駛路徑中客戶點數量。當動態時間發生時，對未被服務的客戶點重新編號C3，將正在執行配送任務的車輛v作為需求量為Q-Qh的虛擬的客戶，且在配送途中的車輛必須先服務其對應的虛擬客戶，對虛擬客戶重新編號，虛擬客戶和未服務客戶的集合為C4。

3.兩階段優化模型構建

3.1 初始優化階段。在初始優化階段時，配送中心已知客戶的配送信息，包括客戶的貨物需求量、時間窗、地理位置等。配送中心根據客戶的信息生成一個初始的車輛路徑方案，并按照該方案安排車輛執行，等到動態事件發生時，再對車輛路徑進行動態調整。目標函數與約束條件如下：。

公式和是目標函數，公式表示初始階段物流總成本最小化，公式表示使用的車輛數最小，公式表示車輛的配送成本和固定成本，公式表示懲罰成本，約束保證客戶需求總量不能超過車輛的最大裝載量，約束規定每個客戶只能由一輛配送服務，約束表示流量守恒，約束用于消除子回路，約束和保證車輛到達客戶和配送中心的時間必須在其時間窗內。約束和是車輛的到達時間，其中G為一個足夠大的正數，約束表示決策變量，如果車輛g直接從節點i到節點j，則xijg=0，否則為0。

3.2 動態調整階段。本文的動態調整采取周期性優化策略，將配送中心工作時間分為多個時間片，再某個時間片內發生的動態事件不會立即處理，而是轉移至下一時間片與已規劃路徑中尚未服務的客戶一同進行優化。將正在執行任務的車輛看成虛擬客戶，將問題轉化為靜態的VRP。設動態客戶的出現時刻為Tc，新增客戶和原來未服務客戶重新編號構成集合C3，剩余的貨物量為Q-Qh。動態調整階段的目標函數及約束如下：

約束保證虛擬客戶首先被服務，約束規定每個客戶只能由一輛配送服務，約束表示流量守恒，約束用于消除子回路，約束(20)和(21)保證車輛到達客戶和配送中心的時間必須在其時間窗內。約束和是車輛的到達時間，，約束表示動態客戶出現時時間必須在配送中心的時間窗內，約束表示決策變量，如果車輛g是初始階段派遣過的車輛，則yg=1，否則為0。

4.兩階段算法設計及實現

4.1 k-means聚類。為了簡化優化過程，得到更好的優化結果，利用k-means聚類方法根據客戶的地理位置計算客戶點之間的距離，根據計算結果將每個客戶分配給鄰近的配送中心。具體步驟如下：第一步：輸入每個配送中心和客戶的位置坐標；第二步：令k等于配送中心的數量，選擇配送中心作為k個初始聚類中心；第三步：計算客戶點到聚類中心的距離；第四步：將客戶點分配給最近的聚類中心，如果客戶點到達多個聚類中心的距離相等，則任意分配給某一聚類中心；第五步：計算每個聚類的均值作為新的聚類中心；第六步：重復以上步驟直到聚類中心不發生改變；第七步：輸出聚類結果。

4.2 NSGA-Ⅱ算法。在初始優化階段，采用改進的NSGA-Ⅱ算法規劃配送路徑，求得初始配送方案，當動態時間發生時，將動態信息轉移到下一時間段，整合已規劃路徑中尚未服務的客戶和動態客戶，對路線進行動態調整，具體的步驟如下：第一步：設置算法相關參數;第二步：應用掃描法生成初始種群；第三步：計算適應度值；第四步：選擇操作，結合精英保留策略和輪盤賭策略，對所有染色體的適應度進行排序，選擇合適數量的適應度好的個體進行保留，保證子代的個體最優優于父代的個體最優，其余的個體采用輪盤賭的，策略進行選擇；第五步：交叉操作，根據交叉概率選擇染色體進行交叉運算，采用單點交叉法，兩點交叉法和部分映射交叉法生成子代染色體[10]；第六步：變異操作，根據變異概率隨機選擇染色體進行變異操作；第七步：將初始種群和子代種群合并成新的種群，評價目標函數值，進行非支配排序并計算擁擠距離；第八步：進行迭代；第九步：通過排序選取帕累托優化解并輸出最優解。

5.實例驗證及分析

本文選取重慶市某物流企業的配送網絡進行實例研究，選取4個配送中心，30個靜態客戶，20個動態客戶，計算結果見表1。

表1 計算結果

由表1計算結果可得，在各個配送中心獨立運行的情況下，通過初始階段預優化，再根據動態事件對車輛路徑進行動態調整的兩階段優化策略，車輛數和成本都有一定程度下降。在考慮各個配送中心協作模式的情況下，成本下降了30.6%，車輛數由20輛減少到了12輛，減少了8輛。顯而易見，配送中心之間相互協作形成大聯盟，將單個配送中心獨立配送模式轉換為共同配送的配送模式能夠有效地降低物流網絡的運營成本。

6.結論

本文基于多中心協同模式下動態的車輛路徑優化問題，首先，針對動態事件的發生，將DVRP轉化為連續的SVRPs。其次，建立了以總成本和車輛數為目標的雙目標兩階段模型。然后，將k-means聚類和改進的NSGA-Ⅱ算法結合，降低了算法的復雜性，提高了算法的全局搜索和局部搜索能力。最后，在現實生活中選取實例研究模型和算法的有效性，計算結果表明，多中心協作配送的模式能夠有效降低物流成本，提高車輛利用率。

引用出處

[1]Wang,Y.,Li,Q.,Guan,X.Y.,Fan,J.X.,Liu,Y.,Wang,H.Collaboration and Resource Sharing in the Multidepot Multiperiod Vehicle Routing Problem with Pickupsand Deliveries[J].Sustainability.2020,12(15):5966.

[2]文軍.基于車輛共享的多配送中心車輛路徑問題研究[J].物流工程與管理[J],2019,41(02):75-77+72.

[3]范厚明,劉鵬程,劉浩,侯登凱.多中心聯合配送模式下集貨需求隨機的VRPSDP問題[J/OL].自動化學報:1-15[2021-05-07].http://202.202.244.12:80/rwt/CNKI/https/MSYXTLUQPJUB/10.16383/j.aas.c190519.

[4]楊翔.多中心開放式VRP拓展問題建模及算法研究[D].大連海事大學,2019.

[5]張婷,賴平仲,何琴飛,靳志宏.基于實時信息的城市配送車輛動態路徑優化[J].系統工程,2015,33(07):58-64.

[6]張文博,蘇秦,程光路.基于動態需求的帶時間窗的車輛路徑問題[J].工業工程與管理,2016,21(06):68-74.