陳崇雙,趙 軍,薛 鋒,郭孜政,左大杰2,
(1.西南交通大學(xué) 數(shù)學(xué)學(xué)院,四川 成都 611756;2.西南交通大學(xué) 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室,四川 成都 611756; 3.西南交通大學(xué) 交通運輸與物流學(xué)院,四川 成都 611756;4.西南交通大學(xué) 綜合交通智能化國家地方聯(lián)合工程實驗室,四川 成都 611756)
貨物列車編組計劃簡稱編組計劃(Train formation Plan, TFP),研究如何將車流組合編掛到各種不同到站和種類的列車之中,其合理編制是提高鐵路網(wǎng)車流組織效率和提供優(yōu)質(zhì)運輸服務(wù)的重要保證。
我國車流組織工作根據(jù)車流的性質(zhì)進(jìn)行分階段考慮,先確定裝車地、空車、班列等直達(dá)列車編組計劃,然后對未被其吸收的車流向就近的技術(shù)站集中,進(jìn)而編制技術(shù)站列車編組計劃,最后再確定剩余車流的區(qū)段管內(nèi)列車編組計劃[1]。在技術(shù)站列車編組計劃中,單組列車即列車僅編掛一個編組去向,相比分組列車其構(gòu)成較為簡單。由于我國鐵路車站改編能力和調(diào)車線不足,以及現(xiàn)場車流組織工作的簡便性等因素,貨物列車中單組列車的比例較高。
路網(wǎng)單組列車編組計劃需確定兩類決策:①網(wǎng)絡(luò)中開行哪些列流,即確定每支列流的始發(fā)終到站;②每支列流吸收哪些車流,從車流的角度來說,即確定每支車流在其徑路上每個車站的改編情況。單組列車編組計劃編制問題中,每支車流的徑路事先已知(如采用最短徑路、特定徑路等),只需要考慮如何經(jīng)濟(jì)可行地將車流組合成列流。其中,經(jīng)濟(jì)性體現(xiàn)在列流的集結(jié)費用和車輛的改編費用;可行性體現(xiàn)在滿足車站的改編能力、調(diào)車線數(shù)限制,以及運輸組織上的車流不拆散原則和接續(xù)歸并原則[1]。值得注意的是,車流徑路是編組計劃問題的輸入?yún)?shù),在其確定過程中已經(jīng)考慮了線路區(qū)間的通過能力。車流不拆散原則要求同一只車流作為一個整體進(jìn)行運輸,使編組計劃問題有別于經(jīng)典的實數(shù)型網(wǎng)絡(luò)流,而是整數(shù)型網(wǎng)絡(luò)流;接續(xù)歸并原則要求相同終點車流一旦在同一車站改編之后,它們合而不分,采用相同的改編方案輸送至共同的終點站,即同終點車流的改編方案具有樹形結(jié)構(gòu)。
目前,國內(nèi)外許多專家學(xué)者就鐵路網(wǎng)上單組列車編組計劃編制進(jìn)行長期探索,提出了比較合理的數(shù)學(xué)模型和有效的求解算法[2]。其中的代表文獻(xiàn)大致可以歸納為如下兩大類:
其一是采用數(shù)學(xué)規(guī)劃理論建模。曹家明等[3]設(shè)置車流的直達(dá)方案、一次改編和多次改編方案為0-1型決策變量,考慮每支車流的方案唯一性約束,建立二次0-1規(guī)劃模型;同時,巧妙引入獨立作業(yè)方式來減少變量數(shù)目,并利用系數(shù)矩陣的稀疏性和分塊特點進(jìn)行線性松弛求解。林柏梁等[4]和Lin等[5]都以車流改編方案和列流方案為0-1型決策變量,考慮方案唯一性約束、改編能力約束、調(diào)車線數(shù)量約束,構(gòu)建非線性雙層規(guī)劃模型,上層確定列車始發(fā)終到站,下層基于流量平衡思想確定車流改編方案。兩者在決策車流改編方案時略有差異,文獻(xiàn)[4]基于車流接續(xù)最遠(yuǎn)站法則,即將車流編入車流在始發(fā)站的最遠(yuǎn)去向,以實現(xiàn)無改編運行距離最遠(yuǎn);文獻(xiàn)[5]是由優(yōu)化模型計算確定。兩者都針對大規(guī)模問題設(shè)計模擬退火算法。Chen等[6]設(shè)置直達(dá)列流方案和車流可能的改編方案為0-1型決策變量,考慮方案唯一性約束、改編能力約束、調(diào)車線數(shù)量約束和接續(xù)歸并原則,建立線性0-1規(guī)劃模型,并設(shè)計基于樹分解的求解算法。
其二是采用網(wǎng)絡(luò)流思想建?;蛘咔蠼?,即將車流視為流,列流視為弧,列車集結(jié)耗費視為弧的固定耗費,改編中轉(zhuǎn)額外耗費視為該弧的長度。李致中等[7]就小規(guī)模路網(wǎng)情形建立無約束的網(wǎng)絡(luò)流模型。史峰等[8]考慮車站改編能力和編組去向數(shù)目限制情形建模,并給出逐步添加編組去向的貪婪算法。史峰等[9]提出合并式編組方案的概念,在給定每個站的編組去向方案集的條件下將原問題轉(zhuǎn)化為以各站為終點的普通最短路問題。查偉雄等[10]設(shè)置決策變量類似文獻(xiàn)[5],考慮車站編組去向數(shù)目約束和車流接續(xù)歸并,建立了非線性(目標(biāo)函數(shù)是高階多項式)0-1規(guī)劃模型。該文獻(xiàn)將開行直達(dá)列車視為新建一個服務(wù),由此將原問題轉(zhuǎn)化為服務(wù)系統(tǒng)選址問題,給出逐步減少直達(dá)列流方案(即保留有利的編組去向)的啟發(fā)式算法。
從既有研究可見,鐵路網(wǎng)絡(luò)單組列車編組計劃問題,雖然具有多商品網(wǎng)絡(luò)流問題的特點,但是車流接續(xù)歸并原則這一獨特約束所蘊(yùn)含的樹形結(jié)構(gòu),使得對其不易建立線性模型和設(shè)計有效算法。例如,文獻(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ī)劃算法,例如前兩者運用模擬退火算法,后兩者設(shè)計加弧減弧的啟發(fā)式方法等。同時,Chen等[6]雖然建立了線性0-1規(guī)劃模型,但是其模型規(guī)模隨網(wǎng)絡(luò)擴(kuò)大呈指數(shù)增長,而且樹分解算法對于大規(guī)模問題的最優(yōu)間隔(Gap)仍不算很理想。
本文將路網(wǎng)單組列車編組計劃優(yōu)化視為1類具有樹形結(jié)構(gòu)的多商品網(wǎng)絡(luò)流問題,在多商品網(wǎng)絡(luò)流的點-弧模型的建??蚣芟?,將車流視為商品,引入一組0-1變量刻畫每支車流如何選擇列流;將直達(dá)列流視為服務(wù),引入一組0-1變量刻畫網(wǎng)絡(luò)中開行哪些列流;再引入一類輔助變量保證車流接續(xù)歸并?;诖?,以列流集結(jié)耗費和車流改編耗費總和最小為目標(biāo),同時考慮車站改編能力和調(diào)車線數(shù)約束,建立基于多商品網(wǎng)絡(luò)流點-弧結(jié)構(gòu)的線性0-1規(guī)劃模型。在合理的求解時間范圍內(nèi),該模型能夠得到高質(zhì)量的可行解以及緊致的下界。最后采取演示算例和大規(guī)模算例,對所構(gòu)建模型的正確性和有效性進(jìn)行驗證。
參數(shù)及其符號說明見表1。
表1 參數(shù)和符號說明
單組列車編組計劃建模,涉及一個有向網(wǎng)絡(luò)G=(V,E),其中節(jié)點集合V即車站集合,其元素為技術(shù)站和線路交匯的支點站等,有向弧集合E是直接相連的線路區(qū)間集合,線路的上下行方向分別對應(yīng)一條有向邊。每支車流(o,d)的徑路已知,可以表示為從其始發(fā)站o至終到站d沿途經(jīng)過車站的有序集合。在單組列車編組計劃問題中,由于各列流〈i,j〉的編組內(nèi)容僅為一個組的車流,該列車的運行徑路可以視為相同始發(fā)終到站的車流(i,j)的徑路。
由于車流徑路的限制,并非每支車流都可以編組到所有的列流當(dāng)中。對于車流(o,d)來說,其實際能夠編組到的列流可以表示為集合
(1)
圖1 包含8個站的簡單路網(wǎng)
表2 決策變量
單組列車編組計劃問題的目標(biāo)函數(shù)包括兩項。第一項為列流的集結(jié)耗費,僅與列流設(shè)計變量有關(guān),相當(dāng)于固定費用;另一項是車流在途中車站(不包括始發(fā)站和終到站)的改編耗費,與車流改編變量有關(guān),相當(dāng)于變動費用。目標(biāo)函數(shù)為
(2)
2.2.1 車流流量守恒約束
每支車流都需滿足以下的流量守恒約束,即每支車流都沿著其給定徑路從其始發(fā)站被輸送至其終點站。與一般多商品網(wǎng)絡(luò)流的流量守恒稍有區(qū)別的是,該組約束僅考慮各支車流在其給定徑路上每個站的流量平衡,而不需要考慮徑路之外的車站。其原因在于,車流徑路已經(jīng)事先給定,各支車流只能在其給定徑路上沿著從其始發(fā)站至其終到站的方向和軌跡流動。
2.2.2 車站改編能力約束
到達(dá)某站的車流,包括終到該站的計劃車流和在該站進(jìn)行途中改編的車流,都需要消耗該站的改編能力。在某站改編的總車流量不能超過其可用改編能力,即
(4)
2.2.3 車站調(diào)車線數(shù)約束
從某站出發(fā)的車流,包括從該站始發(fā)的計劃車流和在該站進(jìn)行途中改編的車流,都需要占用該站的調(diào)車線。從某站出發(fā)的總車流量與該站單條調(diào)車線的平均容納能力之比,視為這些車流實際占用的調(diào)車線數(shù),不能超過該站可用調(diào)車線數(shù)的限制,即
(5)
注意,文獻(xiàn)[4-5]采用分段線性函數(shù)刻畫車流占用的調(diào)車線數(shù),本文采用線性度量策略。
2.2.4 車流接續(xù)歸并約束
車流接續(xù)歸并要求到達(dá)相同終點的車流,一旦在同一個站改編之后,必須采用相同的改編方案從改編站輸送至終點站,即同終點車流的改編方案具有樹形結(jié)構(gòu)。本文用約束式(6)、式(7)共同刻畫車流接續(xù)歸并要求。
(6)
(7)
2.2.5 變量關(guān)聯(lián)約束
(8)
約束式(8)包含兩種情形:
綜上,從多商品網(wǎng)絡(luò)流角度將路網(wǎng)單組列車編組計劃問題構(gòu)建為
?o,d∈Vi∈Po,d
yi,j∈{0,1} ?i,j∈V
其二,同樣由于車流徑路的原因,車流流量守恒約束式(3)只要求每支車流在其給定徑路上每個車站成立,而非要求在網(wǎng)絡(luò)中的全部車站;同時,變量關(guān)聯(lián)約束式(8)確保每支車流的徑路與其選擇列流的徑路具有一致性。
其三,為滿足特殊的車流接續(xù)歸并要求,本文所構(gòu)建的模型額外引入了約束式(6)和式(7),保證同終點車流的改編方案具有樹形結(jié)構(gòu)。可見,本文模型中的車流改編變量比一般的多商品網(wǎng)絡(luò)流模型具有更嚴(yán)格的要求。
文獻(xiàn)[5-6]是最近路網(wǎng)單組列車編組計劃優(yōu)化領(lǐng)域的兩篇典型文獻(xiàn),二者的建模思路和求解算法也各具特點。本節(jié)從決策變量表達(dá)形式、模型規(guī)模和模型特點3個方面,將這兩篇文獻(xiàn)的模型與本文模型進(jìn)行較為詳細(xì)的對比分析。
車流改編變量的3種表達(dá)形式可以相互轉(zhuǎn)化,下表3以直線單方向上4個車站為例進(jìn)行說明。表3中,第1列是車流改編方案的序號,第2列是對應(yīng)的列流方案,第3~5列分別是3種表達(dá)方式的車流改編變量的取值。注意,表中省略了直達(dá)車流的改編變量。例如,第10種方案中,每支車流都是直達(dá),沒有車流采用改編,故非直達(dá)車流的改編變量為空。
表3 3種車流改編變量表達(dá)形式的相互轉(zhuǎn)化
3種模型的規(guī)模估計見表4??梢钥闯?,本文模型的決策變量和約束條件的階數(shù)都為O(N4),多于文獻(xiàn)[5],但是遠(yuǎn)少于文獻(xiàn)[6],后者呈指數(shù)增長。主要原因在于文獻(xiàn)[6]采用全枚舉的方式設(shè)置車流改編變量,同時對每個車流改編變量提供一個約束保證接續(xù)歸并。此外,雖然文獻(xiàn)[5]的模型規(guī)模最小,但是由遞推的車流改編變量顯式表達(dá)車站的改編負(fù)荷和改編費用時,將出現(xiàn)決策變量的乘積項。即使可以引入新的變量和約束消除乘積項進(jìn)行線性化,然而一方面網(wǎng)絡(luò)情形的表達(dá)將會非常復(fù)雜,另一方面也導(dǎo)致模型規(guī)模迅速增長。
表4 模型規(guī)模估計
三種模型的特點總結(jié)見表5??梢?,在車流改編變量設(shè)置上,文獻(xiàn)[5]采用隱式遞推方式,使得模型具有非線性的結(jié)構(gòu)。盡管文獻(xiàn)[6]和本文都建立了線性的0-1規(guī)劃模型,但結(jié)構(gòu)也有差異。文獻(xiàn)[6]的車流改編變量,列舉了車流從始發(fā)站至終到站全過程的所有可能改編方案,而本文的車流改編變量僅確定車流對單支列流編掛與否。因而前者構(gòu)建的是多商品網(wǎng)絡(luò)流的弧-路模型,而本文建立的是點-弧模型。其次,在車流接續(xù)歸并實現(xiàn)手段上,三者迥異。文獻(xiàn)[5]基于遞推方式設(shè)置的車流改編變量,每支車流改編方案的唯一性實現(xiàn)了接續(xù)歸并。文獻(xiàn)[6]以全枚舉方式呈現(xiàn)每支車流的全部改編方案,直接比較同終點車流的改編方案的一致性,以判斷接續(xù)歸并原則是否滿足。而本文通過巧妙引入輔助變量和線性約束條件,正確刻畫車流改編方案之間的樹形關(guān)系。
表5 模型特點對比
采用1個演示算例和1組大規(guī)模算例,對所構(gòu)建模型的正確性和有效性進(jìn)行分析。采用Matab 2016a編程,并調(diào)用CPLEX 12.6求解優(yōu)化模型。為了公平比較,所有計算都在CPU為E5-2620 2.10 GHz、內(nèi)存為128 GB的64位GPU上運行。如果沒有特別說明,CPLEX的參數(shù)都為默認(rèn)配置。
以文獻(xiàn)[5]中的小規(guī)模算例,測試本文模型的正確性。該算例的路網(wǎng)是我國哈爾濱局路網(wǎng)的簡化,共包含19個支點站,23條邊,314支車流。所有車流的徑路都按最短徑路設(shè)置。文獻(xiàn)[5]中車站的可用改編能力,是已經(jīng)扣除了終到車流消耗的結(jié)果。為了讓本文的計算結(jié)果具有可比性,這里將約束式(4)調(diào)整為
(9)
對于這個算例,本文的點-弧模型式(2)、式(3)和式(5)~式(9)包含5 066個決策變量,8 926個約束。設(shè)置CPLEX的收斂mipgap為0時,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時,表示開行直達(dá)列流〈i,j〉。車流的完整改編方案可以由該表遞推得出。以車流(7,2)為例進(jìn)行說明,由表6,該車流先在站5改編后編組到列流〈5,3〉,在站3再次改編后編組到列流〈3,2〉運送至終點站,因而車流(7,2)的改編站為5和3。該表與文獻(xiàn)[6]的弧-路模型的最優(yōu)解并不完全相同,表7列出了改編方案不相同的三支車流。由于它們的車流量均是0,故對于目標(biāo)函數(shù)值不影響。
表6 最優(yōu)車流改編方案
表7 點-弧模型與弧-路模型最優(yōu)解的不同
接下來分析本文點-弧模型對于車流接續(xù)歸并原則的正確性。由問題定義,車流接續(xù)歸并原則規(guī)定,如果同終點的兩支車流都在某站改編,那么從該改編站至終點站的輸送過程中,它們將采用相同的改編方案。本質(zhì)上,車流接續(xù)歸并原則強(qiáng)制約束同終點車流的改編方案具有樹形結(jié)構(gòu)。為了直觀反映這種特殊關(guān)系,以終點為站2的18支車流為例進(jìn)行說明。車流的徑路見圖2(a)。注意,本算例設(shè)定所有車流的徑路都取為其最短路,因此,由最短性原則,終點為站2的車流的最短路構(gòu)成一顆無向樹,根節(jié)點即為站2。車流的最優(yōu)改編方案,見圖2(b)。可見,除了站2之外,其他站都只有唯一一條出弧,即最優(yōu)改編方案是以站2為根節(jié)點的一棵有向樹。對比圖2(a)和圖2(b)可知,如果車流采用直達(dá)方案,無所謂改編;如果采用改編方案,則改編站都限制在其給定車流徑路上。例如,對于車流(6,2),其車流徑路P6,2={6,5,4,3,2},途中改編車站為5和4均在其車流徑路上。
圖2 終點為站2的18支車流
圖3 松弛接續(xù)歸并約束后車流(5,2)和(6,2)的改編方案
以文獻(xiàn)[6]中的10個大規(guī)模算例,驗證所提出方法的有效性。這些算例的路網(wǎng)是我國鐵路貨運網(wǎng)絡(luò)的簡化,包括83個車站,158條邊,平均約5 700支車流,所有車流的徑路都給定為最短徑路。由于文獻(xiàn)[5]采用分段線性函數(shù)刻畫車站調(diào)車線數(shù)約束,而且具有非線性結(jié)構(gòu),故本文點-弧模型僅與文獻(xiàn)[6]的弧-路模型以及樹分解算法進(jìn)行對比。
文獻(xiàn)[6]的弧-路模型和本文的點-弧模型,規(guī)模對比見表8。本文模型的決策變量數(shù)和約束條件數(shù)都僅相當(dāng)于文獻(xiàn)[6]的3%,而且系數(shù)矩陣非常稀疏,非零元僅占1.39×10-5。
表8 大規(guī)模算例模型規(guī)模對比
對比弧-路模型和點-弧模型的解質(zhì)量,設(shè)置CPLEX最長運行時間為3 h,結(jié)果對比見表9。由表9可得,在3 h限制時間下,一方面,弧-路模型的下界都比點-弧模型小,甚至該模型對算例1、4、5和6的下界為0。另一方面,弧-路模型的上界都比點弧模型大。由于這兩方面的原因,弧-路模型的平均最優(yōu)間隔(Gap)高達(dá)63.65%,而點-弧模型平均Gap為9.03%。由于點-弧模型對于算例9和10的Gap較高,為此延長CPLEX最長運行時間為10 h,兩個模型的結(jié)果對比見表10。延長運行時間后,弧-路模型的下界和上界稍有改善,但平均Gap仍高達(dá)60.79%。然而點-弧模型的平均Gap為1.55%,全部Gap低于5%。
對比表9和表10還可發(fā)現(xiàn),當(dāng)計算時間從3 h延長至10 h,點-弧模型對于算例9和算例10的Gap顯著減少。為此,進(jìn)一步分別設(shè)置運行時間為4、5、7 h,應(yīng)用點-弧模型再次求解這兩個算例。算例9和算例10的求解質(zhì)量與計算時間的關(guān)系見圖4,觀察可知,這兩個算例的下界隨著計算時間的變化不明顯,但其上界在計算時間為3~4 h范圍存在陡降,從而使得Gap顯著減小,隨著計算時間的繼續(xù)增加,上界和Gap均趨于穩(wěn)定??梢?,計算時間對于點-弧模型的求解性能具有影響,在實際應(yīng)用時,可取多組不同的計算時間進(jìn)行嘗試,從而對點-弧模型獲得求解質(zhì)量和計算時間的有效折中。
表9 弧-路模型與點-弧模型對比(運行3 h)
表10 弧-路模型與點-弧模型對比(運行10 h)
考察弧-路模型和點-弧模型線性松弛的定界效果。將模型中所有決策變量松弛為[0,1]的實數(shù),限定運行時間為3 h。表11對比兩個模型線性松弛的目標(biāo)函數(shù)值和求解時間。結(jié)果表明,相比弧-路模型,點-弧模型線性松弛的目標(biāo)函數(shù)值平均提高3.15%,最高達(dá)7.92%(第9個算例)。同時結(jié)合表9,兩個模型在分支定界過程中的最優(yōu)下界,相比它們的線性松弛改善都不明顯,分別僅增加3.99%和0.10%。在求解時間方面,點-弧模型線性松弛平均14 min就能求到最優(yōu),但弧-路模型線性松弛在3 h內(nèi)都不能求出最優(yōu)解??梢?,相比于弧-路模型,點-弧模型能夠在較短時間內(nèi)提供更緊的下界。
表11 弧-路模型與點-弧模型線性松弛對比
現(xiàn)將文獻(xiàn)[6]的樹分解算法和本文的點-弧模型進(jìn)行對比。為了對比的公平性,將點-弧模型的求解時間限制為樹分解算法的運行時間。表12列出了兩種方法的上界、Gap和運行時間。可看出,樹分解算法平均需要1.05 h,最長運行2.15 h,平均Gap為12.51%。而點-弧模型在相同運行時間下,平均Gap為51.98%,其中有3個算例的Gap低于樹分解算法。同時結(jié)合表10可知,當(dāng)點-弧模型運行時間延長至10 h時,Gap都將顯著降低(全部低于5%)。
表12 樹分解算法與點-弧模型對比
本文基于多商品網(wǎng)絡(luò)流理論研究了鐵路網(wǎng)上單組列車編組計劃優(yōu)化問題,借助于多商品網(wǎng)絡(luò)流點-弧模型的建??蚣埽⒁粋€新的線性0-1規(guī)劃模型。得到如下結(jié)論:
(1)將車流視為商品、列流視為服務(wù)、車流的改編耗費作為商品的變動費用、列流的集結(jié)耗費作為服務(wù)的固定費用,同時將車流不拆散和接續(xù)歸并原則、車站改編能力和調(diào)車線限制視為邊界約束,則路網(wǎng)單組列車編組計劃問題可轉(zhuǎn)換為1類多商品網(wǎng)絡(luò)流問題。
(2)采用點-弧方式設(shè)置車流改編變量,盡管不同于既有模型,但可以相互轉(zhuǎn)化。本文的模型在形式上更緊湊,模型的決策變量數(shù)和約束條件數(shù)都比文獻(xiàn)[6]的弧-路模型顯著減少,盡管該模型的規(guī)模比文獻(xiàn)[5]的模型稍多,但后者是一個非線性模型。
(3)車流接續(xù)歸并要求使得同終點車流的改編方案具有樹形結(jié)構(gòu),利用這一特點,在多商品網(wǎng)絡(luò)流的建??蚣芟拢ㄟ^引入輔助變量和約束可巧妙刻畫這一要求。小規(guī)模算例的計算結(jié)果表明,本文所提出的基于輔助變量的建模策略,能夠精確表達(dá)車流接續(xù)歸并原則。
(4)大規(guī)模算例的測試結(jié)果表明,本文的點-弧模型相較于文獻(xiàn)[6]的弧-路模型在相同時間限制下均可得到質(zhì)量更高的解。同時,點-弧模型的線性松弛容易求到最優(yōu)(約14 min),而弧-路模型的線性松弛求解仍很困難。
(5)在相同的時間限制下,本文點-弧模型的可行解遜于文獻(xiàn)[6]的樹分解算法,但仍有3/10個算例的Gap優(yōu)于樹分解算法。適當(dāng)延長運行時間(至10 h),點-弧模型的可行解將顯著提高(全部小于5%),均優(yōu)于文獻(xiàn)[6]的樹分解算法。
本文研究可作進(jìn)一步拓展。首先,下一步可利用所構(gòu)建點-弧模型的較優(yōu)良的數(shù)學(xué)性質(zhì)和較高效計算性能,開發(fā)有效求解算法,以更好地求解更大規(guī)模問題。其次,單組列車編組計劃的質(zhì)量受給定車流徑路的影響,未來有價值研究兩者綜合優(yōu)化問題,考慮車流不拆散和接續(xù)歸并兩大原則,建立多項式規(guī)模的線性模型并設(shè)計求解算法。另外,列流設(shè)計方案與車流改編方案受到車流量、車站的集結(jié)與改編時間參數(shù)、改編能力及調(diào)車線數(shù)等參數(shù)的影響,后者的波動性將會影響到鐵路貨物運輸服務(wù)的質(zhì)量與效率,因而研究車站集結(jié)與改編時間參數(shù)等不確定性下的路網(wǎng)單組列車編組計劃優(yōu)化問題,也將是下一階段的方向。