鐵路集裝箱運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)及Benders 分解算法*

江雨星 ?；菝?高如虎

（蘭州交通大學(xué)交通運(yùn)輸學(xué)院 蘭州730070）

0 引 言

鐵路運(yùn)輸正日益成為國(guó)際、國(guó)內(nèi)集裝箱運(yùn)輸組織的重要形式。作為鐵路集裝箱運(yùn)輸戰(zhàn)術(shù)規(guī)劃層次的重要內(nèi)容，動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的主要目標(biāo)不僅是制定列車(chē)的開(kāi)行計(jì)劃，還需要確定出合理的集裝箱分配及中轉(zhuǎn)方案，力求在滿足多樣化的運(yùn)輸需求、提高客戶滿意度的同時(shí)，盡可能的降低鐵路企業(yè)的運(yùn)營(yíng)成本?？梢?jiàn)，鐵路集裝箱運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)與優(yōu)化具有重要的現(xiàn)實(shí)意義。

貨物運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題分為靜態(tài)服務(wù)網(wǎng)絡(luò)和動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)2 個(gè)研究領(lǐng)域，前者是確定運(yùn)輸服務(wù)的徑路、開(kāi)行頻度及貨流的分配，而后者是將前者內(nèi)容與時(shí)間信息結(jié)合起來(lái)進(jìn)行優(yōu)化，從而得到更為詳細(xì)的運(yùn)輸方案[1]。國(guó)內(nèi)外學(xué)者對(duì)于貨物運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題作了大量研究，其中，鐵路貨物運(yùn)輸?shù)南嚓P(guān)文獻(xiàn)一直占據(jù)相當(dāng)大的比重。Duan等[2]考慮了鐵路貨物運(yùn)輸?shù)臅r(shí)效性及可靠性，通過(guò)構(gòu)建線性整數(shù)規(guī)劃模型和設(shè)計(jì)啟發(fā)式算法，實(shí)現(xiàn)貨物在列車(chē)服務(wù)中的分配。Lulli 等[3]以意大利鐵路貨物運(yùn)輸為背景，研究了服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)方法。王保華等[4]研究了考慮車(chē)輛周轉(zhuǎn)的鐵路貨物運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。沈睿[5]針對(duì)行包專(zhuān)列靜態(tài)服務(wù)網(wǎng)絡(luò)和客運(yùn)普包動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，分別構(gòu)建了整數(shù)規(guī)劃模型。唐金金等[6]以車(chē)流總旅行費(fèi)用最小為目標(biāo)，構(gòu)建了服務(wù)網(wǎng)絡(luò)動(dòng)態(tài)配流的優(yōu)化模型。

對(duì)于時(shí)效性要求較高的鐵路集裝箱運(yùn)輸，既有研究主要為靜態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)。夏陽(yáng)等[7]針對(duì)客運(yùn)化模式下的鐵路集裝箱運(yùn)輸系統(tǒng)，建立了班列開(kāi)行方案的優(yōu)化模型，并設(shè)計(jì)模擬退火算法進(jìn)行求解。張小強(qiáng)等[8]對(duì)鐵路集裝箱班列開(kāi)行決策與運(yùn)輸價(jià)格制定的協(xié)同優(yōu)化進(jìn)行了研究。閆偉等[9]通過(guò)構(gòu)建數(shù)學(xué)優(yōu)化模型解決了鐵路集裝箱運(yùn)輸組織模式選擇及班列開(kāi)行方案制定的問(wèn)題。

從既有研究中可知，運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)通常是1個(gè)大規(guī)模的線性?xún)?yōu)化問(wèn)題，涉及眾多決策變量及約束條件，如何設(shè)計(jì)有效的求解算法，同樣是許多學(xué)者關(guān)注的問(wèn)題。啟發(fā)式算法是常采用的方法，如模擬退火算法[2]、遺傳算法[10-11]等，雖然這些方法可在接受的時(shí)間內(nèi)給出優(yōu)化問(wèn)題的1 個(gè)可行解，但是無(wú)法評(píng)判該可行解與最優(yōu)解的偏離程度。為此，部分學(xué)者運(yùn)用了分解思想，將大規(guī)模的復(fù)雜問(wèn)題分解為若干規(guī)模較小的子問(wèn)題，如列生成算法[12]、拉格朗日算法[13-14]等。針對(duì)于大規(guī)模線性混合整數(shù)規(guī)劃，部分學(xué)者運(yùn)用了Benders 分解算法，將原問(wèn)題按變量類(lèi)型分解為相對(duì)易于求解的主問(wèn)題與子問(wèn)題，通過(guò)反復(fù)迭代得到原問(wèn)題的最優(yōu)解。該方法已多次用于解決網(wǎng)絡(luò)設(shè)計(jì)的相關(guān)優(yōu)化問(wèn)題，例如Fontain等[15]運(yùn)用Benders 分解算法解決了危險(xiǎn)貨物運(yùn)輸?shù)木W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，Gelareh 等[16]運(yùn)用該算法求解了班輪運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化模型。但是，Benders分解算法存在一般迭代算法的缺點(diǎn)，如迭代次數(shù)多、收斂較慢等。為克服這些問(wèn)題，部分文獻(xiàn)中對(duì)該算法進(jìn)行了改進(jìn)。何必勝[17]在每一次迭代中，運(yùn)用智能算法獲取大量的可行解,并以此得到多個(gè)割平面，減少主問(wèn)題的解空間。Naoum 等[18]和Fortz 等[19]針對(duì)于一類(lèi)特定問(wèn)題中對(duì)偶子問(wèn)題存在多個(gè)最優(yōu)解會(huì)產(chǎn)生不同割平面的情況，運(yùn)用Pareto 最優(yōu)割平面的理論對(duì)算法進(jìn)行了改進(jìn)。

綜上，對(duì)于鐵路貨物運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，現(xiàn)有研究已取得豐富成果。由于該問(wèn)題涉及眾多因素及約束條件，求解難度大，既有文獻(xiàn)在研究時(shí)，對(duì)問(wèn)題進(jìn)行了簡(jiǎn)化，優(yōu)化時(shí)沒(méi)有考慮貨物中轉(zhuǎn)方案與動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的同時(shí)優(yōu)化, 是在給定貨物中轉(zhuǎn)方案的基礎(chǔ)上,考慮如何設(shè)計(jì)服務(wù)網(wǎng)絡(luò)。而貨物中轉(zhuǎn)方案是鐵路貨物運(yùn)輸決策的核心，與列車(chē)開(kāi)行計(jì)劃的制定緊密聯(lián)系?；谶@一現(xiàn)狀，筆者依據(jù)集裝箱的流量及流向（下文簡(jiǎn)稱(chēng)為箱流），充分考慮箱流的中轉(zhuǎn)方案，構(gòu)建鐵路集裝箱運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的線性規(guī)劃模型，運(yùn)用Benders分解方法將原問(wèn)題分解為僅包含0-1 變量的網(wǎng)絡(luò)設(shè)計(jì)主問(wèn)題及固定0-1變量后的箱流分配子問(wèn)題，并在主問(wèn)題模型中添加有效不等式，使主問(wèn)題更加緊致，以加快算法的收斂速度。

1 問(wèn)題描述

目前，我國(guó)鐵路運(yùn)輸部門(mén)組織開(kāi)行的集裝箱班列主要為直達(dá)班列，即班列在途經(jīng)站不辦理任何集裝箱裝卸和車(chē)組甩掛作業(yè)。基于此，本次研究中假定任意2個(gè)集裝箱辦理站（以下簡(jiǎn)稱(chēng)為辦理站）間開(kāi)行的集裝箱班列均為直達(dá)班列。結(jié)合動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)構(gòu)建的思想，先將設(shè)計(jì)周期劃分為一定數(shù)量的單位時(shí)段，再將鐵路物理網(wǎng)絡(luò)中的辦理站點(diǎn)按照周期及各個(gè)時(shí)段拆分為若干節(jié)點(diǎn)，此時(shí)每個(gè)節(jié)點(diǎn)即代表所在辦理站，又代表所處時(shí)段。為能反應(yīng)箱流在途經(jīng)站的中轉(zhuǎn)作業(yè)過(guò)程，進(jìn)一步將每個(gè)節(jié)點(diǎn)拆分為接入節(jié)點(diǎn)和出發(fā)節(jié)點(diǎn)。在此過(guò)程中，需要注意單位時(shí)段的取值，參照客運(yùn)普包動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)中單位時(shí)段的確定方法[5]，令箱流的中轉(zhuǎn)作業(yè)時(shí)間為單位時(shí)段。見(jiàn)圖1，已知設(shè)有4 個(gè)辦理站的鐵路線路，研究周期為24 h，箱流中轉(zhuǎn)作業(yè)時(shí)長(zhǎng)為3 h，則單位時(shí)段為3 h。構(gòu)建的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)見(jiàn)圖2。節(jié)點(diǎn)間的有向弧段分為3 類(lèi)：①弧段的起終節(jié)點(diǎn)所在辦理站相同，且同為接入節(jié)點(diǎn)或同為出發(fā)節(jié)點(diǎn)，所處時(shí)段為相鄰的2 個(gè)時(shí)段，這類(lèi)有向弧段為延遲弧段，代表集裝箱在辦理站的等待過(guò)程，見(jiàn)圖2中的延遲弧段1；②弧段的起終節(jié)點(diǎn)所在辦理站相同，但時(shí)段不同，且起點(diǎn)為接入節(jié)點(diǎn)，終點(diǎn)為出發(fā)節(jié)點(diǎn)，這類(lèi)有向弧段為中轉(zhuǎn)弧段，代表集裝箱在辦理站的中轉(zhuǎn)作業(yè)過(guò)程，見(jiàn)圖2中的中轉(zhuǎn)弧段1；③弧段的起終節(jié)點(diǎn)所處時(shí)段不同，且起點(diǎn)為某一辦理站的出發(fā)節(jié)點(diǎn)，終點(diǎn)為另一辦理站的接入節(jié)點(diǎn)，這類(lèi)有向弧段為班列弧段，代表辦理站之間提供的每一趟班列服務(wù)，見(jiàn)圖2 中的班列弧段1。參考集裝箱班列開(kāi)行方案的編制[7]，本文中班列服務(wù)開(kāi)行與否的決策采用基于備選集的方法，備選集是研究周期內(nèi)可提供運(yùn)輸服務(wù)的所有班列弧段的1個(gè)集合。

圖1 鐵路物理網(wǎng)絡(luò)圖Fig.1 Railway physical network

圖2 動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)Fig.2 Dynamic service network

鐵路集裝箱運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)，就是在弧段集合中選出一系列連續(xù)的弧段組成服務(wù)路徑來(lái)運(yùn)輸節(jié)點(diǎn)間的集裝箱。對(duì)于任意2 個(gè)節(jié)點(diǎn)間的箱流，可能有多條服務(wù)路徑供其選擇，不同的服務(wù)路徑代表著不同的運(yùn)輸方案。若箱流中轉(zhuǎn)方案改變，選擇的服務(wù)路徑會(huì)隨之改變。例如：已知箱流1，其出發(fā)站為B，目的站為D，產(chǎn)生時(shí)段為第3時(shí)段，運(yùn)到期限為5 個(gè)時(shí)段，該箱流在動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)中的出發(fā)及目的節(jié)點(diǎn)見(jiàn)圖2 中虛線圓圈標(biāo)記，其中目的節(jié)點(diǎn)是通過(guò)出發(fā)節(jié)點(diǎn)所處時(shí)段加上運(yùn)到期限來(lái)確定。若B站至D 站的箱流選擇直達(dá)運(yùn)輸，則箱流1 可由延遲弧段1、延遲弧段2 和班列弧段3 組成的服務(wù)路徑來(lái)運(yùn)輸，該方案表示箱流1 在B 站停留至第5 時(shí)段，由該站在第5 時(shí)段組織開(kāi)往D 站的班列進(jìn)行直達(dá)運(yùn)輸；若B站至D站的箱流在C站中轉(zhuǎn)，且中轉(zhuǎn)后由C站發(fā)往D 站的班列承運(yùn)，則箱流1 可由班列弧段1、中轉(zhuǎn)弧段1和班列弧段2組成的服務(wù)路徑運(yùn)輸，該方案表示箱流1 由B 站在第3 時(shí)段發(fā)往C 站的班列承運(yùn)，到達(dá)C 站后卸下，再裝至C 站在第6 時(shí)段發(fā)往D站的班列將其運(yùn)至目的節(jié)點(diǎn)，其中在C 站的中轉(zhuǎn)作業(yè)消耗了1個(gè)時(shí)段。可見(jiàn)，中轉(zhuǎn)方案的考慮，使得箱流與弧段的對(duì)應(yīng)關(guān)系變得更為復(fù)雜，從而極大的增加了動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的難度。在優(yōu)化過(guò)程中，假設(shè)辦理站作業(yè)能力始終滿足運(yùn)輸需求，既不考慮延遲弧段和中轉(zhuǎn)弧段的能力限制。

2 優(yōu)化模型構(gòu)建

2.1 參變量定義

2.2 優(yōu)化模型

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

本文以總成本最小為優(yōu)化目標(biāo)，總成本分為2個(gè)部分,一部分是班列的開(kāi)行成本,另一部分是與集裝箱運(yùn)輸有關(guān)的成本，后者又包括途中運(yùn)輸成本、延遲成本及中轉(zhuǎn)作業(yè)成本，則目標(biāo)函數(shù)見(jiàn)式（1）。

2.2.2 約束條件

1）流量守恒約束。動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)中所有節(jié)點(diǎn)上進(jìn)、出箱流量必須滿足守恒約束,不得出現(xiàn)箱流的缺失或增加，并保證箱流能夠從出發(fā)節(jié)點(diǎn)運(yùn)至目的節(jié)點(diǎn)。

為了保障送達(dá)速度,通常會(huì)要求辦理站l 至辦理站k 的集裝箱在途經(jīng)站的中轉(zhuǎn)次數(shù)不能超過(guò)規(guī)定的最大次數(shù)ml，k。

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

3.1 子問(wèn)題對(duì)偶模型

3.2 主問(wèn)題模型

3.3 Benders分解算法流程

3.4 Benders分解算法改進(jìn)

圖3 Benders分解算法流程圖Fig.3 Flow for Benders decomposition

圖4 鐵路物理網(wǎng)絡(luò)圖Fig.4 Railway physical network

4 求解算例

4.1 參數(shù)輸入

選取北京、鄭州、西安、武漢、成都和蘭州這6 個(gè)鐵路集裝箱辦理站構(gòu)建集裝箱運(yùn)輸網(wǎng)絡(luò)，見(jiàn)圖4。圖中圓圈表示集裝箱辦理站，連線為辦理站之間的路段。決策周期為24 h，考慮到箱流在辦理站上的中轉(zhuǎn)作業(yè)時(shí)間為3 h，則構(gòu)建動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)時(shí)單位時(shí)段的取值為3 h。單個(gè)集裝箱的中轉(zhuǎn)作業(yè)成本為20 元/箱，延遲成本為10 元/箱。班列的最大編成箱數(shù)為50 箱。班列服務(wù)相關(guān)參數(shù)見(jiàn)表1，箱流信息見(jiàn)表2。

表1 班列服務(wù)相關(guān)參數(shù)Tab.1 Related parameters of train service

表2 箱流信息Tab.2 Information of container flows

4.2 數(shù)值結(jié)果

4.2.1 結(jié)果分析

算法由Python 語(yǔ)言實(shí)現(xiàn)，運(yùn)行環(huán)境為1 臺(tái)CPU Intel，4GB內(nèi)存的個(gè)人計(jì)算機(jī)，算法中的主問(wèn)題與子問(wèn)題均通過(guò)GUROBI 進(jìn)行求解。主問(wèn)題的初始解為所有箱流均采用直達(dá)運(yùn)輸模式的服務(wù)網(wǎng)絡(luò)，相應(yīng)的集裝箱班列開(kāi)行方案見(jiàn)表3，代入子問(wèn)題模型求解得到該方案的總成本為552 480元。在經(jīng)過(guò)69次迭代，運(yùn)行46 s 后得到最終解，總成本為439 490 元，最終的Gap為1.56%。為分析算法性能，運(yùn)用未改進(jìn)的Benders 分解對(duì)該算例進(jìn)行求解。在運(yùn)行了相同的時(shí)間46 s 后，得到目標(biāo)函數(shù)值為450 490 元，Gap為45.17%?？梢?jiàn)，提出的改進(jìn)策略有效提高了算法的求解效率。

表3 直達(dá)運(yùn)輸模式的集裝箱班列開(kāi)行方案Tab.3 Service plan of direct transportation organization

表4 集裝箱班列開(kāi)行方案Tab.4 Service plan of container trains

優(yōu)化結(jié)果中班列的開(kāi)行方案見(jiàn)表4，箱流的中轉(zhuǎn)方案見(jiàn)表5。由表4 數(shù)據(jù)可知，有12 條班列弧段被選擇作為服務(wù)網(wǎng)絡(luò)的組成部分，即在設(shè)計(jì)周期內(nèi)共開(kāi)行12 列集裝箱班列，各班列的編成箱數(shù)接近于最大編成箱數(shù)50 箱，運(yùn)輸能力被充分的利用。表5中，部分箱流在途中不進(jìn)行任何裝卸中轉(zhuǎn)作業(yè)，從出發(fā)辦理站直達(dá)運(yùn)輸至目的辦理站，如蘭州運(yùn)往北京的箱流（箱流1）；而流量較小且運(yùn)距較遠(yuǎn)的部分箱流要在途中進(jìn)行裝卸中轉(zhuǎn)作業(yè)，如蘭州運(yùn)往鄭州的箱流（箱流4），先由蘭州辦理站在第2 時(shí)段發(fā)往西安辦理站的班列承運(yùn)，到達(dá)西安辦理站后卸下，再裝至西安辦理站在第6 時(shí)段發(fā)往鄭州辦理站的班列將其運(yùn)至目的站，在西安辦理站的中轉(zhuǎn)作業(yè)消耗1個(gè)時(shí)段。

表5 箱流中轉(zhuǎn)方案Tab.5 Transfer plan of container flows

4.2.2 對(duì)比分析

比較表3與表4方案的總成本，不難看出優(yōu)化后的服務(wù)網(wǎng)絡(luò)（表4 方案）節(jié)省了20%。同時(shí)，將該優(yōu)化方案與現(xiàn)有集裝箱班列開(kāi)行方案進(jìn)行對(duì)比分析，從“95306”和“中鐵集裝箱運(yùn)輸有限公司”網(wǎng)站公布的數(shù)據(jù)匯總得出現(xiàn)有集裝箱班列開(kāi)行方案見(jiàn)表6。通過(guò)對(duì)比可看出，優(yōu)化方案中各線路中班列的開(kāi)行頻率為1列/d，而現(xiàn)有班列開(kāi)行方案中，開(kāi)行頻率普遍在0.5 列/d，無(wú)法保證箱流的運(yùn)到期限。例如現(xiàn)有開(kāi)行方案中，鄭州至成都的箱流（箱流8）是由鄭州開(kāi)往成都的集裝箱班列進(jìn)行承運(yùn)，每日該去向的箱流量?jī)H產(chǎn)生23 箱，為達(dá)到滿軸或滿長(zhǎng)的發(fā)車(chē)條件，通常每2 d 發(fā)1 列車(chē)，導(dǎo)致出發(fā)站當(dāng)日產(chǎn)生的集裝箱在第2 d 甚至是第3 d 才能被送至目的站，超過(guò)了要求的運(yùn)到期限（7個(gè)時(shí)段）。優(yōu)化后的服務(wù)網(wǎng)絡(luò)（表4 方案）中，箱流8 先同箱流7、箱流14 合并，由鄭州辦理站在第1 時(shí)段發(fā)往西安辦理站的班列承運(yùn)，到達(dá)西安辦理站后卸下，再同箱流6 合并，裝至西安辦理站在第5 時(shí)段發(fā)往成都辦理站的班列，整個(gè)運(yùn)輸時(shí)間為6 個(gè)時(shí)段，滿足了該組箱流運(yùn)到期限的要求。顯然，利用本文模型及算法得到集裝箱班列的發(fā)車(chē)時(shí)段、開(kāi)行頻率在滿足運(yùn)輸需求的同時(shí)，保證各組箱流在規(guī)定的運(yùn)到期限內(nèi)送至目的站。

表6 現(xiàn)有集裝箱班列開(kāi)行方案Tab.6 Existing service plan of container trains

5 結(jié)束語(yǔ)

本文研究了鐵路集裝箱運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)方法，運(yùn)用Benders分解算法求解構(gòu)建的線性混合整數(shù)規(guī)劃模型。通過(guò)算例的求解表明：對(duì)于大規(guī)模的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，改進(jìn)的Benders分解算法可在較短時(shí)間內(nèi)得到高質(zhì)量的解；利用本文模型和算法得到的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)可有效減少鐵路運(yùn)輸企業(yè)的成本，并在滿足運(yùn)輸需求的同時(shí)，保證各組箱流在規(guī)定的運(yùn)到期限內(nèi)送至目的站。在鐵路集裝箱運(yùn)輸組織中，部分班列需在途經(jīng)站辦理一定的集裝箱裝卸或車(chē)組甩掛作業(yè)，今后的研究會(huì)針對(duì)這一情況做深入分析，以擴(kuò)展問(wèn)題的適用性。