李晟東，呂紅霞,c，呂苗苗,c，徐長(zhǎng)安，倪少權(quán),c

(西南交通大學(xué)a.交通運(yùn)輸與物流學(xué)院；b.全國(guó)鐵路列車運(yùn)行圖編制研發(fā)培訓(xùn)中心；c.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都610031)

0 引 言

編組計(jì)劃、列車運(yùn)行圖等運(yùn)輸計(jì)劃根據(jù)中長(zhǎng)期的貨流預(yù)測(cè)數(shù)據(jù)編制得到，是一種靜態(tài)計(jì)劃，主要在宏觀層面確定車流的組織方式.在鐵路日常運(yùn)營(yíng)中，貨流波動(dòng)較大，運(yùn)輸組織根據(jù)“按流行車”原則，使實(shí)際貨物列車的開行與計(jì)劃的列車開行存在一定的出入.為使運(yùn)輸組織符合日常貨流動(dòng)態(tài)變化，有必要構(gòu)建日常動(dòng)態(tài)貨物列車開行方案.

我國(guó)與以北美為代表的國(guó)外鐵路在對(duì)貨物列車開行方案的研究對(duì)象和范圍界定上有較大區(qū)別.我國(guó)貨物列車開行方案一般等同于列車編組計(jì)劃[1-3]，國(guó)外貨物列車大多為分組列車，其開行方案主要包括編組去向方案(blocking plan)，編組去向分配方案(block-to-train plan or makeup plan)，列車運(yùn)營(yíng)方案(train routing plan)[4-7].國(guó)內(nèi)外關(guān)于開行方案的研究大多在中長(zhǎng)期層面進(jìn)行編制，該層面基于預(yù)測(cè)需求，主要確定列車開行的始發(fā)終到站、開行頻率和編組內(nèi)容.少部分研究[8-9]，以1 周為決策期的短期層面對(duì)開行方案進(jìn)行編制，在確定列車開行始發(fā)終到站、開行頻率、編組內(nèi)容的基礎(chǔ)上，進(jìn)一步確定列車開行時(shí)間.在1周層面的計(jì)劃編制中，雖然基于短期需求數(shù)據(jù)相較于中長(zhǎng)期數(shù)據(jù)更為準(zhǔn)確，但仍然是一種預(yù)測(cè)數(shù)據(jù)，與實(shí)際需求數(shù)據(jù)存在差異；其次，得到的開行時(shí)間確定了貨物列車在1 周內(nèi)的哪一天開行，相對(duì)于日常運(yùn)營(yíng)層面而言，其精度仍較為粗略.

日常動(dòng)態(tài)貨物列車開行方案，是以1 d為決策期，在編組計(jì)劃、運(yùn)行圖等基本運(yùn)輸計(jì)劃的基礎(chǔ)上，根據(jù)日常動(dòng)態(tài)車流，確定決策日貨物列車開行的始發(fā)終到站、開行數(shù)量、編組內(nèi)容，以及開行時(shí)段.因此，本文提出的日常動(dòng)態(tài)貨物列車開行方案進(jìn)一步確定了決策日內(nèi)，列車的開行時(shí)段.其次，既有研究在編制開行方案時(shí)，通常從運(yùn)輸企業(yè)生產(chǎn)效益出發(fā)，較少顧及貨物實(shí)際運(yùn)輸需求，本文基于日常實(shí)際動(dòng)態(tài)車流，考慮運(yùn)到期限等貨物運(yùn)輸需求.

1 問題分析

1.1 動(dòng)態(tài)車流

動(dòng)態(tài)車流指決策日路網(wǎng)中實(shí)際車流，由決策日當(dāng)日新產(chǎn)生的車流和之前決策日產(chǎn)生并在當(dāng)日在途的車流兩部分組成.決策日新產(chǎn)生的車流，若在當(dāng)前決策日內(nèi)不能到達(dá)終到站，則當(dāng)下一決策日到來，該車流成為在途車流.

以貨物運(yùn)到期限作為車流的時(shí)間窗，故車流i在途中任一車站s的運(yùn)到時(shí)限(時(shí)間窗)為

式中：Q(i)——車流i所裝運(yùn)貨物的運(yùn)到期限；

——車流i在其終到站的卸車時(shí)間；

Lss′——車站s與車流i終到站s′之間的里程(km)；

vtravel——貨物列車平均旅行速度(km/h)；

Ltransit——貨車平均中轉(zhuǎn)距離(km)；

ttransit——車輛在技術(shù)站的平均中轉(zhuǎn)停留時(shí)間(h).

以上相關(guān)數(shù)據(jù)可由《全國(guó)鐵路統(tǒng)計(jì)資料匯編》查詢得到.

引入車流到達(dá)違反時(shí)間窗的延誤費(fèi)用，即

t(i)——車流i到達(dá)目的站的時(shí)間；

ξ(i)——延誤懲罰系數(shù).

1.2 列車服務(wù)網(wǎng)絡(luò)

為描述列車運(yùn)行過程，提出基于運(yùn)行圖等基本計(jì)劃，構(gòu)建貨物列車服務(wù)時(shí)空網(wǎng)絡(luò).構(gòu)建核心思想為：首先，將技術(shù)站等具有始發(fā)終到列車能力的車站視為車站集合對(duì)象，并獲取相應(yīng)的編組計(jì)劃、運(yùn)行圖等；其次，將決策日離散為連續(xù)的時(shí)段，并將車站按時(shí)段進(jìn)行擴(kuò)展復(fù)制為服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)；第三，基本運(yùn)行圖中，若在某一車站的某一時(shí)段內(nèi)有列車始發(fā)，并終到另一車站的另一時(shí)段，則在相應(yīng)的服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)間構(gòu)建有向的列車服務(wù)弧；第四，對(duì)于目標(biāo)決策日，將同一車站的連續(xù)服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)用有向的車站停留弧進(jìn)行連接，用以表示改編車流在站的停留；最后，構(gòu)建周期跨越弧，用以表示之前決策日出發(fā)，并在目標(biāo)決策日到達(dá)的列車服務(wù)，周期跨越弧的構(gòu)建，使開行方案得以實(shí)現(xiàn)每日滾動(dòng)編制.一個(gè)簡(jiǎn)單列車服務(wù)時(shí)空網(wǎng)絡(luò)如圖1所示.

2 數(shù)學(xué)模型

2.1 邊界假設(shè)

(1)鐵路系統(tǒng)運(yùn)輸能力供應(yīng)大于運(yùn)輸能力需求，保證決策日所有車流都能夠被輸送.

(2)車流徑路已知，并且同一始發(fā)終到的不同支車流的徑路是相同的.

(3)不考慮車流的樹形改編策略.松弛樹形改編策略，能夠更加靈活地編組列車，防止車流為等待集結(jié)而導(dǎo)致在站停留時(shí)間過長(zhǎng).

(4)假定所有貨物列車都為單組列車.

圖1 列車服務(wù)時(shí)空網(wǎng)絡(luò)Fig.1 Train service time-space network

2.2 符號(hào)描述

(1)集 合.

G——列車服務(wù)時(shí)空網(wǎng)絡(luò)；

S——服務(wù)網(wǎng)絡(luò)中車站集合，由技術(shù)站等具有列車始發(fā)終到能力的車站組成，車站索引為s；

A——服務(wù)網(wǎng)絡(luò)中列車服務(wù)弧集合，服務(wù)弧索引為a；

F——車流集合，車流索引為i；

F(1)——決策日內(nèi)新產(chǎn)生的車流集合；

F(2)——之前決策日內(nèi)產(chǎn)生，在目標(biāo)決策日到達(dá)，并將繼續(xù)進(jìn)行運(yùn)輸?shù)脑谕拒嚵骷希?/p>

S(i)——車流i徑路上的車站集合；

δ+(s)——服務(wù)網(wǎng)絡(luò)中s站發(fā)出的所有服務(wù)弧集合；

δ-(s)——服務(wù)網(wǎng)絡(luò)中到達(dá)s站的所有服務(wù)弧集合.

(2)參數(shù).

——車流i在流經(jīng)弧a時(shí)的單位費(fèi)用；

mi——車流i對(duì)應(yīng)的貨車數(shù)量；

oi，di——分別為車流i徑路上的始發(fā)站、終到站；

γa——弧a開行單位列車的運(yùn)營(yíng)成本；

——0-1 常量，表示當(dāng)弧a在車流i的徑路上時(shí)，取值為1，否則為0；

——弧a相應(yīng)的單位列車最大編成輛數(shù)；

——弧a相應(yīng)的單位列車最小編成輛數(shù)；

——弧a對(duì)應(yīng)的最大貨物列車開行數(shù)量；

——弧a所對(duì)應(yīng)的出發(fā)時(shí)段；

——弧a所對(duì)應(yīng)的到達(dá)時(shí)段；

——車站s的最大有調(diào)中轉(zhuǎn)作業(yè)時(shí)間；

——車站s的最小有調(diào)中轉(zhuǎn)作業(yè)時(shí)間；

——本站裝車完畢后新產(chǎn)生的車流，車站規(guī)定最大在站停留時(shí)間；

——本站裝車完畢后新產(chǎn)生的車流，編組出發(fā)所需的最小在站停留時(shí)間，主要包括編組、集結(jié)和出發(fā)作業(yè)時(shí)間；

g——單位時(shí)段所對(duì)應(yīng)的時(shí)長(zhǎng)，單位通常為min；

——集合F(1)中的車流i在其始發(fā)站可以開始編入列車的初始時(shí)段，即裝車完畢后的時(shí)間；

——集合F(2)中的車流i在決策日內(nèi)的初始到達(dá)時(shí)段，即隨之前決策日出發(fā)的列車運(yùn)輸，并在當(dāng)前實(shí)施日到達(dá)的時(shí)間.

(3)變量.

p(t(i))——表示決策日結(jié)束時(shí)，車流i的延誤懲罰費(fèi)用；

——0-1 決策變量，車流i是否選擇流經(jīng)弧a，是為1，否則為0；

ya——非負(fù)整數(shù)決策變量，弧a對(duì)應(yīng)開行列車的數(shù)量.

2.3 目標(biāo)函數(shù)

開行方案構(gòu)建的目的是為貨主提供快捷、準(zhǔn)時(shí)的運(yùn)輸產(chǎn)品，同時(shí)確保鐵路運(yùn)營(yíng)效益.因此，本文目標(biāo)函數(shù)為車流走行費(fèi)用，列車開行運(yùn)營(yíng)費(fèi)用和車流延誤懲罰費(fèi)用之和最小.

式(3)中，第1 和第2 部分是開行方案編制中運(yùn)營(yíng)成本的衡量，第3 部分是對(duì)貨主需求滿足的考慮.

2.4 約束條件

(1)車流徑路唯一約束.

車流i只能選擇在其始發(fā)站至終到站的車流徑路上的弧.

(2)節(jié)點(diǎn)流量平衡約束.

為保證車流能夠完整地到達(dá)目的站，設(shè)置節(jié)點(diǎn)流量平衡約束為

(3)列車編組數(shù)量約束.

對(duì)于每條服務(wù)弧a上計(jì)劃開行的列車，其編成貨車數(shù)量不能超過規(guī)定的最大編組輛數(shù)，也不能低于最小編組輛數(shù).

(4)列車開行數(shù)量約束.

對(duì)于每條服務(wù)弧a，開行的列車數(shù)量不能超過該弧相應(yīng)的最大開行列車數(shù)量.

(5)車流中轉(zhuǎn)時(shí)間約束.

對(duì)于在途中技術(shù)站發(fā)生中轉(zhuǎn)改編的車流而言，其中轉(zhuǎn)時(shí)間應(yīng)不小于該站的最小有調(diào)中轉(zhuǎn)作業(yè)時(shí)間.同時(shí)為防止車流在站停留時(shí)間過長(zhǎng)，車流在技術(shù)站的中轉(zhuǎn)時(shí)間應(yīng)不超過該站的最大有調(diào)中轉(zhuǎn)作業(yè)時(shí)間.

(6)車流始發(fā)時(shí)間約束.

對(duì)于決策日內(nèi)新產(chǎn)生的車流i∈F(1)，其裝車完畢后至出發(fā)時(shí)間不能超過規(guī)定的在站最大和最小停留時(shí)間.

對(duì)于之前實(shí)施日產(chǎn)生的在途車流i∈F(2)，其在當(dāng)前決策期內(nèi)初始站的始發(fā)時(shí)間也應(yīng)滿足最大和最小在站停留時(shí)間限制，該組約束本質(zhì)也是車流的改編中轉(zhuǎn)時(shí)間限制.

3 算法設(shè)計(jì)

本文問題本質(zhì)上是一個(gè)大規(guī)模組合優(yōu)化問題，故利用模擬退火(Simulated Annealing,SA)啟發(fā)式算法，實(shí)現(xiàn)問題近似優(yōu)化求解.傳統(tǒng)SA 算法是一種串行算法，為提高算法搜索效率，本文借鑒遺傳、粒子群等群搜索算法的隱含并行性特性，通過增加解的個(gè)體數(shù)目實(shí)現(xiàn)算法的并行性；同時(shí)，引入多鄰域移動(dòng)準(zhǔn)則，通過隨機(jī)概率決定鄰域算子的選擇產(chǎn)生鄰域解.本文改進(jìn)的多鄰域并行模擬退火搜索算法的總體思路為，建立多個(gè)體進(jìn)行并行搜索，對(duì)每個(gè)個(gè)體利用基于車流排序的分解啟發(fā)式方法得到模型的解，采用多鄰域移動(dòng)準(zhǔn)則隨機(jī)選擇鄰域算子探索解空間，利用模擬退火算法控制搜索迭代方向及進(jìn)程，如圖2所示.

圖2 改進(jìn)的并行模擬退火算法流程圖Fig.2 Flow chart of improved parallel simulated annealing algorithm

3.1 求解空間定義

本文模型實(shí)際上是一類帶容量限制的多商品流模型，弧能力約束式(8)和式(9)，即為“捆”約束，將不同車流聯(lián)系在一起，而式(4)～式(7)、式(10)～式(16)均作用在單支車流上.優(yōu)化模型可分解為 |F|個(gè)子問題，每個(gè)子問題對(duì)應(yīng)單支車流，為該支車流的最短徑路問題，可采用動(dòng)態(tài)規(guī)劃法進(jìn)行高效求解.與此同時(shí)，不同車流所對(duì)應(yīng)的單位流量費(fèi)用不同，模型為總費(fèi)用流最小的優(yōu)化目標(biāo)，弧能力應(yīng)優(yōu)先分配給單位流量費(fèi)用較高的車流，使得到的解較優(yōu).因此，本文提出基于車流排序的分解啟發(fā)式方法生成模型的解，使算法避免一直陷于不可行解空間尋優(yōu).

基于車流排序的分解啟發(fā)式方法的思路為，松弛約束式(8)和式(9)，并在目標(biāo)函數(shù)中添加相應(yīng)懲罰項(xiàng)βU，其中，U為列車編組最小輛數(shù)不滿足的違反量，β為懲罰因子；為提升得到的解的可行性，添加能力約束，即

式中：i——當(dāng)前求解的車流序號(hào)；

k——已求解的車流序號(hào).

按照一定的單位流量費(fèi)用排序，對(duì)每個(gè)子問題采用動(dòng)態(tài)規(guī)劃法進(jìn)行快速求解.每次求解一個(gè)子問題后，更新式(17)為該弧加載已求解的車流的剩余能力.最后，由 |F|個(gè)子問題的解構(gòu)成原問題的解.

3.2 分解子問題求解

采用動(dòng)態(tài)規(guī)劃對(duì)單支車流的時(shí)空網(wǎng)絡(luò)最短路徑進(jìn)行高效求解，步驟如下.

Step 1讀入目標(biāo)車流的可選列車服務(wù)弧，確定相應(yīng)的服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)sj(sj∈N)，代表站s(s∈[1,S])第j個(gè)節(jié)點(diǎn)，以及邏輯起點(diǎn)0，邏輯終點(diǎn)S+1.設(shè)立邊界條件s=0，f(01)=0，并記錄最優(yōu)值b(01)=0.

Step 2對(duì)于s站，遍歷s站的服務(wù)節(jié)點(diǎn)sj，并計(jì)算每一個(gè)與服務(wù)節(jié)點(diǎn)sj相鄰的服務(wù)節(jié)點(diǎn)s′j′對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移函數(shù)其中，為車流j在s站中轉(zhuǎn)時(shí)間的違反量，u(i)為懲罰系數(shù).若s′=s+1，記錄rsj[(s+1)j′]=f(s′j′)；否則，記錄tsj(s′j′)=f(s′j′).

Step 3遍歷s+1 站的服務(wù)節(jié)點(diǎn)(s+1)j′，選取，并 記錄 為 該節(jié) 點(diǎn)的最優(yōu)值b[(s+1)j′].

Step 4判定s是否等于S+1.否，轉(zhuǎn)Step 2；是，算法結(jié)束.

3.3 鄰域移動(dòng)準(zhǔn)則

多鄰域移動(dòng)準(zhǔn)則設(shè)計(jì)如下.

(1)插入.隨機(jī)選取當(dāng)前車流排序L的一段子序列l(wèi)1，將其插入到另一個(gè)位置，如圖3(a)所示.

(2)逆序.隨機(jī)選取當(dāng)前車流排序L的一段子序列l(wèi)1，將其排序逆轉(zhuǎn)，如圖3(b)所示.

(3)交換.隨機(jī)選取當(dāng)前車流排序L的兩段子序列l(wèi)1、l2，交換l1和l2的位置，如圖3(c)所示.

圖3 鄰域算子Fig.3 Neighborhood operators

4 案例分析

以蒙華鐵路為例進(jìn)行案例驗(yàn)算，如圖4 所示.某決策日內(nèi)共23 座車站涉及列車的始發(fā)終到，依次編號(hào)S1～S23，該決策日共有125支車流，當(dāng)日蒙華基本列車運(yùn)行圖共包含182條運(yùn)行線.以階段計(jì)劃的3 h進(jìn)行決策日時(shí)段劃分，車流時(shí)間窗由式(1)計(jì)算得到，相關(guān)參數(shù)取值為：vtravel=34.3 km/h，ttransit=4.8 h，Ltransit=208 km，Lunload=10 h.車流最小、最大中轉(zhuǎn)時(shí)間分別為3 h，6 h，車流單位流費(fèi)用及列車單位開行費(fèi)用參考文獻(xiàn)[1]和[2]設(shè)置，車流單位延誤費(fèi)用設(shè)置為5元/min.

在處理器為i7-6700HQ，內(nèi)存為16 G的個(gè)人計(jì)算機(jī)上，采用Matlab 2016a 實(shí)現(xiàn)編程求解.經(jīng)過多組參數(shù)實(shí)驗(yàn)，在初始溫度為200，終止溫度為1，溫度衰減系數(shù)為0.85 的設(shè)置下，求得蒙華鐵路貨物列車開行方案，如圖5和圖6所示，其中，列車編組內(nèi)容以車流序號(hào)和車輛數(shù)表示.

總目標(biāo)函數(shù)值為86 233元，其中，車流總費(fèi)用為41 868元，列車總開行費(fèi)用為44 365元，總延誤費(fèi)用為0元，即車流都能在規(guī)定時(shí)間窗內(nèi)到達(dá)目的站.下、上行方向各開行列車26 列，列車編組長(zhǎng)度滿足編組數(shù)量要求，從而說明本文模型和算法的有效性.

為進(jìn)一步分析運(yùn)到時(shí)限對(duì)開行方案的影響，在本文算例的基礎(chǔ)上，對(duì)不同運(yùn)到時(shí)限方案(12，24，36，48 h)進(jìn)行計(jì)算，結(jié)果如圖7 所示.由圖7 可知：當(dāng)運(yùn)到時(shí)限不斷縮減時(shí)，車流走行費(fèi)用、列車開行費(fèi)用增加，延誤費(fèi)用保持不變，說明通過增開列車，加快車流輸送，可保障運(yùn)到時(shí)限；當(dāng)運(yùn)到時(shí)限進(jìn)一步縮減時(shí)，車流費(fèi)用、列車費(fèi)用降低，而延誤費(fèi)用增加，說明當(dāng)無法進(jìn)一步加快車流輸送時(shí)，通過少開列車來降低運(yùn)營(yíng)成本.

圖4 蒙華鐵路示意圖Fig.4 Sketch map of Menghua railway

圖5 蒙華鐵路開行方案(下行方向)Fig.5 Tran formation plan of Menghua railway(Haolebaoji South-Ji'an)

圖6 蒙華鐵路開行方案(上行方向)Fig.6 Tran formation plan of Menghua railway(Ji'an-Haolebaoji South)

5 結(jié) 論

本文提出日常貨物列車開行方案的編制優(yōu)化方法，其相較于中長(zhǎng)期層面的開行方案，在對(duì)動(dòng)態(tài)車流異質(zhì)性區(qū)分的基礎(chǔ)上，確定了列車開行的始發(fā)終到站、開行數(shù)量、編組內(nèi)容和開行時(shí)段.構(gòu)建開行方案編制的整數(shù)規(guī)劃模型，并設(shè)計(jì)改進(jìn)的多鄰域并行模擬退火算法求解；并通過蒙華鐵路的實(shí)際算例，說明本文的模型及算法的有效性.未來可研究分組列車開行方案的編制問題.