江雨星 ?；菝?高如虎

（蘭州交通大學交通運輸學院 蘭州730070）

0 引 言

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

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

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

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

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

1 問題描述

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

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

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

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

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

2.1 參變量定義

2.2 優(yōu)化模型

2.2.1 目標函數(shù)

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

2.2.2 約束條件

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

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

3 算法設計

3.1 子問題對偶模型

3.2 主問題模型

3.3 Benders分解算法流程

3.4 Benders分解算法改進

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

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

4 求解算例

4.1 參數(shù)輸入

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

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

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

4.2 數(shù)值結果

4.2.1 結果分析

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

表3 直達運輸模式的集裝箱班列開行方案Tab.3 Service plan of direct transportation organization

表4 集裝箱班列開行方案Tab.4 Service plan of container trains

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

表5 箱流中轉方案Tab.5 Transfer plan of container flows

4.2.2 對比分析

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

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

5 結束語

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