彭 勇，趙子翔，肖云鵬

（1.重慶交通大學(xué)交通運輸學(xué)院，重慶 400074；2.重慶市市政設(shè)計研究院，重慶 400020）

文獻(xiàn)[1]完成了短途客運與貨運的結(jié)合，并提出了一種自適應(yīng)大鄰域搜索算法對其進(jìn)行求解。文獻(xiàn)[2-4]提出利用地鐵網(wǎng)絡(luò)進(jìn)行城市貨運并進(jìn)行樞紐站點選址。文獻(xiàn)[5]構(gòu)建了地鐵配送網(wǎng)絡(luò)優(yōu)化模型，并設(shè)計了一種隨機(jī)變鄰域迭代局部搜索算法進(jìn)行求解。文獻(xiàn)[6]將地鐵與地面交通相結(jié)合建立了POM 模型，并用遺傳算法進(jìn)行求解。文獻(xiàn)[7]建立了地下物流優(yōu)化模型，并用遺傳算法進(jìn)行求解。文獻(xiàn)[8]構(gòu)建了多目標(biāo)優(yōu)化模型，并用蟻群算法進(jìn)行求解。文獻(xiàn)[9]構(gòu)建貨車地鐵聯(lián)運的配送路徑優(yōu)化模型，并通過改進(jìn)自適應(yīng)遺傳算法進(jìn)行求解。文獻(xiàn)[10]提出深度學(xué)習(xí)輔助啟發(fā)式樹搜索方法，實現(xiàn)加速求解問題。文獻(xiàn)[11]使用機(jī)器學(xué)習(xí)提高解的質(zhì)量，并降低計算時間。文獻(xiàn)[12]通過機(jī)器學(xué)習(xí)加速優(yōu)化模型求解并進(jìn)行驗證。文獻(xiàn)[13]通過使用機(jī)器學(xué)習(xí)生成目標(biāo)函數(shù)計算替代方法求解大規(guī)模問題。文獻(xiàn)[14]和文獻(xiàn)[15]使用蒙特卡羅仿真解決問題中的不確定性問題。文獻(xiàn)[16]引入數(shù)據(jù)驅(qū)動策略解決了蒙特卡羅仿真的高耗時問題。

綜上，該文基于貨車地鐵協(xié)同配送網(wǎng)絡(luò)，考慮貨車配送過程中時間的不確定性、貨車容量、地鐵班期及轉(zhuǎn)運花費等影響因素，建立不確定環(huán)境下以總配送成本和總配送時間為目標(biāo)的多目標(biāo)優(yōu)化模型。并設(shè)計了以蟻群算法為主體，結(jié)合蒙特卡羅仿真和Pareto理論的多目標(biāo)仿真蟻群算法，在此基礎(chǔ)上引入結(jié)合數(shù)據(jù)池和機(jī)器學(xué)習(xí)算法的數(shù)據(jù)驅(qū)動策略加速問題的求解，構(gòu)建基于數(shù)據(jù)驅(qū)動的多目標(biāo)仿真蟻群算法。

1 問題描述與模型建立

1.1 問題描述

在城市物流配送中，選擇地鐵客流平峰期進(jìn)行貨車地鐵協(xié)同配送。當(dāng)有貨物運輸需求時，貨車在寄件人處收集貨物運輸至地鐵轉(zhuǎn)運站點，由地鐵轉(zhuǎn)運到預(yù)定的卸貨轉(zhuǎn)運站點處，再由貨車進(jìn)行運輸配送。在整個過程中，地鐵線路具有固定班期，貨物在轉(zhuǎn)運站點通過地鐵運輸可能會產(chǎn)生等待時間。而在貨物轉(zhuǎn)運過程中也會產(chǎn)生一定的時間和成本。貨車地鐵協(xié)同配送模式圖如圖1 所示。

圖1 貨車地鐵協(xié)同配送模式圖

1.2 假設(shè)條件

假設(shè)1：貨物寄件人和收件人的需求都是已知的，客戶隨機(jī)分配給地鐵轉(zhuǎn)運站點；

假設(shè)2：貨車都相同，沒有里程限制，且完成配送后不用回到起點；

假設(shè)3：地鐵按固定班期發(fā)車，均有足夠容量能裝載貨物，且貨物能轉(zhuǎn)運時立刻開始轉(zhuǎn)運；

假設(shè)4：不同節(jié)點間運輸時間隨機(jī)分布。

1.3 參數(shù)與決策變量說明

參數(shù)定義：貨車地鐵協(xié)同配送網(wǎng)絡(luò)為G=(N,E)，其中，N表示節(jié)點集(NC為客戶節(jié)點，p為貨車停車點，p∈N，NS為地鐵站點，NT為轉(zhuǎn)運點集合，NC?N，NT?NS?N)，邊集為E={Eij|i,j∈N} 。當(dāng)i∈NC時，i為貨物寄件人節(jié)點，i＇為與之對應(yīng)的貨物收件人節(jié)點，滿足i＇∈NC，(i,i＇)表示貨物寄件人與收件人的組合。V為完成貨物收集的貨車集合（貨車v∈V），V＇為將貨物交付至收件人的貨車集合（貨車v＇∈V＇），R為地鐵列車合集（列車r∈R）。其他符號表示如下，其中上標(biāo)“～”表示不確定變量：

C：總配送成本；

：總配送時間；

cv：貨車v的固定成本；

xv：貨物運輸過程中使用過貨車v時為1；

Q：貨車最大容量；

?k：在節(jié)點k處地鐵的發(fā)班周期。

決策變量表示如下：

xv：貨車參與配送時取值為1，否則為0；

：貨車參與配送時取值為1，否則為0。

1.4 模型建立

該文建立的不確定環(huán)境下貨車地鐵協(xié)同配送路徑多目標(biāo)優(yōu)化模型的目標(biāo)函數(shù)為minZ=[C,]，其中，運輸成本C如式（1）所示，總時間如式（2）所示：

式（3）表示貨車的容量限制：

式（4）-（7）為流量約束：

式（8）-（10）為時間約束:

2 算法設(shè)計

該文研究的問題屬于NP-hard 問題，采用啟發(fā)式算法（蟻群算法）進(jìn)行求解。文中構(gòu)建了DDS-MSAC算法，分為MSAC 與數(shù)據(jù)驅(qū)動兩部分，MSAC 為主體，負(fù)責(zé)配送方案并尋找評估，并得到求解結(jié)果。數(shù)據(jù)驅(qū)動具有加速MSAC 求解的功能，通過數(shù)據(jù)池收集數(shù)據(jù)和機(jī)器學(xué)習(xí)建模輔助MSAC 流程中目標(biāo)值的計算，降低目標(biāo)值計算消耗時間，流程圖如圖2所示。

圖2 DDS-MSAC算法流程圖

DDS-MSAC 算法步驟如下：

1）算法初始化。

2）螞蟻移動配送路徑。

3）路徑對比和目標(biāo)值計算。標(biāo)記該次迭代中未被數(shù)據(jù)池收錄的配送方案，計算該方案的配送成本；若替代方法誤差滿足要求，使用替代方法進(jìn)行總配送時間預(yù)測，否則用蒙特卡羅仿真計算。

4）數(shù)據(jù)池歸檔。完成目標(biāo)值計算后，將其錄入數(shù)據(jù)池完成更新。

5）目標(biāo)函數(shù)計算替代方法構(gòu)建及其誤差計算。若替代方法不滿足誤差要求，利用機(jī)器學(xué)習(xí)構(gòu)建替代方法并重新統(tǒng)計模型預(yù)測誤差；否則，跳過該步驟。

6）非支配排序。利用快速非支配排序算法尋找可行解集中的Pareto 解。

7）信息素更新。

8）替代方法參數(shù)修正。如果采用替代方法計算的方案比例大于數(shù)據(jù)池的閾值要求，則使用蒙特卡羅仿真重新計算，更新數(shù)據(jù)池后，對替代方法進(jìn)行訓(xùn)練并統(tǒng)計模型預(yù)測誤差；否則，跳過該步驟。

3 結(jié)果分析

3.1 算法分析

常用于構(gòu)造目標(biāo)函數(shù)計算替代方法的機(jī)器學(xué)習(xí)算法有GPR、SVR、RF 和BP 神經(jīng)網(wǎng)絡(luò)等。分析對比不同機(jī)器學(xué)習(xí)算法在該文研究問題上的優(yōu)劣，選取性能較好的機(jī)器學(xué)習(xí)算法構(gòu)建數(shù)據(jù)驅(qū)動中的替代方法加速策略。分別設(shè)置20、30 和50 節(jié)點規(guī)模的抽象算例，運行MSAC 進(jìn)行求解，選取平均絕對誤差（MAE）、平均絕對百分比誤差（MAPE）、均方根誤差（RMSE）和時間作為評價指標(biāo)。

由表1 可知，RF 在該文研究問題情況下表現(xiàn)最優(yōu)，選擇RF 作為構(gòu)造目標(biāo)函數(shù)計算替代方法的數(shù)據(jù)驅(qū)動方法。對數(shù)據(jù)驅(qū)動加速策略進(jìn)行對比分析。分別構(gòu)造基于數(shù)據(jù)池的多目標(biāo)仿真蟻群算法（DPSMSAC）、基于RF 實現(xiàn)替代方法的多目標(biāo)仿真蟻群算法（RF-MSAC）、基于數(shù)據(jù)驅(qū)動的多目標(biāo)仿真蟻群算法（DDS-MSAC）。設(shè)置MSAC 算法實現(xiàn)平臺不變，數(shù)據(jù)池閾值取30%，MAPE 小于5%時，RF-MSAC 和DDS-MSAC 使用替代函數(shù)。

表1 不同節(jié)點規(guī)模下機(jī)器學(xué)習(xí)評價指標(biāo)結(jié)果

如圖3 所示，在不同問題規(guī)模下，DDS-MSAC 算法加速求解效果明顯，加速效率接近50%，且隨著問題規(guī)模增加時加速效率較為穩(wěn)定。因此，DDSMSAC 能夠有效求解該文研究的問題。

圖3 不同加速策略下問題求解用時

3.2 案例分析

3.2.1 案例描述

該文以重慶市軌道交通三號線及其周邊快遞站點構(gòu)建貨車地鐵協(xié)同配送實例。

如圖4 所示，設(shè)置配送實例網(wǎng)絡(luò)。貨物需從南岸區(qū)運送至渝中區(qū)或北部片區(qū)。設(shè)置貨車容量為80，車輛固定成本為100 元，地鐵單位貨物運輸成本為0.2 元/km，貨車單位貨物運輸成本為0.6 元/km，轉(zhuǎn)運成本為30 元/次，轉(zhuǎn)運時間為5 min/次，滿足運輸條件的地鐵發(fā)班間隔為30 min，各點間配送需求滿足[20,40]均布分布。

圖4 實例配送網(wǎng)絡(luò)圖

3.2.2 求解結(jié)果分析

對DDS-MSAC 算法參數(shù)進(jìn)行設(shè)置：螞蟻數(shù)量取30；迭代次數(shù)取30 次；蒙特卡羅抽樣次數(shù)取1 000次；信息素啟發(fā)因子α=0.6 ；能見度啟發(fā)因子β=0.3；信息素?fù)]發(fā)因子ρ=0.3；替代函數(shù)的使用依據(jù)為MAPE 小于5%，數(shù)據(jù)池閾值取30%。利用Matlab（R2016a）軟件編程進(jìn)行求解，部分Pareto 解如表2 所示。

由表2 中的配送方案結(jié)果可知，貨物由南岸片區(qū)運輸至北部片區(qū)采用的是貨車地鐵協(xié)同配送；而貨物由南岸片區(qū)運輸至渝中片區(qū)都采用貨車單獨配送。如果決策者對配送方案的成本更為敏感，選擇方案1；如果決策者更多考慮貨物運輸帶來的負(fù)面影響，則選擇方案2。

表2 貨車地鐵協(xié)同配送模式部分Pareto解

對比分析貨車地鐵協(xié)同配送和貨車單獨配送兩種模式，刪除實例中的地鐵轉(zhuǎn)運點，構(gòu)建貨車單獨配送路徑優(yōu)化網(wǎng)絡(luò)，采用DDS-MSAC 進(jìn)行求解，求解結(jié)果如表3 所示。

表3 貨車單獨配送模式部分Pareto解

由表3 可知，貨車地鐵協(xié)同配送模式比貨車單獨配送模式有明顯的優(yōu)勢。在貨物配送過程中采用了運輸價格較低的地鐵，使得總配送成本下降。同時因為地鐵運輸速度快、延誤少，減少了總配送時間。在貨車地鐵協(xié)同配送模式中，長距離運輸由地鐵完成，貨車負(fù)責(zé)貨物的收集和轉(zhuǎn)運后的交付，貨車的行駛距離更短，排放少，對環(huán)境更友好。

3.2.3 參數(shù)敏感性分析

對貨車容量和地鐵發(fā)班間隔兩個參數(shù)分別進(jìn)行討論。實例和算法參數(shù)設(shè)置保持不變，改變貨車容量下實例求解結(jié)果如表4 所示。

表4 不同貨車容量下求解結(jié)果

由表4 結(jié)果可知，隨著貨車容量增加，貨車最大行駛距離增加，貨車數(shù)量和總配送成本降低，而配送時間在貨車容量為120 時最小，最小載貨率在貨車容量為100 時取得。因此，在決策過程中，除了考慮成本和時間外，還需要考慮貨車容量和貨車載貨率，減少運力浪費。

改變地鐵發(fā)班間隔，求解結(jié)果如表5 所示。

表5 不同發(fā)班間隔下求解結(jié)果

表5 中，隨著發(fā)班間隔的增加，地鐵配送貨物數(shù)量增加，總配送時間增加；但由于貨物配送決策的發(fā)生變化，總配送成本不一定增加。因此，在決策過程中，當(dāng)?shù)罔F運力余量較大時，可以通過調(diào)整發(fā)班間隔將貨物集中進(jìn)行配送，降低貨物運輸對地鐵客運的影響。

4 結(jié)束語

該文綜合考慮貨車運輸時間的不確定性和地鐵班期限制，建立了貨車地鐵協(xié)同配送的路徑多目標(biāo)優(yōu)化模型。通過基于數(shù)據(jù)驅(qū)動的多目標(biāo)蟻群算法，對問題進(jìn)行有效求解，為貨車地鐵協(xié)同配送提供實踐參考，實現(xiàn)總配送時間和成本最少。該文設(shè)計了一種新的DDS-MSAC 算法，并分析驗證了算法的有效性。以重慶市軌道交通三號線和其周邊部分快遞網(wǎng)點為實例，檢驗?zāi)Ｐ偷膶嵺`可行性，同時驗證了Pareto 理論在解決該問題上的優(yōu)勢。通過實例對貨車地鐵協(xié)同配送模式和單一貨車配送模式進(jìn)行比較，得出貨車地鐵協(xié)同配送模式在總配送時間、成本等方面都有明顯優(yōu)化，同時發(fā)現(xiàn)貨車容量和發(fā)車間隔都會對配送結(jié)果產(chǎn)生影響。