周芳汀，張 錦*,b，周國華

(西南交通大學a.交通運輸與物流學院；b.綜合交通運輸智能化國家地方聯(lián)合工程實驗室；c.經(jīng)濟管理學院，成都610031)

0 引 言

多頻次、高時效性的物流配送是現(xiàn)代城市運營的重要組成部分.但客貨運需求的增長與道路資源的緊張造成的交通擁堵問題日益凸顯，很多城市為緩解交通擁堵對貨運車輛采取的限行措施又降低了配送及時性.因此，探索基于地鐵的城市配送服務等新型可持續(xù)發(fā)展的配送模式十分必要[1].在地鐵網(wǎng)絡化運營時代，人們將地鐵作為日常出行的主要方式之一，可減少道路交通的擁堵；貨物通過地鐵運載使資源利用率最大化的同時分流一部分道路流量《.“十三五”交通領域科技創(chuàng)新專項規(guī)劃》提出針對大城市中心區(qū)域之間、中心區(qū)域與市郊之間生活物資等運輸需求及特征，開發(fā)適于城軌客運空檔期專用的智能及經(jīng)濟型載運工具.地鐵配送網(wǎng)絡正是充分利用地鐵連通商業(yè)中心和集中居住區(qū)的網(wǎng)絡能力，在保證客運需求的前提下挖掘空閑運輸能力，針對中小型包裹及低密度高附加值貨物運輸需求，融合道路交通網(wǎng)，實現(xiàn)地鐵列車和城市配送車輛的接力，構(gòu)建新型城市配送網(wǎng)絡.地鐵站點是銜接地鐵網(wǎng)和道路交通網(wǎng)的節(jié)點，從道路交通網(wǎng)進入地鐵網(wǎng)的為進站點，反之為出站點，如圖1所示.

圖1 地鐵配送網(wǎng)絡示意圖Fig.1 Subway distribution network diagram

針對地鐵配送服務，日本和英國等國家從理論及實踐上驗證了地鐵配送系統(tǒng)的可行性和經(jīng)濟性.在英國紐卡斯爾，研究人員通過基于事件的仿真模型的測試，得到地鐵配送貨物是城市配送可行替代方案的結(jié)論[2].YAMATO已將地鐵配送貨物付之于實踐，日本札幌于2010年啟動了地鐵配送服務，車廂內(nèi)設置了專門放置貨物的區(qū)域[3]，京都于2011年啟動了輕軌貨運服務，每天早晨在乘客繁忙期之前使用現(xiàn)有車廂運送貨物[4]，該服務可以有效地代替常規(guī)卡車運輸.現(xiàn)有文獻針對地鐵配送問題的研究較少.Masson等[5]研究了整合客運和貨運系統(tǒng)背景下的混合城市交通問題，利用1條公交線路將貨物從配送中心運送到7個站點，再用三輪車將貨物從站點運送至目的地.這項研究沒有考慮列車時間表及客戶時間窗的限制.Ghilas等[6]針對公交車、地鐵等預定線路研究了帶時間窗的裝卸貨問題，其進出站點為線路的起終點，不涉及站點的客戶分配，且沒有考慮運輸距離對預定線路成本的影響.

不同于傳統(tǒng)的帶硬時間窗的車輛路徑問題[7]，本文同時考慮了客戶收貨時間窗和列車發(fā)車時間表，整合了兩種運輸方式，且配送路徑是開放的.將1趟上(下)行列車稱作1個地鐵列車班次.為綜合優(yōu)化地鐵列車班次的客戶分配、出站點的客戶分配及末端配送路徑，本文構(gòu)建了帶時間窗的地鐵網(wǎng)絡路徑優(yōu)化模型.

1 問題描述與建模

1.1 問題描述與符號說明

問題描述為：物資自配送中心由貨車配送至進站點，再通過地鐵配送至多個出站點，即地鐵配送，最后用城市配送車輛從出站點配送至客戶，為末端配送.這些車輛必須在客戶收貨時間窗內(nèi)開始服務，配送完成后不用返回起始點.地鐵線路和列車發(fā)車時間表既定，配送中心、進站點、出站點、客戶點的位置坐標已知，客戶點的貨物需求和收貨時間窗已知，配送車輛的負載能力一定.

模型假設如下：

(1)貨物離開配送中心后，由指定的進站點進入地鐵系統(tǒng)；

(2)地鐵列車按照時間表發(fā)車，每班列車均能裝載貨物，且沒有容量限制；

(3)地鐵線路運輸貨物的同時不會影響乘客服務質(zhì)量；

(4)出站點沒有存儲功能，貨物到達出站點后需要立即分揀并裝入配送車輛；

(5)客戶沒有固定被分配給某個出站點；

(6)貨物送達時間必須滿足客戶的硬時間窗限制，送貨人員不能早到，也不能晚到.

VD、VD′、VK、VC分別為配送中心d、進站點d′、出站點k、客戶j的集合，d∈VD,d′∈VD',k∈VK,j∈VC；VR為地鐵列車班次r的集合，r∈VR；VV為城市配送車輛v的集合，v∈VV.i為末端配送的節(jié)點，i∈VK?VC；jk+為鄰接出站點k的客戶，jk+∈VC.qj為客戶j的需求量，ej、lj分別為客戶j允許的最早、最晚服務開始時間，sj為在客戶j的服務時間；QV為配送車輛v的容量限制，cv為配送車輛v的固定運營成本，cij、tiv j分別為末端配送路徑(i,j)的運輸成本和行駛時間；fk為貨物在出站點k所需的轉(zhuǎn)運時間；θdk為配送中心d到出站點k運送每單位貨物的成本，包括配送中心d到進站點的貨車運輸成本及該站點到出站點k的地鐵配送成本；tdd′為配送中心d到進站點d′的行駛時間，為列車班次r由進站點d′到出站點k的行駛時間，為地鐵配送路徑上第r班列車離開進站點d′的時間，表示客戶j分配給出站點k由列車班次r提供服務所花費的時間，包括等待時間和列車行駛時間；M是1個大的正整數(shù).

1.2 模型建立

其中，式(1)為目標函數(shù)，表示最小化總成本，第1項配送中心到出站點的運輸成本，包括到進站點的貨車運輸成本和站點間的地鐵配送成本，第2項末端配送成本，第3項配送車輛使用成本；式(2)表示每輛車對每個客戶只能訪問1次；式(3)表示使用配送車輛的數(shù)量；式(4)為配送車輛負載限制；式(5)表示若某客戶的需求用了d到k的地鐵線路，那么配送車輛應在k處轉(zhuǎn)運；式(6)表示客戶j的需求只有到達出站點k，才能進行末端配送；式(7)表示鄰接出站點k的客戶jk+服務開始時間限制；式(8)表示1條線路上兩鄰接客戶i,j服務時間限制；式(9)為客戶j服務開始時刻和終止時刻的關系；式(10)為客戶j時間窗約束；式(11)和式(12)表示決策變量的非負整數(shù)約束；式(13)和式(14)表示決策變量的0-1約束.

2 求解算法

迭代局部搜索(Iterated Local Search,ILS)能夠很好地求解車輛路徑問題[8]，ILS-RVND是基于ILS的啟發(fā)式算法，該算法在局部搜索階段使用具有隨機鄰域排序的可變鄰域下降過程(Randomized Variable Neighborhood Descent,RVND).Penna等[9]已證實在ILS中使用RVND作為局部搜索算法，能得到較好的解.

2.1 算法思路

ILS-RVND算法先生成初始解，然后使用隨機變鄰域局部搜索算法對解進行優(yōu)化，如果得到的解比當前最優(yōu)解好，則替換它，再通過輕微的擾動得到1個新的解，即下一次迭代的起點.本文在局部搜索之前增加了調(diào)節(jié)列車班次的操作，使改進的算法適應于帶時間窗的地鐵配送網(wǎng)絡路徑優(yōu)化問題的求解.

2.2 算法設計要素

(1)構(gòu)建初始解.

城市配送車輛的初始分配方案通過對所有客戶構(gòu)成的隨機排列進行合理的分割實現(xiàn)，按隨機排列的順序?qū)⒖蛻舴峙渲粮鱾€出站點，獲得末端配送方案；計算各出站點轉(zhuǎn)運量，按照貪婪原則分配地鐵列車班次，設計地鐵配送方案，從而得到初始解.

(2)調(diào)節(jié)列車班次.

隨機改變?nèi)我荒┒伺渌吐窂綄牧熊嚢啻味x為調(diào)節(jié)列車班次，執(zhí)行該操作直到找到最優(yōu)解，若有改進，則接受.

(3)局部搜索.

局部搜索操作被應用于鄰域中的局部改善，包括路徑內(nèi)(Intra-Route)搜索算子2-Opt、Intraswap、Intra-move，以及路徑間(Inter-Route)搜索算子2-Opt*、Inter-swap、Inter-move，如圖2所示.

圖2 局部搜索示意圖Fig.2 Local search diagram

每次生成1個可行的初始解后，隨機選取1個Inter-Route搜索算子，執(zhí)行算子的鄰域搜索找到最優(yōu)解，若有改進，則進入Intra-Route搜索過程，隨機選取1個Intra-Route算子，若有改進，則繼續(xù)進行Intra-Route搜索；若沒有改進，從NL′中去掉該算子，繼續(xù)進行Intra-Route搜索，直到NL′為空.而若執(zhí)行Inter-Route搜索算子解沒有被改進，則從NL中去掉該算子，繼續(xù)進行Inter-Route搜索，直到NL為空，1次迭代過程的局部搜索操作結(jié)束.

(4)擾動機制.

局部搜索后需要對當前解進行1個小的擾動，得到新的起始點，從而進入下一代局部搜索.這里使用Split和Merge兩種擾動機制，其中Split是將1條路徑拆分成更短的路徑，Merge則是將2條路徑合并為1條.

ILS-RVND算法流程如圖3所示，其中Imax為迭代搜索的最大迭代次數(shù).

圖3 ILS-RVND算法流程圖Fig.3 ILS-RVND algorithm flowchart

3 實例計算與結(jié)果分析

3.1 實例數(shù)據(jù)

某企業(yè)需要從成都市新都配送中心向二環(huán)內(nèi)20個客戶運送貨物，客戶從商業(yè)住宅點中抽取，地理位置服從均勻分布，客戶需求量服從[5,15]的均勻分布.地鐵3號線作為配送線路，駟馬橋、市二醫(yī)院、春熙路、省體育館4個站為出站點.新都配送中心到進站點的裝運時間是6.2 min，單位貨物的裝運成本為0.3.進站點到出站點的距離和運行時間分別為：駟馬橋(10.9 km/16 min)，市二醫(yī)院(15 km/24 min)，春熙路(15.9 km/26 min)，省體育館(19.1 km/32 min)[1].在3 h區(qū)間內(nèi)，每10 min有1班列車可用于運輸貨物，可選的列車班次共18趟，VR={1,2,3,…,18}，客戶時間窗如表1所示.

表1 客戶時間窗Table 1 Customer time windows

根據(jù)百度地圖API得到出站點到客戶點及客戶點相互之間的距離，配送車輛的平均速度為15 km/h，容量為60.單位貨物單位距離地鐵配送成本、單位距離末端配送成本、車輛固定運營成本分別為0.1、2、30，轉(zhuǎn)運時間和客戶服務時間分別為5 min、1 min.

3.2 求解結(jié)果分析

本文采用標準GA算法[10]和ILS-RVND算法分別求解，各運行30次得到兩種算法的優(yōu)化結(jié)果對比如表2所示.雖然GA具有更短的運算時間，但ILS-RVND能夠獲得更高質(zhì)量的最優(yōu)解，且經(jīng)過多次反復試驗，結(jié)果顯示，ILS-RVND獲得最優(yōu)解的穩(wěn)定性較GA更好，驗證了本文算法的有效性.

基于上述實例數(shù)據(jù)與ILS-RVND算法，計算了貨車單獨配送時的最優(yōu)方案，得到兩種配送模式最優(yōu)方案的對比如表3所示，其配送路徑信息如表4所示.0表示配送中心，A、B、C、D分別表示出站點駟馬橋、市二醫(yī)院、春熙路和省體育館.每條末端配送路徑從可選列車班次里選中1個列車班次，選中的列車班次形成1個集合.貨車單獨配送時，未按時配送的需求點有5個，而在基于地鐵的城市配送模式下，貨物均在客戶要求的30 min時間窗內(nèi)送達客戶手中，且各項指標均得到了較大的改善.可見，地鐵配送網(wǎng)絡配送成本低，準時性高，配送車輛行駛距離短，能滿足比貨車單獨配送更精準的服務需求.

表2 兩種算法優(yōu)化結(jié)果比較Table 2 Comparison of optimization results for two algorithms

表3 兩種配送模式最優(yōu)方案比較Table 3Comparison of optimal solutions for two distribution modes

3.3 敏感性分析

根據(jù)不同配送車輛容量QV及不同可運貨列車開行間隔，得到的最優(yōu)方案如表5和表6所示.車載率為某配送車輛服務的客戶需求量qj之和與該配送車輛最大容量QV的比值，1次服務時間窗個數(shù)是指配送車輛1次配送路徑中所服務的客戶時間窗個數(shù).每個配送車輛的行駛距離、車載率、1次服務時間窗個數(shù)不同，通過對比得到其最大的行駛距離、最小的車載率及最多的1次服務時間窗個數(shù).

表4 兩種配送模式路徑比較Table 4 Comparison of routing for two distribution modes

表5 不同配送車輛容量QV的結(jié)果Table 5 Results of different capacities of terminal distribution vehicles

由表5可得，配送車輛容量越大，總成本逐漸降低，所需列車班次減少，配送車輛數(shù)目減少，最大的行駛距離增加，最小的車載率降低，最多的1次服務時間窗個數(shù)增多.這時可按照時間窗先后次序配送更多數(shù)量的貨物，與實際情況相符.配送車輛容量大于60時，總成本減少不明顯，且部分配送車輛利用率較低，這說明當前情況下無需使用容量更大的配送車輛.未來可采用多車型車輛配送，以最大化利用資源，進一步減少成本.

表6 不同可運貨列車開行間隔TR的結(jié)果Table 6 Results of different interval between freight trains

由表6可得，增加可運貨列車的開行間隔，由于可選的列車班次有所不同，并不一定增加了總成本.開行間隔由10 min增加到40 min，4、11班列車的貨物多集中到了第9班；而由20 min增加到60 min，第11班列車的貨物集中到了第7班.可運貨列車開行間隔為60 min時，總成本相對較低，僅使用兩班次列車完成地鐵配送的任務，且列車載貨量較均衡，對客運質(zhì)量影響較小.因此，當?shù)罔F列車容量允許時，可盡量將貨物集中到某些班次，以提高列車滿載率，減少對客運質(zhì)量的影響.在貨運需求量較大，客運量較小的時段，應適當增大客運列車運貨的比例，亦可在客運列車間隙加開貨運專用列車.

4 結(jié) 論

本文構(gòu)建了帶時間窗的地鐵配送網(wǎng)絡路徑優(yōu)化模型，設計了ILS-RVND算法.以單條地鐵線路運輸貨物為例，驗證了模型和算法的實用性和有效性.研究表明，地鐵配送網(wǎng)絡能提供比貨車單獨配送更精準的服務，具有更高的綜合績效.同時也有助于配送企業(yè)根據(jù)列車發(fā)車時間表、客戶時間窗、配送需求量合理分配列車運貨班次和出站點的客戶，優(yōu)化地鐵配送網(wǎng)絡的路徑.

若存在多條發(fā)車頻率不同或客流量不均衡的地鐵線路時，需進一步考慮列車剩余能力、站點存儲能力、列車在站點的最大等待時間等約束條件，深入探討多條線組合的地鐵配送網(wǎng)絡路徑優(yōu)化問題，將是今后研究的重要方向.