基于鲸鱼优化算法的多目标多式联运路径选择

吴志勇，戴 弌，鞠传香，胡本佳，胡 啸

(1. 青岛蓝智现代服务业数字工程技术研究中心，山东 青岛 266100； 2. 山东理工大学 计算机科学与技术学院，山东 淄博 255049)

0 引 言

近年来，我国物流产业迅速发展的同时也在大力实施运输结构调整策略，旨在推动我国绿色运输，降低物流运输成本，提高运输效率。多式联运是运输结构调整的重要方式之一，已成为当前众多企业国际、国内运输的重要物流方式之一。多式联运指的是在一次运输作业中，通过两种及以上的运输方式转换将货物运输到目的地的过程。如何提升多式联运效益，已成为众多学者研究的课题[1-3]。

目前，国内外针对多式联运模型构建的研究主要集中在约束环境下如何改进最优路径与运输方式的组合。例如，L. MOCCZA等[4]在构建模型时考虑了节点到达时间、出发时间和整体运输时间等条件对运输路径的选择，将多式联运线路虚拟化为有向网络后，采用列生成算法优化路径选择；T. GRBENER等[5]构建了城市中采用脚踏车、步行、公交车等多种方式快速到达目标地点的模型，设计了基于Dijkstra的改进Martins算法进行求解；J. ZHANG等[6]设计了考虑转运时间和成本的总成本最小化的可靠双目标优化模型，并结合遗传算法(genetic algorithm，GA)与模拟退火算法(simulated annealing, SA)对目标函数进行求解；姜金贵等[7]针对城市路径优化问题，采用随机选取节点并引入信息素更新策略，以广义代价作为目标函数，通过改进的蚁群优化算法求得连续解；谢楚楚等[8]研究了引入环境成本，以客户满意度与时间窗为约束条件的多式联运优化模型，并利用符合节点时间及提升客户满意度的NGSA-Ⅱ算法进行求解；于雪峤等[9]仅考虑了公路与铁路两种运输方式，将用户满意度和时间窗约束条件引入，基于机会约束规划方法对模型进行求解；万杰等[10]将运输费用和服务质量引入多式联运路径优化多目标模型，采用遗传算法进行目标求解；万杰等[11]将运输成本、运输时间和物流服务质量引入多目标多式联运路径选择模型，采用混合算法进行目标求解。

从上述研究来看，各文献运输成本考虑不一，目标函数的构建需求、路径优化模型及仿真数据也不尽相同。但总体来看，模型的求解多采用启发式算法，例如蚁群优化算法[7]和遗传算法[1,6,10]等。多式联运成本因素不仅考虑了运输费用和中转费用，而且将运输途中的碳排放绿色成本和到达目的城市的时间窗成本也考虑在内，笔者提出了一种基于鲸鱼优化算法的多式联运路径选择模型。仿真实验结果表明：提出的路径优化模型在考虑多因素成本的同时能够满足运输成本最小化，鲸鱼优化算法在求解最优路径方面也具有较好的全局寻优能力和较快的收敛特性。

1 多式联运路径选择问题的描述

1.1 模型假设

假设一批货物从始发城市A运输到目的城市B,途中可选择m个节点城市作为中转，并且两个节点城市之间可以通过两种及以上的运输方式进行转换。其中，运输方式包括公路、水运、铁路、空运等。运输过程中，城市节点之间会产生运输成本、碳排放成本、城市节点运输方式转换的转运成本和到达目的城市非时间窗成本。可见，为完成运输任务，选择不同的运输路线和方式组合会产生不同的运输成本，目标是求解最佳运输方式和路线组合。考虑到案例研究更加反映真实场景，笔者做出如下假设[11]：①一次运输任务中，城市起点和终点明确，整体运量不变；②各运输方式的运行速度为平均运输速度，中转时间在各城市节点明确；③运输成本中的转运费用在每个城市节点计算明确，碳排放成本仅考虑运输过程中；④运输中到达任何城市节点都可以选择可变的运输方式，并且只能改变1次；⑤运输和中转的载运能力充足；⑥货物到达目的地的时间不在时间窗内，将产生储存费用和惩罚费用。

1.2 模型构建

对于以上模型假设，建立如下3个目标函数:

glmax(sD-TL,0)

(1)

式(1)表示运输过程中的成本目标函数，其中包括所有运输方式产生的运输成本、城市节点之间进行运输方式转换时的转运成本，以及到达终点非时间窗延期到达或提前到达时支付的时间惩罚成本。

(2)

式(2)表示货物运输过程中产生的碳排放成本最小目标函数。

(3)

式(3)表示货物运输任务到达目的城市B所耗费的最短时间目标函数。其中，利用式(4)计算，表示货物到达各转运城市节点的总等待时间，各转运城市节点的等待时间等于该待转运方式最近的出发时间减去到达此城市节点时间，然后加上在此城市节点进行运输方式转换所花费的时间。

(4)

式中：n为城市节点，n∈{0,1,…,C}；w为总等待时间；q为由城市节点i+1转运方式m班次间隔时间；f为城市节点i到i+1转运方式m最近的出发时间，避免在转运节点错过最近的班次造成时间浪费，定义式(5)作为约束条件。

(5)

为保证时间连续性，si+1用式(6)计算，表示到达下一个城市节点的运输时间等于上一个节点运输时间加上转运时间和等待时间。

(∀i,m,l)

(6)

用式(7)表示两个运输城市节点之间有且只有一种运输方式。

(7)

式(8)表示在某个城市节点只允许一次运输方式转换。

(8)

式(9)表示当前节点与后续节点运输方式的连续性。

(9)

式(10)表示整个货物运输过程中时间的连续性。

(10)

为限制运输方式要进行转换时只能在相应备选集中选取，定义式(11)作为约束条件。

(11)

上述式(1)～式(11)中的模型符号说明如表1。

表1 模型符号说明Table 1 Model symbol description

2 鲸鱼优化算法

2016年，澳大利亚学者S.MIRJALILI提出了一种鲸鱼优化算法(the whale optimization algorithm, WOA)[12-13]，WOA属于一种通过模拟座头鲸狩猎行为的新型群体智能算法,其搜索过程是对座头鲸的泡泡网捕食策略进行数学建模[14]，主要包括了3个过程的数学结构，即目标包围、泡泡网攻击和目标搜索。

2.1 目标包围

在WOA模型中，将一个猎物坐标作为当前的最佳解决法案，在这一次迭代搜索完成之后，搜索代理会根据更新的最佳搜索代理完成位置的更新，并进行下一次的迭代，整个过程为：

(12)

(13)

(14)

(15)

2.2 泡泡网攻击

在WOA模型中，模拟座头鲸泡泡网攻击的步骤包括收缩包围和螺旋更新位置两部分：

2)螺旋更新位置的步骤是：先计算当前鲸鱼位置和最佳鲸鱼位置的距离，然后在这个距离之间建立螺旋方程，如式(16)；然后，鲸鱼延着螺旋路线到达最佳鲸鱼位置，即猎物位置。

(16)

为模拟收缩包围和螺旋更新位置的过程模型，笔者设置了鲸鱼更新位置的概率阈值为0.5，如式(17)。其中，p表示概率，在[0，1]中随机取值。

(17)

2.3 目标搜索

与基于更新当前最佳鲸鱼位置的包围机制不同，模拟鲸鱼搜索猎物的更新是通过随机搜索代理实现的，数学模型可表示为式(18)和式(19)：

(18)

(19)

3 基于鲸鱼优化算法的多式联运路径选择模型

鲸鱼优化算法是一种新提出的元启发式优化算法，已在车间调度、图像分割等应用领域有成功案例，与其它启发式算法相比，鲸鱼优化算法具有结构简单、参数少、搜索能力强、易于实现等优点。笔者将鲸鱼优化算法和Pareto求解多目标最优理论方法相结合引入到多目标多式联运路径选择问题中，仿真实验显示该算法在求解路径选择方面具有较好的全局寻优能力和较快的收敛特性。

3.1 路径选择算法

在算法初始化阶段，结合多式联运仿真模型中城市节点数据要求，采用随机生成节点的方式对各城市节点进行排序，同时对鲸鱼优化算法的初始化数据进行取整处理，基于节点随机排列的初始解矩阵X为：

矩阵中共有k行记录,对应k条路径选择;其中,每行数据的前n个元素代表n个城市节点，后n-1个元素对应了每两个城市之间所选择的运输方式。

基于鲸鱼优化算法的多式联运多目标路径选择模型计算步骤如下：

步骤1导入多式联运网络基础数据，随机初始化生成鲸鱼路线Xi，其中i=1,2,…,k。

步骤2如果当前迭代次数≤最大迭代次数,则继续步骤3～步骤5,否则输出当前最优路线。

步骤5当p≥0.5时,利用式(16)更新当前路线Xi。

步骤6更新当前路线,当迭代次数达到最大时，输出结果最优路线。

3.2 多目标优化Pareto适应度计算

Pareto是求解多目标最优理论方法[15]，上述算法步骤3中需选择Pareto适应度最小的线路。在多式联运过程中不同的运输路线和方式组合会产生不同的运输成本、碳排放成本和时间成本，每个运输方式和路径组合都对应了Pareto适应度值，求解最佳运输方式和路径组合的问题演变成求Pareto适应度最小的过程。文中多式联运路径选择的多目标优化问题用式(20)表示为：

minY=[Y1(x)+Y2(x)+Y3(x)]

(20)

式中：Yk(x)为Y的第k个分目标，文中涉及3个目标函数，Y是x在模型中的目标值。若x使得任意一个目标函数不再减小，则x为Pareto最优解。求Pareto适应度具体包括4个步骤，可参考文献[16]。

4 案例计算与分析

4.1 案例场景

假定某次货物运输任务需要将600台家电从青岛运输到广州，每台家电重量约为50 kg，总运输重量为30 t。设置货物计划到达目的地广州的运输时间控制在38～40 h区间，若运输时间超过40 h，则按单位每吨每小时惩罚费用1 000元计算；若运输时间小于38 h，则按单位每吨每小时储存费用500元计算。表2是各种运输方式的单位费用，表3给出了3种运输方式碳排放的单位成本。

根据此次运输任务路程的实际情况，在国内选择了青岛、上海、武汉、南京、济南、杭州、合肥、福州、南昌、郑州、长沙、南宁、广州等13个城市组成运输网络，城市之间公路、铁路、水路运输的里程分别如表4～表6。

表2 运输方式费用Table 2 Transportation mode cost 元/km

表3 运输方式碳排放Table 3 Carbon emissions of transportation mode 元/(t·km)

表4 各城市节点之间公路运输距离Table 4 Highway transportation distance between nodes in each city km

表5 各城市节点之间铁路运输距离Table 5 Railway transportation distance between nodes in each city km

表6 各城市节点之间海路运输距离Table 6 Sea transportation distance between nodes in each city km

4.2 运行结果与分析

算法模型利用MATLAB软件仿真实现，运行环境为CPU Intel Core i7-6700 3.4 GHz，内存16 G，Win10 64位操作系统。分别使用遗传算法和文中鲸鱼优化算法进行比较验证，遗传算法初始设置种群规模和算法初始设置随机矩阵k值均为20，最大迭代值50。图1表示两种算法的运输费用迭代对比，图2表示两种算法的碳排放迭代对比，图3表示了两种算法的运输时间迭代对比。从结果对比图2～图4中可以看出，遗传算法(GA)模型迭代2次后运输费用达到约2.1万元左右稳定值，迭代5次后碳排放达到490 kg稳定值，迭代2次后运输时间达到38 h稳定值；而文中鲸鱼优化算法(WOA)模型迭代8次后运输费用达到约1.8万元左右稳定值，迭代2次后碳排放达到490 kg稳定值，迭代3次后运输时间达到36 h稳定值。与遗传算法相比，笔者基于鲸鱼优化算法求解多目标多式联运问题可以较快获得更为合理的寻优结果，具有更好的寻优能力和收敛特性。

图1 运输费用迭代Fig. 1 Iterative diagram of transportation costs

图2 碳排放迭代Fig. 2 Iteration of carbon emissions

图3 运输时间迭代Fig. 3 Iterative diagram of transportation time

图4路线方案Pareto适应度值，最大适应度约1.187，最小适应度约0.190 7。

表7显示了模型运算求解得出的6条推荐路线方案，用户可结合实际情况从推荐路线中选择最佳运输方案。例如，方案1的Pareto适应度最低，表明该方案的运输费用、碳排放和运输时间综合因素最佳；方案6总成本最少，但用时最多。两种方案在成本和时间上各占优势，从适应度来看比较符合运输实际，充分体现文中鲸鱼优化算法迭代寻优的优势，证明了其可行性和有效性。

表7 运算结果Table 7 Operation results

图4 路线方案Pareto适应度Fig. 4 Pareto adaptability of route plan

5 结 语

多式联运是目前物流行业提高运输效率，符合企业多目标运输要求的最有效方法。综合考虑运输成本、环保和时限要求，引入鲸鱼优化算法和多目标适应度算法，仿真验证了多式联运的路径选择问题的可行性和有效性。从目前研究文献来看，多位学者对鲸鱼算法的优化策略进行了改进，研究团队也针对该问题进行了相关研究，并取得了相关成果。下一步将利用提出的新鲸鱼算法优化策略对多式联运场景进行深入应用研究，达到提升更加有效的目的。另外，未来将考虑引入国际物流实验数据，提升国际多式联运效率。