改进类电磁机制算法的时变关联运输调度问题

汤雅连 蔡延光 郭栋 郭帅

(广东工业大学 自动化学院，广州 510006)

在实际中常有这样的情况，客户需要多种零件商品，这些零件商品是成品的组成部分，具有关联性。客户常常为了保证其需求不受影响而将所有的零件商品供货交付给一个物流运输公司来为其配货。客户的这种需求称之为关联需求;零件商品在被客户使用，即在加工组成成品的过程中，零件的使用有一个先后顺序，称零件商品具有时间关联性。这时，物流公司应该考虑怎样进行车辆分配和寻求最优配送路线以达到最低的物流成本来为多个这种性质的客户配送货物，这样的问题称之为关联物流运输调度问题［1］(Incident Vehicle Routing Problem)。由于车辆的行驶速度在一天中不同时间段是变化的，而且行驶速度的变化直接导致客户间的往返时间不同，所以提出了时变关联运输调度问题(Time Varying Incident Vehicle Routing Problem，TVIVRP)。

针对单车场单车型的车辆路径问题(Vehicle Routing Problem，VRP)，Barrie M. Baker 等［2］对单车场有容量限制且带时间窗的VRP 做了研究，引进领域搜索后的GA 能更好地寻优;Geonwook Jeon［3］等也利用基于OPL-STUDIO 的混合遗传算法及对多车场多种车型的VRP 求解，寻优结果优于GA 得到的结果。Birbil 和Fang 受电磁场中带点粒子见“吸引—排斥”机制的启发，于2003年提出了一种新的全局优化启发式算法——类电磁机制算法(Electromagnetism-like Mechanism Algorithm，EMA)。韩丽霞等［4］提出了无约束优化问题的类电磁机制算法。王晓娟等［5］对此算法进行了研究，综述了该算法在函数优化、神经网络训练和调度等方面的应用;Peitsang Wu 等［6］运用传统EMA 及改进的EMA(引入二分法)对不同规模客户的VRP 进行求解，得出改进的算法可找到更优解;Alkin Yurtkuran 等［7］利用领域搜索和传统EMA 的混合算法对有容量约束的benchmark 问题求解，证明该混合算法解决此类问题是极有优势的。但是对于时变关联物流运输调度问题的探讨甚少，本文就单车场单车型的TVIVRP 问题进行探讨，将车辆行驶速度表述为与行驶时间相关的分段函数，并提出了改进的类电磁机制算法来对其求解。

1 问题描述及数学模型的建立

1.1 问题描述

问题可以简单描述为，假设给定车场及客户信息(位置和货物需求量等)，货物之间的关联系数，车辆信息(载重约束、里程约束和容量约束等)，要求合理安排车辆、车辆出发时间和运输路线，在满足所有客户需求的前提下，使配送成本最低。

1)物流配送渠道由1 个车场，l 个客户(1，2，…，l)，1 个车场，1 个配送中心;

2)车辆从车场出发，完成配送后返回原车场;

3)配送车辆有最大配送距离约束，非满载;

4)硬时间窗约束;

5)速度时变约束。车辆的行驶速度随着所处时间段变化，非高峰期的行驶速度明显高于高峰期。车辆行驶速度分段函数图示如图1 所示。

6)优化目标为车辆完成所有配送任务的配送成本最低。

第i 个客户的货运量为gi(i=1，2，…，l)，需要从车场将货物运给客户，车辆载重量为q，已知gi＜q。预先对需要车辆数进行估计。可以按照式(1)确定车辆数。

式中，［］表示不大于括号内数字的最大整数;0 ＜α ＜1，是对装车(或卸车)的复杂程度及约束多少的估计。

以cij表示为从点i 到点j 的运输成本，cij=cji。目标为使车辆的总配送成本最小。车场编号为0。关联系数为r，rij表示点i 处的货物与点j 处货物的关联系数。

客户要求送货的时间窗为［eti，lti］，每小时等待费用和延迟费用分别为s1和s2，车辆早到或者晚到，都会受到惩罚。tij表示车辆从客户i 出发到j 的行驶时间;ati表示车辆抵达用户i 的时间，wi为车辆在客户i 的等待时间，si为车辆在客户i 的服务时间。

图1 车辆行驶速度

1.2 数学模型

定义变量如下:

建立数学模型

目标函数式(2)表示总运输成本最小，rij越大，表明货物的兼容性越好，因不兼容产生的成本越低，反之亦然。式(3)为车辆行驶距离约束，其中表示车辆k 行驶了客户i 到j 的路程，n 是车辆k服务的客户数目，最大为N。式(4)和式(5)表示两个变量之间的关系。式(6)表示车辆服务客户i 后直接行驶到j 为其服务。式(7)表示每个客户只能由1 辆车来服务且每个客户都能得到服务。式(8)表示每辆车所运送的货物重量不能超过车辆载重量的限制。式(9)表示保证每辆车的客户总数小于等于总客户数目。式(10)、式(11)和式(12)表示时间窗约束，T 为一足够大的整数。

2 改进的EMA

2.1 基本原理

EMA 是一种随机全局优化算法。它是模拟电磁场中的吸引和排斥机制，将每个解比作一个带电粒子，然后按一定准则使得搜索粒子朝最优解移动。由于此思想与电磁理论中吸引与排斥机制有相似性，但也存在差异性，所以称之为类电磁机制。该算法的收敛性已经得到证明，当迭代次数趋于极限时，种群中至少有一个粒子以概率1 移动到全局最优附近。

根据电磁理论中的吸引—排斥机制，EM 算法把每个搜索粒子想象成空间中的一个带电粒子，每个粒子的电荷由待优化的目标函数的函数值决定。该电荷也决定了该粒子对其他粒子的吸引或排斥的强弱。目标函数值越有，寻优越强。通过计算其他粒子与当前粒子的合力来确定每个粒子下一步的走向。其流程图如图2 所示。

2.2 算法流程

不失一般性，考虑极小值的优化问题，如式(13)所示。f(x)为目标函数，x 为决策向量。

Step1 初始化

初始化就是从已知可行域中随机取一定数量的点，即从可行解空间中等概率地选取样本点{y1，y2，…，ypop_size}作为初始解。然后对这些点进行进一步搜索，计算每个粒子的目标函数值，并将目标函数值最优的粒子记为xbest。

初始解的选取方法为:1)采用旋转赌轮机制从集合{0，1，…，ri}中选择任意一个整数令=，i=1，2，…，l;2)采用旋转赌轮机制从集合 {，+1，…，ri}中选择任意一个整数，令=i=1，2，…，l。

Step2 局部搜索

局部搜索是针对单个粒子，用来改进种群中已搜索到的解。它为种群的全局搜索提供了有效的局部信息，使得算法既有全局搜索能力，又有局部区域精细搜索能力。

Step3 计算合力

模拟电磁理论的叠加原理，EM 算法通过计算合力来决定粒子的下一步走向。粒子i 的电荷量qi决定了此粒子所受吸引力或排斥力的大小，电荷量qi的计算如式(14)所示。

图2 改进EMA 算法流程图

由此可知，目标函数值较优的粒子拥有较大的电荷数，具有更强的吸引力，在比较两粒子的目标函数值后决定两粒子间作用力的方向。作用在粒子i 上的合力Fi，如式(15)所示。每两个粒子之间，目标函数值较优的粒子将吸引另一个粒子，目标函数值较劣的粒子会排斥另外一个粒子。由于当前最优粒子xbest的目标函数值最优，所以它是绝对吸引子，吸引所有其他粒子。

Step4 移动粒子

由于传统的EMA 中，粒子移动步长的确定没有考虑粒子的优劣及进化代数的影响［8］，所以为了使粒子能更精确地靠近最优解，设计了一个自适应移动算子，如式(16)所示。t 表示粒子i 当前的进化代数。并将作用在粒子上的力做“归一化”处理，λ∈(0，1)范围内的随机数，则更新后的位置如式(17)所示，由该式可知，粒子在每次移动时，目标函数值较差的粒子所带电荷量较小，因而其移动步长要比目标函数值较优的粒子也就是所带电荷量较大的粒子移动的步长要大，这样能够使得较差粒子能快速收敛到当前最优值附近。随着迭代次数的增加，移动步长开始变小，在进化后期，粒子只在当前最优粒子附近随机扰动。RNG 为可行步长，uk为上边界，lk为下边界，如式(18)所示。

Step5 终止准则

当达到最大迭代次数时，算法结束;否则，转Step2。

3 算例分析及结果

某供应中心有1 个车场，车场坐标为(30，30)，客户信息如表2。每辆车载重8 吨，最大配送里程为150 km，关联系数由Visual C++6.0 随机生成。单位配送费用为1 元/t* km，已知车辆最早发车时间为7:00。

本文中的实验是在Intel(R)CoreTMi3 CPU2.53 GHz、内存2.0G 的win7 平台上采用Microsoft Visual C++ 6.0 编程实现的。关联系数由Visual C++随机产生。遗传算法中参数设置:初始化种群，种群规模N=20，最大迭代次数gen=500，交叉概率pc=0.8，变异概率pm=0.005。本文中用到的遗传算法，其交叉算子指多点杂交，按Poisson 分布确定交叉点数，如式(19)所示。其中，x 为杂交点数，均值E(x)和方差D(x)为位串长度的函数。变异算子特指单点变异。

表1 客户信息一览表

表2 两种算法运行结果对比

分别用GA、ANA 和改进的EMA 运行20 次，得到该算法求解本算例的结果，如表2 所示，配送示意图如图3(a)、(b)和(c)所示。由表2 知，改进的EMA 比其他两种算法的寻优能力更强，得到的效果更好，求得最优配送网络的总路程为321.5 米，成本为2 254.5 元。

图3 不同算法的最优配送路径示意图

4 结语

本文分别用遗传算法、蚁群算法和改进的类电磁机制算法对单车场单车型一个配送中心硬时间窗约束的时变关联物流运输调度模型求解，实验结果证明，改进的类电磁机制算法对解决此模型是有效可行的，而且在寻优方面优于另外两种算法。粒子在每次移动过程中，目标函数值较差的粒子移动的步长比目标函数值较优的粒子移动的步长要大，而且随着进化代数的增加，粒子的移动步长也随着变小，而在后期，粒子只在最优粒子附近随机扰动，这样可以更精细地寻优。下一步工作可以扩展到用改进EMA解决多扩展特征(如带时间窗、道路容量约束、路障情形、多车场、多车型等)的TVIVRP，并可将该算法应用到流水线生产物流运输调度及时变的关联物流运输调度等问题中。

［1］汤雅连，蔡延光，赵学才.关联物流运输调度问题的改进遗传算法［J］. 微型机与应用，2012，31(17):69－71.

［2］Baker Barrie M，Ayechew M A. A genetic algorithm for the vehicle routing problem［J］.Computers ＆ Operations Research，2003(30):787－800.

［3］Geonwook Jeon，Herman R Leep，Jae Young Shim.A vehicle routing problem solved by using a hybrid genetic algorithm［J］.Comerter＆Industrial Engineering，2007(37):680－692.

［4］王晓娟，高亮，陈亚洲.类电磁机制算法及其应用［J］.计算机应用研究，2006(6):67－70.

［5］韩丽霞，王宇平. 求解无约束优化问题的类电磁机制算法［J］.电子学报，2009，37(3):664－668.

［6］Birbil S I，Fang S C. Electromagnetism-like Mechanism for Global Optimization［J］. Journal of Global Optimization，2003，25:263－282.

［7］Alkin Yurtkuran，Erdal Emel. A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems［J］. Expert Systems with Applications，2010(37):3427－3433.

［8］姜建国，龙秀萍，田旻，等.一种基于佳点集的类电磁机制算法［J］.西安电子科技大学学报:自然科学版，2011，38(6):167－172.