多中心協(xié)同模式下動態(tài)的車輛路徑優(yōu)化研究

文/柘佳怡

1.引言

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

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

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

2.問題描述

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

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

3.兩階段優(yōu)化模型構(gòu)建

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

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

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

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

4.兩階段算法設(shè)計及實現(xiàn)

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

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

5.實例驗證及分析

本文選取重慶市某物流企業(yè)的配送網(wǎng)絡(luò)進行實例研究，選取4個配送中心，30個靜態(tài)客戶，20個動態(tài)客戶，計算結(jié)果見表1。

表1 計算結(jié)果

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

6.結(jié)論

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

引用出處

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

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

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

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