需求响应的集装箱班列时刻表优化及Benders分解算法

江雨星，牛惠民

(兰州交通大学交通运输学院，兰州730000)

0 引 言

铁路集装箱运输继承了铁路运输和集装箱运输的双重优势,拥有巨大的发展潜力[1].为保障货物运到期限，提高铁路货运市场竞争力，集装箱旅客化运输作为一种全新的运输组织模式被提出，并已在国内外部分铁路线上实行[2].这种新型集装箱运输组织问题的核心工作是设计科学的集装箱班列时刻表.班列到达、出发时刻的确定，除满足车站和邻接线路的技术条件要求，还应考虑集装箱货物的数量、去向及货主要求的送达时间，即制定的列车时刻表尽可能响应货物的需求特征.

货物列车运行图的优化一直备受学术界的关注.Kuo等[3]以最小化运营成本和运输延误为目标，构建了货物列车运行图优化的整数规划模型.Cacchian 等[4]在旅客列车运行线已定的情况下，研究了货物列车运行图编制和径路选择的协同优化.江峰等[5]将货物列车运行图编制转化为时空网络中的路径选择问题.既有货物列车运行图的研究主要是解决列车对车站、区间的时空占用问题，很少考虑货物的数量、时间特征，这样设计的列车运行图会造成车站“有车无货”或“货物排队”的现象.在旅客列车运行图研究中，已有学者考虑了客流需求.Niu 等[6]以旅客候车时间最少为目标构建了二次整数规划模型，解释客流需求与列车运行图的内在耦合机理.李得伟等[7]提出列车间非定序越行情况下需求驱动的运行图编制方法.但是，铁路集装箱货物运输与旅客运输之间存在较大差异，货主关注的是货物能否在要求的时间内送至目的站，因此，旅客列车运行图编制理论无法解决需求响应下集装箱班列时刻表的优化.

对于集装箱班列，鲜有文献考虑其时刻表的优化，该类列车运行组织的研究，主要为开行方案的设计.夏阳等[8]针对客运化模式下的铁路集装箱运输系统，建立了班列开行方案的优化模型.张小强等[9]研究了铁路集装箱班列开行决策与运输价格制定的协同优化.

本文将研究需求响应下集装箱班列时刻表的优化问题.依据离散到达办理站的集装箱货物数量、去向及货主要求的送达时间，构建集装箱班列时刻表优化的数学模型.运用Benders算法将原问题分解为确定集装箱货物和班列匹配方案的主问题，以及优化班列时刻表的子问题，并设计启发式策略，使每次迭代中可产生多个优化割平面同时添加至主问题中，以增加算法的收敛速度.

1 问题描述

在铁路集装箱旅客化运输中，集装箱办理站是负责集装箱受理、装卸，以及班列到达、出发等业务的场所.货主会提前领取空箱装货，通过卡车在指定时间内将重箱送至出发站内的箱区，待班列到达站内到发线停车后，通过装卸设备装车并运至目的站[2]，如图1 所示.整个运输过程中，班列采用固定车底编组的形式，脱离了传统的技术站内解编的组织模式.

图1 铁路集装箱办理站示意图Fig.1 An illustration of a rail-road terminal

本文考虑途经m个集装箱办理站的铁路集装箱运输专用线上，在研究时段(1 d)内，由办理站1～m开行一定数量的集装箱班列，承运需在该时段内运送的各批集装箱货物(简称为集装箱).依据文献[2]，班列采用站站停模式.货主的需求体现在托运的各批集装箱的数量、去向、到达出发站的时间，以及货主要求送达目的站的时间.基于此，根据货主需求信息确定集装箱班列在沿途各站最有利的到发时刻.货主需求信息可由铁路集装箱运输管理信息系统获取.

集装箱班列在办理站的到发时刻应尽可能与集装箱需求相吻合.图2中，有5批u站去往v站的集装箱陆续到达u站内的箱区，当集装箱q-2、q-1 和q+1 由班列j承运时，该班列在u站的到达时刻不应早于这3批集装箱到达该站的时刻tq-2、tq-1和tq+1.对于在班列j进行装卸作业过程中或在其出发时刻之后到达的集装箱q+2，只能由后续班列j+1 承运.同时，班列在v站的到达时刻，应尽可能的在货主要求的送达时间之内.

图2 集装箱与班列匹配关系示意图Fig.2 Assignment scheme for containers to trains

铁路货物运输中，任意1批货物只能由1列车运送.为满足班列承运集装箱的数量要求，相邻到达办理站的两批集装箱与班列间的匹配不一定遵循“先到先服务”原则.如图2 所示，班列j承运集装箱q-2 和q-1 后，剩余承运能力小于集装箱q的数量，但大于或等于较晚到达的集装箱q+1 的数量，此时该班列将承运集装箱q+1，而集装箱q由之后的班列j+1承运.

2 优化模型构建

2.1 模型假设

假设1假定货主托运的货物均由20 英尺的标准集装箱装载，每批需要运送的集装箱数量不大于班列的最大承运箱数.

假设2通常情况下，集装箱班列在途经站的停留时间比在始发站的要短.假定各班列在始发站的停留时间相等，在途经各办理站的停留时间也相等，且在始发站的停留时间大于途经站的停留时间.同时假定各班列在同一区间的运行时间相同.

假设31 d 内可能会有一些货主要求当天送达目的站而未被组织装车运送的集装箱.假定研究时段的最后时刻有1列虚拟班列出发，用以承运这些未被运送的集装箱.

2.2 参数定义

Q——研究时段(1 d)内需要承运的集装箱批次集合；

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

S——集装箱办理站集合，S={1,2,…,m}，m为办理站的总数；

u,v,v′——集装箱办理站索引，u,v,v′∈S；

J——集装箱班列集合，J={1 ,2,…,k-1,k} ，其中，1～k-1为实际开行的班列，k为虚拟班列；

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

nq——集装箱q的数量(箱)；

tq——集装箱q到达其出发站的时刻(min)；

oq，eq——集装箱q的出发站和目的站；

Tq——集装箱q的货主要求该批集装箱被送达目的站的时刻(min)；

lu——办理站u上单个集装箱的平均装车/卸车作业时间(min)；

——班列j在办理站u的停留时间(min)；

——班列j从办理站u至u+1 的运行时间(min)；

h——相邻班列在办理站的最小间隔时间(min)；

Nmax，Nmin——班列承运集装箱的最大数量和最小数量(箱)；

M——充分大的正数.

2.3 决策变量

——整数决策变量，表示集装箱班列j在办理站u的出发时刻，≥0；

——整数决策变量，表示集装箱班列j在办理站u的到达时刻，≥0；

——0-1 决策变量，若集装箱q由班列j承运，取值为1，否则为0.

本文是在集装箱班列开行数量给定条件下，优化班列时刻表.可先依据文献[2]提出的方法确定区段内实际开行的班列数量，再根据本文模型及算法优化班列时刻表.

2.4 目标函数

以集装箱被送达目的站的总延误时间最小为优化目标.为此，引入辅助变量yq，表示集装箱q被送达目的站的延误时间，yq≥0，则目标函数为

2.5 约束条件

(1)集装箱送达目的站的延误约束.

当集装箱q由班列j承运时，若班列到达eq站的时刻小于或等于要求的送达时刻Tq，则不会产生送达延误；否则，延误时间为.

(2)车站间隔时间约束.

承运同去向集装箱的班列，需在同一条到发线上办理装卸作业.班列j从办理站u内的到发线出发后，班列j+1 才能进入该到发线，且班列j出发时刻与班列j+1 到达时刻的间隔要满足车站的最小间隔时间要求，如图3 所示，相邻班列在始发站上的间隔时间约束同样如此.

图3 间隔时间示意图Fig.3 Illustration of safety headway

(3)集装箱班列到达、出发时刻关联约束.

班列在沿途各站的到达、出发时刻要满足区间运行时间和车站停留时间的要求，如图3所示.

(4)集装箱班列在终点站的到达时刻约束.

班列j在终点站m的到达时刻不应超过研究时段(1 d)的结束时刻，令1 440为结束时刻.

为使货主要求当天送达目的站的集装箱尽可能组织装车并被运送，应对剩余的集装箱赋予较大的送达延误时间，假定虚拟班列在各站的到达时刻均为第二天的结束时刻.

(5)班列与集装箱的匹配关系约束.

班列j在集装箱q的出发站oq的到达时刻大于或等于集装箱q到达其出发站的时刻tq时，集装箱q才可能由班列j承运.同时，对于任意1批集装箱q，仅能由1列班列承运.

(6)集装箱班列装卸作业时间约束.

班列j在u站办理装卸作业时，通常是先卸下目的站为u的集装箱，再装上由该站出发的部分集装箱，且装卸时间不能大于班列的停站时长.

式中：Qvu——出发站为v目的站为u的集装箱批次集合，Qvu={q|oq=v且eq=u}.

(7)集装箱班列承运集装箱数量约束.

班列j在办理站u出发后所承运的集装箱数量为其必须在规定的数量范围[Nmin,Nmax] 内.

3 算法设计

对于大规模混合整数规划问题，Benders 分解是一种高效的求解方法.本文将运用该方法分离模型中的0-1 变量和整数变量，得到仅包含0-1变量的主问题和固定0-1 变量后只包含整数变量的子问题，即分解为确定集装箱和班列匹配方案的主问题和优化班列时刻表的子问题，通过求解子问题不断产生主问题的有效割平面，由此进行迭代.

3.1 子问题对偶模型建立

当集装箱与班列的匹配方案确定后，即给定0-1 变量的值(下文中用表示给定的值)，原问题转化为确定班列在各站的到达、出发时刻，由式(1)～式(8)构成.在各班列区间运行时间和途经站停留时间均已知的情况下，设计班列时刻表的核心为确定班列在始发站的出发时刻.定义参数表示班列j从1站至u站的运行时间，则班列j在u站的到达、出发时刻分别为和的计算公式为

对于虚拟班列k，令且从而保证该班列在各站的到达时刻均为2 880.由式(1)～式(8)转化得到的班列始发时刻优化模型为

需要说明的是，在假设2 的前提下，相邻班列在途经各站的间隔时间约束可简化为仅考虑在始发站的间隔时间约束，即式(16).令和分别为式(15)～式(19)的对偶变量，子问题的对偶模型为

3.2 主问题模型建立

主问题是在迭代过程中通过求解子问题的对偶模型来不断添加割平面而建立的，在此过程中，可能会出现子问题的对偶模型无界，其原因是当前给定的集装箱与班列的匹配方案是不可行的.为避免这种情况，可对集装箱与班列的匹配加以更严格的约束.

加入式(26)后，每次求解主问题所得的集装箱与班列匹配方案始终是可行的，使得子问题的对偶模型总是可行且有界，从而可根据其最优解构造优化割平面添加到主问题中.得到主问题模型为

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

式中：π——辅助变量，π≥0；

式(28)为优化割平面.

3.3 改进策略

计算时发现，每次迭代为主问题提供的割平面中，变量的系数大部分是0，导致割平面的有效性较低.为此，设计启发式策略，使每次迭代中可产生多个优化割平面同时添加至主问题中，具体过程如下.

Step 1将当前集装箱与班列匹配方案代入子问题模型求解，选出送达延误时间yq＞0的集装箱批次，改变这些集装箱与班列的当前匹配关系.如集装箱q的送达延误时间大于0，已知该批集装箱目前是由班列j承运，改变其匹配关系，令集装箱q由班列j′承运，其中，j′是在j之前出发的班列且满足，即产生了新的匹配方案.

Step 2检验新方案是否满足班列承运集装箱数量及装卸作业时间的约束，若不满足，可在班列j′承运的集装箱批次中选取集装箱q′(q′与q具有相同的出发站与目的站)，将其改由班列j承运，以此进行调整，直至满足班列承运箱数及装卸作业时间约束.

Step 3将生成的多个可行匹配方案，分别代入子问题的对偶模型进行求解，产生相应的优化割平面，加入主问题中，进行下一次迭代.

3.4 算法流程

先求解未添加任何割平面的主问题，以获得初始匹配方案.主问题的目标函数值Zmaster作为下界LB，割平面的不断添加使LB的值逐渐上升,子问题对偶模型的目标函数值Zdual-sub作为上界UB.随着计算的进行，UB与LB不断更新，当GGap=(UB-LB)/UB小于给定的值ε或迭代次数达到最大值时，算法停止，流程如图4所示.

4 求解算例

4.1 参数输入

以胶黄铁路开行的集装箱班列为例，对所提方法进行仿真计算.班列由青岛铁路集装箱中心站出发，途经胶州站、营海站、红石崖站和黄岛站，最终到达前湾港区港湾站，区间运行时间分别为8，17，17，10，8 min.在所选的1 d 内，共有120 批集装箱需要运送，因篇幅有限，不罗列集装箱的相关信息.班列最大承运箱数为30 箱，最小承运箱数为20 箱，根据文献[2]需组织开行15 列班列.各班列在始发站停留时间为60 min，途径站的停留时间均为10 min，各办理站上单个集装箱的平均装车/卸车作业时间均为2 min，车站最小间隔时间为5 min.

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

4.2 求解结果分析

算法由Python 语言实现，运行环境为1 台CPU Intel，4 GB内存的个人计算机，算法的主问题与子问题均通过GUROBI 进行求解.经过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

优化得到的班列始发时刻如表1 所示，其与集装箱需求的变化规律是吻合的.例如：在10:20-16:20，大量的集装箱密集到达青岛铁路集装箱中心站，其中大部分集装箱货主要求送达时间在18:00以内，组织开行6列班列承运这些集装箱，即表1中第7至第12列班列，这部分班列发车较为紧凑，相邻班列出发间隔时间均不超过65 min；而在16:20-22:20，各批集装箱的平均到达间隔时间较大，且箱量较少，相应地后续出发班列的间隔时间增大.

表1 集装箱班列始发时刻Table 1 Departure times of railway container trains

4.3 班列承运能力对时刻表优化的影响

班列承运集装箱能力的变化对时刻表的优化产生影响.在集装箱运输需求数据不变的前提下，令班列承运集装箱的最大数量Nmax分别取30、40、50，60箱，最小数量Nmin与最大数量Nmax的差值均为10箱，依据文献[2]确定不同承运能力方案下所需开行班列数量分别为15、12、9，7列，各方案中班列j在始发站的停留时间其余参数不变，通过计算得到各方案的最优目标函数值如图6所示.

图6 不同承运能力下的送达延误时间Fig.6 Tardiness with different transport capacity

从图6 可知：班列承运能力增加，所需班列数量减少，集装箱总的送达延误时间增加.可见，班列承运能力发生变化，班列时刻表会随之改变.

5 结 论

本文研究了需求响应的集装箱班列时刻表优化方法，运用Benders分解算法求解所构建的线性混合整数规划模型，并提出启发式的改进策略.通过算例求解得出：相较于传统Benders 分解，改进策略的运用增加了迭代1次的运行时间，但减少了算法的迭代次数，使总运行时间缩短，算法效率得到极大提高；本文模型及算法得到的班列时刻表与集装箱货物的数量、时间分布之间具有较好的匹配性，可有效减小集装箱送达目的站的总延误时间.

在部分既有铁路线中，集装箱班列与旅客列车是共线运行的，这就会出现集装箱班列被旅客列车越行的情况，使班列时刻表的优化更为复杂.今后将针对这一情况做深入分析，以扩展问题的适用性.