基于服务网络的综合快运方案优化

李海鹰，曹 玥，廖正文，王 莹

（1.北京交通大学 轨道交通控制与安全国家重点实验室，北京 100044；2.北京交通大学 交通运输学院，北京 100044）

随着工业化进程的不断加快以及物流业的迅猛发展，具有高附加值、高时效性等特征的快捷货物运输比重越来越大，其对运输方案的制定提出了更高的要求。在铁路、公路、水运、航空等运输方式组成的综合运输体系下，如何根据快捷货物的运输时效性需求，优化各运输方式间相互协调的综合快运方案，提高货物运输的无缝衔接水平，更好地发挥各运输方式的优势和组合效率，是一个值得我们深入研究的问题。

综合快运方案是针对快捷货物运输需求，在既有的综合运输网络中，使铁路、公路、水运、航空等运输方式之间有机衔接和协调匹配，将货物快捷运送到目的地的货物运输方案。货物运输方案的优化通常可以抽象为一类服务网络设计问题，文献［1-3］提出了货运服务网络设计优化问题的基本思路和方法；文献［4］研究了行包流分配与车流径路、行包专列开行方案的统一优化问题；文献［5］基于快运需求，利用动态服务网络优化直达列车开行方案；文献［6-7］将快运网络的拓扑结构划分成多个层次，提出了考虑车辆周转的服务网络设计问题。在综合货运服务网络设计方面，文献［8］基于服务水平的概念构建了综合运输体系下的快运网络；文献［9］将综合运输枢纽选址和服务网络设计问题相结合；文献［10］研究了考虑时间维度的服务网络路径搜索和流量分配；文献［11］建立了考虑运输时间可靠性的综合快运服务网络运输能力计算模型。由于传统的单层动态服务网络无法精确刻画货流集结、编组和中转作业，文献［12］提出了基于3 层时空网络的整数规划数学模型以精细化刻画上述流程，但其仅考虑铁路单一运输方式；文献［10］利用3 层时空网络研究了综合运输体系下的货运服务网络优化设计问题。此外，不同的服务网络模型表达方式对求解算法的影响很大［13］；当模型中约束和决策变量的数量非常庞大时，会通过给定服务或路径备选集的方式缩减解空间，以降低求解难度。目前应用服务网络设计相关理论对货物运输方案的优化研究主要局限于单一的运输方式，较少关注枢纽内部不同运输方式间的中转衔接，难以直接利用既有的服务网络设计模型准确刻画货物在不同运输方式间的中转作业过程，尚不能满足综合快运方案的优化设计要求。

为此，本文针对快捷货物运输需求，将单一运输方式的服务网络设计问题拓展至涵盖铁路、公路、水运、航空等多种运输方式的综合运输领域，考虑不同运输方式间中转衔接的协调性，应用服务网络设计理论，构造包含货流层、编组单元层和运输服务层的3 层动态服务网络，对综合快运组织过程中的货物集结和中转、装载工具的集结和编组、运输方式选择、在途运输等环节进行刻画，构建基于服务网络的综合快运方案优化模型；设计2 阶段求解算法，确定满足快捷货物运输时效性需求，各运输方式分工合理、衔接顺畅的综合快运方案。

1 服务网络构建及特性分析

综合快运方案决定了货物运输中采用的运输方式，及其对应运输工具运输的起讫点、运行时间、运行路径、编组内容。货物在运输全过程中可以依次被多个运输服务运载，并在枢纽完成中转。货物的中转作业可以分为2 种：①货物在不同运输方式间直接换载，例如驮背运输中挂车在铁路列车和公路货车间的换载，铁水联运中集装箱在铁路列车和水运船舶间的非落地换装；②货物需要在枢纽内卸载落地，然后换装到其他运输工具中。为了表达这2 种中转作业，明确如下概念。装载工具：指的是铁路货车、公路整车、水运船只、航空飞机等载运工具，以及挂车、集装箱等可以装运货物并可作为中转单元的设备的统称。编组单元：指的是1 组路径相同的装载工具，如铁路运输中以2 节以上车辆构成的车组，公路运输中的1组挂车或若干车辆组成的车队。

在运输过程中货物可处于3 种状态：货流状态，指去向相同、且发送时间相近的货物集结成为货流；编组单元状态，指始发或中转的装载工具集结形成编组单元；运输服务状态，指在途运输以及运输服务间的接续。3 种状态可以相互转化，货流状态与编组单元状态的相互转化表示货物装入装载工具或从装载工具卸载；编组单元状态与运输服务状态的相互转化表示编组单元搭载某种运输服务运输或从某个运输服务上卸载。

传统的单层服务网络如图1所示。该服务网络的横向按照时间轴展开，t1，t2，…，t6为节点对应的时间；纵向按照站点展开，A和B为2 个综合快运站点；每个节点具有时间和站点2 个属性。图1中：弧表示运输服务，如公路运输弧指向（B，t1）节点，表示通过公路运输于t1时段到达B站点；铁路运输弧从（B，t5）节点发出指向（A，t6）节点，表示通过铁路运输于t5时段离开B站点，并于t6时段运行至A站点；中转弧由（B，t1）节点指向（B，t5）节点，表示货物从公路运输服务中转至铁路运输服务。该单层服务网络只能描述服务的起讫点和开行时间属性，无法详细刻画站内的货物集结与中转、装载工具的集结和编组的过程，不利于精细化地刻画综合快运的作业组织流程。

图1 单层服务网络示意图

为了克服单层服务网络的缺陷，根据货物在综合快运组织过程中的3种状态，将单层动态服务网络拓展为“货流层”、“编组单元层”、“运输服务层”，并将各层中每个节点拓展为“IN”和“OUT”2 个节点；针对每一层，横向上分别表示站间货流的进入和离开，纵向上分别表示站内运输服务—编组单元—货流间不同状态的转化。例如，图1中B站的节点，拓展后可得到如图2所示的3层服务网络，此网络描述了1 批需要运输的货物，通过公路运输到达B站点，然后中转到从B站出发的铁路运输的过程。由于篇幅限制，图2所示的网络仅刻画了发生在B站的作业流程，其他站点以及通过铁路运输到达其他站点后再转接其他运输方式的过程与其类似，这里不再赘述。

3层动态服务网络的具体内容如下。

（1）货流层：用来刻画站内的货物集结。例如，图2中t2和t3时段B站产生的货运需求，还有到达B站的公路编组单元卸载的货物，两者在货流层等待、集结，然后到达货流层的“OUT”节点，再于t3和t4时段装入铁路货车，进入编组单元层。

（2）编组单元层：表示编组单元的站内中转。例如，图2中在t1时段通过公路运输到达B站的货物，其中终到站为B站的货物完成运输，通过拆分弧离开编组单元层，转移到货流层，进而离开运输服务网络；其中在B站需要落地中转的货物，也要转移到货流层进行换装，并重新组建编组单元；而通过直接换载中转的货物，则可在编组单元层以集装箱或挂车为单位中转至其他运输方式。

图2 3层服务网络示意图

（3）运输服务层：表示站点之间的运输服务以及服务间的接续关系。其中，接续关系包含同种或不同运输方式间的中转换装、同种运输方式间的停站作业等。

上述3 层之间通过层间弧连接，表示运输服务与编组单元之间、编组单元与货流之间的状态转换。运输服务层和编组单元层之间通过编发弧和解编弧连接，分别表示运输服务搭载和卸载编组单元；编组单元层和货流层通过组合弧和拆分弧连接，分别表示编组单元的构建和拆分。

2 基于服务网络的综合快运方案优化模型

2.1 符号定义

1）集合与元素

N为动态服务网络时空节点集合，n∈N为1个节点；NS，NB，NC∈N分别为运输服务层、编组单元层、货流层时空节点集合。K为给定的OD 需求集合；k∈K为1 个OD 需求，其起点为NOk，终点为NDk，货运量为Qk，运输起始时间为tk，需求种类为lk。lk∈L表示1 种运输服务种类，L={公路运输、铁路运输、水路运输、航空运输}表示运输服务种类集合；S为运输服务集合，s∈S为1 个运输服务；Sn为节点n对应的服务集合。B为编组单元集合，b∈B为1 个编组单元；Bs为服务s对应的编组单元集合；Bn为节点n对应的编组单元集合。

A为网络中所有弧的集合，a∈A表示1 条弧。AZ为层间弧集合，包含组合弧、拆分弧、解编弧、编发弧，AZ∈A。AS∈A为运输服务层弧集合，ASM，ASD∈AS为运输服务层运输弧、等待弧（接续弧）集合。AB∈A为编组单元层弧集合，ABT，ABY∈AB为编组单元层中转弧、等待弧（待运弧、待转弧）集合。AC∈A为货流层弧集合，ACC，ACY∈AC为货流层集结弧、等待弧（待组弧、待集弧）集合。和分别为从节点n∈N出发的弧段集合和到达节点n∈N的弧段集合。

2）参数

为对应时段节点n∈NS开行运输服务的能力，个；uBn为节点n∈NB对应时段内组建编组单元的能力，t；us为运输服务s的装载能力，t；ub为编组单元b的装载能力，t；ua为弧a∈ACC的容量，即弧段起点对应的时段内货流的集结能力，t；

Cb为组建编组单元b∈B的固定成本，元·次-1；Cs为开行运输服务s∈S的固定成本，元·个-1；Cka为需求k∈K在中转弧a∈ABT的中转固定成本，元· 次-1；CkGa为需求k∈K在弧a∈A*={ACY∪ABY∪ACC∪ASD∪ASM}上的可变成本，元·t-1；ρlk为lk∈L种类需求单位货物运输收入，元·t-1。

为需求k∈K的运输时间，为服务网络间隔时间的倍数；Tk为需求k∈K的运到时限，为服务网络间隔时间的倍数；τk为对需求k∈K逾期运到的惩罚费用，元·t-1；ε为运到时限逾期惩罚系数，元。

3）决策变量

xka为需求k∈K分配到服务弧a∈A上的流量，t。yb为0-1 变量，表示编组单元b∈B是否组建，若组建编组单元则取值为1，否则取值为0。zs为0-1 变量，表示运输服务s∈S是否开行，若运输服务开行则取值为1，否则取值为0。

2.2 模型构建

综合考虑货主及运输企业的利益，以运输企业收益最大为目标函数，将货主对于时效性等因素的要求作为广义成本和惩罚费用在运输企业收益内扣除，同时，以运输能力、流量平衡等限制为约束条件，建立综合快运方案优化模型P1如下。

s.t.

式（1）为目标函数，表示运输企业收益最大化，由运输收入、运输成本和惩罚费用3 部分组成，其中为运输收入，为运输服务层、编组单元层和货流层的集结、等待作业的可变运输成本，为中转作业、组建编组单元、开行运输服务的固定运输成本之和，为运到期限逾期惩罚费用。

约束条件中：式（2）为货流集结能力约束，即弧上分配的流量要小于对应时间段内货流的集结能力；式（3）为编组单元的装载能力约束，表示编组单元层弧上分配的流量要小于其装载能力；式（4）为运输服务的装载能力约束，即运输服务弧上承担的流量应小于其装载能力；式（5）为运输服务决策变量与编组单元决策变量之间的关联关系约束；式（6）为节点组建编组单元的能力约束，表示某站点在某时段内，编组单元对应的弧上分配的流量之和不大于编组单元的组建能力；式（7）为节点的运输服务出发能力约束，表示某站点某时段出发的运输服务数量不超过其发车能力；式（8）为节点的流平衡约束，表示某节点的流入流量要等于流出流量，且对于始发或终到节点，流入或流出流量要与运输需求量一致；式（9）为超过运到时限要求的惩罚约束；式（10）是决策变量的取值范围约束。

3 2阶段遗传算法设计

对于建立的模型P1，由于每一个流量分配决策变量对应的是一个弧段，随着网络节点的增多，模型的约束和决策变量的数目迅速增大，从而增加了求解的难度［13］，一些文献通过给定服务集或路径集来降低求解难度，但这样会使目标函数优化程度受限。模型P1 中，表示编组单元是否组建的变量yb与表示运输服务是否开行的变量zs均为0-1变量，且两者之间具有关联关系。而流量分配变量xka是连续型变量，某弧段上是否允许分配流量取决于其相关的服务是否开行。为了降低求解难度而又不影响目标函数优化程度，本文针对模型的特点，设计了1种2阶段的求解方法。

3.1 求解思路

第1 阶段，假定开行运输服务变量zs已知，将货流按照“时效性最好”的原则分配到服务网络上，得到变量xka的值。鉴于编组单元组建变量yb与运输服务开行变量zs之间的关联关系，若给定运输服务开行变量zs，与未开行的运输服务相关联的编组单元就不可能被组建，一旦某运输服务弧被分配流量，则代表与该弧段相关联的编组单元yb需要组建。因此，在这个阶段可将模型P1 中仅与zs及yb相关的部分进行如下处理：①目标函数中的部分仅涉及编组单元构建及运输服务开行的固定成本，该部分成本已经确定，可不在目标函数中体现；②在zs及yb已知的前提下，约束条件式（5）已经确定，而约束条件式（7）则应在运输服务设计阶段被满足，故在本阶段可不考虑约束条件式（5）和式（7）；③定义SR为确认开行的运输服务集合，此时可选编组单元将局限于集合BRS，相应的Bn将变为BRSn。定义ARS为货流层弧和确认开行运输服务对应的编组单元层上所有弧的集合，A**={ACY∪ABY∪BRS}为货流层、编组单元层的等待弧和编组单元对应运输服务弧的集合，并进一步压缩目标函数及约束条件式（3）、式（4）和式（6）的变量取值范围。由此处理后，可将模型P1 简化为只需要考虑货流分配的模型P2，如下。

s.t.

模型P2 为经典的多商品网络流模型，各变量的取值范围进一步缩小，只需要在货流层和编组单元层进行流量分配，即可获得1个服务决策方案。

第2 阶段，运输服务设计。采用基于遗传算法的迭代机制对服务决策方案进行优化，以便于获得更优的货流分配结果。即以第1 阶段的流量分配结果对应的综合快运方案的收益大小作为本阶段遗传算法个体优劣的判断指标，在此基础上进行遗传进化操作，得到新的种群再反馈给第1 阶段；2 阶段的结果互相反馈，根据遗传进化结果不断优化服务集合，获得优化的综合快运方案，从而实现“企业运输收益”和“货主运输时效性”的综合最优。

3.2 算法步骤

遗传算法采用二进制编码，以服务网络中所有编组单元的选择方案作为1 个染色体，长度为所有可能存在的编组单元数量之和；以每个编组单元相关联的运输服务弧是否为网络的构成弧作为基因位点：是则取值为1，反之则取值为0。结合上述2阶段遗传算法求解思路，设计的求解算法步骤如下。

Step1：种群初始化。设置种群规模P、交叉概率pc、变异概率pm以及进化代数gmaxgen。随机生成单个初始化染色体，获得初始种群。

Step2：网络构建。针对种群中每一个个体的编组单元对应的运输服务弧的不同，根据运输服务弧时间间隔的不同，在服务网络中依次补全编发弧、解编弧、待转弧、中转弧、拆分弧。并根据需求产生时间生成集结弧，为相应集结弧补全待集弧、待组弧、组合弧，根据已经添加的弧补全待运弧。

Step3：流量分配。在已知网络结构的前提下，求解模型P2。按照“大宗先行，先到先运”的分配顺序进行流量分配，根据货运量将货物需求进行排序，在运量相同的情况下优先考虑产生时间较早的需求。对需求进行排序后，再按照“全有全无”的方式分配，利用Dijkstra 算法为各个需求选择路径。为每个需求计算最短路径前，需要将网络中当前剩余容量小于当前需求流量的弧暂时剔除，再进行路径选择；判定所有弧容量已满，或者所有需求已经被分配完毕的情况下，得到最终的流量分配方案，获得每个染色体对应的服务决策方案。

Step4：种群进化。计算适应度函数，对种群进行选择、交叉、变异操作，得到新的种群，具体如下。

（1）适应度函数计算。根据Step3 的“流量分配方案”计算模型P1 的目标函数，并记录目标函数最优的个体，将其对应的综合快运方案作为当前模型P1 的解。以模型P1 的目标函数值，作为遗传算法中染色体适应度的计算依据。为保证适应度函数始终为正，设计适应度函数为f=(z-zmin+M)，其中M为1 个较大的正整数，根据算例中具体参数设计而确定大小。

（2）选择：采用轮盘赌选择与精英选择相结合的染色体选择方式，保证较优的父代性状被子代保存。

（3）交叉：等概率随机产生交叉位点，对种群相邻染色体采用单点交叉，对交叉位点后的基因进行交叉。

（4）变异：随机选择种群中的某个体，然后根据其染色体长度随机选择固定数量的变异点进行突变。

Step5：终止条件判定。当前进化代数ggen=ggen+1 。如果ggen≤gmaxgen，则跳转至Step2；否则，退出求解，输出目标函数最优的综合快运方案，算法终止。

4 实例分析

选取如图3所示的某铁路局集团公司管内铁路快运列车运行线路及其辖区内主要干线公路构成的公铁联运网络，对上述模型和算法进行验证。图3中：有MH，TH，JGTQ，…，SFH 共15 个铁路车站（节点），每个车站均有干线公路与其相连；节点间标注了铁路快运列车车次，如BJ—QQHR每日开行X429 次列车。设定集装箱容量为15 t，1辆卡车至多装载2 个集装箱，1 列货物列车至多装载40 个集装箱。由于运输服务可能在全天的任意时段开行，且运行距离较长的服务可能存在运行时间跨天的情况，故时空网络的时间轴长度设置为35 h，时间离散化的精度为1 h。由此生成的3层服务网络共有节点3 150 个［15（车站节点）×3（3层服务网络）×2（“IN”和“OUT”节点）×35（离散时间单位）］。

图3 公铁联运网络结构

假设图3所示的网络中每个节点均有需求产生，且需求有明确的发货时间段（以需求产生时刻表示），由此共产生72 个运输需求，其中公路运输需求30 个，铁路运输需求42 个，部分OD 需求流量见表1。为方便表述，运量的单位采用t，1 个容量为15 t的集装箱，运量记为15 t。

参数取值：各站点之间开行铁路货物列车、公路整车的运输服务的部分固定成本见表2；中转固定成本为4.2 元·次-1，组建编组单元的固定成本为3.3 元·次-1；货物等待装箱、装箱的可变成本分别为0.5，1.2 元·t-1；集装箱等待装车、装车、等待运输服务开行、等待中转、中转、卸车的可变成本分别为0.5，0.9，0.5，0.6，1.2，0.5 元·t-1；铁路运输的单位收入为28.3 元·t-1，公路运输的单位收入为31.2 元·t-1；运输时限逾期惩罚为1元·t-1。

设置遗传算法参数取值：种群规模P=30，交叉概率pc=0.9，变异概率pm=0.1，进化代数gmaxgen=500。采用C#语言，对上述2阶段求解算法编写计算程序，以上述数据作为输入，计算得到遗传算法的收敛趋势如图4所示，综合快运方案见表3。由图4可知：初始方案的目标函数为-24 147.3元，优化方案的目标函数为54 114.9 元，算法在进化前期的收敛速度较快，后期变缓，并在200 代后逐步收敛，最优目标函数和平均目标函数都趋于稳定；虽然每代的最优结果有所波动，但整体结果还是呈现优化的趋势；由此验证了模型和算法的合理性和有效性。

表1 部分OD需求流量

表2 运输服务固定成本（部分）

图4 遗传算法收敛趋势

由计算结果可知：综合快运方案共产生48 个运输服务，其中公路运输服务17 个，铁路运输服务31 个；有4 个公路运输服务和铁路运输服务间存在货流中转关系，有15 个铁路运输服务间存在货流中转关系，说明本文的优化方法可使不同运输方式间的中转接续更协调顺畅；而在全部72 个运输需求中，有7 个需求未被运输，这是因为这些需求的货运量较小，在运输服务装载能力接近饱和时，再加开运输服务会增大运输成本，降低运输收益；在公路的30 个运输需求中，有16 个依旧选择公路运输服务，有10 个选择了铁路运输服务，如HRB—SH（产生时间为7：00，运量为9 t）、JG⁃DQ—TH（产生时间为6：00，运量为7 t）等，有4 个需求通过铁路及公路联合运输至目的地，如HRB—JGDQ（产生时间为9：00，运量为6 t）等，说明本文的优化方法可为不同种类需求选择合适的运输方式，从而发挥不同运输方式的优势，以达到综合考虑运输企业收益和货主时效性需求的目的。

表3 综合快运方案（部分）

采用上述综合快运方案，最终得到运输企业收益为54 114.9 元，运输收入为170 179.6 元，运输总成本为112 773.7 元，其中固定成本为99 700 元，可变成本为13 073.7 元，运到期限逾期惩罚为3 291元。若不采用公铁联运，且为保证满足上述方案中运输的货物需求，假定铁路运输服务中列车X401，X413，X415，X429开行频率均为1 列·日-1，X411开行频率为2 列·日-1，则共产生48 个运输服务，其中公路运输服务31 个，铁路运输服务17 个，得到运输企业收益为39 903.3 元，运输收入为191 311.4元，运输总成本为137 518.1 元，其中运输固定成本为105 300 元，可变成本为32 218.1 元，运到期限逾期惩罚为13 890 元。由此可见，采用联运的综合快运方案，虽然增加了部分铁路直达运输服务，但减少了部分铁路班列的停站，并通过公路和铁路之间的中转接续，发挥了铁路运量大速度快、公路适合两端集疏运的优势，使得运输总成本降低了17.9%，运输可变成本降低了59.4%，运到期限惩罚降低了76%，运输企业收益提高了35.6%。

从货流角度而言，不同运输方式的协调配合，使得货运需求转移到运输费用更低的运输方式上；从运输服务角度而言，优化的运输方案为中转接续提供了良好的条件。运输企业可以利用更多的服务组合，制定更加灵活的综合快运方案，更好地适应运输需求的实时变化。

5 结 语

为实现综合运输体系下各运输方式的合理分工和顺畅衔接，本文应用服务网络设计理论研究了综合快运方案优化问题。基于货物在综合快运作业流程中的3 种状态，构建了3 层服务网络，详细刻画综合快运站点内部各项作业流程。在此基础上，建立了综合考虑时效性需求及运输企业收益的综合快运方案优化模型，设计了2 阶段遗传算法求解模型，克服了目标函数优化程度受限于备选路径集或服务集的问题。以某铁路局集团公司管内铁路快运列车运行线路及所辖区域内主要干线公路构成的公铁联运网络为例，验证了模型及算法的合理性和有效性。结果表明，优化的综合快运方案能够降低运输成本，提升运输收益，为不同种类需求选择合适的运输方式，更好地体现不同运输方式之间的协调配合，提升综合快运系统的运营效能。但在求解时仅考虑了选择最短路进行流量分配，对于各类作业弧的作业时间及作业成本分配尚待进一步完善。