加班费用影响下多式联运路径问题研究

唐 祯 陈 枫 傅志妍 谷朋飞

(重庆交通大学交通运输学院1) 重庆 400074) (重庆第二师范学院经济与工商管理学院2) 重庆 400067)

0 引 言

多式联运可以提高运输效率、降低物流成本并且减少环境污染，是一种高效的运输组织方式.多式联运路径问题是多式联运优化研究的重要方向之一，其本质上是最短路问题的延伸与扩展，但由于多式联运存在应用环境复杂、牵扯主体较多、涉及约束多样等特征，Dijkstra算法、标号法等传统最短路问题方法难以直接用于解决多式联运路径问题，需要针对特定的研究内容设计优化模型和算法.

在模型方面，现有研究的优化目标主要集中于经济成本最小、耗费时间最短和碳排放总量最小.刘杰等[1]构建了一个经济成本最小、碳排放总量最小的多目标0-1规划模型，其中经济成本考虑运输成本、装卸转运成本、存储成本以及运输弧段与代理商匹配关系的影响，碳排放量由运输、换装过程的碳排放构成.户佐安等[2]构建由多个决策主体目标构成的广义费用函数，并建立以广义费用最优为目标的多式联运路径优化模型，设计符合实际情况的算例，采用理想点法并借助LINGO软件进行求解，获得不同权重组合下的多组全局最优解，为不同决策主体提供了参考依据.Bowen等[3]考虑到运输车辆容量限制和中间节点可装卸货物的情况，构建了包含装卸成本、转运成本和运输成本组成的经济成本最小为目标的优化模型.在优化算法方面，现有研究大部分基于Dijkstra算法、图论和启发式算法.Hendrik等[4]采用一种动态策略分析运输成本的变化，并设计了一种基于模拟退火的生成树方法用于求解多阶段最短路径.熊桂武等[5]提出了时间窗约束下基于改进遗传算法的代理商、运输路径，以及运输方式协同优化的求解算法.Ayed等[6]在分析具有时间依赖的多式联运路径问题时，设计了基于改进Dijkstra算法和蚁群算法相结合的求解算法.Maciek等[7]考虑到货物运输中存在里程计价的方式，构建了里程计价影响下的路径优化问题，并提出了以最小化运输成本为优化目标的算法.

但是在当前的主要研究中，多式联运路径问题多采用货物在中转节点装卸转运完毕后立刻运往下一节点的假设，但实际情况是铁路、水路等运输方式多是按固定的时刻表发班(即班期)，考虑到这一情况的研究文献较少.另外，由于货物运抵中转节点时间存在不确定性，在非正常工作时间装卸转运不可避免，而在非正常工作时间装卸转运需额外支付相关费用(即加班费用)，这必然会对路径选择产生影响，现有研究尚未注意到这一点.因此，本文统筹虑班期、加班费用等多式联运实际存在的影响因素，建立以成本最小的为目标的多式联运路径优化模型.由于班期的影响，传统的多式联运路径优化算法不能直接应用于本文提出的问题.因此，本文设计不定长度编码的遗传算法，并给出算例证明了算法的可行性和有效性.

1 问题描述与建模

1.1 问题描述

多式联运网络见图1.在实际运输过程中，货主往往对货物抵达目的地有时间要求；公路、铁路以及水路等运输方式一般按设定的班期进行运营；当货物运抵至某一节点时，若需要以另一种运输方式运往下一节点，则会产生货物装卸转运费用，如果运抵时间处于工人非正常上班时间，就会产生加班费用进而影响整个货物运输的总费用.

图1 多式联运网络

1.2 模型假设

1) 运输货物单一且不可分割.

2) 不同运输方式之间的转运时间与成本已知.

3) 货物运抵节点时刻为装卸转运开始时刻.

4) 所有转运节点处装卸工人正常上班时间段已知，加班薪资系数一定.

5) 货物在装卸转运完成后按所选运输方式最近班期开始后一行程运输.

1.3 参数定义

设多式联运网络为G=(N,E,M)；N为顶点集(节点o与节点d分别为起讫节点，o,d∈N)；E为边集；M为运输方式集合，E={ei,j,a|i,j∈N,a∈M}；C为运输总费用；ci,ja为从节点i到节点j采用运输方式a进行运输的运输费用；θia,b为在节点i处正常工作时段由运输方式a转为运输方式b的转运费用；TiG为货物从节点i的出发时刻，起点货物出发时刻T0G已知；TiR为货物到达节点i的时刻；δi为货物在节点i完成装卸转运的时刻；ti,ja为从节点i到节点j采用运输方式a进行运输的运输时间；τia,b为在节点i处由运输方式a转为运输方式b的装卸转运时间；α为装卸转运加班薪资系数；ω为装卸工人正常工作时间；TMAX为客户要求货物最迟送达时刻.

决策变量：

1.4 模型建立

(1)

当货物运抵至某一节点i完成转运装卸时刻为

(2)

(3)

节点i实际发生换装费用为

(4)

考虑加班费用的多式联运路径优化模型(以上已给出约束不再在以下模型中重复给出)为

(5)

s.t.

(6)

(7)

(8)

(10)

式(6)确保每一节点最多有一次货物运出；式(7)与式(8)保证货物运输是从节点o(货物发运地)运出，运抵节点d(货物目的地)；式(9)为节点流量平衡关系；式(10)为货物运抵目的地最迟时刻约束.

2 求解算法

基于多种群、模拟退火策略，组合设计四种遗传算法.其中对单个种群进行选择、交叉、变异操作的算法称之为单种群遗传算法(GA)；对单个种群进行选择、交叉、退火式变异操作的算法称之为单种群模拟退火遗传算法(SGA)；在单种群遗传算法的基础上采用多种群管理策略的算法称之为多种群遗传算法(MGA)；在单种群模拟退火遗传算法的基础上采用多种群管理策略称之为多种群模拟退火遗传算法(MSGA).

采用不定长度的染色体编码方式.个体由两个染色体片段构成，“染色体片段一”代表多式联运网络中从起点到终点按顺序经历的各个节点，用整数排列进行编码；“染色体片段二”代表各节点间的运输方式，用1、2、3进行编码(其中，1为公路运输(H)，2为铁路运输(R)，3为水路运输(W)).以图1的多式联运网络为例，其编码与解码方式见图2.

图2 编码与解码

基于多式联运网络路径问题的特点设计了种群初始化的方法.不考虑运输方式以权值随机来生成与该网络对应的邻接矩阵，利用floyd算法得到一条起讫点之间的最短路径，针对最短路径随机生成节点间运输方式，形成初始种群新个体.

交叉运算为对两个染色体片段依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体.由于本文采用的是不定长度染色体编码机制，采用传统的单点交叉或多点交叉策略进行交叉操作，将导致非法路径以较大的概率产生，影响整个算法的效能，因此需根据本文所述问题的特点对传统交叉方法进行改进.

本文将染色体交叉操作的情景分为两类，第一类为两父辈个体染色体片段一具有相同节点(起讫点除外)；第二类为两父辈个体染色体片段一不具有相同节点.

图3 相同节点交叉

图4 相同位置交叉

上述两类情景的交叉操作有可能导致子代染色体出现重复基因的情况，即运输路径中出现了“圈”.而包含“圈”的运输路径一定不是最短路径，因此本文采用了删除重复基因的方法，以消除路径中的“圈”，提高算法效率.具体见图5.

图5 去圈操作

变异操作具体为从种群个体染色体片段一的基因(起讫点除外)中，随机选取一点，再改变多式联运网络的权值，利用floyd算法寻找从该点至终点的一条最短通路.染色体片段二根据染色体片段一的变异基因随机补填有效基因来实现变异.具体变异操作见图6.

图6 变异规则

为了提高遗传算法的效率，设计了退火式变异.即以一定的退火概率Pm来确定是否发生变异，表达式为

(11)

式中：Pm为接受变异概率；Cold为个体变异前的适应值；Cnew为个体变异后的适应值；W为退火温度.

固体温度将随遗传算法迭代次数增加而降温为

(12)

式中：d为遗传算法迭代次数；Wd为第d次迭代时的退火温度；W0为初始温度，设置第一代种群个体适应值的方差为

(13)

多种群策略是进化时每个种群都保持相对的独立性，将同一代的最优个体进行交叉，生成新个体并计算适应值，从局部最优解、新个体适应值、当前全局最优解中选出最优解，更新全局最优解，并将最优个体保留至下一代种群，流程见图7.

图7 多种群策略流程

3 算例分析

根据Solomon’s Benchmark中C101案例的100个点数据[8]，构造了9个不同规模的多式联运网络，两点之间距离取欧几里得距离.不同运输方式之间的转运时间、转运成本见表1，各种运输方式的行驶速度、单位运输成本及发班时刻见表2，各节点之间的运输方式随机给定.鉴于非正常工作时间装卸转运费用高昂，故取装卸转运加班薪资系数α为2.在不同规模的网络下对本文设计的四种算法进行算法性能对比，四种算法参数设置相同，迭代次数均为100，种群规模均为100，交叉概率均为0.90，变异概率均为0.15，单种群模拟退火遗传算法与多种群模拟退火遗传算法不设置变异概率.实验平台为CPU：Intel Core(i5)、内存：8.0GB的笔记本计算机，编程软件为Matlab2014b，运行次数分别为20次.B为20次运行结果中优化目标最低值，BAV为20次运行结果的平均值，C表示20次运行中第一次找到优化目标值的迭代次数的平均值，运行结果见表3.

表1 换装参数

表2 运输参数

由表3可知：

1) 针对小规模网络，四种算法均能找到最优解，而且随着网络规模逐渐增大，SGA算法的寻优效果最好，其次是MSGA算法；

2) 对比分析4种算法的最优值B，发现SGA算法的求解质量明显优于其余三种算法；

3) 对比分析4种算法的平均最优值BAV，发现在稳定性方面，MSGA算法、SGA算法最优，其次是MGA算法，最后为GA算法；

4) 对比分析4种算法寻优平均迭代次数C，发现MSGA算法的寻优速度最快，其次是SA算法.

综上所述，SGA算法在求解本文所述问题上综合表现最优.

针对SGA算法，以50节点的网络规模为例，参数设置中迭代次数为100，种群规模为100，变更交叉概率，运行20次结果见表4.结果显示当交叉概率为0.8时，整体求解效果最好.

表4 网络节点数为50时不同交叉概率对比结果

交叉概率确定为0.8后，改变迭代次数I和种群规模Z，分别运行20次，结果见表5.由表5可知：在最优值B一定的情况下，如果迭代次数一定时，种群规模越大，其最优解的平均值BAV越低(即求解质量越高)，最后一代种群的平均适应值A也会越来越低(即SGA算法的收敛性越快)；当种群规模一定、迭代次数超过100时，迭代次数与算法求解质量、收敛性之间未发现明显相关联系.

表5 Pc为0.8时不同代次数和种群规模对比结果

4 结 束 语

在实际多式联运中，加班费用、班期约束和目的地时间窗约束是真实存在的，都会影响到运输路径与方式的选择，从而产生的运输费用不同，费耗时间不同，若不考虑这些影响因素，将使得优化方案应用效果劣化.本文考虑到加班费用、班期和目的地时间窗对多式联运路径与运输方式决策的影响，建立了以总费用最低为目标的多式联运路径决策模型.结合模型特点，设计了求解该问题四种遗传算法策略，通过算例对给出的算法进行对比，证明了算法的可行性和有效性，其中SGA算法在求解本文所述问题上综合表现最优.