基于海鸥优化算法的企业平衡运输问题研究

邵良杉，闻爽爽＊

1.辽宁工程技术大学，管理科学与工程研究院，辽宁 葫芦岛 125105

2.辽宁工程技术大学，工商管理学院，辽宁 葫芦岛 125105

引 言

2006年3 月通过的《国民经济和社会发展第十一个五年规划纲要》中，将“大力发展现代物流业”作为单独小节列出，至此物流逐渐成为经济研究中的热议话题。作为物流的核心过程，运输掌握着整个物流系统的“命脉”，运输成本的高低关系着整个物流系统运营的优劣。运输活动不能创造实物产品，只会提供运输劳动，使待运输物资发生位移。身处快速发展的社会中，随着制造业、服务业的不断发展和人们逐步提升的生活水平，出现了一种区位关系——即资源、产地和市场，由此造成运输成本在经济发展中的作用日渐明朗。因此，降低运输成本、优化产销配置、合理规划路线，将对整个物流系统产生巨大的影响。

目前运输问题的发展趋势主要分为：传统运输问题、B 运输问题、D 运输问题以及JIT 运输问题。传统运输问题包括两类，即企业产销平衡问题和企业产销不平衡问题。在产销平衡问题的运价表中一般将不可能的运输方案设为任意大的正数，而对于产销不平衡问题通常采取虚拟假设产地或销地的办法将其转化为产销平衡问题。本研究主要讨论传统运输问题中的企业产销平衡问题。

运输问题的几大特点主要为：（1）多产地与多销地；（2）产销两地的产额不同——每个产地的产量不同，每个销地的销量也不同；（3）每种产销组合之间的运价都不同；（4）在满足供需的条件下如何组织调运，选出最佳调运方案使总运费最小。

针对运输问题的特点，以往解决运输问题的方法通常包括：线性规划法、表上作业法、图上作业法、网络解法。传统算法的时间复杂度和空间复杂度会随着数据维度的不断增加而升高，使问题求解变得不易，耗时费力，故针对大型复杂运输问题，目前主要采用如机器学习、神经网络优化算法、人工群峰算法、遗传算法、邻域搜索算法、混沌优化算法等一系列智能优化算法来求解[1-5]。Sharma 等通过启发式算法成功求解了经典运输问题并得到一个良好的初始化解[6]； Adlakha 等提出了一种简单的启发式算法来解决成本固定的运输问题，但其求解时间更久[7]；Lotfi 等[8]通过优先级编码的遗传算法解决运输问题，在与结合最小生成树的遗传算法求解质量对比后，证明了其效率；Molla-Alizadeh-Zavardehi等对比了三种优化算法求解可变参数的运输问题[9]；Kenan 等在2019年建立了Karagul-Sahin 近似方法，使运输问题的求解时间相较于之前算法下降[10]。早期研究除了会带来人工运筹学计算的误差、经验判断等缺陷外，还包括神经网络的大量数据需求、遗传算法的交叉变异过程、易陷入局部最优等计算机算法的工作问题。

海鸥优化算法（Seagull Optimization Algorithm，SOA）是Dhiman 等[11]于2019年最新提出的新型元启发式优化算法，该算法的原理是模拟海鸥在迁徙过程中通过自身位置的不断变化，朝着最佳位置的方向前进所表现出的较强全局搜索能力，以及海鸥在攻击猎物过程中通过不断改变角度和速度产生螺旋运动形状所具有的较强局部搜索能力优化目标函数，该算法的发明初衷即解决大规模工程约束问题。故针对运输问题的特点以及早期研究的缺陷，本研究基于海鸥优化算法来解决企业平衡运输成本最小化问题，同时为煤矿行业运输调度系统管理提供智能解算工具，后续可推广至各个行业的运输问题求解中。

1 问题模型

1.1 问题描述

物资的运输调度问题一直是运输问题研究的重点，其具体文字表述如下：某种物料有多个生产地点和销售地点，根据每个销售地点的需求和生产地点的产量，该种物料需要运送到相应的销售地点，且为了不浪费资源，总产量必须等于总销量，在了解各生产厂家的产量和各销售厂家的销售量以及各生产区到各销售区的单位运输价格（或运距）后，问如何分配货物的运输量和运输路线，使总运输成本（或总运输量）最小，效益最大化[12-14]？

1.2 运输问题数学模型

1.2.1 传统运输问题模型

典型的运输问题数学模型：设某种产品有m个产地Ai（i=1,2,…,m），有n 个销地Bj（j=1,2,…,n），将X 设为从产地Ai运往销地Bj的物资量，从Ai运出的总运量应等于Ai的产量ai，销地Bj的销量等于bj，Cij是对应产地与销地之间的费用，因此Xij应满足：

所以，总费用为：

运费问题的数学模型如下：

其中，约束条件为：

通常情况下，对于实际问题，不会始终满足产销平衡条件，所以常用以下2种方法将不满足产销平衡条件的运输问题转化为符合产销平衡条件的产销平衡运输问题，其数学模型如下：

1.2.2 B 运输问题数学模型

B 运输问题是基于传统运输问题在考虑节约资源、紧急情况约束条件下的特殊运输问题，在传统运输问题上引入了时间，B 运输问题的数学模型：

1.2.3 D 运输问题数学模型

随着社会的进步，网络的发展，一些及时供应商品如保鲜产品、节日物资等要在给定时间之前送达，故D 运输问题应运而生，在B 运输问题基础上，给定一个预警时间t0，D 运输问题数学模型[15]：

则满足t0的数学模型为：

1.2.4 JIT 运输问题数学模型

随着丰田生产方式的发展，一种零库存的JIT（Just In Time）运输问题被广泛用于多产地、多物资、多销地的运输问题中，在此种模式下，引入了更多的约束条件，包括m个产地不止生产一种物资，而是可以生产ω1，ω2，…，ωk等k种物资，物资ω1从Ai运到Bj所需时间为tijl，运价为Cijl，Xijl表示运量，JIT 运输问题模型：

综上所述，运输问题经历了由传统运输问题——B 运输问题——D 运输问题——JIT 运输问题，其中D 运输问题是特殊的JIT 运输问题，即当时，也就是只有一种物资的JIT 问题；而B 运输问题就是将预警时间设为0 的D 运输问题的特殊情况；传统运输问题同理是时的特殊B 运输问题。

故本文通过研究传统运输问题，便能推导出B运输问题——D 运输问题——JIT 运输问题等后续延伸出的运输问题的求解过程。

2 SOA 算法介绍

2.1 SOA 生物学范式

海鸥，学名为落叶松科（拉丁学名：Larus canus），是一种海鸟，一般情况下，喜群居生活。海鸥是非常聪明的鸟，他们可以通过团队协作顺利找到并攻击猎物。迁移和攻击行为是海鸥最显著的特性，其中迁移被定义为为了生存，海鸥从一个地方到另一个地方的季节性移动，在迁移的同时，它们通过攻击海上的候鸟，从而达到捕食的目的。在攻击行为中，海鸥表现的最明显特征就是做出自然的螺旋形运动，概念模型如图1所示，使其与目标函数相关联，便可以完成一系列优化过程[16]。后续内容主要通过研究海鸥的迁移和攻击两种自然行为过程，使其与约束条件及目标函数相关联，进而求解企业平衡运输问题[17-22]。

图1 海鸥的迁徙和攻击行为示意图Fig.1 Schematic diagram of seagull migration and attack behavior

2.2 SOA 数学模型

2.2.1 迁移（全局搜索）

海鸥优化算法的迁移过程就是该算法的全局搜索过程，主要通过模拟海鸥迁移过程中海鸥群的位置移动。在全局搜索阶段，每只海鸥个体必须符合以下三个条件：

（1）避免相互接触

为了避免与其他海鸥之间相互接触，通过引入变量A来计算海鸥的新位置（图2(a)）。

其中：fc是根据题目设置的用来控制变量A的频率的常数，变量A从fc线性减小到0。在本次运算中，fc的值被设置为2。

（2）向最适合的海鸥方向移动

在避免了海鸥之间的相互接触后，海鸥朝着最适合的海鸥方向移动（图2(b)）。

式中：rd∈[0,1]。

靠近最适合的海鸥位置：海鸥移动到不与其他海鸥相撞的位置后，就向着最适合的位置所在方向进行移动，最终到达新位置。

（3）保持接近最佳海鸥位置

最后，海鸥可以更新其相对于最佳海鸥的位置，如图2(c)所示。

图2 海鸥迁徙行为和攻击行为示意图Fig.2 Schematic diagram of seagull migration and attack behavior

2.2.2 攻击（局部搜索）

海鸥优化算法的攻击过程就是该算法的局部搜索过程。海鸥的自重和翅膀煽动可以使其在迁移过程中维持平衡，且可以不断改变攻击角度和速度。在攻击猎物时，通过变换螺旋队形，进行捕食（见图2（d））。此行为在x、y、z平面中的描述公式如下：

式中：r是螺旋线每一圈的半径，k是 [0-2π]范围内的随机数。u和v是定义螺旋形状的相关系数，e是自然对数的基。使用公式（18）-（22）计算海鸥的更新位置。

完整的海鸥优化算法步骤如下：

SOA 算法从随机生成的总体开始，在迭代过程中，搜索代理（海鸥）可以更新其相对于最佳搜索代理（最佳海鸥）的位置。变量A从fc线性减小到0，变量B负责实现迁移和攻击之间的平稳过渡。海鸥优化算法具有极好的探索和开发能力，兼具全局搜索、局部搜索的先天优势，故SOA 被认为是一个全局优化器。

2.3 算法测试分析及超参数确定

本研究通过10 个基准测试函数对3 个不同的群智能优化算法进行对比分析，如表1所示。其中f1、f2、f3、f4、f5是检验算法全局探索能力的多峰函数；f6、f7、f8、f9、f10为评估算法寻优精度以及收敛速度的单峰函数。

表1 本文选用的10 个测试函数Table 1 Ten test functions selected in this paper

将SOA 算法与标准PSO、GA 算法对比实验，从而验证SOA 算法性能。函数变量维数D=30,种群规模N=100。实验结果统计30 次运行的最优解均值（Mean）和标准差（Std.Dev），具体实验结果见表2。

从表2可以看出，本文所采用的SOA 算法在8个测试函数上具有较明显的优势，在f3上的结果虽不具明显优势，其标准差略高于PSO、GA 算法，但其平均值仍优于PSO、GA 算法，在f10上的测试效果一般。总体看来海鸥优化算法相比于粒子群算法、遗传算法更具优势。因此可以说明本文采用的SOA算法有较高的寻优能力。此外，由10 个对比函数可以看出本文采用的SOA 算法比标准PSO、GA 的寻优结果都好，尤其对于f2、f4来说，SOA 的收敛速度提高，因此，本文的SOA 算法求解问题具备更好的性能。

表2 各算法的优化结果（D=30,N=100）Table 2 Optimization results of each algorithm (D=30,N=100)

元启发式算法在实际应用中的超参数调整被作为主要挑战，不同的超参数值可能会产生不同的结果，故SOA 算法的参数设置有必要做如下讨论：正如现有文献所阐述的SOA 超参数设置，SOA 算法包含三个超参数，即最大迭代次数、搜索代理数和参数fc，本研究根据现有文献设置标准设置相关参数。

（1）最大迭代次数：SOA 算法在不同的迭代次数下运行。实验中[11]使用的Maxitemeration的值为100、500、800 和1000。结果揭示了当迭代次数增加时，SOA 会收敛到最佳状态，故本研究取1000。

（2）搜索代理数：为了研究搜索代理数对测试函数的影响，分别对50、80、100 和200 执行SOA算法。研究发现，当搜索代理数量设置为100 时，SOA 提供了最佳的解决方案。

（3）参数fc的变化：SOA 算法是针对参数fc的不同值而运行的，保持其他参数不变，即最大迭代次数和搜索代理数。取不同的fc值，分别为为1、2、3、4 和5。结果表明，当fc的值设为2 时，目标函数获得最优解。

故根据原始参考文献[11]，以及现有有关于海鸥优化算法的文献[23-27]对于海鸥优化算法超参数的测试、选取，本研究在仿真时，令最大迭代次数=1000，搜索代理数=100，fc=2。

3 应用实例

3.1 数据描述

为了验证应用的SOA 算法可以有效解决企业平衡运输问题，通过以下实例说明。

某饮料在国内有三个生产厂家，地处城市 A1，A2，A3，其一级承销商有四个，地处城市B1，B2，B3，B4，已知各生产厂家的产量、各承销商的销售量以及从产地 Ai到销地 Bj的每吨饮料的运费Cij，为响应绿色供应链的要求，公司要求统筹产销问题，其运价表如表3所示，求运费最小的调运方案？（为了更好地与管理运筹学方法、量子粒子群算法、遗传算法相比较，表中数据均来自文献[28-30]。）

表3 运价表Table 3 Tariff table

3.2 结果验证

由于该案例不涉及时间约束、重大紧急事件等约束，便不需要额外参数，故采用传统运输问题模型。

该运输问题的数学模型如下：

（1）决策变量

设从产地Ai到销地Bj的运量为Xij；

（2）目标函数

运费最小的目标函数为：

（3）约束条件

即产量之和等于销量之和，故要同时满足供应、销售平衡条件。

供应平衡条件：

X11+X12+X13+X14=5

X21+X22+X23+X24=2

X31+X32+X33+X34=3

销售平衡条件：

X11+X21+X31=2

X12+X22+X32=3

X13+X23+X33=1

X14+X24+X34=4

因为运量不能为负，所以运量都要满足以下非负性约束条件：

通过对饮料厂采用SOA 算法求解，应用Matlab对案例企业途中运输成本最小化进行软件求解运算后，得到的最优解如表4所示。

表4 最优解Table 4 Optimal solution

由表中数据可知，该运输问题最佳调运方案的成本为34，即3×2+2×1+5×2+4×2+3×2+2×1=34。通过SOA 算法得到的最优解与传统管理运筹学方法、量子粒子群算法、遗传算法的最优解相吻合，都是34，确实验证了海鸥优化算法可以解决企业平衡运输成本最小化问题。

SOA 算法参数设置简单，兼具全局搜索和局部搜索能力，不需要交叉、变异等步骤，提高了智能优化算法求解运输问题的工作效率，与传统求解成本最小化的方法相比，避免了管理运筹学求解时的人为失误、有较强的可操作性。将该算法应用在物流运输成本问题的成本最小化中，具有较好的适应性。

对于本研究以外涉及的B 运输问题、D 运输问题、JIT 运输问题与本研究方法同理操作，只需在运算时多加入对应的约束条件即可，操作较简单，这里不再赘述。

4 结论

（1）采用了国外最新元启发式算法——海鸥优化算法求解企业平衡运输问题，为今后的企业平衡运输问题求解提供了一种新的元启发式智能优化算法。

（2）海鸥优化算法作为新兴的启发式智能优化算法，在企业传统平衡运输问题中的成功应用，开拓了B 运输问题、D 运输问题、JIT 运输问题等多约束问题的解算思路，对智能时代煤矿运输调度系统管理显得尤为重要，将为煤矿行业运输调度提供参考方法，可持续推广至各行业的成本问题求解中。

（3）仿真结果只是验证了小规模的企业平衡运输成本问题，对于大规模的实际案例还需进一步推广研究。在未来的研究中，可以开发并行海鸥优化算法来自动检测可用处理器的数量并在其中分配工作负载，从而实现对可用资源的有效利用；OpenMP库可用于提高当前海鸥优化算法的性能和效率；还可以开发SOA 算法的二进制和多目标版本来解决大规模的实际工程问题。

利益冲突声明

所有作者声明不存在利益冲突关系。