基于列車備選集的技術(shù)站單組列車編組計(jì)劃優(yōu)化模型

方 波，魏玉光，楊 浩

(北京交通大學(xué) 交通運(yùn)輸學(xué)院, 北京 100044)

技術(shù)站列車編組計(jì)劃作為貨物列車編組計(jì)劃的重要組成部分[1]，是一個(gè)復(fù)雜的大規(guī)模組合優(yōu)化問題。而單組列車作為我國技術(shù)站貨物列車的主要組織形式，承擔(dān)了大部分技術(shù)站間的車流運(yùn)輸任務(wù)。因此，技術(shù)站單組列車編組計(jì)劃的優(yōu)化是提高路網(wǎng)車流運(yùn)輸組織水平的關(guān)鍵。

大規(guī)模實(shí)際路網(wǎng)涉及范圍廣、因素多，使得單組列車編組計(jì)劃成為NP-hard問題，用現(xiàn)有模型和方法幾乎難以得到最優(yōu)解，簡化實(shí)際問題并求解出符合運(yùn)輸需要的編組計(jì)劃成為研究重點(diǎn)。國內(nèi)外學(xué)者圍繞技術(shù)站單組列車編組計(jì)劃開展了大量研究，研究成果主要集中于車流徑路優(yōu)化、單組列車編組計(jì)劃優(yōu)化、單組列車與分組列車編組計(jì)劃協(xié)同優(yōu)化、車流徑路與單組列車編組計(jì)劃的綜合優(yōu)化等方面。

車流徑路優(yōu)化方面：江南等[2]提出適合鐵路管理方式的車流徑路制定參照模型及算法，并針對各種車流徑路的求解方法給出詳細(xì)的數(shù)學(xué)模型與算法；溫旭紅等[3]以路網(wǎng)上車流的廣義里程成本最小化為目標(biāo)，以車流徑路的樹形結(jié)構(gòu)約束、車流強(qiáng)度守恒以及路段通過能力限制等為約束條件，提出基于樹形結(jié)構(gòu)的鐵路車流徑路優(yōu)化模型。

單組列車編組計(jì)劃優(yōu)化方面：史峰等[4]將給定編組去向集時(shí)有改編能力約束的編組計(jì)劃問題轉(zhuǎn)化為車流徑路問題，提出交替添加、剔除編組去向的啟發(fā)式算法；許紅等[5]綜合考慮車站編組能力、解體能力、調(diào)車線容車數(shù)等影響因素，構(gòu)建了以技術(shù)站車流總消耗最小及改編能力利用程度最均衡的多目標(biāo)0-1規(guī)劃模型，并以改進(jìn)的遺傳算法求解；林柏梁等[6]基于最遠(yuǎn)站法則，構(gòu)建了列車編組計(jì)劃的雙層模型，上層確定列車到發(fā)站，下層確定車流改編方案，并采用模擬退火算法對模型進(jìn)行求解；Chen等[7]假設(shè)車流徑路已知，構(gòu)建了基于路徑的單組列車編組計(jì)劃線性模型，以車站最大編組去向數(shù)代替分類線數(shù)量約束來避免模型的非線性，并設(shè)計(jì)了一種啟發(fā)式的樹分解算法進(jìn)行求解。

單組列車與分組列車編組計(jì)劃協(xié)同優(yōu)化方面：梁棟等[8]分析了分組列車相較于單組列車的耗費(fèi)節(jié)省，在單組列車編組計(jì)劃的基礎(chǔ)上，以分組列車取代單組列車的節(jié)省最大為目標(biāo)求解分組列車編組計(jì)劃模型；肖杰等[9]建立了單組列車和分組列車編組計(jì)劃的綜合優(yōu)化模型，以遺傳算法求解得到的單組列車編組計(jì)劃為基礎(chǔ)，采用遍歷算法求解綜合優(yōu)化模型；另外，Xiao等[10]開發(fā)了一種基于遺傳算法和禁忌搜索的混合算法來求解單組列車編組計(jì)劃模型，然后將分組列車替換為單組列車，并提出一種貪婪算法求解綜合優(yōu)化模型。

車流徑路與單組列車綜合優(yōu)化方面：李德義[11]提出另一種列車備選集方法，構(gòu)建以技術(shù)站車流集結(jié)、改編中轉(zhuǎn)、無改編中轉(zhuǎn)和走行總消耗最小的車流徑路與編組計(jì)劃綜合優(yōu)化模型，并設(shè)計(jì)基于分支定界和列生成算法的分支定價(jià)算法進(jìn)行求解；林柏梁等[12]提出了將車流徑路選擇、裝車地直達(dá)列車編組計(jì)劃及技術(shù)站直達(dá)列車編組計(jì)劃三者統(tǒng)一優(yōu)化的模型；嚴(yán)余松等[13]根據(jù)機(jī)會(huì)約束規(guī)劃理論，建立了基于車流量波動(dòng)的列車編組計(jì)劃與車流徑路綜合優(yōu)化模型，并設(shè)計(jì)基于隨機(jī)模擬的改進(jìn)分枝定界法對模型進(jìn)行求解。

文獻(xiàn)[4-10,12-13]可歸納為“車流-車組-列車”的遞歸方法，即先將車流合并為車組(編組去向)，再將車組分配給列車，大多基于點(diǎn)-弧或弧-路模型建?？蚣埽ㄟ^引入決策變量表示車流是否在某站改編來遞歸求解車流的完整改編過程。這種方法容易導(dǎo)致模型的非線性結(jié)構(gòu)，求解難度高，依賴于啟發(fā)式算法，并且車流遞歸難以直觀展示各支車流的改編過程。文獻(xiàn)[11]可概括為“車流-列車”的研究方法，模型基于多商品網(wǎng)絡(luò)流框架，車流改編接續(xù)過程直觀，但冗余變量過多，求解結(jié)果不理想。

針對現(xiàn)有研究存在的不足，本文基于多商品流服務(wù)網(wǎng)絡(luò)設(shè)計(jì)原理，提出列車備選集的方法，首先構(gòu)建列車備選集，再進(jìn)行車流分配，把單組列車編組計(jì)劃問題轉(zhuǎn)化為列車服務(wù)網(wǎng)絡(luò)上的車流分配問題，并建立了兩階段線性規(guī)劃模型分別求解最優(yōu)車流徑路和最優(yōu)編組計(jì)劃。第一階段的車流徑路模型用于求解各OD對的最優(yōu)車流徑路；第二階段為編組計(jì)劃模型，以上一階段所得最優(yōu)車流徑路生成的列車備選集為輸入，求解最優(yōu)列車服務(wù)和車流分配方案。最后分別以小規(guī)模路網(wǎng)和大規(guī)模路網(wǎng)案例驗(yàn)證模型的可行性和結(jié)果的精確性。

1 列車備選集的構(gòu)建及優(yōu)化

1.1 列車備選集的構(gòu)建

列車備選集是指技術(shù)站之間可開行的全部直達(dá)(直通)列車和區(qū)段列車的集合。以圖1所示的直線方向5個(gè)技術(shù)站為例，t為列車，假定兩相鄰技術(shù)站之間必開區(qū)段列車，即t12、t23、t34、t45；方向上所有可開行的直達(dá)(或直通)列車(以下統(tǒng)稱直達(dá)列車)為t13、t14、t15、t24、t25、t35，共6列。此時(shí)的列車備選集為{t12,t23,t34,t45,t13,t14,t15,t24,t25,t35}。同理，當(dāng)直線方向有n個(gè)技術(shù)站時(shí)，備選列車數(shù)q為

圖1 直線方向5個(gè)技術(shù)站

式中：第一項(xiàng)為直達(dá)列車數(shù)；第二項(xiàng)為區(qū)段列車數(shù)。

對于直線方向的鐵路線路，相當(dāng)于已經(jīng)給定了任意兩個(gè)站之間的車流徑路，列車備選集的構(gòu)建簡單明了。簡單路網(wǎng)示意見圖2，以O(shè)D對(1,4)之間的車流為例，車流的走行徑路可能為1→2→4或1→2→3→4，這兩種車流徑路會(huì)生成不同的備選列車{t12,t24,t124}和{t12,t23,t34,t123,t234,t1234}。因此，需要先確定路網(wǎng)條件下每個(gè)OD對之間的最終車流徑路，從而將路網(wǎng)轉(zhuǎn)化為各OD對間只有唯一徑路的簡單直線線路，以此構(gòu)造路網(wǎng)條件下的列車備選集。

圖2 簡單路網(wǎng)示意圖

假設(shè)圖2路網(wǎng)中所有OD間的所有車流徑路都滿足繞道率且最終徑路已知，圖2所示路網(wǎng)(單方向)列車備選集的構(gòu)建過程見表1，剩余未列舉的OD對恰好與表1中列舉的對稱。

表1 簡單路網(wǎng)單方向的列車備選集構(gòu)建

需要注意，對于備選集里的列車，每支車流只能選擇由其車流徑路產(chǎn)生的列車。以O(shè)D對(1,3)之間的車流為例，該支車流只能選擇徑路1→2→3產(chǎn)生的列車{t12,t23,t123}。該規(guī)定能夠剔除大量冗余方案，進(jìn)一步減少變量規(guī)模。

由于實(shí)際路網(wǎng)往往比圖2所示情況復(fù)雜，每個(gè)OD對之間可能存在成百上千條車流徑路，這些徑路一方面難以全部納入考慮范圍，另一方面包含了大量過長的無效徑路。為降低問題的復(fù)雜度，在求解各OD對間的備選車流徑路時(shí)，引入車流徑路繞道率μr[14]來剔除過長的不合理徑路，定義為

(1)

式中：Lr為某OD間的任意一條徑路r的長度；Lrmin為該OD間最短徑路rmin的長度。

當(dāng)某條徑路的繞道率大于規(guī)定閾值(本文取1.35)時(shí)，該條徑路將不予以考慮。

1.2 列車備選集的優(yōu)化

上述列車備選集中的直達(dá)列車，是理論可開行的所有直達(dá)列車，而實(shí)際生產(chǎn)中，由于技術(shù)站作業(yè)設(shè)備、線路條件、改編時(shí)間消耗和車流量大小等條件的影響，兩技術(shù)站間可能必須開行直達(dá)列車或是禁止開行直達(dá)列車，以下稱為必開條件和禁開條件。

(1)必開條件

傳統(tǒng)的分析計(jì)算法指出，若某一單支車流無改編通過其運(yùn)行途中任何一個(gè)技術(shù)站所得車小時(shí)節(jié)省都大于或等于其在編成站的集結(jié)車小時(shí)消耗，則該車流滿足絕對條件，可直接列入方向最優(yōu)編組方案[1]。對應(yīng)列車備選集，若某支車流滿足絕對條件，則該車流起訖點(diǎn)之間必開直達(dá)列車。除此之外，規(guī)定兩相鄰技術(shù)站之間必開區(qū)段列車。

(2)禁開條件

編組計(jì)劃需遵守技術(shù)站禁開去向規(guī)定，通過剔除禁開去向的直達(dá)列車，可以進(jìn)一步縮減列車備選集。

2 單組列車編組計(jì)劃兩階段優(yōu)化模型

模型中的集合、參數(shù)及變量說明分別見表2～表4。

表2 集合符號及定義

表3 參數(shù)符號及定義

表4 變量符號及定義

2.1 第一階段——車流徑路模型

(2)

(3)

(4)

(5)

(6)

目標(biāo)函數(shù)式(2)第一項(xiàng)指車流選擇不同徑路時(shí)的總走行車小時(shí)消耗，第二項(xiàng)指車流完全改編車小時(shí)消耗，表示所有車流在其運(yùn)行途中的每個(gè)技術(shù)站均進(jìn)行改編時(shí)的車小時(shí)總和。由于車流總改編車小時(shí)消耗等于車流完全改編消耗減去車流無改編節(jié)省，而每支車流在每條徑路下的完全改編車小時(shí)都是確定的，為了使總的車流改編車小時(shí)盡可能少，車流徑路模型求解出的最終徑路既要使車流走行總消耗少，也要使車流完全改編消耗盡可能少，同時(shí)，編組計(jì)劃模型目標(biāo)函數(shù)使車流無改編節(jié)省最大，兩個(gè)模型的目標(biāo)函數(shù)相加將能保證總的車流改編消耗最少。約束式(3)為徑路唯一性約束，表示每支車流最終只能選擇一條車流徑路。約束式(4)為弧通過能力約束，弧通過能力以“列”為單位，每條有向弧代表一個(gè)單向站間區(qū)間，因此，流經(jīng)任一有向弧的車流量不能超過其可用通過能力。

(7)

對于式(4)和式(7)，模型任選一式即可。

2.2 第二階段——編組計(jì)劃模型

(8)

(9)

(10)

(11)

?v∈V?d∈D

(12)

(13)

xt=1 ?t∈Ssuff

(14)

xt=0 ?t∈Sforb

(15)

xt∈{0,1} ?t∈P

(16)

(17)

wt∈N?t∈P

(18)

式中：wt為列車t的車流所占用的分類線數(shù)，為非負(fù)整數(shù)；k為每條分類線一晝夜可服務(wù)的貨車輛數(shù)，取值為200車/條[5-6]，并規(guī)定每條分類線只能由一個(gè)編組去向的車組占用；M為一個(gè)很大的正數(shù)。

(19)

則每個(gè)編組去向占用的分類線數(shù)量為

(20)

因此，技術(shù)站的分類線約束為

(21)

式(21)為非線性約束，故引入輔助決策變量wt，因此，式(21)可線性化為

(22)

根據(jù)式(20)，wt滿足

k(wt-1)

(23)

式(12)為流平衡約束，能夠保證兩技術(shù)站間只有一種列車開行方案以及每支車流只選擇一種輸送方案，同時(shí)還能保證車流從始發(fā)站運(yùn)輸至終到站；式(13)為變量的邏輯約束，只有在列車開行的情況下，車流才能選擇該列車；式(14)、式(15)分別表示滿足必開和禁開條件時(shí)列車開行決策變量的取值；式(16)～式(18)分別表示列車開行決策變量、車流分配決策變量、輔助決策變量的取值范圍。

經(jīng)線性化處理后，模型整體為線性規(guī)劃，可以通過功能強(qiáng)大的商業(yè)求解器或者傳統(tǒng)精確算法求出精確解。模型的求解流程見圖3。

圖3 模型整體求解流程

2.3 模型復(fù)雜度分析

表3 模型規(guī)模對比

3 案例求解

分別以INFORMS 2019 RAS競賽[14]中的8個(gè)技術(shù)站和32個(gè)技術(shù)站的路網(wǎng)對本文所提方法和模型進(jìn)行求解驗(yàn)證。

3.1 小規(guī)模路網(wǎng)案例

8個(gè)技術(shù)站的小規(guī)模路網(wǎng)見圖4，路網(wǎng)數(shù)據(jù)及參數(shù)均按照文獻(xiàn)[14]要求設(shè)置，不考慮必開去向和禁開去向。在處理器為Inter(R) Core(TM) i7-9750 H 2.60 GHz，內(nèi)存為16 GB，操作系統(tǒng)為Windows 10的Lenovo ThinkPad P53計(jì)算機(jī)上，用Python 3.7語言編程實(shí)現(xiàn)，并運(yùn)用新一代大規(guī)模數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi 9.1.0對提出的模型進(jìn)行求解驗(yàn)證。

圖4 小規(guī)模路網(wǎng)示意圖

求解得到車流總的消耗為236 135.1車·h，最終開行34列列車，其中區(qū)段列車18列，直達(dá)列車16列。各技術(shù)站的改編能力及分類線使用情況見表4，各區(qū)間的通過能力利用情況見表5，最終的直達(dá)列車服務(wù)方案見圖5，最終的車流分配方案見表6。

圖5 最終的直達(dá)列車服務(wù)方案

表4 各技術(shù)站的改編能力及分類線使用情況

表5 各區(qū)間通過能力利用情況

表6 最終的車流分配方案

文獻(xiàn)[14]求解結(jié)果與本文兩階段線性規(guī)劃模型的求解結(jié)果對比見表7。其中，文獻(xiàn)[14]基于模擬退火算法求解非線性綜合優(yōu)化模型，而本文采用精確方法求解線性模型，兩者求解結(jié)果相比，本文總消耗減少了488.9車·h，結(jié)果表明本文所提方法和模型有效。

表7 小規(guī)模路網(wǎng)的求解結(jié)果對比 車·h

3.2 大規(guī)模路網(wǎng)案例

8個(gè)技術(shù)站的小規(guī)模案例已證明本文所提模型的可行性，為了更好驗(yàn)證和展示模型的求解效率和精確性，以文獻(xiàn)[14]中32個(gè)站的大規(guī)模路網(wǎng)為例，路網(wǎng)共包括32個(gè)技術(shù)站，128個(gè)單向站間區(qū)間，992支車流，見圖6。

圖6 大規(guī)模路網(wǎng)示意圖

由于該路網(wǎng)各技術(shù)站之間連接的復(fù)雜性和區(qū)間長度的特點(diǎn)，導(dǎo)致兩技術(shù)站間滿足繞道率μ=1.35的備選徑路可能存在成百上千條，為了降低求解的復(fù)雜度，在滿足繞道率的條件下，任意兩技術(shù)站間的備選徑路最多取20條，設(shè)置求解GAP為0.1%，其余參數(shù)不變，模型共耗時(shí)91 s得到最優(yōu)解，車流總消耗為5 163 471.8車·h，較文獻(xiàn)[14]所給結(jié)果共節(jié)省1 855車·h。

為研究模型的穩(wěn)定性以及各OD對間備選徑路數(shù)量對求解結(jié)果的影響，本文在求解車流徑路模型時(shí)，每個(gè)OD對間滿足繞道率的K-短路最多分別選5、10、20、30、40、50條。求解結(jié)果見表8，模型求解時(shí)間在91～248 s之間，平均耗時(shí)147 s，證明本文模型求解效率高且穩(wěn)定；6次實(shí)驗(yàn)總消耗最大相差2 953.6車·h，平均總消耗為5 164 922.3車·h，較文獻(xiàn)[14]平均節(jié)省404車·h，證明備選徑路數(shù)量對本文模型的求解結(jié)果影響較小，同時(shí)也說明，在利用本文模型求解單組列車編組計(jì)劃時(shí)，只需為每個(gè)OD對選取少量的備選徑路便可得到近似最優(yōu)解。

表8 各OD對間不同備選徑路數(shù)對求解結(jié)果的影響

4 結(jié)論

技術(shù)站列車編組計(jì)劃作為貨物列車編組計(jì)劃的重要組成部分，規(guī)定了路網(wǎng)上所有技術(shù)站間的車流徑路、列車的編成、到達(dá)站(或是裝卸、解體站)以及列車的編組內(nèi)容和編掛辦法等，是車流組織計(jì)劃，也是路網(wǎng)上各車站分工的戰(zhàn)略部署[1]，對發(fā)揮鐵路運(yùn)輸能力，提高運(yùn)輸效率和經(jīng)濟(jì)效益有著重要作用，準(zhǔn)確、高效地求解出符合運(yùn)輸需求的技術(shù)站列車編組計(jì)劃對運(yùn)輸生產(chǎn)尤為關(guān)鍵。

本文基于多商品流服務(wù)網(wǎng)絡(luò)設(shè)計(jì)原理，提出了列車備選集的構(gòu)建方法，并建立了基于列車備選集的技術(shù)站單組列車編組計(jì)劃兩階段線性規(guī)劃模型，得到以下結(jié)論：①較車流遞歸方法，本文模型更加簡單，能夠直觀展示車流的改編過程；②構(gòu)建列車備選集可以限制每支車流只能分配到其最優(yōu)徑路生成的備選列車上，以此剔除不合理的車流分配變量，減小模型規(guī)模，加快求解效率；③將分類線約束有效轉(zhuǎn)化為線性約束，既避免了復(fù)雜的非線性結(jié)構(gòu)，也避免將分類線約束轉(zhuǎn)化為最大編組去向數(shù)而造成與運(yùn)輸實(shí)際不符；④小規(guī)模和大規(guī)模路網(wǎng)的求解結(jié)果表明，本文模型能夠快速、準(zhǔn)確地得到最優(yōu)解，求解結(jié)果質(zhì)量優(yōu)于非線性模型；⑤各OD對間不同備選徑路數(shù)對本文模型求解結(jié)果影響很小，模型穩(wěn)定可靠。下一階段的研究將著重于車流徑路和編組計(jì)劃的綜合協(xié)同優(yōu)化，同時(shí)將分組列車納入考慮，構(gòu)建更加符合運(yùn)輸實(shí)際的編組計(jì)劃模型。