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

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

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

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

1 鐵路環(huán)形班列動態(tài)服務網絡構建

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

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

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

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

2 鐵路環(huán)形班列服務網絡優(yōu)化模型

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

圖1 動態(tài)服務網絡構建方法Fig.1 Establishment of dynamic service network

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

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

3 算法與實例分析

3.1 求解算法

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

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

3.1.1 確定停站方案

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

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

步驟2：按次序計算每一條染色體的適應度函數。

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

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

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

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

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

步驟2：將時間段拆分為更小的2個時間段，拆分后的2個時間段的長度必須為服務網絡時間段長度的整數倍，拆分時保證拆分后的時間段長度相同或相近。

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

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

圖3 基因編碼Fig.3 Gene encoding

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

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

3.2 實例分析

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

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

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

表1 參數取值Tab.1 Parameter value

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

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

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

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

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

4 結束語

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