铁路集装箱运输服务网络设计优化模型及算法

江雨星，李和壁

(1. 兰州交通大学 交通运输学院，兰州 730070;2. 中国铁道科学研究院 铁道科学技术研究发展中心，北京 100081)

作为货物运输物流化的主要形式，铁路集装箱运输在现代物流和国际集装箱多式联运体系中居于重要地位[1].每日有大量的集装箱通过公路交通送至铁路集装箱办理站，由办理站间组织开行的集装箱班列进行运输.对于这样的铁路集装箱运输决策问题，最重要的任务就是设计合理的集装箱运输服务网络.高质量的运输服务网络，不仅可满足多样化的运输需求、提高客户满意度，同时还能保证铁路企业的高效运营及盈利.可见，铁路集装箱运输服务网络的设计与优化具有重要的现实意义.

运输服务网络理论在交通运输领域中的应用极为广泛，如航空企业中航班时刻表的优化[2]、公路货运中车辆运行路径的确定[3]、海洋运输中船舶在各航线上的合理分配[4]、铁路运输中旅客列车开行方案的编制[5]及客流分配[6].对于铁路货物运输服务网络的设计，国内外学者作了大量研究.Crainic[7]系统性的阐述了运输服务网络设计的理论与方法.Newton等[8]将货物列车编组计划转化为服务网络设计问题.王保华等[9]为解决快捷货物运输动态服务网络的设计问题，建立了线性整数规划模型.沈睿[10]针对铁路行包快运服务产品，研究了运输服务网络的设计方法.唐金金等[11]将列车开行方案转化为服务网络，构建了服务网络动态配流的优化模型.Duan等[12]在设计运输服务网络时，综合考虑了铁路货物运输的时效性及可靠性.

部分学者专门研究了铁路集装箱运输服务网络设计的问题.Newman等[13]以成本最小为优化目标建立了整数规划模型，将大量集装箱有效分配到开行的班列上.闫海峰等[14]采用遗传算法求解构建的集装箱班列开行方案优化模型.张小强等[15]为分析运输价格制定与班列开行决策之间的关系，构建了双层规划模型.夏阳等[16]研究了客运化模式下集装箱班列开行方案的编制问题.

现有的铁路集装箱运输服务网络设计的研究，虽已通过建立数学模型及设计求解算法，确定出班列运行径路、开行频度及箱流分配方案，但是在此过程中较少考虑集装箱办理站装卸能力及邻接路段通过能力的约束.同时，随着铁路企业运输服务质量的不断改进，客户对于集装箱运输的时效性提出了更高的要求，而现有文献很少考虑.本文综合考虑集装箱办理站装卸能力、邻接路段通过能力及集装箱运到期限的要求，构建铁路集装箱运输服务网络设计的线性混合整数规划模型，并设计基于遗传算法的求解方法.

1 问题描述

目前，我国铁路企业组织开行的集装箱班列主要为直达班列，即班列从出发站至到达站间途中不办理任何集装箱装卸和车组甩挂作业.基于此，本文考虑任意两集装箱办理站间开行的集装箱班列均为直达班列.依据运输服务网络构建思想，将铁路物理网络中的办理站作为服务网络中的节点，办理站间开行的所有直达去向作为服务网络中有向服务弧段集合.如图1所示，已知设有4个办理站和4条有向路段的铁路网络，其对应开行的全部可能直达去向如图2所示.将这4个办理站作为服务网络中的节点，所有直达去向作为节点间的服务弧段集合，如图3所示.需要说明的是，本次研究中各服务弧段对应的直达去向在物理网络中的实际运行路径均已给定，为出发站至到达站间的最短路径.例如：图3中服务弧段1对应的直达去向为办理站1→办理站4，其在物理网络中(图1)的实际运行路径由路段1和路段2组成.

依据铁路货运系统中同股车流不可拆分的性质，本文假设同一OD间的箱流同样是不可拆分的.铁路集装箱运输服务网络的设计，就是在服务弧段集合中选出一系列连续的弧段组成服务路径来运输节点间的集装箱，并确定各弧段的服务频度(即服务弧段关联起点与终点间开行的直达班列数量).对于任意两节点间的箱流，可能有多条服务路径供其选择，不同的服务路径表示不同的运输作业过程.例如：对于起点为节点1、终点为节点3的箱流，可选择服务弧段2作为服务路径，也可选择服务弧段3和5组成服务路径.若选择弧段2，则表示该箱流由1站开往3站的集装箱班列进行直达运输；若选择弧段3和5，则表示该箱流先由1站开往2站的班列承运，到达2站后卸下，再装至2站开往3站的班列将其运至终到站.同时，集装箱办理站装卸能力、邻接路段通过能力及集装箱运到期限的限制，对服务弧段的选择有很大的影响.例如：弧段3和5组成服务路径的运输时间超过了节点1去往节点3箱流的运到期限，而弧段2的运输时间在运到期限范围内，则该箱流只能选择弧段2.服务弧段的选择及其频度的确定，不仅要满足运输需求，还要尽可能减小支出成本，再加上办理站装卸能力、邻接路段通过能力及运到期限约束，使得问题求解比一般的网络设计更为困难.

2 优化模型构建

2.1 参变量定义

2.2 优化模型

2.2.1 目标函数

本文以成本最小为优化目标，总成本分为两部分,一部分是服务成本(班列的开行成本),另一部分是与集装箱运输有关的成本，后者包括途中运输成本及中转装卸成本，则目标函数如式(1)所示.

(1)

2.2.2 约束条件

1) 箱流唯一性约束

(2)

表示任意1组箱流在途中是不可拆分的.

2) 流量守恒约束

(3)

表示任意1组箱流在途经站的中转装卸是连续的，并保证全部集装箱能从出发站点运送至终到站点.

3) 箱流中转装卸约束

(4)

4) 运到期限约束

(5)

表示任意箱流的运输时间不能超过规定的运到期限，其中箱流的运输时间包括出发站点收箱至将集装箱发出的时间、途经办理站的中转装卸作业时间及途中运行时间.

5) 办理站装卸能力约束

(6)

6) 路段通过能力约束

(7)

表示物理网络中任意有向路段上通过的班列数量，不能超过该路段的通过能力.

7) 服务能力与箱流量的关系约束

(8)

表示弧段的服务能力应满足所运输的箱流量.

3 算法设计

本文构建的模型为线性混合整数规划模型，随着铁路网络规模、集装箱运输需求的增加，精确求解算法或商业优化软件无法在接受时间内得到优化结果.遗传算法是一种基于随机搜索的群体智能算法，具有较高的求解效率，本文将运用遗传算法求解构建的数学模型.

3.1 染色体编码

(9)

3.2 初始种群

在满足运输完整性的约束下，箱流通过连续的服务弧段组成1条由出发站点至终到站点的服务路径，因此，确定箱流与服务弧段的对应关系可视为服务路径的选择.服务路径选择的前提和基础是要确定出各箱流可选择的服务路径集合.为此，本文运用回溯法的思想，搜索满足箱流唯一性、流量守恒及运到期限约束的的可行服务路径.对于箱流q，可行服务路径的搜索流程如下：

Step1：令Lq表示箱流q的运输时间，选定箱流q的出发站点o(q)作为搜索起点，并将起点o(q)视为当前节点，初始化运输时间Lq=wq，转Step2；

Step2：检查以当前节点为起点的服务弧段是否都已遍历，若都已遍历，转Step5；否则，转Step3；

Step3：在以当前节点为起点的服务弧段中，选择未遍历的弧段a，已知该弧段的终点为u，更新运输时间Lq=Lq+τa，判断运输时间是否满足运到期限的要求，若Lq≤Tq，转Step4；否则，将弧段a标记为已遍历，返回该弧段起点，同时还原运输时间Lq=Lq-τa，转Step2；

得到各OD箱流可选的服务路径集合后，依次让各箱流在其可行路径方案中随机选取1条路径，以此产生一定数量的初始方案.再将各初始方案代入式(9)，计算不同方案下的服务频度.

上述生成初始种群的方法可使各染色体均满足箱流唯一性、流量守恒及运到期限约束.对于其中不满足办理站装卸能力及路段通过能力约束的初始染色体，则运用下文设计的启发式策略进行修复.

3.3 染色体修复

算法设计的核心思想，就是通过交叉、变异等操作对箱流选择的服务路径进行不断改变.显然，初始染色体及遗传操作后产生的新染色体始终满足箱流唯一性、流量守恒及运到期限约束，但是各OD箱流选择的服务路径及各弧段服务频度的不断变化，使得办理站装卸集装箱数量及路段通过班列数量随之改变，部分染色体可能不满足办理站装卸能力及路段通过能力要求.对于这些不可行染色体，需设计适宜的方法进行处理.相较于既有文献常采用的罚函数法和直接删除法，染色体修复可使种群规模不改变的同时，保证染色体组合的多样性.为此，本文考虑对不可行的染色体进行修复，并设计相应的启发式修复规则.

启发式修复规则的实现过程具体为：检验各节点装卸的集装箱数量，对于节点n，若装卸的集装箱数量超过装卸能力kn，则选出在该节点进行中转装卸的任意1组箱流，在其可选的路径集合中选出不在节点n中转的1条路径，替换当前路径.同时，检验各路段上通过的班列数量是否满足要求，若路段e上通过的班列数量大于其通过能力fe，则先选出对应的直达去向在物理网络中的实际运行路径经过路段e的服务弧段a，再选取通过服务弧段a的任意1组箱流，在该箱流可选的路径集合中选出不经过弧段a的1条路径替换当前路径.以此进行调整，直至各办理站装卸箱数及各路段上通过的班列数量满足约束要求.

3.4 遗传算法流程

设计遗传算法流程如下：

Step1：生成初始种群.

Step2：令目标函数的倒数为适应度函数，将当前所有染色体带入适应度函数计算适应度值.

Step3：选择操作.为避免优秀个体被破坏，采用轮盘赌与精英保留相结合的策略进行选择.

Step4：交叉操作.随机选取1组箱流，将表示该箱流及之后所有箱流与服务弧段对应关系的基因，与另一染色体中相同位置的基因进行互换，修复不可行染色体.

Step5：变异操作.在执行变异操作的染色体中，随机选取1组箱流，改变该箱流与服务弧段对应关系，即在其可选的服务路径集合中任选1条与当前不同的路径进行替换，修复不可行染色体.

Step6：判断循环终止条件，若迭代次数没有达到设定的最大循环次数，则转Step2；否则算法结束.

4 求解算例

4.1 参数输入

构造如图5所示的路网结构对本文模型和算法进行仿真计算，图中圆圈表示铁路集装箱办理站，连线为车站之间的有向路段.铁路物理网络中路段相关参数如表1所列，服务网路中服务弧段相关参数如表2所列，各OD箱流相关参数如表3所列.各OD箱流的出发站收箱至将集装箱发出的时间均为4 h，途经各站办理中转装卸作业的时间均为8 h，运到期限均为24 h.各服务弧段对应直达去向上班列的运行时间，由物理网络中该去向途经各路段的运行时间相加而得，各办理站装卸能力均为1 800箱，中转装卸成本为10元/箱，班列的最大编成箱数为50箱.

表1 路段相关参数Tab.1 Related parameters of each section

表2 服务弧段相关参数Tab.2 Related parameters of each service arc

表3 箱流相关参数Tab.3 Related parameters of container flow

4.2 求解结果分析

运用Matlab2014编程对算例进行测试，种群规模取30，交叉概率取0.9，变异概率取0.09，迭代次数为500次.计算过程中适应度函数值的变化如图6所示，在运行了104 s后得到最终解，其适应度值为6.264 890 86×10-8，目标函数值为15 961 970元.由图6可知，随着迭代次数的增加，适应度函数值逐渐增加，在260次以后，适应度值已无明显变化，表明算法的收敛性良好，具有较高的计算效率.

表4 箱流经过的服务弧段Tab.4 Passing service arcs of each container flow

表5 服务频度Tab.5 Service frequency

表6 各集装箱办理站装卸箱数Tab.6 Number of containers loaded and unloaded at each container terminal

表7 各路段通过的班列数量Tab.7 Number of trains passing each section

5 结论

本文对铁路集装箱运输服务网络的设计方法进行了研究，运用遗传算法求解构建的线性混合整数规划模型，通过算例的求解表明：对于大规模的集装箱运输服务网络设计问题，提出的模型及算法可在较短时间内获得满意解，具有较高的计算效率；所得结果中，各OD间箱流的运输时间均在运到期限范围内，集装箱办理站装卸箱数和路段通过班列数量均满足能力要求，验证了本文提出的方法是有效可行的，可为铁路企业优化集装箱运输组织提供决策参考.现实中部分班列需在途经站办理集装箱装卸或车组甩挂作业，未来研究会针对这一情况做深入分析，使设计的方案与现实更好的吻合.