江雨星，?；菝?/p>

(蘭州交通大學交通運輸學院，蘭州730000)

0 引 言

鐵路集裝箱運輸繼承了鐵路運輸和集裝箱運輸?shù)碾p重優(yōu)勢,擁有巨大的發(fā)展?jié)摿1].為保障貨物運到期限，提高鐵路貨運市場競爭力，集裝箱旅客化運輸作為一種全新的運輸組織模式被提出，并已在國內(nèi)外部分鐵路線上實行[2].這種新型集裝箱運輸組織問題的核心工作是設計科學的集裝箱班列時刻表.班列到達、出發(fā)時刻的確定，除滿足車站和鄰接線路的技術條件要求，還應考慮集裝箱貨物的數(shù)量、去向及貨主要求的送達時間，即制定的列車時刻表盡可能響應貨物的需求特征.

貨物列車運行圖的優(yōu)化一直備受學術界的關注.Kuo等[3]以最小化運營成本和運輸延誤為目標，構建了貨物列車運行圖優(yōu)化的整數(shù)規(guī)劃模型.Cacchian 等[4]在旅客列車運行線已定的情況下，研究了貨物列車運行圖編制和徑路選擇的協(xié)同優(yōu)化.江峰等[5]將貨物列車運行圖編制轉化為時空網(wǎng)絡中的路徑選擇問題.既有貨物列車運行圖的研究主要是解決列車對車站、區(qū)間的時空占用問題，很少考慮貨物的數(shù)量、時間特征，這樣設計的列車運行圖會造成車站“有車無貨”或“貨物排隊”的現(xiàn)象.在旅客列車運行圖研究中，已有學者考慮了客流需求.Niu 等[6]以旅客候車時間最少為目標構建了二次整數(shù)規(guī)劃模型，解釋客流需求與列車運行圖的內(nèi)在耦合機理.李得偉等[7]提出列車間非定序越行情況下需求驅動的運行圖編制方法.但是，鐵路集裝箱貨物運輸與旅客運輸之間存在較大差異，貨主關注的是貨物能否在要求的時間內(nèi)送至目的站，因此，旅客列車運行圖編制理論無法解決需求響應下集裝箱班列時刻表的優(yōu)化.

對于集裝箱班列，鮮有文獻考慮其時刻表的優(yōu)化，該類列車運行組織的研究，主要為開行方案的設計.夏陽等[8]針對客運化模式下的鐵路集裝箱運輸系統(tǒng)，建立了班列開行方案的優(yōu)化模型.張小強等[9]研究了鐵路集裝箱班列開行決策與運輸價格制定的協(xié)同優(yōu)化.

本文將研究需求響應下集裝箱班列時刻表的優(yōu)化問題.依據(jù)離散到達辦理站的集裝箱貨物數(shù)量、去向及貨主要求的送達時間，構建集裝箱班列時刻表優(yōu)化的數(shù)學模型.運用Benders算法將原問題分解為確定集裝箱貨物和班列匹配方案的主問題，以及優(yōu)化班列時刻表的子問題，并設計啟發(fā)式策略，使每次迭代中可產(chǎn)生多個優(yōu)化割平面同時添加至主問題中，以增加算法的收斂速度.

1 問題描述

在鐵路集裝箱旅客化運輸中，集裝箱辦理站是負責集裝箱受理、裝卸，以及班列到達、出發(fā)等業(yè)務的場所.貨主會提前領取空箱裝貨，通過卡車在指定時間內(nèi)將重箱送至出發(fā)站內(nèi)的箱區(qū)，待班列到達站內(nèi)到發(fā)線停車后，通過裝卸設備裝車并運至目的站[2]，如圖1 所示.整個運輸過程中，班列采用固定車底編組的形式，脫離了傳統(tǒng)的技術站內(nèi)解編的組織模式.

圖1 鐵路集裝箱辦理站示意圖Fig.1 An illustration of a rail-road terminal

本文考慮途經(jīng)m個集裝箱辦理站的鐵路集裝箱運輸專用線上，在研究時段(1 d)內(nèi)，由辦理站1～m開行一定數(shù)量的集裝箱班列，承運需在該時段內(nèi)運送的各批集裝箱貨物(簡稱為集裝箱).依據(jù)文獻[2]，班列采用站站停模式.貨主的需求體現(xiàn)在托運的各批集裝箱的數(shù)量、去向、到達出發(fā)站的時間，以及貨主要求送達目的站的時間.基于此，根據(jù)貨主需求信息確定集裝箱班列在沿途各站最有利的到發(fā)時刻.貨主需求信息可由鐵路集裝箱運輸管理信息系統(tǒng)獲取.

集裝箱班列在辦理站的到發(fā)時刻應盡可能與集裝箱需求相吻合.圖2中，有5批u站去往v站的集裝箱陸續(xù)到達u站內(nèi)的箱區(qū)，當集裝箱q-2、q-1 和q+1 由班列j承運時，該班列在u站的到達時刻不應早于這3批集裝箱到達該站的時刻tq-2、tq-1和tq+1.對于在班列j進行裝卸作業(yè)過程中或在其出發(fā)時刻之后到達的集裝箱q+2，只能由后續(xù)班列j+1 承運.同時，班列在v站的到達時刻，應盡可能的在貨主要求的送達時間之內(nèi).

圖2 集裝箱與班列匹配關系示意圖Fig.2 Assignment scheme for containers to trains

鐵路貨物運輸中，任意1批貨物只能由1列車運送.為滿足班列承運集裝箱的數(shù)量要求，相鄰到達辦理站的兩批集裝箱與班列間的匹配不一定遵循“先到先服務”原則.如圖2 所示，班列j承運集裝箱q-2 和q-1 后，剩余承運能力小于集裝箱q的數(shù)量，但大于或等于較晚到達的集裝箱q+1 的數(shù)量，此時該班列將承運集裝箱q+1，而集裝箱q由之后的班列j+1承運.

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

2.1 模型假設

假設1假定貨主托運的貨物均由20 英尺的標準集裝箱裝載，每批需要運送的集裝箱數(shù)量不大于班列的最大承運箱數(shù).

假設2通常情況下，集裝箱班列在途經(jīng)站的停留時間比在始發(fā)站的要短.假定各班列在始發(fā)站的停留時間相等，在途經(jīng)各辦理站的停留時間也相等，且在始發(fā)站的停留時間大于途經(jīng)站的停留時間.同時假定各班列在同一區(qū)間的運行時間相同.

假設31 d 內(nèi)可能會有一些貨主要求當天送達目的站而未被組織裝車運送的集裝箱.假定研究時段的最后時刻有1列虛擬班列出發(fā)，用以承運這些未被運送的集裝箱.

2.2 參數(shù)定義

Q——研究時段(1 d)內(nèi)需要承運的集裝箱批次集合；

q——集裝箱批次索引，q∈Q；

S——集裝箱辦理站集合，S={1,2,…,m}，m為辦理站的總數(shù)；

u,v,v′——集裝箱辦理站索引，u,v,v′∈S；

J——集裝箱班列集合，J={1 ,2,…,k-1,k} ，其中，1～k-1為實際開行的班列，k為虛擬班列；

j——班列的索引，j∈J；

nq——集裝箱q的數(shù)量(箱)；

tq——集裝箱q到達其出發(fā)站的時刻(min)；

oq，eq——集裝箱q的出發(fā)站和目的站；

Tq——集裝箱q的貨主要求該批集裝箱被送達目的站的時刻(min)；

lu——辦理站u上單個集裝箱的平均裝車/卸車作業(yè)時間(min)；

——班列j在辦理站u的停留時間(min)；

——班列j從辦理站u至u+1 的運行時間(min)；

h——相鄰班列在辦理站的最小間隔時間(min)；

Nmax，Nmin——班列承運集裝箱的最大數(shù)量和最小數(shù)量(箱)；

M——充分大的正數(shù).

2.3 決策變量

——整數(shù)決策變量，表示集裝箱班列j在辦理站u的出發(fā)時刻，≥0；

——整數(shù)決策變量，表示集裝箱班列j在辦理站u的到達時刻，≥0；

——0-1 決策變量，若集裝箱q由班列j承運，取值為1，否則為0.

本文是在集裝箱班列開行數(shù)量給定條件下，優(yōu)化班列時刻表.可先依據(jù)文獻[2]提出的方法確定區(qū)段內(nèi)實際開行的班列數(shù)量，再根據(jù)本文模型及算法優(yōu)化班列時刻表.

2.4 目標函數(shù)

以集裝箱被送達目的站的總延誤時間最小為優(yōu)化目標.為此，引入輔助變量yq，表示集裝箱q被送達目的站的延誤時間，yq≥0，則目標函數(shù)為

2.5 約束條件

(1)集裝箱送達目的站的延誤約束.

當集裝箱q由班列j承運時，若班列到達eq站的時刻小于或等于要求的送達時刻Tq，則不會產(chǎn)生送達延誤；否則，延誤時間為.

(2)車站間隔時間約束.

承運同去向集裝箱的班列，需在同一條到發(fā)線上辦理裝卸作業(yè).班列j從辦理站u內(nèi)的到發(fā)線出發(fā)后，班列j+1 才能進入該到發(fā)線，且班列j出發(fā)時刻與班列j+1 到達時刻的間隔要滿足車站的最小間隔時間要求，如圖3 所示，相鄰班列在始發(fā)站上的間隔時間約束同樣如此.

圖3 間隔時間示意圖Fig.3 Illustration of safety headway

(3)集裝箱班列到達、出發(fā)時刻關聯(lián)約束.

班列在沿途各站的到達、出發(fā)時刻要滿足區(qū)間運行時間和車站停留時間的要求，如圖3所示.

(4)集裝箱班列在終點站的到達時刻約束.

班列j在終點站m的到達時刻不應超過研究時段(1 d)的結束時刻，令1 440為結束時刻.

為使貨主要求當天送達目的站的集裝箱盡可能組織裝車并被運送，應對剩余的集裝箱賦予較大的送達延誤時間，假定虛擬班列在各站的到達時刻均為第二天的結束時刻.

(5)班列與集裝箱的匹配關系約束.

班列j在集裝箱q的出發(fā)站oq的到達時刻大于或等于集裝箱q到達其出發(fā)站的時刻tq時，集裝箱q才可能由班列j承運.同時，對于任意1批集裝箱q，僅能由1列班列承運.

(6)集裝箱班列裝卸作業(yè)時間約束.

班列j在u站辦理裝卸作業(yè)時，通常是先卸下目的站為u的集裝箱，再裝上由該站出發(fā)的部分集裝箱，且裝卸時間不能大于班列的停站時長.

式中：Qvu——出發(fā)站為v目的站為u的集裝箱批次集合，Qvu={q|oq=v且eq=u}.

(7)集裝箱班列承運集裝箱數(shù)量約束.

班列j在辦理站u出發(fā)后所承運的集裝箱數(shù)量為其必須在規(guī)定的數(shù)量范圍[Nmin,Nmax] 內(nèi).

3 算法設計

對于大規(guī)模混合整數(shù)規(guī)劃問題，Benders 分解是一種高效的求解方法.本文將運用該方法分離模型中的0-1 變量和整數(shù)變量，得到僅包含0-1變量的主問題和固定0-1 變量后只包含整數(shù)變量的子問題，即分解為確定集裝箱和班列匹配方案的主問題和優(yōu)化班列時刻表的子問題，通過求解子問題不斷產(chǎn)生主問題的有效割平面，由此進行迭代.

3.1 子問題對偶模型建立

當集裝箱與班列的匹配方案確定后，即給定0-1 變量的值(下文中用表示給定的值)，原問題轉化為確定班列在各站的到達、出發(fā)時刻，由式(1)～式(8)構成.在各班列區(qū)間運行時間和途經(jīng)站停留時間均已知的情況下，設計班列時刻表的核心為確定班列在始發(fā)站的出發(fā)時刻.定義參數(shù)表示班列j從1站至u站的運行時間，則班列j在u站的到達、出發(fā)時刻分別為和的計算公式為

對于虛擬班列k，令且從而保證該班列在各站的到達時刻均為2 880.由式(1)～式(8)轉化得到的班列始發(fā)時刻優(yōu)化模型為

需要說明的是，在假設2 的前提下，相鄰班列在途經(jīng)各站的間隔時間約束可簡化為僅考慮在始發(fā)站的間隔時間約束，即式(16).令和分別為式(15)～式(19)的對偶變量，子問題的對偶模型為

3.2 主問題模型建立

主問題是在迭代過程中通過求解子問題的對偶模型來不斷添加割平面而建立的，在此過程中，可能會出現(xiàn)子問題的對偶模型無界，其原因是當前給定的集裝箱與班列的匹配方案是不可行的.為避免這種情況，可對集裝箱與班列的匹配加以更嚴格的約束.

加入式(26)后，每次求解主問題所得的集裝箱與班列匹配方案始終是可行的，使得子問題的對偶模型總是可行且有界，從而可根據(jù)其最優(yōu)解構造優(yōu)化割平面添加到主問題中.得到主問題模型為

式(9)～式(12)，式(26)

式中：π——輔助變量，π≥0；

式(28)為優(yōu)化割平面.

3.3 改進策略

計算時發(fā)現(xiàn)，每次迭代為主問題提供的割平面中，變量的系數(shù)大部分是0，導致割平面的有效性較低.為此，設計啟發(fā)式策略，使每次迭代中可產(chǎn)生多個優(yōu)化割平面同時添加至主問題中，具體過程如下.

Step 1將當前集裝箱與班列匹配方案代入子問題模型求解，選出送達延誤時間yq＞0的集裝箱批次，改變這些集裝箱與班列的當前匹配關系.如集裝箱q的送達延誤時間大于0，已知該批集裝箱目前是由班列j承運，改變其匹配關系，令集裝箱q由班列j′承運，其中，j′是在j之前出發(fā)的班列且滿足，即產(chǎn)生了新的匹配方案.

Step 2檢驗新方案是否滿足班列承運集裝箱數(shù)量及裝卸作業(yè)時間的約束，若不滿足，可在班列j′承運的集裝箱批次中選取集裝箱q′(q′與q具有相同的出發(fā)站與目的站)，將其改由班列j承運，以此進行調整，直至滿足班列承運箱數(shù)及裝卸作業(yè)時間約束.

Step 3將生成的多個可行匹配方案，分別代入子問題的對偶模型進行求解，產(chǎn)生相應的優(yōu)化割平面，加入主問題中，進行下一次迭代.

3.4 算法流程

先求解未添加任何割平面的主問題，以獲得初始匹配方案.主問題的目標函數(shù)值Zmaster作為下界LB，割平面的不斷添加使LB的值逐漸上升,子問題對偶模型的目標函數(shù)值Zdual-sub作為上界UB.隨著計算的進行，UB與LB不斷更新，當GGap=(UB-LB)/UB小于給定的值ε或迭代次數(shù)達到最大值時，算法停止，流程如圖4所示.

4 求解算例

4.1 參數(shù)輸入

以膠黃鐵路開行的集裝箱班列為例，對所提方法進行仿真計算.班列由青島鐵路集裝箱中心站出發(fā)，途經(jīng)膠州站、營海站、紅石崖站和黃島站，最終到達前灣港區(qū)港灣站，區(qū)間運行時間分別為8，17，17，10，8 min.在所選的1 d 內(nèi)，共有120 批集裝箱需要運送，因篇幅有限，不羅列集裝箱的相關信息.班列最大承運箱數(shù)為30 箱，最小承運箱數(shù)為20 箱，根據(jù)文獻[2]需組織開行15 列班列.各班列在始發(fā)站停留時間為60 min，途徑站的停留時間均為10 min，各辦理站上單個集裝箱的平均裝車/卸車作業(yè)時間均為2 min，車站最小間隔時間為5 min.

圖4 Benders 分解算法流程Fig.4 Flowchart for Benders decomposition

4.2 求解結果分析

算法由Python 語言實現(xiàn)，運行環(huán)境為1 臺CPU Intel，4 GB內(nèi)存的個人計算機，算法的主問題與子問題均通過GUROBI 進行求解.經(jīng)過120次迭代，運行189 s 后得到最終解，送達總延誤為3 262 min，最終的GGap=4.35%，上界與下界的變化情況如圖5 所示，可以看出，算法具有較好的收斂性.運用未改進的Benders分解對該算例進行求解，分析所提算法性能.運行189 s后，迭代253次，最終GGap=28.87%.可見，本文改進策略可有效提高算法的求解效率.

圖5 上界、下界變化情況Fig.5 Progression of UB and LB values

優(yōu)化得到的班列始發(fā)時刻如表1 所示，其與集裝箱需求的變化規(guī)律是吻合的.例如：在10:20-16:20，大量的集裝箱密集到達青島鐵路集裝箱中心站，其中大部分集裝箱貨主要求送達時間在18:00以內(nèi)，組織開行6列班列承運這些集裝箱，即表1中第7至第12列班列，這部分班列發(fā)車較為緊湊，相鄰班列出發(fā)間隔時間均不超過65 min；而在16:20-22:20，各批集裝箱的平均到達間隔時間較大，且箱量較少，相應地后續(xù)出發(fā)班列的間隔時間增大.

表1 集裝箱班列始發(fā)時刻Table 1 Departure times of railway container trains

4.3 班列承運能力對時刻表優(yōu)化的影響

班列承運集裝箱能力的變化對時刻表的優(yōu)化產(chǎn)生影響.在集裝箱運輸需求數(shù)據(jù)不變的前提下，令班列承運集裝箱的最大數(shù)量Nmax分別取30、40、50，60箱，最小數(shù)量Nmin與最大數(shù)量Nmax的差值均為10箱，依據(jù)文獻[2]確定不同承運能力方案下所需開行班列數(shù)量分別為15、12、9，7列，各方案中班列j在始發(fā)站的停留時間其余參數(shù)不變，通過計算得到各方案的最優(yōu)目標函數(shù)值如圖6所示.

圖6 不同承運能力下的送達延誤時間Fig.6 Tardiness with different transport capacity

從圖6 可知：班列承運能力增加，所需班列數(shù)量減少，集裝箱總的送達延誤時間增加.可見，班列承運能力發(fā)生變化，班列時刻表會隨之改變.

5 結 論

本文研究了需求響應的集裝箱班列時刻表優(yōu)化方法，運用Benders分解算法求解所構建的線性混合整數(shù)規(guī)劃模型，并提出啟發(fā)式的改進策略.通過算例求解得出：相較于傳統(tǒng)Benders 分解，改進策略的運用增加了迭代1次的運行時間，但減少了算法的迭代次數(shù)，使總運行時間縮短，算法效率得到極大提高；本文模型及算法得到的班列時刻表與集裝箱貨物的數(shù)量、時間分布之間具有較好的匹配性，可有效減小集裝箱送達目的站的總延誤時間.

在部分既有鐵路線中，集裝箱班列與旅客列車是共線運行的，這就會出現(xiàn)集裝箱班列被旅客列車越行的情況，使班列時刻表的優(yōu)化更為復雜.今后將針對這一情況做深入分析，以擴展問題的適用性.