日常動(dòng)態(tài)貨物列車(chē)開(kāi)行方案優(yōu)化研究

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

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

0 引 言

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

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

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

1 問(wèn)題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 邊界假設(shè)

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

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

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

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

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

2.2 符號(hào)描述

(1)集 合.

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

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

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

F——車(chē)流集合，車(chē)流索引為i；

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

F(2)——之前決策日內(nèi)產(chǎn)生，在目標(biāo)決策日到達(dá)，并將繼續(xù)進(jìn)行運(yùn)輸?shù)脑谕拒?chē)流集合；

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

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

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

(2)參數(shù).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)變量.

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

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

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

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

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

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

2.4 約束條件

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

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

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

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

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

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

(4)列車(chē)開(kāi)行數(shù)量約束.

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

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

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

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

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

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

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

本文問(wèn)題本質(zhì)上是一個(gè)大規(guī)模組合優(yōu)化問(wèn)題，故利用模擬退火(Simulated Annealing,SA)啟發(fā)式算法，實(shí)現(xiàn)問(wèn)題近似優(yōu)化求解.傳統(tǒng)SA 算法是一種串行算法，為提高算法搜索效率，本文借鑒遺傳、粒子群等群搜索算法的隱含并行性特性，通過(guò)增加解的個(gè)體數(shù)目實(shí)現(xiàn)算法的并行性；同時(shí)，引入多鄰域移動(dòng)準(zhǔn)則，通過(guò)隨機(jī)概率決定鄰域算子的選擇產(chǎn)生鄰域解.本文改進(jìn)的多鄰域并行模擬退火搜索算法的總體思路為，建立多個(gè)體進(jìn)行并行搜索，對(duì)每個(gè)個(gè)體利用基于車(chē)流排序的分解啟發(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í)際上是一類(lèi)帶容量限制的多商品流模型，弧能力約束式(8)和式(9)，即為“捆”約束，將不同車(chē)流聯(lián)系在一起，而式(4)～式(7)、式(10)～式(16)均作用在單支車(chē)流上.優(yōu)化模型可分解為 |F|個(gè)子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)單支車(chē)流，為該支車(chē)流的最短徑路問(wèn)題，可采用動(dòng)態(tài)規(guī)劃法進(jìn)行高效求解.與此同時(shí)，不同車(chē)流所對(duì)應(yīng)的單位流量費(fèi)用不同，模型為總費(fèi)用流最小的優(yōu)化目標(biāo)，弧能力應(yīng)優(yōu)先分配給單位流量費(fèi)用較高的車(chē)流，使得到的解較優(yōu).因此，本文提出基于車(chē)流排序的分解啟發(fā)式方法生成模型的解，使算法避免一直陷于不可行解空間尋優(yōu).

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

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

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

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

3.2 分解子問(wèn)題求解

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

Step 1讀入目標(biāo)車(chē)流的可選列車(chē)服務(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ù)其中，為車(chē)流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)前車(chē)流排序L的一段子序列l(wèi)1，將其插入到另一個(gè)位置，如圖3(a)所示.

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

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

圖3 鄰域算子Fig.3 Neighborhood operators

4 案例分析

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

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

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

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

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

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

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

5 結(jié) 論

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