基于列生成算法的高速铁路快捷货运组织方案优化研究

2020-09-29李夏苗周凌云于雪峤

铁道学报 2020年9期

金伟，李夏苗，周凌云，于雪峤

(1.中南大学交通运输工程学院，湖南长沙 410075；2.中国铁路北京局集团有限公司货运部，北京 100055；3.中国铁道科学研究院集团有限公司运输及经济研究所，北京 100081)

近年来，随着城市规模和空间布局规划的调整以及电商企业的快速发展，大城市的土地利用、交通拥堵及环境污染问题突显，减少城市内公路货运车辆，加快城市绿色物流体系建设势在必行。高速铁路(以下简称高铁)快捷货物运输作为一种新型运输产品，以其经济、高效、稳定的优势受到市场广泛关注。高铁货运动车组下线运营，将进一步提升中长距离城市之间高铁快运产品服务水平与效能。借鉴发达国家“外集内配”物流体系建设的先进经验，充分结合我国市场需求与运输结构特征，基于高铁货运列车高效、准时、运能大的优势，充分发挥高铁干线运输能力及溢出效应，对减少公路货运量、大气环境污染，助力打赢“蓝天保卫战”具有重要的现实意义[1]。然而目前对高铁货物运输组织方面的研究较少，如何平衡高铁货运动车组购置、运营成本与收入的关系，如何确保铁路客运与货运业务协同发展，以及如何充分利用高铁时空资源成为高铁货运列车运输组织的关键问题。

铁路列车开行方案是铁路运输组织方案的基础，其编制和优化是铁路运输组织领域的经典问题。国内外学者重点研究了组织方案的经济性、时效性、服务水平、经营收益等与客户需求的耦合关系，考虑不同场景下的发展目标构建了优化模型，并基于模型特征设计了求解算法。在模型构建方面，目前主要有考虑运营成本[2]与考虑旅客(货物)出行(运输)时间[3]两种方法。在算法设计方面，受限于铁路运输多场景多网络的复杂特征，既有应用精确求解算法的求解器仅能求解小规模算例，列生成算法适用于求解一类每个决策方案对应整体规划模型中约束矩阵的一列的组合优化问题，因其不直接同时处理所有备选方案，而是基于当前生成的列的子集，通过限制原问题进行优化求解，提升了求解问题的能力，基于该思想，何必胜等[4]进一步优化了算法存在退化解和分支定界中缺乏有效上下解边界导致求解效率较低的问题，设计了基于大规模领域搜索算法的混合列生成算法，有效避免了出现退化解的问题。许仲豪等[5]构造了一个仅包含一个乘务段的日计划初始可行解，快速生成了满足条件的乘务任务，且初始矩阵即为单位矩阵，初始可行解易于表达计算。对于复杂网络的建模及计算则必须采取不同策略将原问题拆分，以降低问题及变量规模，如国外Carey等[6]、Castillo等[7]，国内周磊山等[8]、彭其渊等[9]都基于不同网络与特征设计了基于问题分解的启发式求解算法。

目前对于高铁快运组织方案优化的研究相对较少，于雪峤[10]设计了基于列车备选集的高铁快运列车开行方案两阶段优化模型，以成本与收益关系为目标，考虑了网络能力、需求耦合等约束，以哈大高铁为例设计了高铁快运列车方案。李莅等[11]分析了货运动车组开行的收益和成本问题，考虑了网络能力、作业能力与运输需求的平衡关系，构建了货运动车组开行方案优化模型并设计了启发式算法求解。吴优[12]分析了货运动车组开行的可行性，借鉴铁路旅客列车开行方案的设计思路，构建了满足经济效益、运输能力及市场需求的多目标混合整数规划模型，并提出了求解可行径路集的K短路算法。以上研究均实现了高铁快运组织方案的定量优化，但仍存在以下不足：均只考虑应用高铁货运动车组满足市场需求，而未考虑现存的确认车、捎带运输、快运柜等组织模式，不符合实际运输组织需求；仅考虑了运输产品与货流分配的关系，未考虑其与组织模式的相互关系，不利于指导生产实践。

针对以上问题，本文考虑高铁货物快运需求、运力供给与运输产品的匹配关系，设计基于列车备选集的两阶段组织方案优化模型，通过引入备选集的思想剔除明显不符合高铁货运列车的服务径路，再基于运输产品及服务模式特征建立高铁快运货流分配优化模型，以及适应复杂网络及大规模变量的列生成算法求解模型。

1 高铁快运服务径路优化模型

1.1 问题描述

高铁快运服务径路优化问题是一类求解规模巨大、变量组合繁多的时空资源优化配置问题，对于这一类组合优化问题，直接计算难以求得最优解，因此应在确定高铁快运组织方案前首先剔除一些明显不符合组织方案原则的情况，以降低配流阶段的计算复杂性、降低问题规模，主要包括：某些方案没有充分考虑网络能力限制，部分繁忙区段运力资源紧张，没有开行货运列车的能力；没有充分考虑列车与列车间的关系，导致在部分区段重复开行造成资源浪费；没有考虑货流与产品的耦合关系，导致区间虚糜过高等问题。为解决上述问题，首先应构造列车服务径路优化模型，构造一个满足货运列车开行条件、经济收益及货流需求的服务网络，即筛选出合理可行的列车服务径路，再基于列车备选服务径路在下一阶段将其细分为服务产品与模式，实现货流的精准分配。

1.2 问题假设和已知

假设列车在双线铁路网上运行，结合我国铁路开行方案编制的实际，将车站看作网络中的节点，高铁快运业务开展的重要制约条件就是场站设施设备的不配套，随着业务的拓展，铁路也必将对场站设施进行新建或改造，以便于组织货物装卸、搬运、存储，因此假设各经停车站都具有组织高铁快递各项业务的条件和足够的能力，且目前货运动车组参数与载客动车组参数相同，假设高铁快运列车等级与客运列车等级相同，不考虑货运动车组的车底运用问题。

模型的输入为：列车开行的固定成本、与距离相关的可变成本、与列车起停相关的停站成本、区段能力、货流需求及列车载运等。模型的输出为优化后可满足市场需求的列车可选服务径路及组合停站模式。

1.3 模型构建

列车服务径路优化模型的目标函数是列车运营总成本最低，即

(1)

模型约束条件如下：

(1)区间通过能力约束

(2)

式中：Cjk为区段能力。

列车区间通过能力约束能够有效降低对高速铁路客运业务的影响，满足区间通过能力的限制。

(2)区间承载能力约束

(3)

货物断面流量的大小与列车装载能力相关，即要求每一列车运行径路的断面中载货量受列车额定装载能力的限制，为此，设置该约束可以保证各个区间的货运需求能够有效被满足。

(3)列车到达出发事件状态约束

(4)

该约束保证了每一个OD对均有足够承载能力的列车满足。

2 基于列生成的模型求解算法

2.1 算法原理

从原问题与检验数子问题的现实意义来看，原问题中的每一“列”代表了不同停站模式的一列车，在求解检验数的迭代过程中，若当前存在的“列”不能有效满足货物运输需求，则会“加列”，即增加另外一种新的停站模式的列车，随着加入的“列”增多，列车的停站模式也不断增加，直至无法加入新的列则表明没有更优类型的停站组合模式，原问题即取得最优解。

2.2 算法流程

基于对列生成算法原理的分析可知，列生成算法的关键是构造原问题的检验数子问题，已知原问题为最小化问题，则当检验数子问题的最小值为非负数时，则原问题取到最优解，列生成算法流程见图1。

图1 列生成算法流程示意图

2.3 检验数子问题模型构建

根据列生成算法的原理，出现在每一“列”位置上的变量均与列车和区间相关，因此每增加一“列”其实际含义为增加一列车。在原问题中，主要考虑的是列车与区段、需求间的耦合关系，及可考虑通过能力、载运能力等因素，而在检验数子问题中，则需具体考虑每一列车的停站、径路、载运能力等因素。

检验数子问题的目标函数是原问题检验数的最小值，即

(5)

式中：α、β、γ分别为原问题中3种资源(式(2)、式(3)、式(4))的价值系数，故检验数子问题又可称“定价子问题”。

模型约束如下：

(1)服务与起讫点关系约束

(6)

(7)

(8)

该组约束限定了列车i的起讫点与停站关系，即若列车i服务于OD对ω，则必须要在OD对ω的起讫点停站，反之成立。

(2)停站次数约束

(9)

式中：π为一个常数。

该约束有效限制了列车的停站次数，过多的停站会降低高铁快运的时效性并占用更多的高铁运输能力资源。

(3)列车起讫点约束

(10)

(11)

(12)

该组约束定义了列车起讫点与停站间的关系，即列车的起讫点唯一，且OD对ω的起讫点均需停站。

(4)径路选择约束

(13)

(14)

式中：M为一个无穷大正数。

该组约束定义了列车运行径路与OD对ω的关联关系，即列车运行的径路不会超过所服务OD对的范围，即OD范围外的车站不允许停站，且起讫点所夹区间必为列车运行径路。

3 高铁快运货流分配模型构建

3.1 问题描述

第2节通过考虑列车与停站、区间与需求之间的关系确定了列车的服务径路，生成了一个能够满足市场需求，包含列车运行种类、停站组合的框架性开行方案，但具体货运需求与运输产品和组织模式的关系并未计算。本节基于目前推出的当日达、次晨达、次日达和经济快递4种运输产品，以及确认车运输、捎带运输、预留车厢以及高铁货运列车专列4种组织模式细分市场需求，实现货流的精准分配。

3.2 问题的假设和已知条件

在配流阶段，假设每个OD对的区间均可满足不同组织模式的作业要求，且具有所需设施设备；捎带运输与预留车厢模式因其基于客运列车时刻表组织运营，故假设其能够满足不同运输产品对时效性的需要；各OD对需求区间调用上一阶段求得的最优方案，且高铁快运列车不与客运列车产生冲突。

模型的输入为：高铁快运收益与成本、高铁快运市场需求；模型的输出为优化后各运输组织模式承载不同运输产品的运量。

3.3 模型构建

配流问题的目标函数是高铁快运收益最大，即

(15)

模型约束如下：

(1)需求满足约束

(16)

该约束保证铁路组织方案能够承载OD间不同运输产品的需求。

(2)产品供给特征约束

(17)

(18)

式中：η为列车满载率。

该组约束考虑到产品供给特征，m=1表示服务模式为确认车，m=4表示服务模式为高铁货运列车，由于确认车开行时间为04:00天窗后，不能满足当日达产品集货需求，因此应用确认车模式不能服务与当日达产品；为保证高铁快运列车收益，应满足高铁快运列车最低装载率。

(3)开行频次约束

fi,m∈N∀i∈Tm=4

(19)

该约束保证列车的开行频次为整数。

4 算例分析

4.1 参数取值

京沪高铁是北京至上海的重要通道，全长1 318 km，连接了北京、天津和上海3个直辖市，经过4个省份，两端连接京津冀和长三角两个经济区域，是中国社会经济发展活跃的地区之一，也是中国客货运输较繁忙、增长潜力较大的客运专线。因此，以京沪高铁为例，选取区间包括北京、天津、济南、南京和上海6个重要城市，利用上文给出的两阶段模型，进行快运列车开行方案的设计。

本文开行方案中，高铁快递列车速度等级一致，列车种类i区别在于列车停站不同，可分为站站停、多站停、一站直达列车。列车停站方式应根据货源OD灵活安排。目前设计的高铁快递专列单列标记载运量为87 t。根据文献[8]关于2025年高铁快运需求的预测，京沪间高铁快递日均OD量见表1。

根据文献[13]关于高铁快运产品货流分担率的研究与实际统计相对比，可预测产品分担率见表2。

表1 京沪间主要节点高铁快运需求 t

表2 高铁快运产品货流分担率 %

表3 京沪高铁主要节点运输距离 km

4.2 列车备选集生成

本文用Python语言调用CPLEX12.7.1引擎编程实现列生成算法，算法运行环境为一台CPU为Intel Xeon E5520 2.27 GHz内存2.8 GB的台式计算机。

(1)上行方向列车备选集

上行方向共生成了8种停站类型的列车，其停站模式见图2。

图2 上行方向列车停站方案示意图

(2)下行方向列车备选集

下行方向共生成了10种停站类型的列车，其停站模式见图3。

图3 下行方向列车停站方案示意图

从图2、图3可知，列车对于运输需求及停站的组合方式均有较好的侧重，设置了多种停站类型、运行径路的列车以满足各地不同运输需求。

4.3 货流分配方案

进一步将运输需求与列车备选集输入货流分配模型，可得京沪主要节点间高铁快运产品运输模式决策方案，因OD需求与运输产品的组合较多，仅给出部分决策方案，见表4。

表4 高铁快运产品运输模式决策方案

由表4可知，4种运输产品与4种组织模式均有匹配，实现了货流的精准分配。从不同运输组织模式来看，充分发挥了确认车与捎带运输小批量、多批次的灵活特征，承担了部分短运距的货运需求，预留车厢和高铁货运专列模式在中长距离中承担了主要运输任务，发挥了大节点间开行的优势。

为进一步分析货运动车组装载效率及对区间的利用情况，各区段断面流量及具体列车剩余载运能力见表5。

由表5可知，上下行货流均被较好的分配在了相应列车，大部分OD需求由同一列车满足，该方案便于车站装卸组织的集中进行，能够有效提升货物组织效率。具体来看，上下行方向的1号列车均为“站站停”列车，能够有效满足沿途节点运输需求，下行方向8号列车与上行方向5号列车为“一直直达”或停站较少的列车，其装载率较高，可以有效满足OD间运输需求，并保证货运动车组运营收益。

为直观展示本文所构建的两阶段模型优势，将第一阶段智能生成列车备选集改为全枚举法生成备选集和由人工经验判断给出的备选集，分别作为第二阶段配流模型的输入条件进行求解。研究结果表明：①在对全枚举法生成的备选集进行配流时，由于问题规模变大，求解时间由原来的2 s变为13 min，配流方案与上文所述两阶段模型一致；②在对人工经验判断的备选集进行配流时，由于无法精准判断合理备选集，货流无法分配到最优备选集中，导致在部分方案中，因无法满足货流需求，增开了4列列车，相较上文方案增加了固定成本支出，在部分方案中因没有合适的列车备选集，列车装载率较差。