基于點(diǎn)-弧結(jié)構(gòu)的路網(wǎng)單組列車編組計(jì)劃優(yōu)化線性0-1規(guī)劃模型

陳崇雙，趙 軍，薛 鋒，郭孜政，左大杰2,

(1.西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 611756；2.西南交通大學(xué) 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 611756； 3.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756；4.西南交通大學(xué) 綜合交通智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 611756)

貨物列車編組計(jì)劃簡(jiǎn)稱編組計(jì)劃(Train formation Plan, TFP)，研究如何將車流組合編掛到各種不同到站和種類的列車之中，其合理編制是提高鐵路網(wǎng)車流組織效率和提供優(yōu)質(zhì)運(yùn)輸服務(wù)的重要保證。

我國(guó)車流組織工作根據(jù)車流的性質(zhì)進(jìn)行分階段考慮，先確定裝車地、空車、班列等直達(dá)列車編組計(jì)劃，然后對(duì)未被其吸收的車流向就近的技術(shù)站集中，進(jìn)而編制技術(shù)站列車編組計(jì)劃，最后再確定剩余車流的區(qū)段管內(nèi)列車編組計(jì)劃[1]。在技術(shù)站列車編組計(jì)劃中，單組列車即列車僅編掛一個(gè)編組去向，相比分組列車其構(gòu)成較為簡(jiǎn)單。由于我國(guó)鐵路車站改編能力和調(diào)車線不足，以及現(xiàn)場(chǎng)車流組織工作的簡(jiǎn)便性等因素，貨物列車中單組列車的比例較高。

路網(wǎng)單組列車編組計(jì)劃需確定兩類決策：①網(wǎng)絡(luò)中開行哪些列流，即確定每支列流的始發(fā)終到站；②每支列流吸收哪些車流，從車流的角度來(lái)說(shuō)，即確定每支車流在其徑路上每個(gè)車站的改編情況。單組列車編組計(jì)劃編制問題中，每支車流的徑路事先已知(如采用最短徑路、特定徑路等)，只需要考慮如何經(jīng)濟(jì)可行地將車流組合成列流。其中，經(jīng)濟(jì)性體現(xiàn)在列流的集結(jié)費(fèi)用和車輛的改編費(fèi)用；可行性體現(xiàn)在滿足車站的改編能力、調(diào)車線數(shù)限制，以及運(yùn)輸組織上的車流不拆散原則和接續(xù)歸并原則[1]。值得注意的是，車流徑路是編組計(jì)劃問題的輸入?yún)?shù)，在其確定過(guò)程中已經(jīng)考慮了線路區(qū)間的通過(guò)能力。車流不拆散原則要求同一只車流作為一個(gè)整體進(jìn)行運(yùn)輸，使編組計(jì)劃問題有別于經(jīng)典的實(shí)數(shù)型網(wǎng)絡(luò)流，而是整數(shù)型網(wǎng)絡(luò)流；接續(xù)歸并原則要求相同終點(diǎn)車流一旦在同一車站改編之后，它們合而不分，采用相同的改編方案輸送至共同的終點(diǎn)站，即同終點(diǎn)車流的改編方案具有樹形結(jié)構(gòu)。

目前，國(guó)內(nèi)外許多專家學(xué)者就鐵路網(wǎng)上單組列車編組計(jì)劃編制進(jìn)行長(zhǎng)期探索，提出了比較合理的數(shù)學(xué)模型和有效的求解算法[2]。其中的代表文獻(xiàn)大致可以歸納為如下兩大類：

其一是采用數(shù)學(xué)規(guī)劃理論建模。曹家明等[3]設(shè)置車流的直達(dá)方案、一次改編和多次改編方案為0-1型決策變量，考慮每支車流的方案唯一性約束，建立二次0-1規(guī)劃模型；同時(shí)，巧妙引入獨(dú)立作業(yè)方式來(lái)減少變量數(shù)目，并利用系數(shù)矩陣的稀疏性和分塊特點(diǎn)進(jìn)行線性松弛求解。林柏梁等[4]和Lin等[5]都以車流改編方案和列流方案為0-1型決策變量，考慮方案唯一性約束、改編能力約束、調(diào)車線數(shù)量約束，構(gòu)建非線性雙層規(guī)劃模型，上層確定列車始發(fā)終到站，下層基于流量平衡思想確定車流改編方案。兩者在決策車流改編方案時(shí)略有差異，文獻(xiàn)[4]基于車流接續(xù)最遠(yuǎn)站法則，即將車流編入車流在始發(fā)站的最遠(yuǎn)去向，以實(shí)現(xiàn)無(wú)改編運(yùn)行距離最遠(yuǎn)；文獻(xiàn)[5]是由優(yōu)化模型計(jì)算確定。兩者都針對(duì)大規(guī)模問題設(shè)計(jì)模擬退火算法。Chen等[6]設(shè)置直達(dá)列流方案和車流可能的改編方案為0-1型決策變量，考慮方案唯一性約束、改編能力約束、調(diào)車線數(shù)量約束和接續(xù)歸并原則，建立線性0-1規(guī)劃模型，并設(shè)計(jì)基于樹分解的求解算法。

其二是采用網(wǎng)絡(luò)流思想建?；蛘咔蠼?，即將車流視為流，列流視為弧，列車集結(jié)耗費(fèi)視為弧的固定耗費(fèi)，改編中轉(zhuǎn)額外耗費(fèi)視為該弧的長(zhǎng)度。李致中等[7]就小規(guī)模路網(wǎng)情形建立無(wú)約束的網(wǎng)絡(luò)流模型。史峰等[8]考慮車站改編能力和編組去向數(shù)目限制情形建模，并給出逐步添加編組去向的貪婪算法。史峰等[9]提出合并式編組方案的概念，在給定每個(gè)站的編組去向方案集的條件下將原問題轉(zhuǎn)化為以各站為終點(diǎn)的普通最短路問題。查偉雄等[10]設(shè)置決策變量類似文獻(xiàn)[5]，考慮車站編組去向數(shù)目約束和車流接續(xù)歸并，建立了非線性(目標(biāo)函數(shù)是高階多項(xiàng)式)0-1規(guī)劃模型。該文獻(xiàn)將開行直達(dá)列車視為新建一個(gè)服務(wù)，由此將原問題轉(zhuǎn)化為服務(wù)系統(tǒng)選址問題，給出逐步減少直達(dá)列流方案(即保留有利的編組去向)的啟發(fā)式算法。

從既有研究可見，鐵路網(wǎng)絡(luò)單組列車編組計(jì)劃問題，雖然具有多商品網(wǎng)絡(luò)流問題的特點(diǎn)，但是車流接續(xù)歸并原則這一獨(dú)特約束所蘊(yùn)含的樹形結(jié)構(gòu)，使得對(duì)其不易建立線性模型和設(shè)計(jì)有效算法。例如，文獻(xiàn)[4-5]采用遞推方式設(shè)置車流改編變量，導(dǎo)致模型具有非線性結(jié)構(gòu)。史峰等[8-9]刻畫接續(xù)歸并關(guān)系也依賴于遞推地確定車流改編序列。這兩種思路都不便應(yīng)用強(qiáng)大的商業(yè)優(yōu)化軟件以及經(jīng)典的精確整數(shù)規(guī)劃算法，例如前兩者運(yùn)用模擬退火算法，后兩者設(shè)計(jì)加弧減弧的啟發(fā)式方法等。同時(shí)，Chen等[6]雖然建立了線性0-1規(guī)劃模型，但是其模型規(guī)模隨網(wǎng)絡(luò)擴(kuò)大呈指數(shù)增長(zhǎng)，而且樹分解算法對(duì)于大規(guī)模問題的最優(yōu)間隔(Gap)仍不算很理想。

本文將路網(wǎng)單組列車編組計(jì)劃優(yōu)化視為1類具有樹形結(jié)構(gòu)的多商品網(wǎng)絡(luò)流問題，在多商品網(wǎng)絡(luò)流的點(diǎn)-弧模型的建模框架下，將車流視為商品，引入一組0-1變量刻畫每支車流如何選擇列流；將直達(dá)列流視為服務(wù)，引入一組0-1變量刻畫網(wǎng)絡(luò)中開行哪些列流；再引入一類輔助變量保證車流接續(xù)歸并?；诖?，以列流集結(jié)耗費(fèi)和車流改編耗費(fèi)總和最小為目標(biāo)，同時(shí)考慮車站改編能力和調(diào)車線數(shù)約束，建立基于多商品網(wǎng)絡(luò)流點(diǎn)-弧結(jié)構(gòu)的線性0-1規(guī)劃模型。在合理的求解時(shí)間范圍內(nèi)，該模型能夠得到高質(zhì)量的可行解以及緊致的下界。最后采取演示算例和大規(guī)模算例，對(duì)所構(gòu)建模型的正確性和有效性進(jìn)行驗(yàn)證。

1 參數(shù)和符號(hào)說(shuō)明

參數(shù)及其符號(hào)說(shuō)明見表1。

表1 參數(shù)和符號(hào)說(shuō)明

單組列車編組計(jì)劃建模，涉及一個(gè)有向網(wǎng)絡(luò)G=(V,E)，其中節(jié)點(diǎn)集合V即車站集合，其元素為技術(shù)站和線路交匯的支點(diǎn)站等，有向弧集合E是直接相連的線路區(qū)間集合，線路的上下行方向分別對(duì)應(yīng)一條有向邊。每支車流(o,d)的徑路已知，可以表示為從其始發(fā)站o至終到站d沿途經(jīng)過(guò)車站的有序集合。在單組列車編組計(jì)劃問題中，由于各列流〈i,j〉的編組內(nèi)容僅為一個(gè)組的車流，該列車的運(yùn)行徑路可以視為相同始發(fā)終到站的車流(i,j)的徑路。

由于車流徑路的限制，并非每支車流都可以編組到所有的列流當(dāng)中。對(duì)于車流(o,d)來(lái)說(shuō)，其實(shí)際能夠編組到的列流可以表示為集合

(1)

圖1 包含8個(gè)站的簡(jiǎn)單路網(wǎng)

表2 決策變量

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

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

單組列車編組計(jì)劃問題的目標(biāo)函數(shù)包括兩項(xiàng)。第一項(xiàng)為列流的集結(jié)耗費(fèi)，僅與列流設(shè)計(jì)變量有關(guān)，相當(dāng)于固定費(fèi)用；另一項(xiàng)是車流在途中車站(不包括始發(fā)站和終到站)的改編耗費(fèi)，與車流改編變量有關(guān)，相當(dāng)于變動(dòng)費(fèi)用。目標(biāo)函數(shù)為

(2)

2.2 約束條件

2.2.1 車流流量守恒約束

每支車流都需滿足以下的流量守恒約束，即每支車流都沿著其給定徑路從其始發(fā)站被輸送至其終點(diǎn)站。與一般多商品網(wǎng)絡(luò)流的流量守恒稍有區(qū)別的是，該組約束僅考慮各支車流在其給定徑路上每個(gè)站的流量平衡，而不需要考慮徑路之外的車站。其原因在于，車流徑路已經(jīng)事先給定，各支車流只能在其給定徑路上沿著從其始發(fā)站至其終到站的方向和軌跡流動(dòng)。

2.2.2 車站改編能力約束

到達(dá)某站的車流，包括終到該站的計(jì)劃車流和在該站進(jìn)行途中改編的車流，都需要消耗該站的改編能力。在某站改編的總車流量不能超過(guò)其可用改編能力，即

(4)

2.2.3 車站調(diào)車線數(shù)約束

從某站出發(fā)的車流，包括從該站始發(fā)的計(jì)劃車流和在該站進(jìn)行途中改編的車流，都需要占用該站的調(diào)車線。從某站出發(fā)的總車流量與該站單條調(diào)車線的平均容納能力之比，視為這些車流實(shí)際占用的調(diào)車線數(shù)，不能超過(guò)該站可用調(diào)車線數(shù)的限制，即

(5)

注意，文獻(xiàn)[4-5]采用分段線性函數(shù)刻畫車流占用的調(diào)車線數(shù)，本文采用線性度量策略。

2.2.4 車流接續(xù)歸并約束

車流接續(xù)歸并要求到達(dá)相同終點(diǎn)的車流，一旦在同一個(gè)站改編之后，必須采用相同的改編方案從改編站輸送至終點(diǎn)站，即同終點(diǎn)車流的改編方案具有樹形結(jié)構(gòu)。本文用約束式(6)、式(7)共同刻畫車流接續(xù)歸并要求。

(6)

(7)

2.2.5 變量關(guān)聯(lián)約束

(8)

約束式(8)包含兩種情形：

2.3 優(yōu)化模型

綜上，從多商品網(wǎng)絡(luò)流角度將路網(wǎng)單組列車編組計(jì)劃問題構(gòu)建為

?o,d∈Vi∈Po,d

yi,j∈{0，1} ?i,j∈V

其二，同樣由于車流徑路的原因，車流流量守恒約束式(3)只要求每支車流在其給定徑路上每個(gè)車站成立，而非要求在網(wǎng)絡(luò)中的全部車站；同時(shí)，變量關(guān)聯(lián)約束式(8)確保每支車流的徑路與其選擇列流的徑路具有一致性。

其三，為滿足特殊的車流接續(xù)歸并要求，本文所構(gòu)建的模型額外引入了約束式(6)和式(7)，保證同終點(diǎn)車流的改編方案具有樹形結(jié)構(gòu)?？梢?，本文模型中的車流改編變量比一般的多商品網(wǎng)絡(luò)流模型具有更嚴(yán)格的要求。

3 與既有模型的對(duì)比分析

文獻(xiàn)[5-6]是最近路網(wǎng)單組列車編組計(jì)劃優(yōu)化領(lǐng)域的兩篇典型文獻(xiàn)，二者的建模思路和求解算法也各具特點(diǎn)。本節(jié)從決策變量表達(dá)形式、模型規(guī)模和模型特點(diǎn)3個(gè)方面，將這兩篇文獻(xiàn)的模型與本文模型進(jìn)行較為詳細(xì)的對(duì)比分析。

3.1 決策變量對(duì)比

車流改編變量的3種表達(dá)形式可以相互轉(zhuǎn)化，下表3以直線單方向上4個(gè)車站為例進(jìn)行說(shuō)明。表3中，第1列是車流改編方案的序號(hào)，第2列是對(duì)應(yīng)的列流方案，第3～5列分別是3種表達(dá)方式的車流改編變量的取值。注意，表中省略了直達(dá)車流的改編變量。例如，第10種方案中，每支車流都是直達(dá)，沒有車流采用改編，故非直達(dá)車流的改編變量為空。

表3 3種車流改編變量表達(dá)形式的相互轉(zhuǎn)化

3.2 模型規(guī)模對(duì)比

3種模型的規(guī)模估計(jì)見表4。可以看出，本文模型的決策變量和約束條件的階數(shù)都為O(N4)，多于文獻(xiàn)[5]，但是遠(yuǎn)少于文獻(xiàn)[6]，后者呈指數(shù)增長(zhǎng)。主要原因在于文獻(xiàn)[6]采用全枚舉的方式設(shè)置車流改編變量，同時(shí)對(duì)每個(gè)車流改編變量提供一個(gè)約束保證接續(xù)歸并。此外，雖然文獻(xiàn)[5]的模型規(guī)模最小，但是由遞推的車流改編變量顯式表達(dá)車站的改編負(fù)荷和改編費(fèi)用時(shí)，將出現(xiàn)決策變量的乘積項(xiàng)。即使可以引入新的變量和約束消除乘積項(xiàng)進(jìn)行線性化，然而一方面網(wǎng)絡(luò)情形的表達(dá)將會(huì)非常復(fù)雜，另一方面也導(dǎo)致模型規(guī)模迅速增長(zhǎng)。

表4 模型規(guī)模估計(jì)

3.3 模型特點(diǎn)對(duì)比

三種模型的特點(diǎn)總結(jié)見表5?？梢?，在車流改編變量設(shè)置上，文獻(xiàn)[5]采用隱式遞推方式，使得模型具有非線性的結(jié)構(gòu)。盡管文獻(xiàn)[6]和本文都建立了線性的0-1規(guī)劃模型，但結(jié)構(gòu)也有差異。文獻(xiàn)[6]的車流改編變量，列舉了車流從始發(fā)站至終到站全過(guò)程的所有可能改編方案，而本文的車流改編變量?jī)H確定車流對(duì)單支列流編掛與否。因而前者構(gòu)建的是多商品網(wǎng)絡(luò)流的弧-路模型，而本文建立的是點(diǎn)-弧模型。其次，在車流接續(xù)歸并實(shí)現(xiàn)手段上，三者迥異。文獻(xiàn)[5]基于遞推方式設(shè)置的車流改編變量，每支車流改編方案的唯一性實(shí)現(xiàn)了接續(xù)歸并。文獻(xiàn)[6]以全枚舉方式呈現(xiàn)每支車流的全部改編方案，直接比較同終點(diǎn)車流的改編方案的一致性，以判斷接續(xù)歸并原則是否滿足。而本文通過(guò)巧妙引入輔助變量和線性約束條件，正確刻畫車流改編方案之間的樹形關(guān)系。

表5 模型特點(diǎn)對(duì)比

4 算例分析

采用1個(gè)演示算例和1組大規(guī)模算例，對(duì)所構(gòu)建模型的正確性和有效性進(jìn)行分析。采用Matab 2016a編程，并調(diào)用CPLEX 12.6求解優(yōu)化模型。為了公平比較，所有計(jì)算都在CPU為E5-2620 2.10 GHz、內(nèi)存為128 GB的64位GPU上運(yùn)行。如果沒有特別說(shuō)明，CPLEX的參數(shù)都為默認(rèn)配置。

4.1 演示算例

以文獻(xiàn)[5]中的小規(guī)模算例，測(cè)試本文模型的正確性。該算例的路網(wǎng)是我國(guó)哈爾濱局路網(wǎng)的簡(jiǎn)化，共包含19個(gè)支點(diǎn)站，23條邊，314支車流。所有車流的徑路都按最短徑路設(shè)置。文獻(xiàn)[5]中車站的可用改編能力，是已經(jīng)扣除了終到車流消耗的結(jié)果。為了讓本文的計(jì)算結(jié)果具有可比性，這里將約束式(4)調(diào)整為

(9)

對(duì)于這個(gè)算例，本文的點(diǎn)-弧模型式(2)、式(3)和式(5)～式(9)包含5 066個(gè)決策變量，8 926個(gè)約束。設(shè)置CPLEX的收斂mipgap為0時(shí)，0.59 s獲得最優(yōu)解，最優(yōu)目標(biāo)值為45 421車·h，與文獻(xiàn)[5]以及文獻(xiàn)[6]弧-路模型的最優(yōu)目標(biāo)值完全相同。

每支車流的最優(yōu)改編策略見表6，構(gòu)成19×19的矩陣。在該表中，第i行第j列的單元格中元素k表示車流(i,j)在站k首次改編。特別地當(dāng)k=j時(shí)，表示開行直達(dá)列流〈i,j〉。車流的完整改編方案可以由該表遞推得出。以車流(7,2)為例進(jìn)行說(shuō)明，由表6，該車流先在站5改編后編組到列流〈5，3〉，在站3再次改編后編組到列流〈3，2〉運(yùn)送至終點(diǎn)站，因而車流(7,2)的改編站為5和3。該表與文獻(xiàn)[6]的弧-路模型的最優(yōu)解并不完全相同，表7列出了改編方案不相同的三支車流。由于它們的車流量均是0，故對(duì)于目標(biāo)函數(shù)值不影響。

表6 最優(yōu)車流改編方案

表7 點(diǎn)-弧模型與弧-路模型最優(yōu)解的不同

接下來(lái)分析本文點(diǎn)-弧模型對(duì)于車流接續(xù)歸并原則的正確性。由問題定義，車流接續(xù)歸并原則規(guī)定，如果同終點(diǎn)的兩支車流都在某站改編，那么從該改編站至終點(diǎn)站的輸送過(guò)程中，它們將采用相同的改編方案。本質(zhì)上，車流接續(xù)歸并原則強(qiáng)制約束同終點(diǎn)車流的改編方案具有樹形結(jié)構(gòu)。為了直觀反映這種特殊關(guān)系，以終點(diǎn)為站2的18支車流為例進(jìn)行說(shuō)明。車流的徑路見圖2(a)。注意，本算例設(shè)定所有車流的徑路都取為其最短路，因此，由最短性原則，終點(diǎn)為站2的車流的最短路構(gòu)成一顆無(wú)向樹，根節(jié)點(diǎn)即為站2。車流的最優(yōu)改編方案，見圖2(b)?？梢姡苏?之外，其他站都只有唯一一條出弧，即最優(yōu)改編方案是以站2為根節(jié)點(diǎn)的一棵有向樹。對(duì)比圖2(a)和圖2(b)可知，如果車流采用直達(dá)方案，無(wú)所謂改編；如果采用改編方案，則改編站都限制在其給定車流徑路上。例如，對(duì)于車流(6，2)，其車流徑路P6，2={6，5，4，3，2}，途中改編車站為5和4均在其車流徑路上。

圖2 終點(diǎn)為站2的18支車流

圖3 松弛接續(xù)歸并約束后車流(5,2)和(6,2)的改編方案

4.2 大規(guī)模算例

以文獻(xiàn)[6]中的10個(gè)大規(guī)模算例，驗(yàn)證所提出方法的有效性。這些算例的路網(wǎng)是我國(guó)鐵路貨運(yùn)網(wǎng)絡(luò)的簡(jiǎn)化，包括83個(gè)車站，158條邊，平均約5 700支車流，所有車流的徑路都給定為最短徑路。由于文獻(xiàn)[5]采用分段線性函數(shù)刻畫車站調(diào)車線數(shù)約束，而且具有非線性結(jié)構(gòu)，故本文點(diǎn)-弧模型僅與文獻(xiàn)[6]的弧-路模型以及樹分解算法進(jìn)行對(duì)比。

文獻(xiàn)[6]的弧-路模型和本文的點(diǎn)-弧模型，規(guī)模對(duì)比見表8。本文模型的決策變量數(shù)和約束條件數(shù)都僅相當(dāng)于文獻(xiàn)[6]的3%，而且系數(shù)矩陣非常稀疏，非零元僅占1.39×10-5。

表8 大規(guī)模算例模型規(guī)模對(duì)比

對(duì)比弧-路模型和點(diǎn)-弧模型的解質(zhì)量，設(shè)置CPLEX最長(zhǎng)運(yùn)行時(shí)間為3 h，結(jié)果對(duì)比見表9。由表9可得，在3 h限制時(shí)間下，一方面，弧-路模型的下界都比點(diǎn)-弧模型小，甚至該模型對(duì)算例1、4、5和6的下界為0。另一方面，弧-路模型的上界都比點(diǎn)弧模型大。由于這兩方面的原因，弧-路模型的平均最優(yōu)間隔(Gap)高達(dá)63.65%，而點(diǎn)-弧模型平均Gap為9.03%。由于點(diǎn)-弧模型對(duì)于算例9和10的Gap較高，為此延長(zhǎng)CPLEX最長(zhǎng)運(yùn)行時(shí)間為10 h，兩個(gè)模型的結(jié)果對(duì)比見表10。延長(zhǎng)運(yùn)行時(shí)間后，弧-路模型的下界和上界稍有改善，但平均Gap仍高達(dá)60.79%。然而點(diǎn)-弧模型的平均Gap為1.55%，全部Gap低于5%。

對(duì)比表9和表10還可發(fā)現(xiàn)，當(dāng)計(jì)算時(shí)間從3 h延長(zhǎng)至10 h，點(diǎn)-弧模型對(duì)于算例9和算例10的Gap顯著減少。為此，進(jìn)一步分別設(shè)置運(yùn)行時(shí)間為4、5、7 h，應(yīng)用點(diǎn)-弧模型再次求解這兩個(gè)算例。算例9和算例10的求解質(zhì)量與計(jì)算時(shí)間的關(guān)系見圖4，觀察可知，這兩個(gè)算例的下界隨著計(jì)算時(shí)間的變化不明顯，但其上界在計(jì)算時(shí)間為3～4 h范圍存在陡降，從而使得Gap顯著減小，隨著計(jì)算時(shí)間的繼續(xù)增加，上界和Gap均趨于穩(wěn)定?？梢?，計(jì)算時(shí)間對(duì)于點(diǎn)-弧模型的求解性能具有影響，在實(shí)際應(yīng)用時(shí)，可取多組不同的計(jì)算時(shí)間進(jìn)行嘗試，從而對(duì)點(diǎn)-弧模型獲得求解質(zhì)量和計(jì)算時(shí)間的有效折中。

表9 弧-路模型與點(diǎn)-弧模型對(duì)比(運(yùn)行3 h)

表10 弧-路模型與點(diǎn)-弧模型對(duì)比(運(yùn)行10 h)

考察弧-路模型和點(diǎn)-弧模型線性松弛的定界效果。將模型中所有決策變量松弛為[0,1]的實(shí)數(shù)，限定運(yùn)行時(shí)間為3 h。表11對(duì)比兩個(gè)模型線性松弛的目標(biāo)函數(shù)值和求解時(shí)間。結(jié)果表明，相比弧-路模型，點(diǎn)-弧模型線性松弛的目標(biāo)函數(shù)值平均提高3.15%，最高達(dá)7.92%(第9個(gè)算例)。同時(shí)結(jié)合表9，兩個(gè)模型在分支定界過(guò)程中的最優(yōu)下界，相比它們的線性松弛改善都不明顯，分別僅增加3.99%和0.10%。在求解時(shí)間方面，點(diǎn)-弧模型線性松弛平均14 min就能求到最優(yōu)，但弧-路模型線性松弛在3 h內(nèi)都不能求出最優(yōu)解?？梢?，相比于弧-路模型，點(diǎn)-弧模型能夠在較短時(shí)間內(nèi)提供更緊的下界。

表11 弧-路模型與點(diǎn)-弧模型線性松弛對(duì)比

現(xiàn)將文獻(xiàn)[6]的樹分解算法和本文的點(diǎn)-弧模型進(jìn)行對(duì)比。為了對(duì)比的公平性，將點(diǎn)-弧模型的求解時(shí)間限制為樹分解算法的運(yùn)行時(shí)間。表12列出了兩種方法的上界、Gap和運(yùn)行時(shí)間。可看出，樹分解算法平均需要1.05 h，最長(zhǎng)運(yùn)行2.15 h，平均Gap為12.51%。而點(diǎn)-弧模型在相同運(yùn)行時(shí)間下，平均Gap為51.98%，其中有3個(gè)算例的Gap低于樹分解算法。同時(shí)結(jié)合表10可知，當(dāng)點(diǎn)-弧模型運(yùn)行時(shí)間延長(zhǎng)至10 h時(shí)，Gap都將顯著降低(全部低于5%)。

表12 樹分解算法與點(diǎn)-弧模型對(duì)比

5 結(jié)論

本文基于多商品網(wǎng)絡(luò)流理論研究了鐵路網(wǎng)上單組列車編組計(jì)劃優(yōu)化問題，借助于多商品網(wǎng)絡(luò)流點(diǎn)-弧模型的建?？蚣埽⒁粋€(gè)新的線性0-1規(guī)劃模型。得到如下結(jié)論：

(1)將車流視為商品、列流視為服務(wù)、車流的改編耗費(fèi)作為商品的變動(dòng)費(fèi)用、列流的集結(jié)耗費(fèi)作為服務(wù)的固定費(fèi)用，同時(shí)將車流不拆散和接續(xù)歸并原則、車站改編能力和調(diào)車線限制視為邊界約束，則路網(wǎng)單組列車編組計(jì)劃問題可轉(zhuǎn)換為1類多商品網(wǎng)絡(luò)流問題。

(2)采用點(diǎn)-弧方式設(shè)置車流改編變量，盡管不同于既有模型，但可以相互轉(zhuǎn)化。本文的模型在形式上更緊湊，模型的決策變量數(shù)和約束條件數(shù)都比文獻(xiàn)[6]的弧-路模型顯著減少，盡管該模型的規(guī)模比文獻(xiàn)[5]的模型稍多，但后者是一個(gè)非線性模型。

(3)車流接續(xù)歸并要求使得同終點(diǎn)車流的改編方案具有樹形結(jié)構(gòu)，利用這一特點(diǎn)，在多商品網(wǎng)絡(luò)流的建?？蚣芟?，通過(guò)引入輔助變量和約束可巧妙刻畫這一要求。小規(guī)模算例的計(jì)算結(jié)果表明，本文所提出的基于輔助變量的建模策略，能夠精確表達(dá)車流接續(xù)歸并原則。

(4)大規(guī)模算例的測(cè)試結(jié)果表明，本文的點(diǎn)-弧模型相較于文獻(xiàn)[6]的弧-路模型在相同時(shí)間限制下均可得到質(zhì)量更高的解。同時(shí)，點(diǎn)-弧模型的線性松弛容易求到最優(yōu)(約14 min)，而弧-路模型的線性松弛求解仍很困難。

(5)在相同的時(shí)間限制下，本文點(diǎn)-弧模型的可行解遜于文獻(xiàn)[6]的樹分解算法，但仍有3/10個(gè)算例的Gap優(yōu)于樹分解算法。適當(dāng)延長(zhǎng)運(yùn)行時(shí)間(至10 h)，點(diǎn)-弧模型的可行解將顯著提高(全部小于5%)，均優(yōu)于文獻(xiàn)[6]的樹分解算法。

本文研究可作進(jìn)一步拓展。首先，下一步可利用所構(gòu)建點(diǎn)-弧模型的較優(yōu)良的數(shù)學(xué)性質(zhì)和較高效計(jì)算性能，開發(fā)有效求解算法，以更好地求解更大規(guī)模問題。其次，單組列車編組計(jì)劃的質(zhì)量受給定車流徑路的影響，未來(lái)有價(jià)值研究?jī)烧呔C合優(yōu)化問題，考慮車流不拆散和接續(xù)歸并兩大原則，建立多項(xiàng)式規(guī)模的線性模型并設(shè)計(jì)求解算法。另外，列流設(shè)計(jì)方案與車流改編方案受到車流量、車站的集結(jié)與改編時(shí)間參數(shù)、改編能力及調(diào)車線數(shù)等參數(shù)的影響，后者的波動(dòng)性將會(huì)影響到鐵路貨物運(yùn)輸服務(wù)的質(zhì)量與效率，因而研究車站集結(jié)與改編時(shí)間參數(shù)等不確定性下的路網(wǎng)單組列車編組計(jì)劃優(yōu)化問題，也將是下一階段的方向。