改进野马算法求解低碳开放式送取货选址路径问题

虎翼飞，张惠珍，陈曦

改进野马算法求解低碳开放式送取货选址路径问题

虎翼飞，张惠珍*，陈曦

（上海理工大学 管理学院，上海 200093）

针对当前物流背景下普遍出现的送货公司外包、退换货频繁等问题，结合现有的碳排放政策，提出低碳背景下开放式同时送取货选址−路径模型（Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem，LOLRPSPD），并通过改进野马算法进行求解。首先设计一种新的解码方式，使得原离散问题可以采用连续算法求解。之后，运用哈尔顿序列生成初始解，改进非线性进化概率因子，使用模拟二进制交叉，增加变异操作，以及精英保留、设置连续失败重新初始化等步骤，改进野马算法。最后，通过6组不同大小的算例将改进野马算法与原始野马算法、模拟退火算法、粒子群算法、遗传算法进行对比。针对中大型算例，改进野马算法远超原始野马算法。针对小型算例，在确保准确率的同时，改进野马算法对比各经典算法也在速度上具有优势。提出的LOLRPSD模型具备合理性，改进的野马算法针对选址路径问题具有较好的搜索能力。

选址路径问题；开放式问题；同时送取货；改进野马算法；元启发式算法

选址路径问题（Location-routing Problem, LRP）是一类经典的组合优化问题，需要同时将设施点的选址及车辆路线的选择纳入决策。中国作为人口大国，物流行业规模庞大，且发展迅速。相对而言，我国在物流研究方面仍较落后，大多企业只能依靠经验来制定物流标准，使得物流服务缺乏创新。随着互联网的普及，更多中老年群体开始使用手机购物，使得快递名目更繁杂，且退换货的比例加大。将开放式与同时送取货组合对增强企业竞争优势、减少社会不必要浪费具有显著意义。

Cooper[1]首次将设施选址问题与车辆路径问题结合起来，提出了LRP。将标准LRP与实际情况结合后，可以形成多种扩展LRP，如有容量限制的LRP（Capacitated LRP, CLRP）、带车容量限制的选址路径问题（Capacitated Location-Routing Problem，CLRP）、开放式选址路径问题（Open Location-routing Problem，OLRP）、同时送取货选址路径问题（Location-Routing Problem with Simultaneous Pickup and Delivery，LRPSPD）等。已有大量学者对LRP及其扩展问题进行了研究。Karaoglan等[2-4]根据实际运输网络中同时送取货的需要，提出了同时送取货选址路径问题（Location Routing Problem with Simultaneous Pickup and Delivery，LRPSPD），并分别使用混合遗传算法、分支定界法、启发式算法进行求解。Wang[5]提出了具有多种服务模式和模糊时间窗的 LRPSPD ，使用禁忌搜索算法进行求解验证，作为单起点式算法，其求解速度相对较慢，未发挥启发式算法的优势。刘亚平等[6]在同时送取货的基础上，考虑了客户时间窗，建立了LRPSPDTW模型，并用改进的烟花算法求解。通过与B&C（Branch and Cut algorithm）获得的最优解进行比较，取得了不错的成果，但在大规模算例中缺少与其他启发式算法的对比实验。刘东等[7]在同时送取货的基础上，考虑了开放式，即车辆配送后不返回仓库，提出了OLRPSPD（Open Location-routing Problem with Simultaneous Pickup and Delivery Problem）模型，进一步增大了现实意义。还改进了蘑菇算法，相较于模拟退火算法、蚁群算法、混合免疫算法等经典启发式算法，此改进方法在中型算例中具有明显的优势。

随着多项节能减排政策的实施和中国碳排放权交易市场的建立，物流活动中的碳排放成为一个亟待解决的关键问题。为此，国内外学者们通过在LRP中加入低碳要素，通过构建低碳模型来减少碳排放量。Barth等[8]考虑了车辆的速度和装载量对车辆油耗的关系，建立了货车燃油消耗模型。Zhang等[9]考虑了行驶距离、汽车行驶速度、车辆装载量等，假设燃油消耗随着车辆的载质量呈等比例增加，提出了燃油消耗模型。由于在LRP中很难具体描述车辆的速度和加速度，故Xiao等[10]假设车辆匀速行驶，只考虑载质量和行驶距离对车辆燃油排放的影响。文中在OLRPSPD模型的基础上加入油耗计算公式，建立LOLRPSPD（Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem）模型。

野马优化算法（Wild Horse Optimizer，WHO）是Naruei等[11]在2021年提出的一种智能优化算法，该算法的灵感来自野马的放牧、交配和群体领导行为。通过模拟野马放牧过程中马驹在领头马周围游荡和不同马驹群体间交配的特点，将领头马和马驹群体位置的变化过程作为算法的优化过程。WHO具有参数少、寻优能力强、时间复杂度低等优点。该算法仍然存在种群初始化阶段种群多样性差、全局搜索能力弱、后期难以脱离局部最优等问题。针对基本WHO的不足，文中提出一种混合多策略改进野马优化算法（Improved Wild Horse Optimizer，IWHO），并将其运用于LCLRPSPD问题。

1 低碳开放式送取货选址路径问题

1.1 碳排放成本

基于模型的复杂性，以及在实际情况中难以预测车辆的情况，这里依照Xiao等[10]的方法将车辆的行驶速度设为匀速，仅考虑车辆的负载和行驶路程。考虑到车辆在行驶过程中的油耗与负载近似呈线性关系[12-13]，将其表示为式（1）。

式中：为单位碳排放价格；μ为燃油转换碳排放系数；d为两点之间的距离。

1.2 符号说明

1.3 模型建立

总成本最小值的计算见式（3），包括设施点开放成本、运输成本、车辆启用成本和碳排放成本。碳排放的计算见式（4）。式（5）表示每个需求点被访问有且仅有1次。式（6）表示进入节点的流等于流出节点的流。式（7）表示每辆车只能行驶1次。式（8）表示每个需求点都有唯一指定的设施点为其服务。式（9）表示消除子回路。式（10）和（11）分别表示送取货不超过设施点容量限制。式（12）表示车辆装卸平衡约束。式（13）表示车辆不能超载。式（14）表示车辆运送完成后不返回设施点。式（15）～（17）为决策变量取值范围。

s.t.

上述模型中，各点位置集合、建设费用、容量及启用成本已知，车辆启用成本及最大负荷已知，运输成本已知。送取货需求量和碳排放相关系数由后文拟定。车辆实时载重可由送取货需求计算得到。为计算过程中的罚成本，用以筛除不符合约束的路线。

2 野马算法

2.1 基本野马算法

之后，种马带领种群前往合适的水洼，但若该水洼已被另一个种群占领，则后来的种马只能找寻其他水洼。具体计算见式（21）。

再后，当种马适应度被其他成员超越时，则执行种马交换，见式（22）。

2.2 编码及解码方式

采用实数编码方式，每个基因的取值为0～1内的实数。重要的是解码方式，在计算适应度前解码。解码方式如图1所示，给定具有可选设施点5个、需求点20个、备选车辆7辆的LRP，其染色体维度为5+7+20=32。

2）之后的7个基因代表备选车辆，分别乘以可建设设施点的数目2（从步骤1得出），并向上取整，得到备选车辆所服务设施点的编号。需要说明的是，这里求出的编号2代表建设的第2个设施点，即5，编号1表示4，如图2所示。

3）剩余的20个基因代表需求点，用于计算需求点所选择的车辆及运输顺序。同理，将其乘以备选车辆数量7，并向上取整，得到每个需求点所选车辆编号。若此步骤未出现某辆候选车辆编号，则此车辆停止使用。之后分别按基因排序，可得车辆服务需求点的顺序。以第2辆车为例，共有编号5、9、10、11需要2号车服务，如图3所示。

通过此种编码方式，仓库开放与否、客户点服务顺序及归属清晰可见。另外，此编码考虑了实际情况中车辆运输能力的差异性，更加符合数学模型和实际情况。

2.3 改进野马算法

这里详细介绍改进野马算法（IWHO）的改进策略。为了增强基本算法的全局搜索能力、提升初始化种群多样性，改善后期难以逃脱局部最优等问题，进行了多次实验。这里改进了6种方法，包括引入哈尔顿序列生成初始种群、非线性进化参数、模拟二进制交叉、多项式变异、精英保留策略、多次失败后个体重新初始化。

图1 完整染色体实例

图2 备选车辆基因选择设施点流程

图3 需求点基因解码逻辑

2.3.1 初始种群的生成

算法的种群初始化阶段会极大地影响算法的后期处理。基本的WHO是先根据种群数量选择等量种马，再在其他所有马驹里随机选择个体跟随指定的种马行动。这样会导致前期种群的混乱。例如，存在一个较好的马驹个体，在周围有优秀种马的情况下，因过分随机而被分配给遥远的种马，使得该马驹在迭代初期并未向有利个体靠近。在多次重复实验过程中发现，针对LRP，基本WHO算法这种对于前期种群过于“混乱”的处理方式，对整体迭代有着不良影响。Halton序列是一种更接近于均匀分配的伪随机。经大量反复实验后可以得出结论，针对LRP引入Halton序列，可以降低算法开局迭代中的种群混乱程度，加快全局搜索。

2.3.2 非线性进化概率因子

在原始算法中，放牧行为的进化概率参数（DR）按迭代次数线性递减，见式（23）。

式中：iter为当前迭代次数；iterations为总迭代次数。

2.3.3 模拟二进制交叉算子

为自定义参数，越大，则产生的后代逼近父代个体的概率越大。SBX算子在使用实数编码的进化算法中，针对局部搜索的表现优越，且处理高维目标优化问题时对于个体空间稀疏性的效果良好，十分适用于LRP。

2.3.4 多项式变异算子

在原算法交叉环节后加入变异操作，即使用多项式变异（Polynomial Mutation Operator，PMO）算子对当前解施加扰动，并以一定概率接受劣化解，且接受劣化解的概率随时间的推移而降低。一方面，可以在算法前期维持解的多样性，以加强全局搜索能力。另一方面，可以使算法后期变异产生的新解逐渐逼近当前解，提升局部随机搜索能力。多项式变异算子形式见式（27）～（28）。

2.3.5 精英保留策略

为了避免交叉及变异步骤丢失父代种群中的精英个体，采取精英保留策略存储运算过程中的精英个体。精英个体是种群进化中搜索到的具有最优适应度的个体，它包含目前最好的基因数据。精英保留策略的核心思想是把种群进化过程中出现的精英个体复制到下一代中。在变异后进行精英保留操作，通过合并交叉和变异的种群，并与原种群对比，选择最优的保留下来，有效地提高了算法的收敛能力。

2.3.6 连续失败重新初始化

原始野马算法极易陷入局部最优，为了改善这种情况，在算法中设定最大失败统计数fail（设定为迭代次数的1/10）。当算法连续运行fail都未找到更好的解时，说明局部收敛。此时对个体重新初始化，计算个体适应度，并进行迭代。经大量实验证明，该方法对防止算法过快陷入局部最优有效。

2.4 改进野马算法流程描述

改进野马算法（IWHO）求解低碳开放式送取货选址路径问题（LOLRPSPD）步骤如下。

1）初始化算法参数。包括种群规模、种马比例S、最大迭代次数、交配概率C等。

2）解码。计算种群个体适应度，通过哈尔顿序列初始化种群，并选取种马。

3）根据式（24）计算DR，根据式（18）～（19）进行放牧行为。

4）先根据式（20）进行交配行为，再根据式（25）～（26）进行二进制交叉，根据式（27）～（28）进行多项式变异，然后解码，并按精英保留策略将优秀个体保留。

5）根据式（21），种马选择新的水洼（目标区域）。

6）解码。更新种群适应度，若种群中存在适应度优于种马个体，则根据式（22）更换种马。

7）若连续失败，则重新初始化种群，转到步骤2）。

8）判断是否达到最大迭代次数，若是，终止循环，否则转到步骤3）。

9）满足算法终止条件，输出最优解。

2.5 时间复杂性分析

文中对野马算法的变动有6点。首先，在初始种群阶段引入Halton序列，替代原有随机序列，然后保持时间复杂度不变，仍为1()。在放牧阶段改进了进化概率参数DR，虽然增加了运算量，但未产生额外的循环，故时间复杂度仍为2()。交配阶段改变较大，改进了交叉方式，使用多项式交叉，又增加了多项式变异和精英保留策略。对于交叉与变异，依旧只增加运算量，未产生额外的循环。在精英保留步骤中，多使用了1个循环，影响较大，故改进后的交配阶段时间复杂度为3(2)。领导者阶段不变，时间复杂度仍为4()。最后新增连续失败重新初始化阶段，时间复杂度应为5()。故改进野马算法的时间复杂度(2)=1()+2()3(2)4()+5()。

3 算例分析

表1 算例数据

Tab.1 Example data

3.1 算法参数设置

为了得到优秀的参数组合，分别对算例1和算例3进行了分析。通过比较每个算例最优目标函数值和平均运行时间，对种群规模、种马数量和迭代次数进行了灵敏度分析。在研究其中1个参数的性能时，保持其他参数不变。表2～4分别为3种参数在6组不同取值情况下对2组不同算例的平均运行结果，黑体表示最优结果。对应的变化曲线如图4所示。不难看出，种群规模的改变对运行时间的影响不大，但当过大或过小时，IWHO很容易陷入局部最优，从而产生较差的平均目标值。种马数量的改变对运行时间的影响很大，运行时间随着种马数量的提升显著延长。在种马数量为36时，运行时间甚至超过种马数量为12时的8倍。对总成本的影响可以从折线图看出，算例1和算例3均在种马数量为12时存在明显的低谷，在结合了适当运行时间的情况下，这里选择种马数量12作为实验标准。迭代次数对解的影响最明显，在基本不影响运行时间的前提下，2组算例均在迭代次数为40时取到最优成本。综上所述，选取种群规模=60、种马数量=12、迭代次数40作为实验标准。

表2 种群规模对解的影响

Tab.2 Influence of population size on the solution

表3 种马数量对解的影响

Tab.3 Influence of the number of stallions on the solution

表4 迭代次数对解的影响

Tab.4 Influence of iteration times on the solution

图4 参数灵敏度分析

3.2 算法性能分析

为了检验IWHO算法的性能，针对以上6个算例进行求解，并与原始野马算法（WHO）、粒子群优化算法（Particle Swarm Optimization, PSO）、模拟退火算法（Simulated Annealing, SA）、遗传算法（Genetic Algorithm，GA）进行了对比。实验对每个算例求解20次，记录最优解及所用时间，求解结果如表5所示。

实验结果表明，针对中型（编号1～2）、大型（编号3～6）算例，文中所提改进野马算法相较于原始野马算法具有显著优势。从运行结果来看，由于LOLRPSPD问题的复杂性，原始野马算法在实验过程中极易过早陷入局部收敛，难以获得最优结果。IWHO在2组中型算例中都取得了已知最优解，说明改进后非线性进化概率因子及连续失败多次重新初始化步骤均取得了十分理想的结果。从运行稳定性来看，IWHO针对中型算例每次都能求得已知最优解，且迭代次数不多。原始野马算法不论在中型算例还是大型算例上的结果都难令人满意，在中型算例上，即使迭代20次都无法求得已知最优解，且结果平均偏差在15%以上。对比分析后不难得出，改进后运用Halton序列种群初始化配合多次失败重新初始化产生了良好效果。从运算速度来看，虽然IWHO每次迭代的时间约为原始WHO的3倍，但得出合适解的总时间更短。由于WHO在处理LOLRPSPD问题上总是过早收敛，很难统计有效时间，因此对于2组中型算例，这里在规定运行时间的前提下设置了合适的迭代次数。实验结果基本证明文中所提的二进制交叉算子SBX、多项式变异算子（PMO）及精英保留策略较大程度地改善了原始WHO的全局搜索能力，使得IWHO可以适应LRP。

与其他3个经典算法相比，遗传算法GA和粒子群算法PSO都较适合求解LOLRPSPD问题。这可能是因为算法本身的全局搜索能力较强，且收敛速度较慢。模拟退火算法SA与原始野马算法WHO一样，虽然局部搜索能力较强，但全局搜索能力较弱、收敛速度较快，不太适合求解LRP类问题。针对20个需求点的中型算例，改进野马算法IWHO对比PSO和GA在时间上具有优势。针对50个需求点的大型算例，IWHO可以一次求得已知最优解，但求解时间弱于GA。针对100个需求点的大型算例，IWHO会过早陷入局部最优，难以求出超过GA的结果，但胜过PSO。

从实验结果推断，求解LOLRPSPD问题更需要算法的广度，即全局搜索能力。虽然原始野马算法WHO拥有不错的局部搜索能力，但初始化种群不稳定、全局搜索能力弱、收敛快，不适合求解LOLRPSPD问题。文中提出的改进野马算法IWHO在保留原算法优势的同时，弥补了其劣势，处理小型LRP问题具有一定优势。

3.3 IWHO有效性评估

为了进一步验证IWHO在求解LRP上的有效性，这里用IWHO求解了6组标准CLRP数据库中的算例，将其求解结果与GRASP[15]、MAPW[16]和2phase-HGTS[17]的求解结果进行对比分析。其中，Best是算例已知最优解。GRASP、MAPW和2phase-HGTS由C++编写，运行环境参见文献[15-17]。IWHO由Matlab编写。

由表6可知，IWHO可以取得前5个中型算例的最优解，证明文中提出的改进野马算法IWHO在处理LRP上可信。

表5 5种算法求解LOLRPSPD算例对比

Tab.5 Comparison of five algorithms for solving LOLRPSPD examples

表6 标准算例的求解结果

Tab.6 Solution results of standard examples

4 结语

在开放式送取货选址−路径问题模型上加入碳排放成本，以适应目前的低碳背景，并使用改进的野马算法进行求解。通过引入哈尔顿序列生成初始种群、非线性进化参数、模拟二进制交叉、多项式变异、精英保留策略和多次失败后个体重新初始化等，有效改善了原始算法针对LRP存在的初始种群分布不均、全局搜索能力弱和容易陷入局部最优等问题。算例分析结果表明，文中所提的改进IWHO算法对于LCLRPSPD问题具有良好的优化性能。

为了进一步加强该问题的现实意义，人文关怀是不可或缺的，因此后续研究将构建多目标模型，考虑顾客满意度及配送员工作量，并设计其相应的IWHO求解算法。

[1] COOPER L. The Transportation-Location Problem[J]. Operations Research, 1972, 20(1): 94-108.

[2] KARAOGLAN I, ALTIPARMAK F, KARA I, et al. Formulations for Location-Routing Problem with Simultaneous Pickup and Delivery[E/OL]. 2009. http://w3.gazi. edu.tr/～fulyaal/Papers/LRPSPD_MIP Formulations.

[3] KARAOGLAN I, ALTIPARMAK F, KARA I, et al. A Branch and Cut Algorithm for the Location-Routing Problem with Simultaneous Pickup and Delivery[J]. European Journal of Operational Research, 2011, 211(2): 318-332.

[4] KARAOGLAN I, ALTIPARMAK F, KARA I, et al. The Location-Routing Problem with Simultaneous Pickup and Delivery: Formulations and a Heuristic Approach[J]. Omega, 2012, 40(4): 465-477.

[5] WANG X F. An Location-Routing Problem with Simultaneous Pickup and Delivery in Urban-Rural Dual- Directions Logistics Network[J]. Advanced Materials Research, 2013, 756/757/758/759: 3423-3429.

[6] 刘亚平, 张惠珍, 张莉, 等. 带时间窗同时送取货选址路径问题及其烟花算法求解[J]. 计算机应用, 2022, 42(7): 2292-2300.

LIU Y P, ZHANG H Z, ZHANG L, et al. Fireworks Algorithm for Location-Routing Problem of Simultaneous Pickup and Delivery with Time Window[J]. Journal of Computer Applications, 2022, 42(7): 2292-2300.

[7] 刘冬, 张惠珍, 刘亚平, 等. 改进蘑菇算法求解开放式同时送取货选址–路径问题[J]. 控制工程, 2023, 30(10): 1801-1811.

LIU D, ZHANG H Z, LIU Y P, et al. An Improved Mushroom Algorithm for Solving the Open Location- Routing Problem with Simultaneous Pickup and Delivery[J]. Control Engineering of China, 2023, 30(10): 1801-1811.

[8] BARTH M, YOUNGLOVE T, SCORA G. Development of a Heavy-Duty Diesel Modal Emissions and Fuel Consumption Model，UCB-ITS-PRR-2005-1[R]. California PATH Research Report, 2005.

[9] ZHANG J H, ZHAO Y X, XUE W L, et al. Vehicle Routing Problem with Fuel Consumption and Carbon Emission[J]. International Journal of Production Economics, 2015, 170: 234-242.

[10] XIAO Y Y, ZHAO Q H, KAKU I, et al. Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2012, 39(7): 1419-1431.

[11] NARUEI I, KEYNIA F. Wild Horse Optimizer: A New Meta-Heuristic Algorithm for Solving Engineering Optimization Problems[J]. Engineering with Computers, 2022, 38(4): 3025-3056.

[12] 张春苗, 赵燕伟, 张景玲, 等. 低碳定位——车辆路径问题[J]. 计算机集成制造系统, 2017, 23(12): 2768-2777.

ZHANG C M, ZHAO Y W, ZHANG J L, et al. Location and Routing Problem with Minimizing Carbon[J]. Computer Integrated Manufacturing Systems, 2017, 23(12): 2768-2777.

[13] 王舜, 赵燕伟, 冷龙龙, 等. 基于蚁群选择超启发算法的低碳选址–路径问题[J]. 计算机集成制造系统, 2020, 26(6): 1702-1716.

WANG S, ZHAO Y W, LENG L L, et al. Low Carbon Location-Routing Problem Based on Evolutionary Hyper-Heuristic Algorithm of Ant Colony Selection Mechanism[J]. Computer Integrated Manufacturing Systems, 2020, 26(6): 1702-1716.

[14] LI Y C, YUAN Q Y, HAN M X, et al. Hybrid Multi-Strategy Improved Wild Horse Optimizer[J]. Advanced Intelligent Systems, 2022, 4(10): 2200097.

[15] PRINS C, PRODHON C, CALVO R W. Solving the Capacitated Location-Routing Problem by a GRASP Complemented by a Learning Process and a Path Relinking[J]. 4OR, 2006, 4(3): 221-238.

[16] PRINS C, PRODHON C, CALVO R W. A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem[M]// Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006: 183-194.

[17] ESCOBAR J W, LINFATI R, TOTH P. A Two-Phase Hybrid Heuristic Algorithm for the Capacitated Location-Routing Problem[J]. Computers & Operations Research, 2013, 40(1): 70-79.

Improved Wild Horse Optimizer for Solving Low-carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem

HU Yifei, ZHANG Huizhen*,CHEN Xi

(School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China)

The work aims to propose an Open Location-Routing Problem with Simultaneous Pickup and Delivery (LOLRPSPD) model under the low-carbon background to solve the common problems of outsourcing, frequent return and exchange of goods in delivery companies and solve the problem through the Wild Horse Optimizer. Firstly, a new decoding mode was designed so that the discrete problems could be solved by continuous algorithms. Then, the initial solutions were generated through the Halton sequence to improve the nonlinear evolution probability factor TDR; The simulated binary crossover was used. Polynomial mutation operators were added. Elite preservation, and setting of consecutive failed reinitialization steps were completed. Finally, the effectiveness of the improved algorithm was verified through the comparison results between Improved Wild Horse Optimizer (IWHO), Wild Horse Optimizer (WHO), Simulated Annealing (SA), Particle Swarm Optimization (PSO), and genetic algorithm (GA). The experimental results showed that IWHO in this paper had better optimization ability than normal WHO in terms of large and medium-sized examples, and had a good advantage in the processing of small examples whiling ensuring accuracy. The proposed LOLRPSD model is reasonable, and the Improved Wild Horse Optimizer has better searching ability for LRP problems.

location-routing problem; open location-routing problem; simultaneous pickup and delivery; improved wild horse optimizer; heuristic algorithm

TP302；TB48

A

1001-3563(2024)01-0229-10

10.19554/j.cnki.1001-3563.2024.01.027

2023-05-17

国家自然科学基金（72101149）；教育部人文社会科学基金（21YJC630087）