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

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

0 引 言

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

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

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

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

1 問題描述與建模

1.1 問題描述與符號說明

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

模型假設(shè)如下：

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

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

(3)地鐵線路運(yùn)輸貨物的同時(shí)不會(huì)影響乘客服務(wù)質(zhì)量；

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

(5)客戶沒有固定被分配給某個(gè)出站點(diǎn)；

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

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

1.2 模型建立

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

2 求解算法

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

2.1 算法思路

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

2.2 算法設(shè)計(jì)要素

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

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

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

隨機(jī)改變?nèi)我荒┒伺渌吐窂綄?yīng)的列車班次定義為調(diào)節(jié)列車班次，執(zhí)行該操作直到找到最優(yōu)解，若有改進(jìn)，則接受.

(3)局部搜索.

局部搜索操作被應(yīng)用于鄰域中的局部改善，包括路徑內(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個(gè)可行的初始解后，隨機(jī)選取1個(gè)Inter-Route搜索算子，執(zhí)行算子的鄰域搜索找到最優(yōu)解，若有改進(jìn)，則進(jìn)入Intra-Route搜索過程，隨機(jī)選取1個(gè)Intra-Route算子，若有改進(jìn)，則繼續(xù)進(jìn)行Intra-Route搜索；若沒有改進(jìn)，從NL′中去掉該算子，繼續(xù)進(jìn)行Intra-Route搜索，直到NL′為空.而若執(zhí)行Inter-Route搜索算子解沒有被改進(jìn)，則從NL中去掉該算子，繼續(xù)進(jìn)行Inter-Route搜索，直到NL為空，1次迭代過程的局部搜索操作結(jié)束.

(4)擾動(dòng)機(jī)制.

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

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

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

3 實(shí)例計(jì)算與結(jié)果分析

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

某企業(yè)需要從成都市新都配送中心向二環(huán)內(nèi)20個(gè)客戶運(yùn)送貨物，客戶從商業(yè)住宅點(diǎn)中抽取，地理位置服從均勻分布，客戶需求量服從[5,15]的均勻分布.地鐵3號線作為配送線路，駟馬橋、市二醫(yī)院、春熙路、省體育館4個(gè)站為出站點(diǎn).新都配送中心到進(jìn)站點(diǎn)的裝運(yùn)時(shí)間是6.2 min，單位貨物的裝運(yùn)成本為0.3.進(jìn)站點(diǎn)到出站點(diǎn)的距離和運(yùn)行時(shí)間分別為：駟馬橋(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班列車可用于運(yùn)輸貨物，可選的列車班次共18趟，VR={1,2,3,…,18}，客戶時(shí)間窗如表1所示.

表1 客戶時(shí)間窗Table 1 Customer time windows

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

3.2 求解結(jié)果分析

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

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

表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ùn)貨列車開行間隔，得到的最優(yōu)方案如表5和表6所示.車載率為某配送車輛服務(wù)的客戶需求量qj之和與該配送車輛最大容量QV的比值，1次服務(wù)時(shí)間窗個(gè)數(shù)是指配送車輛1次配送路徑中所服務(wù)的客戶時(shí)間窗個(gè)數(shù).每個(gè)配送車輛的行駛距離、車載率、1次服務(wù)時(shí)間窗個(gè)數(shù)不同，通過對比得到其最大的行駛距離、最小的車載率及最多的1次服務(wù)時(shí)間窗個(gè)數(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次服務(wù)時(shí)間窗個(gè)數(shù)增多.這時(shí)可按照時(shí)間窗先后次序配送更多數(shù)量的貨物，與實(shí)際情況相符.配送車輛容量大于60時(shí)，總成本減少不明顯，且部分配送車輛利用率較低，這說明當(dāng)前情況下無需使用容量更大的配送車輛.未來可采用多車型車輛配送，以最大化利用資源，進(jìn)一步減少成本.

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

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

4 結(jié) 論

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

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