馬 利，王鵬翔，李海鷹，王 瑩

（1.中國鐵路北京局集團(tuán)有限公司 貨運處，北京 100860；2.北京交通大學(xué) 軌道交通控制與安全國家重點實驗室，北京 100044；3.北京交通大學(xué) 交通運輸學(xué)院，北京 100044)

隨著國家經(jīng)濟(jì)結(jié)構(gòu)轉(zhuǎn)型升級，鐵路部門于2014年開行了環(huán)形班列，專門受理區(qū)域零散貨物快運業(yè)務(wù)。環(huán)形班列為區(qū)域經(jīng)濟(jì)的發(fā)展起到了良好的促進(jìn)作用，但在運營過程中仍存在一些問題，一是班列在運量小的車站停站過多，影響了環(huán)形班列的運輸時效；二是班列開行時間與貨流需求配合難度大，導(dǎo)致貨物在車站的等待裝車時間過長。這些問題降低了班列運輸?shù)臅r效性，一定程度上影響了環(huán)形班列對貨主的吸引力，因而有必要對環(huán)形班列開行方案進(jìn)行優(yōu)化，提升市場競爭力。

環(huán)形班列提出的時間較晚，專門針對其開行方案的研究基本處于空白階段，普通快運班列開行方案的研究主要集中在班列開行頻率和運輸路徑的選擇上，涉及到班列開行具體時間的研究較少。Jeong[1]以最小成本為目標(biāo)函數(shù)建立模型，考慮了運輸成本問題，對開行進(jìn)路的選擇、開行數(shù)量的確定等問題進(jìn)行了研究。張文斌[2]利用復(fù)雜網(wǎng)絡(luò)的方法對行包運輸網(wǎng)絡(luò)進(jìn)行了研究和規(guī)劃。李昂[3]考慮站點之間的距離，以“門到門”廣義費用最小為目標(biāo)對環(huán)形班列停站方案進(jìn)行了優(yōu)化，解決了班列停站過密的問題。趙婷[4]考慮了貨源情況、路網(wǎng)能力、編組輛數(shù)、經(jīng)濟(jì)條件等影響因素下的開行方案編制問題，對班列的開行頻率和停站方案進(jìn)行了優(yōu)化。王瑩等[5]對路網(wǎng)條件下多方式、多模式的“五定”班列開行方案的優(yōu)化方法進(jìn)行了研究。李海鷹等[6]以動態(tài)服務(wù)網(wǎng)絡(luò)為基礎(chǔ)，引入了貨物發(fā)送、到達(dá)和運輸時限3個時間窗對班列運到時限進(jìn)行約束，以利潤最大為目標(biāo)建立了班列開行方案優(yōu)化模型，并設(shè)計了相應(yīng)的啟發(fā)式算法進(jìn)行求解。楊毅凡[7]綜合考慮了運送的需求量最大化、鐵路運營效益最大化、貨主成本最小化3個目標(biāo)下開行方案的編制問題。張玉召等[8]以貨運量最大化及貨主支出運輸成本最小化為目標(biāo)，構(gòu)建快捷貨物列車開行方案的多目標(biāo)優(yōu)化模型，實現(xiàn)了貨流在可選走行路徑上列車內(nèi)的分配。李小波[9]按不同班列產(chǎn)品分析影響快運班列運輸時效性的主要因素，提出了提高鐵路快運班列運輸時效性的方法。綜上，在現(xiàn)有研究的基礎(chǔ)上，以動態(tài)服務(wù)網(wǎng)絡(luò)為基礎(chǔ)，重點考慮班列的時效性，對環(huán)形班列開行方案優(yōu)化方法進(jìn)行研究。

1 鐵路環(huán)形班列動態(tài)服務(wù)網(wǎng)絡(luò)構(gòu)建

每趟環(huán)形班列都可以為其所經(jīng)過的站點提供運輸服務(wù)，如果將這些運輸服務(wù)看作站點之間的弧，那么班列開行方案編制問題就可以轉(zhuǎn)化為動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計問題。

用G= (N，A)來表示動態(tài)服務(wù)網(wǎng)絡(luò)，其中N為網(wǎng)絡(luò)中的節(jié)點集合，表示帶有時間屬性的站點；A為網(wǎng)絡(luò)中弧段的集合，是環(huán)形班列提供的運輸服務(wù)集合，包括運行弧As和停站弧Aw。運行弧表示班列在線路上運行，其弧長表示兩節(jié)點之間的運行時間；停站弧表示班列在車站停站，其弧長表示班列在該站的停留時間。

動態(tài)服務(wù)網(wǎng)絡(luò)構(gòu)建方法如圖1所示，環(huán)形班列基礎(chǔ)路網(wǎng)如圖1a所示，在其基礎(chǔ)上簡單建立的環(huán)形班列動態(tài)服務(wù)網(wǎng)絡(luò)如圖1b所示。在圖1b中，同一列的點代表同一站點的不同時間狀態(tài)，同一行的點代表同一時間狀態(tài)下的不同站點，黑色實線代表運行弧，黑色虛線代表停站弧。A與A'都表示中心站，A表示始發(fā)狀態(tài)下的A站，A'表示終到狀態(tài)下的A站。網(wǎng)絡(luò)中的弧首尾相連構(gòu)成一個班列運輸路徑，圖中的路徑表示t1時刻由A站出發(fā)，最終在t16時刻返回A站的班列，運行途中在中間站點B，C，E分別停留了一段時間進(jìn)行裝卸作業(yè)，停站的時刻依次為t5，t9和t13。

通過這種方式可以將班列的開行方案用上述動態(tài)服務(wù)網(wǎng)絡(luò)來表示，對于一個特定的服務(wù)網(wǎng)絡(luò)，可以通過配流，得到各個需求的運輸路徑，從而計算貨物運輸過程中的各項費用指標(biāo)，而不同的網(wǎng)絡(luò)結(jié)構(gòu)代表不同的開行方案，其配流結(jié)果不同，各項費用指標(biāo)也不同。開行方案優(yōu)化問題，對應(yīng)在服務(wù)網(wǎng)絡(luò)上則是在給定運輸物理起點、終點條件下，利用網(wǎng)絡(luò)設(shè)計優(yōu)化的理論，獲得使費用和收入等指標(biāo)最優(yōu)的班列運輸路徑，從而得到一個快捷、經(jīng)濟(jì)、高效的班列開行方案。

2 鐵路環(huán)形班列服務(wù)網(wǎng)絡(luò)優(yōu)化模型

環(huán)形班列服務(wù)網(wǎng)絡(luò)設(shè)計就是確定各班列在網(wǎng)絡(luò)上的運輸路徑，通過減少貨物等待裝車時間及旅行時間來提高班列運輸?shù)臅r效性，因而在模型中引入出發(fā)時間窗和到達(dá)時間窗對等待裝車時間和旅行時間進(jìn)行約束，對超出約束的部分進(jìn)行懲罰，從而達(dá)到提高班列時效性的目的。據(jù)此，以總利潤最大為目標(biāo)，以網(wǎng)絡(luò)容量為約束，以服務(wù)弧是否被構(gòu)建及各站之間的運輸需求是否被滿足為決策變量構(gòu)建環(huán)形班列服務(wù)網(wǎng)絡(luò)優(yōu)化模型。

圖1 動態(tài)服務(wù)網(wǎng)絡(luò)構(gòu)建方法Fig.1 Establishment of dynamic service network

式中：v為列車最大編掛輛數(shù)；e為車輛標(biāo)準(zhǔn)載重；S為班列集合；A為服務(wù)網(wǎng)絡(luò)中弧的集合；K為OD需求集合；dk表示需求k的需求量大??；P為需求經(jīng)過的路徑集合；ρ為運輸收入；c為班列固定成本；μ為需求不滿足時的懲罰費用；Q為周期內(nèi)OD需求總量；φk和τ?k分別為出發(fā)時間窗懲罰函數(shù)和到達(dá)時窗罰函數(shù)；為0-1變量，當(dāng)取值為1時表示服務(wù)弧a屬于班列s；?a為0-1變量，當(dāng)取值為1時表示弧a是始發(fā)弧；為0-1變量，當(dāng)取值為1時表示需求k被路徑p運送；la為弧a對應(yīng)的物理區(qū)段的里程；為0-1變量，當(dāng)取值為1時表示弧a屬于路徑表示路徑p的里程，其中，模型的決策變量為前者決定了班列的發(fā)車時間和停站方案，后者決定了在特定網(wǎng)絡(luò)結(jié)構(gòu)下各弧段的流量分配情況。

⑴ 式表示模型目標(biāo)為利潤最大化，該利潤由運輸收入、班列固定成本、時間窗懲罰費用和未完成周期內(nèi)全部需求的懲罰費用4部分組成。在目標(biāo)函數(shù)中引入貨物的發(fā)送和到達(dá)時限懲罰項對等待裝車時間和旅行時間進(jìn)行約束，盡可能地滿足貨主對于運到時限的要求。其中，φk和τ?k分別為出發(fā)時間懲罰和到達(dá)時間懲罰，具體取值如下。①出發(fā)時間懲罰。出發(fā)時間懲罰是指貨物必須要在規(guī)定的時間段內(nèi)發(fā)出，否則就給予一定的懲罰。出發(fā)時間懲罰能夠有效地對貨物在車站等待裝車時間進(jìn)行約束，計算公式為其中，tps為需求k的實際發(fā)車時間；為需求k的期望發(fā)車時間，不同種類的需求具有不同的期望發(fā)車時間；ω為出發(fā)懲罰系數(shù)。②到達(dá)時間懲罰。到達(dá)時間懲罰是指貨物必須要在規(guī)定的時間內(nèi)到達(dá)，否則就要給予一定的懲罰，在出發(fā)時間懲罰的基礎(chǔ)上對到達(dá)時間進(jìn)行懲罰，能夠有效地對旅行時間進(jìn)行約束，從而減少班列不必要的停站，計算公式其中，tpe為需求k的實際到達(dá)時間；Tak為需求k的期望到達(dá)時間，不同種類的需求具有不同的期望到達(dá)時間；σ為到達(dá)懲罰系數(shù)。⑵ 式是服務(wù)弧的邏輯約束，表示網(wǎng)絡(luò)上的服務(wù)弧必須屬于班列運輸路徑的一部分。⑶ 式為班列容量約束，表示班列上裝載的運量不超過班列的運輸能力。⑷—⑸ 式是邏輯約束。⑷ 式表示總運量不能超過總運輸需求。⑸ 式表示變量取值為 0或1。

3 算法與實例分析

3.1 求解算法

上述模型是一個大規(guī)?；旌戏蔷€性整數(shù)規(guī)劃模型，傳統(tǒng)的數(shù)學(xué)優(yōu)化方法求解較為困難，根據(jù)問題的特性，將開行方案優(yōu)化拆分為“停站方案優(yōu)化”和“發(fā)車時間優(yōu)化”2個階段順次計算，分別設(shè)計遺傳算法和啟發(fā)式算法進(jìn)行求解，進(jìn)而得出最優(yōu)的班列開行方案，算法流程如圖2所示。

圖2 算法流程圖Fig.2 Flow chart of algorithm

3.1.1 確定停站方案

由于停站方案的決策變量為0-1變量，采用遺傳算法編碼方便，適合求解。結(jié)合問題特征，采用0-1變量對染色體進(jìn)行編碼，1代表在該站停站，0代表在該站不停站，基因編碼如圖3所示，適應(yīng)度函數(shù)采用模型中建立的目標(biāo)函數(shù)，交叉方式采用單點交叉，種群規(guī)模設(shè)為32，交叉概率設(shè)為0.3，變異概率設(shè)為0.1，當(dāng)種群適應(yīng)度函數(shù)趨于穩(wěn)定時終止算法。遺傳算法流程如下。

步驟1：生成初始染色體種群，包含16條染色體。

步驟2：按次序計算每一條染色體的適應(yīng)度函數(shù)。

步驟3：判斷是否達(dá)到終止條件，是則轉(zhuǎn)到步驟6，否則繼續(xù)向下執(zhí)行。步驟4：通過輪盤賭算法對染色體進(jìn)行選擇。步驟5：對染色體進(jìn)行交叉、變異以產(chǎn)生新一代種群，轉(zhuǎn)到步驟2。

步驟6：算法終止，種群中適應(yīng)度函數(shù)最大的染色體對應(yīng)的停站方案即是最優(yōu)停站方案。

3.1.2 班列發(fā)車時間優(yōu)化

考慮到班列可選的發(fā)車時間較多，研究采用逐步逼近的思想，設(shè)計了基于“二分法”的啟發(fā)式方法，通過反復(fù)迭代逐步逼近最優(yōu)解。首先，將周期內(nèi)每一天劃分為2個等分時間段，規(guī)定周期內(nèi)每趟班列的發(fā)車時間只能是時間段的下限，即12 : 00或24 : 00，通過枚舉法計算出周期內(nèi)班列發(fā)車時間的最優(yōu)組合；在此基礎(chǔ)上，將每趟班列發(fā)車時間所在的時間段繼續(xù)細(xì)分為2個等分時間段，通過枚舉法找出此精度下最優(yōu)的發(fā)車時間組合，循環(huán)往復(fù)，直到滿足精度要求為止。“二分法”流程如下。

步驟1：初始狀態(tài)，時間段長度為1 d，沒有進(jìn)行拆分，每趟班列發(fā)車時間默認(rèn)為24 : 00。

步驟2：將時間段拆分為更小的2個時間段，拆分后的2個時間段的長度必須為服務(wù)網(wǎng)絡(luò)時間段長度的整數(shù)倍，拆分時保證拆分后的時間段長度相同或相近。

步驟3：通過枚舉法計算出本精度條件下最優(yōu)發(fā)車時間組合。

步驟4：判斷是否達(dá)到精度要求，是則轉(zhuǎn)到步驟6，否則繼續(xù)下一步。

圖3 基因編碼Fig.3 Gene encoding

步驟5：選取步驟3得到的每趟班列發(fā)車時間，將其所在的時間段作為下輪循環(huán)拆分的時間段，轉(zhuǎn)到步驟2。

步驟6：算法終止，所得到的發(fā)車時間組合即為要求精度下的最優(yōu)發(fā)車時間組合。

3.2 實例分析

采用京津冀環(huán)形班列北逆環(huán)線的數(shù)據(jù)進(jìn)行實例驗證，北逆環(huán)線共41個站點，里程1 379 km，原有方案固定每日22 : 55發(fā)車，開行頻率為每日1列，在41個站點均進(jìn)行停站作業(yè)。根據(jù)現(xiàn)有環(huán)形班列各站的運量數(shù)據(jù)，經(jīng)初步測算，設(shè)計一個以3 d為周期的班列開行方式，即每天仍然開行1列，但前2天的班列僅?？坎糠周囌?，第3天的班列在41個站點均停站。在該環(huán)形班列開行方式下，每3天為一個循環(huán)，開行2列擇站停和1列站站停列車?；谠撻_行方式，運用優(yōu)化方法，對其具體的停站方案和每日發(fā)車時間進(jìn)行優(yōu)化?？紤]到第3天開行的班列最晚第5天才能返回，因而求解5天內(nèi)班列在各站的到發(fā)時刻，如圖4所示，實線為前3天發(fā)出的列車，屬于周期內(nèi)班列，需為其確定在各站的到發(fā)時刻，虛線為后2天發(fā)出的列車，屬于下一周期，計算時不予考慮。

不同種類的需求對運輸時效性有不同的要求，按時效性高低將其分為3類，并將其出發(fā)時間窗分別設(shè)為起票后的2 h，4 h和6 h；需求的到達(dá)時間窗統(tǒng)一設(shè)為貨物最快到站后的6 h，最快到站指貨物通過直達(dá)的運輸方式到達(dá)目的站點。模型中的相關(guān)參數(shù)取值如表1所示。

原方案停站數(shù)量41個，采用遺傳算法對停站方案進(jìn)行優(yōu)化，第1天停站數(shù)量減少了18個，第2天停站數(shù)量減少了17個，停站方案優(yōu)化結(jié)果如表2所示。從計算結(jié)果可以看出，與優(yōu)化前相比，運輸利潤提高了4.3%，出發(fā)時間懲罰減少了4.5%，到達(dá)時間懲罰減少了2.7%，說明優(yōu)化停站后運輸時效性得到了一定程度的提升，同時運輸收益有所增加。

表1 參數(shù)取值Tab.1 Parameter value

表2 停站方案優(yōu)化結(jié)果Tab.2 Optimization results of stop plan

圖4 運行周期示意圖Fig.4 Schematic of operation cycle

在優(yōu)化停站方案的基礎(chǔ)上，進(jìn)一步采用“二分法”對發(fā)車時間進(jìn)行優(yōu)化，班列發(fā)車時間從原先的每日22 : 55變?yōu)榍?天17 : 35，第3天14 : 25，發(fā)車時間優(yōu)化結(jié)果如表3所示。與優(yōu)化前相比，運輸利潤值提高了22.4%，出發(fā)時間懲罰減少了38.8%，到達(dá)時間懲罰減少了13.3%，說明貨物在車站等待裝車的時間減少了很多，班列到達(dá)各站的時間更好地滿足了客戶需求，運輸時效性得到了大幅提升，同時運輸收益也有了較大提升。

表3 發(fā)車時間優(yōu)化結(jié)果Tab.3 Optimization results of departure time

由以上2步的優(yōu)化結(jié)果可以看出，通過對現(xiàn)有班列的停站方案進(jìn)行優(yōu)化，運輸時效性和運輸收益均有所改善，但優(yōu)化幅度不高。在此基礎(chǔ)上，通過進(jìn)一步優(yōu)化班列的發(fā)車時間，可以大幅提升運輸時效性及增加運輸收益。該優(yōu)化結(jié)果說明，通過合理設(shè)置班列停站方案和班列開行時間可以大幅提升環(huán)形班列的時效性。

4 結(jié)束語

鐵路環(huán)形班列滿足了中小企業(yè)靈活分散的運輸需求，具有快捷、安全、方便的特點，適合運送小件零散貨物。但是，鐵路部門在提供物流服務(wù)過程中，依然存在重運輸成本、輕時間成本的問題，研究以動態(tài)服務(wù)網(wǎng)絡(luò)為基礎(chǔ)，構(gòu)建了考慮發(fā)車時間的環(huán)形班列開行方案優(yōu)化模型，將問題分為2個階段順次求解，先設(shè)計遺傳算法對停站方案進(jìn)行優(yōu)化，再采用“二分法”對班列發(fā)車時間進(jìn)行優(yōu)化，進(jìn)而完成開行方案的優(yōu)化。實例計算表明，該優(yōu)化方法可以為環(huán)形班列發(fā)車時間、停站方案的確定提供理論指導(dǎo)，減少班列不必要的停站和貨物等待裝車的時間，從而提高環(huán)形班列的運輸時效性，提升鐵路運輸企業(yè)的競爭力。此外，上述模型及算法經(jīng)過改進(jìn)，也可用于解決其他運輸模式下快運班列的開行方案編制問題。