多式联运情形下货物中转集拼的运作优化

吕博文 杨 斌 朱小林

(上海海事大学物流科学与工程研究院 上海 201306)

0 引 言

中转集拼是指货物运输过程中经过多次中转、集拼、分拨，最终到达目的地的一种物流作业形式。中转集拼具有作业集约化、分工专业化、操作灵活等特点，广泛应用于快递、航空、集装箱多式联运等物流运作中。

目前关于中转集拼的运作优化研究，各类相关文献涉及不多，这与当前新运输方式的发展不相适应。本文在前人研究的基础上，提出了多式联运情形下的中转集拼运作优化研究。权家祥[1]于1998年对货物如何拼箱进行研究，指出在转拼过程中，为了尽量减少集装箱的空载率，在拆箱卸货的同时，可拼入适当数量的货物，充分利用集装箱，此种运输方式随后也被称为中转集拼。中转集拼业务[2]具体是指：货物经过运输至集拼点，在该节点处进行二次分拣和包装，并根据不同目的地或不同客户，与本地货源一起重新装箱后进行运输的一种新型物流业务。该业务涉及多OD对货物的同时装卸、货物对集装箱的选择以及集装箱运输路线与货物运输路线的耦合等问题。

针对多OD同时装卸问题有以下研究。卜雷等[3]对多种货物的拼箱装配问题进行研究，并构造合理的个体编码适应度函数，运用遗传算法优化普零货物拼箱装配问题。Tasan等[4]在解决同时装卸的VRP问题的基础上，提出了一种遗传算法，并通过解决多个测试问题对方法进行评估，证明了算法的有效性。Belgin等[5]考虑双梯队车辆路线问题同时取货和交货，运用一种基于变邻域下降(VND)和局部搜索(LS)的混合启发式算法，并运用单级和双级分销系统对同时取货交货系统进行研究。

拼箱问题与零担问题的研究有一定的相通之处。Salvador等[6]运用分支裁剪法，解决动态容量下零担货物承运人之间的合作问题，通过等待装箱和转运，权衡持有成本和拥挤成本。Cheung[7]提供了一种策略，对零担服务网络路线的随机性和动态性进行研究，通过具有随机弧成本的网络找到动态最短路径并计算出行时间。不同之处在于中转集拼问题可与多式联运相结合，不仅仅作为一个运载工具。但针对多式联运的研究多集中于整箱集装箱的研究，文献[8]研究了有容量约束的枢纽中心的网络设计，从枢纽点的建立和不同交通工具运营两个层面分析多式联运网络的效率。文献[9]从各个网络节点，考虑整个网络的优化研究，用贪婪算法和智能搜索来求解多式联运问题，并对两种算法的运行时间进行对比，得出最优的运营时间。谢雪梅等[10]考虑运输成本、换装成本、风险成本以及时间惩罚成本的整车多式联运，并运用二进制编码的遗传算法进行求解。这些研究针对整个集装箱在特定条件下的多式联运问题进行建模和求解，并没有考虑集装箱内多OD流货物运输过程中的作业整合，即货物的中转集拼作业优化。对于小批量多批次货物运输来说，从空间利用的角度，顺路搭车的观念出发，在货物装运，集装箱转运的过程中，多式联运运作的优化策略也大不相同。

因此，本文从拼箱的全局角度考虑，充分、均衡利用集装箱的载重和容积，减少空载率，建立一个混合整数规划的多式联运模型，目标函数考虑运营成本的最小化，包括运输成本、转运成本以及节点的作业成本。通过设计遗传算法，并进行一定规模的算例验证，有效地完成集装箱中转集拼过程中不同集装箱拼箱点和转运点的选取，运输方式和运输路线的选取。

1 问题描述

本文在传统的多式联运网络的基础上，考虑小批量货物的运输和集装箱中转集拼作业，由一个货运代理，多个不同国家或地区的多个货主以及公路、铁路和水路三种运输方式组成了联运网络。研究的对象是拼装入箱的多批货物，研究的整体是一个集装箱由空箱经中转装卸、再到空箱的作业流程，选取适当的拼箱点和中转点，使总成本最小。文中将运输网络G定义为由卡车F、火车R、轮船B、节点N、集装箱C组成的网络图，以满足不同货主的需求。该网络是由节点连接而形成的有向图，近似为相邻节点之间形成的折线图，M和E分别表示拼箱点和转运点。图中 s表示供应方，c表示需求方，同一需求方可以有多个供应商，同时同一供应商也可以为多个客户提供服务，o、d分别表示单批次货物的起点和终点，m或o表示港口可拼卸点，t表示铁路可拼卸点，由此形成具体情形下的最优运输路线。

图1为起点到终点完成订单任务的全过程，货物由供应点S到需求点C，首先货物先到达起拼点o或者t，此时货物所在区域为同一区域，比如同一国家，可以选择运输方式有铁路和水路运输，为了降低中转的复杂性，假设同一地区的起拼点之间无运输连接。不同的集装箱按照装入集装箱的货物的目的地、集装箱的剩余容量，选择不同的运输路线、不同的中转集拼路线，在运输过程中会不断地到达货物的目的地卸货，然后拼入相同目的地或途经目的地的货物，进行运输。在货物数量允许的情况下，也可直接拼装一个目的地的货物，由o直接到达d。在拼箱的同时，如果转换运输方式，会有一定的成本优势，可选择铁路运输，或直接门到门运输，使集装箱由空箱到重箱再到空箱不断地转换，完成对小批量货物的运输。

图1 中转集拼的多式联运网络图

图1的运输路线为从供应点到需求点的集装箱以及货物的流动，模型设计针对多个阶段的滚动优化。起运端要完成空的集装箱与拼箱货的组合决策。涉及货物装入集装箱的选择、沿途各节点的选择、运输方式的选择，停靠点的选取(假设整个网络中的信息完全共享)，中间节点需决定货物重新装箱、卸箱后运输方式的选择，以形成该条件下的最优网络运输。

2 模型的建立

2.1 基本假设

1) 服务对象为小批量的货物，便于进行拼箱操作；供给地与需求地不属于同一个国家，便于进行多式联运操作。

2) 整个运输过程中，同一个集装箱全球运输的过程中只有一个货代，可对全局进行统筹规划；货主可以是多个国家，便于沿途边装边卸。

3) 货物拼箱后，该集装箱所装货物的类型已经确定，只能再拼入相同类型的货物，并且集装箱的目的地取决于装入最远距离货物的目的地。

4) 进行拼箱的货物足够多，不会有箱等货的现象；集装箱进行转运，不考虑车辆的调度，是无缝连接的。

5) 指令性优先装箱的原则是：在符合装箱质量和容积限制的货物中，最高优先级：装入和箱内已装货物有相同目的地的货物；次优先级：装入能减少集装箱的空载率的货物。

2.2 数学模型的建立

本文提出了一种基于混合整数线性规划的方法，通过考虑特殊节点，使点与线相结合，形成多式联运网络，用于解决包括不同运输模式和转运位置的联运计划问题。

2.2.1 参数说明

1) 集合：

K运载工具

F卡车

B轮船

R火车

N节点

P货物类别

C集装箱

L路线集

Ak弧的集合

2) 成本参数：

(r/f/b⊆K;i∈N;j∈N)

c1单位质量货物的装载成本

c2单位质量货物的卸载成本

c3单位集装箱的转运成本

ec一个集装箱经过的所有节点的个数

3) 箱货参数：

Pm0在节点m处优先装箱的货物集

Pm1在节点m处不能装入同一集装箱的货物集

A(ic)在节点i处装入集装箱c的货物集

B(ic)在节点i处从集装箱c卸下的货物集

λ如果最大利用容积λ=0，如果最大利用承重量λ=1,如果两者均最大利用λ=0.5

η1集装箱装载的弹性系数

η2集装箱容积的弹性系数

q中转集拼网络中总的货物批次

dijk节点i和节点j之间的距离

lp货物p的运输路线

4) 决策变量：

Yic0-1变量，集装箱c在节点i处集拼为1，否则为0

Zic0-1变量，集装箱c在节点i处卸下货物为1，否则为0

xic0-1变量，集装箱c在节点i处进行物流作业为1，否则为0

xpci0-1变量，货物p在节点i处装入集装箱c为1，否则为0

2.2.2 模型建立

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

xpci∈{0,1}i⊆N;c⊆C;p∈P

(22)

(23)

(24)

式(1)是总成本目标函数，包含货物从供给地到需求地的固定成本和可变成本，固定成本是指整个运输过程中集装箱的固定使用费用，与所选的运输方式和集装箱经过的节点有关。可变成本包括两个阶段：节点作业、运输阶段。节点作业阶段，包含装载工具对集装箱的装卸成本、集装箱对货物的装卸成本，以及集装箱在节点的转运成本。运输阶段的成本主要包含集装箱的运输成本。

式(2)为节点的流量守恒；式(3)确保只有弧(i，j)可用时，目的地为d的货物才可以经过这段弧；式(4)表示满足所有货物需求；式(5)表示集装箱在相同路线上运送的货物量。式(6)-式(15)为节点作业的约束：式(6)为不能同时装箱的约束；式(7)表示同一种货物只能装在同一集装箱内；式(8)为指令性优先装箱的约束；式(9)-式(11)为货物装箱的质量和容积约束；式(12)表示如果在m点发生了拆箱作业，则必发生了货物的拼入或卸出；式(13)为作业点的约束；式(14)表示集装箱由空箱变为空箱的流量约束；式(15)表示只要节点发生物流作业，则拼箱、卸箱、转运至少发生一次。式(16)-式(24)为0-1约束和非负约束。

3 求解算法

针对货物装箱运输问题的求解研究，可采用分支裁剪法、分支定价法等方法解决此类问题[11]。但大规模、多约束的复杂问题，多采用智能算法求解[12-15]。中转集拼的多式联运网络优化问题，包含货物的装箱分布问题和复杂运输网络的多式联运问题，因此是一个具有复杂约束的组合优化问题，属于NP-hard问题。本文针对中转集拼的混合整数规划问题，运用遗传算法，选取整个过程总成本最小的装箱和运输方案。

3.1 算法步骤

步骤1初始化种群Chrom，包含Npop对染色体，每对染色体由双层染色体组成，分别代表货物段序列和装箱分配关系序列；

步骤2解码染色体，计算每个染色体对应的适应度值，即完成货物运输的总成本；

步骤3判断是否满足迭代停止条件：最大的遗传代数，若满足，则结束算法操作，否则转步骤2，进行适应度值的计算；

步骤4选取适应度值相对最大的Npop个染色体组成新的种群Chrom*；

步骤5以新种群Chrom*作为父代，按照交叉概率Pc，变异概率Pm执行对应算子，获得子代，重复进行步骤2的操作。

3.2 编码和解码

本文的染色体编码采用双层染色体编码方式，如图2所示第一层L1为货物编号的随机生成，第二层编码L2是一个维数可变的向量，在容量约束下，根据贪婪算法，计算出货物的装箱分布。

图2 染色体的编码方式

例如，自然数1～9代表货物的编号，其大小依次为1,2,1,3,2,1,2,2,3，集装箱容量约束为7个单位。如图2所示，按照容量约束，第一个集装箱装入货物1、2、4，第二个集装箱装入货物7、5、3、6，第三个集装箱装入货物9、8。装入集装箱的第一批货物，作为L2每段基因的编号。

解码过程分为三个阶段，首先根据集装箱编号与货物编号依次解码，得到集装箱1装入货物1、2、4，集装箱2装入货物7、5、3、6，集装箱3装入货物9、8；然后可根据已知的货物起始点位置信息，得到集装箱1经过节点1、5，集装箱2经过节点1、5、2、4，集装箱3经过节点3、4；根据货物的OD关系：[1-3,1-5,5-1,1-3,5-4,2-4,3-5,4-1,4-3]，得出最终集装箱经过的节点，如图3所示。

图3 染色体的解码方式

当集装箱1到达节点3后，卸下货物1、3，重新装进货物7进行运输；集装箱2从节点5处开始装入货物3、5，到达节点2装入货物6，到达节点4，卸下货物5、6，由于集装箱容量有剩余，故装入货物8、9，继续运输，此时只需两个集装箱，即可完成整个运输。

3.3 适应度计算

根据目标函数中作业成本的最小化，计算适应度的步骤如下：

步骤1对所生成的染色体，通过模型中装入集装箱的货物的体积、质量约束，对不符合条件的染色体，给予一定的罚数Cu；

步骤2依照装入集装箱的货物的先后顺序，对单个集装箱货物的装卸成本，按照所经过的节点的先后顺序对C3进行累加；

步骤3按照经过节点的先后顺序，对运输成本C1和集装箱的固定成本C2求和；

步骤4计算所需集装箱的总的成本C=Cu+C1+C2+C3。

步骤5种群的适应度值fit=1/C，求得种群的适应度值。

4 算例分析

4.1 数据描述

为了考察算法的有效性，本文模拟了具有35个节点(代表不同国家和地区的货物集散港口)的多式联运网络，具体空间分布如图4所示。x轴表示作业节点位置的横坐标，y轴表示其纵坐标。网络中包含50批含不同或相同起点和目的地的货物，为了符合实际情况，数据随机生成且满足公路的单位运输成本高于铁路和水路，单位运输成本公路是水路的2～3倍，水路大于铁路，但相差不大，同时公路的单位集装箱固定使用费用少于铁路和水路。

图4 35个节点的空间分布

表1 网络中所有货物的信息

续表1

表2 影响因子设计

4.2 结果与分析

4.2.1 模型有效性验证

为了验证遗传算法求解模型的有效性，影响因子分别取表2集合中的第一组元素，通过MATLAB编程，对代码运行10次，选取最优的一次计算过程，其最大迭代次数为200代，其中到达80代时，曲线趋于收敛趋势，其后相对收敛缓慢,此时的满意成本是14 688.587 9，需要安排6个集装箱，以满足整体作业要求，货物装箱的分布如表3所示。

表3 货物装箱的分布表

各集装箱经过的节点集合，以及各节点间的运输方式如表4所示。

表4 集装箱经过的操作节点和节点间的运输方式

4.2.2 载重弹性系数和集装箱的固定运输费对结果的影响

(a)

(b)图5 集装箱载重系数和其固定成本对箱数和总成本的影响

图5(a)表示载重系数和集装箱的固定成本对所需集装箱的个数的影响，x轴表示集装箱载重系数，y轴表示所需集装箱的个数。当载重系数一定时，固定成本越大，箱数需求越小，当固定成本很小时，运输成本占总成本的比重较大；当固定成本一定时，载重系数越大，需求量越少，符合实际情况。

4.2.3 对比分析集装箱的利用率

与设立枢纽点进行对比，经求解得：节点35为枢纽点，由于货物是静态存在的，此时首先需要起点非35的货物分别运送至枢纽点，然后从35点开始装箱运输，需要10个集装箱，由于此时的整体成本不具有可比性，故只比较单个集装箱的成本之和，相比中转集拼的成本14 688.587 9元，采用枢纽点装箱运输的成本为19 742.736 4元，其中4 672.9元为分散节点运往枢纽点的成本，且不包含枢纽点的建设成本。因此，采用中转集拼所具有很明显的成本优势。

分析两种不同方案下的集装箱的动态吨位利用率，如表5所示。

表5 集装箱中转集拼的吨位利用率

表6 集装箱建立枢纽点的吨位利用率

通过建立枢纽点，需要10个集装箱，不仅成本上不占优势，而且集装箱的利用率也很低，平均吨位利用率为52.19%，低于中转集拼中的集装箱的最低利用率；而且集装箱的实际货运周转量和有载行程周转量均比较高。因此对于小批量的货物，中转集拼减少了集装箱的空载里程，提高了装载效率，实现了集装箱的极大利用。

5 结 语

本文对中转集拼的运作优化的问题进行分析，通过分析集装箱动态容量和运输优化，提供了一种分析拼箱货运代理的运输整合潜在效益的机制。并设计遗传算法应用于中转集拼运作优化得出以下结论：

在小批量货物的运输网络中，选择合适的货物包装布局和运输方式将降低整个过程的总成本(节省5 054.148 5元的成本)，这与实际情况相符，说明模型的有效性。利用该算法可以有效解决多货物运输拼装问题；同时得出载重系数与所需集装箱个数、总成本反比的关系；并获得最佳的货物布局，以及每个集装箱的路线，平均动态吨位利用率与建立枢纽相比提高了15.86%，由此得出中转集拼运作优化的有效性。算法设计说明了该中转集拼运作优化的可行性，值得进一步研究和探讨。