基于萤火虫算法带时间窗的双向配送调度

王俊峰，李玉华，张凯丽

（合肥工业大学　管理学院，安徽　合肥　230009）

基于萤火虫算法带时间窗的双向配送调度

王俊峰，李玉华，张凯丽

（合肥工业大学管理学院，安徽合肥230009）

针对带时间窗的双向配送调度问题，重新建立新的带多目标的数学模型，提出一种离散型萤火虫算法和编码策略，并重新定义了个体交叉变异移动公式。同时，根据萤火虫编码个体之间的逻辑距离，构建邻域集合，提高局部搜索能力。并引进个体历史最优记忆功能，加快收敛速度。最后利用随机数和求余函数对编码个体进行扰动，防止过早陷入局部极值。通过仿真案例实验验证了算法的有效性。

双向配送；时间窗；多目标；离散型萤火虫算法

1　引言

如今，全球经济的繁荣和生活节奏的加快，快捷及时、低碳环保的运输配送日益重要。其中，车辆路径问题VRP（Vehicle Routing Problem，VRP）一直是学者专家热衷的研究课题。随着信息智能化技术的发展，研究学者更是把人工智能优化算法引入到车辆配送调度问题中，为配送问题提供了比较满意的解决方案。对此，针对不同类型的车辆配送调度问题，研究学者提出了不同的解决方案。

文献［1］Jayaraman对包含多产品、单个生产工厂、多个配送中心的物流配送网络优化问题进行了研究，并用模拟退火算法对该问题的直拨运输情况进行了一定程度的优化。文献［2］分析了大中城市市内邮政运输路径规划中存在路径重复的弊端，利用禁忌搜索算法对大中城市市内的邮政运输车辆配送问题进行了探索，并提出了辐射型邮路的解决方案。文献［3］运用整体优化的思想，利用离散型粒子群优化算法并加入了变异和扰动因子，对定位-运输路线安排问题进行了深入研究，得到了一定的效果。文献［4］利用RFID技术实现物流配送动态数据的跟踪，但是研究目标单一，不能很好地满足现实中物流配送的及时性和提高客户满意度的要求。在分析了前面研究的基础上，本文将利用萤火虫算法解决车辆双向配送调度问题。

萤火虫优化算法（Glowworm Swarm Optimization，GSO）是由印度学者K.N.Krishnanad和D.Ghose于2005年提出的一种新型仿生群智能优化方法［5］。该算法具有较好的全局优化搜索能力，在函数优化［6-8］、多信号源追踪定位［9］等连续优化问题方面取得了一些成果，但是在组合优化具有离散性质问题方面的研究才刚刚起步。并且，萤火虫算法也和其他群智能优化算法一样，存在优化精度低、收敛速度慢、震荡等缺点［10］。郭丽萍、周永权等［11-13］将萤火虫算法应用到离散型TSP组合优化问题中，不过萤火虫算法缺少个体的自身反馈和群体引导没有被考虑到，以致优化不明显。对萤火虫算法进行全面深入的研究，在理论拓展和工程应用实践上都具有重要意义。本文不仅丰富了解决物流配送调度问题的优化解决算法，还拓宽了萤火虫算法的应用领域。

2　带有时间窗的双向配送问题描述和数学模型建立

通常一个高级的物流配送中心周围存在着多个低级的物流配送中心，并进行双向交流。我们把此简化成“一个中心，多个供需点”结构。然而，传统的配送路径规划通常只考虑路径最短或配送车辆最少的单个性能指标，不能很好地满足现代物流配送的及时性要求和客户满意度。针对此结构，我们对带时间窗的双向配送路径调度优化问题重新建立数学模型和多目标指标并进行研究。

2.1问题描述

配送中心需要m台相同的配送车辆。车辆最大载重为w，平均速度为v，最长行驶路程为L。供需点有n个，供需点i需求量为ri，供应量为ui，与配送中心之间的距离为di0，要求服务时间段为［］ai，bi。任意两个供需点i和 j之间的距离为dij。装载或卸掉每吨货物需要时间长为t小时。用集合Rk表示第k辆车的行驶路径，Rk中供需点的顺序表示被服务的先后顺序，用Ck表示Rk中元素的个数，即第k辆车所服务供需点的个数。Rk中元素rky表示供需点rky被第k辆车服务的顺序为y（y=1，2，…，Ck），令rk0表示配送中心。现规定：在此时间段之前到达或之后离开，都将耽误时间；车辆在配送过程中其载货量不能超过其最大载重量；每条配送路径的长度不能超过配送车辆的最长行驶路程。

2.2模型建立

以配送总路程最短为主要目标，以使用的车辆数最少、耽误的时间最短为辅助目标。其中，目标函数、约束条件公式如下：

在目标函数中，tia表示提前到达供需点i而等待耽误的时间，tib表示晚点离开供需点i而耽误的时间；公式（6）表示达到下一供需点的时间=达到当前供需点时间+等待时间+卸货和装货时间+行驶时间，srki表示到达供需点rki的时间，trkia表示在供需点rki时间窗之前到达需要等待的时间。如果在时间窗内到达，则trkia=0；公式（7）表示车辆行驶到下一供需点卸掉该点需求量，装上该点供应量之后不能大于最大载重，uk0表示配送中心。

3　基本的萤火虫算法描述

萤火虫算法是模拟自然界中萤火虫觅食行为的一种群智能优化算法。萤火虫会发光，光亮强度由自身所携带的荧光素决定。荧光素越多，发光越亮，代表该萤火虫所在位置的适应度值也高，从而在感知范围内吸引其他萤火虫移动。每只萤火虫的移动分为三个阶段，即荧光素更新、萤火虫个体移动和感知范围更新。萤火虫算法无非就是此三个阶段的反复迭代。每个阶段的相关描述如下［14］：

第一阶段：荧光素更新。利用公式（8）计算萤火虫Xi第t代的荧光素值。其中是萤火虫 Xi第代的荧光素值，ρ是荧光素挥发因子是萤火虫Xi第t代的位置是所对应的适应度值，γ是荧光素更新率。

第二阶段：萤火虫个体移动。利用公式（9）计算萤火虫Xi向内每只萤火虫移动的概率，且利用公式（10）计算萤火虫Xi第代的位置。其中是第t代在萤火虫Xi感知范围内的并且比自己亮、比自己适应度值高的萤火虫的邻域集合，s是移动步长。

第三阶段：感知范围更新。利用公式（11）计算萤火虫Xi第代的感知范围半径。其中，rs是每只萤火虫的初始感知半径，β是感知范围更新率，nt是感知范围内包含萤火虫数目的阈值是萤火虫Xi感知范围内的并且比自己亮的萤火虫的数目。

4　改进的萤火虫算法

4.1编码策略

针对上述提到的车辆双向配送调度模型，对配送中心编号为0，n个供需点编号为1，2，…，n。并进行编码：对n个供需点从1到n进行无重复地随机全排列，构成一个萤火虫个体 Xi=（xi1，xi2，…，xij，…，xin），j=1，2，…，n，xij∈（1，2，…，n）。

4.2适应度值计算

把主要目标配送的总路程当做适应度值。计算适应度值就是计算配送的总路程，就得在编码的基础上插入0。插入0的规则是：这个全排列首尾插入0，然后根据约束条件，从头到尾在适当位置依次插入0。0与0之间的编号表示一辆车从配送中心出发，所要配送的供需点，最后又回到配送中心。把所有车辆配送的距离加起来，就是配送的总距离，就是适应度值。并借鉴鱼群算法中的公告板［15］，将适应度值和当前编码状态保存到公告板。此时，作为辅助目标，需要的车辆个数就是0的个数减1。比如，随机生成的全排列632451，插0之后，变成序列0632405010，表示需要3辆车。第1辆车从配送中心出发，先后配送6，3，2，4四个供需点，最后回到配送中心。第2辆车配送5号供需点，第3辆车配送1号供需点。

4.3个体之间的逻辑距离计算

针对本文具体的编码方式，重新定义构建感知范围内邻域集合的方法。萤火虫个体Xi（t）依公式（12）计算出与其他个体之间的逻辑距离dij（t），并将dij（t）与rid（t）进行比较。将与Xi（t）之间距离dij（t）比rid（t）小的且比Xi（t）适应度值大的萤火虫个体放入邻域集合。

4.4定义个体移动方式

借鉴粒子群算法的个体产生机制［16］，更改公式（9）、（10）概率移动方式，重新定义离散型萤火虫算法的个体移动方式，并引进个体历史最优。个体Xi（t）移动除了受前一次移动结果的影响外，还要受个体历史最优Xh、感知范围内最优个体Xg的影响。个体Xi（t+1）中第 j个元素xij（t+1）是在个体Xi（t）中第 j个元素xij（t）基础上根据概率被Xi（t）本身或Xh（t）或Xg（t）中第j个元素所代替形成的，见移动方式公式（13）。在替换过程中，如果被替换之后所形成的Xi（t+1）第 j个元素xij（t+1）与Xi（t）第j个元素之后的某个元素xik（t）相同，则把xik（t）替换成xij（t），保证在后面的替换过程中Xi（t+1）个体元素不会出现重叠；如果被替换之后所形成的Xi（t+1）第 j个元素xij（t+1）与Xi（t+1）第j个元素之前的某个元素xih（t+1）相同，则把Xi（t+1）第 j个元素xij（t+1）替换成xij（t），防止元素出现重叠。

表1　移动方式演示

4.5添加扰动项

萤火虫算法在寻优时容易出现早熟现象陷入局部极值中。为了让算法跳出局部极值，增加个体多样性，本文采用了加随机数、求余数扰动项。采用公式（14）对萤火虫个体Xi（t）里面的元素xij（t）进行扰动。其中，rand（）表示随机生成一个从1到29的整数，mod（a，b）表示求a除以b的余数。公式对算法起到扰动效果，并且确保了元素都在1到30之间，增加了个体多样性。

4.6改进的萤火虫算法求解配送路径优化的步骤

（1）按照编码方式随机生成N个萤火虫个体，并初始化算法参数。

（2）计算每只萤火虫初始时所在位置的适应度值，并将每只萤火虫初始时的位置状态和适应度值保存到公告板。

（3）利用公式（8）更新每只萤火虫的荧光素值。

（4）每只萤火虫利用式（12）寻找感知范围内比自己荧光素值大的个体，添加到邻域集合。如果找不到，利用式（14）进行扰动移动，再转步骤（6）。

（5）在感知范围内，每只萤火虫利用式（13）向自己的历史最优、邻域集合内最优个体移动。

（6）计算每只萤火虫移动之后的适应度值，并将每只萤火虫在移动迭代过程中适应度值最高时的位置状态和最高适应度值更新到公告板。

（7）若满足终止条件，则输出公告板纪录的结果；否则，根据公式（11）更新感知半径，转步骤（3）。

5　仿真实验

5.1仿真环境

采用Matlab R2012a软件编码测试，编译运行程序PC机的设置：32位Win7操作系统，处理器：Intel（R）Core（TM）i5-3570 CPU@3.40GHz，安装内存：4.00GB。

5.2参数设置

为了验证改进萤火虫算法对本文配送路径优化具体问题的求解性能，对改进的离散型萤火虫算法参数设置如下：萤火虫个体数N=100、最大迭代次数Max=500、荧光素挥发因子ρ=0.4、荧光素更新率γ=0.6、感知半径更新率β=8、感知范围域阈值nt=5、初始荧光素值l0=5、初始感知半径rs=50。并给出1个配送中心、30个供需点进行模拟运算。配送中心坐标为（20km，20km），配送车辆速度为20km/h，最大载重为2t，最长行驶距离为55km。每1h卸掉或装载货物1t，即t=1。供需点坐标及时间窗、供应量、需求量见表2。

表2　供需点坐标及时间窗、供应量、需求量

5.3结果分析

采用改进的萤火虫算法对配送路径调度经过500次的迭代运算之后，得到比较满意的结果见表3。

针对表5的运算结果，我们给出了最终比较满意的车辆调度仿真可视化路线，如图1所示。

为了进一步验证改进萤火虫算法的性能，分别采用遗传算法、粒子群算法求解的结果和改进萤火虫算法求解的结果进行对比，见表4。

表3　运算结果

图1　车辆双向配送调度仿真结果

表4　结果对比

由表4看到，不管是主目标还是辅助目标，改进的萤火虫算法都取得了最好的求解结果，

图2　配送距离与迭代次数的关系

通过图2可以清楚地看到，在求解配送距离迭代过程中，不管在收敛速度上还是最终最短路径上，改进的萤火虫算法都要优于粒子群算法和遗传算法。收敛速度，改进的萤火虫算法要优于粒子群算法和遗传算法，得益于添加的历史最优记忆功能，加快了收敛速度。通过图3，虽然粒子群算法刚开始收敛比较快，不过最后变慢了，并且收敛值不如遗传算法和改进的萤火虫算法，改进的萤火虫算法效果更优。从图4可以看到，随着迭代次数的增加，配送车辆数逐渐收敛，达到了比较满意的状态。这三张图的数据都表明了改进的离散型萤火虫算法还是比较优越的。改进的萤火虫个体逻辑距离公式更适合离散的编码个体距离计算，用改进的计算方法构建了邻域集合，加快了局部搜索精度。历史最优记忆功能和扰动项的加入提高了收敛速度，比较符合实际情况。

图3　耽误时间与迭代次数的关系

图4　配送车辆数和迭代次数的关系

6　小结

车辆路径问题VRP是一类很复杂的NP问题，是目前热点研究问题。本文利用改进的离散型萤火虫算法对带有时间窗的车辆双向配送调度问题进行了深入研究，构建了新的带多目标的数学模型和特殊的编码方式，给出了求解步骤和处理流程。移动方式的改进，扰动项的添加，提高了算法收敛速度和局部搜索能力。最后通过实例验证，并和遗传算法、粒子群算法进行了对比，结果证明改进的离散型萤火虫算法求解带有时间窗的双向配送调度问题的可行性和优越性。

［1］Jayaraman V，Ross A.A simulated annealing methodology to distributionnetworkdesignandmanagement［J］.European Journal of Operational Research，2003，144:614-643.

［2］段凤华，符卓.有软时窗约束带取送作业的车辆路径问题及其禁忌搜索算法［J］.计算机工程与科学，2009，31（3），68-74.

［3］彭扬，陈子侠，吴承建.定位-运输路线安排问题的改进离散粒子群优化算法［J］.智能系统学报，2010，5（1）:75-79.

［4］吴斌，钱存华，倪卫红.基于免疫萤火虫算法的RFID仓储车辆动态调度［J］.计算机工程与应用，2013，49（6）.

［5］Krishnanand K N，Ghose D.Glowworm Swarm Optimization for Multimodal Search Spaces［A］.Handbook of Swarm Intelligence［C］. Springer Berlin Heidelberg，2010.

［6］刘佳昆，周永权.一种最大最小荧光素值人工萤火虫算法［J］.计算机应用研究，2011，28（10）:3 662-3 664.

［7］王湘中，俞寿益.多模态函数优化的多种群进化策略［J］.控制与决策，2006，21（3）:285-288.

［8］Horng Ming-Huwi，Liou Ren-Joan.Multilevel minimum cross entropy threshold selection based on the firefly algorithm［J］.Expert Systems with Applications，2011，38（11）:14 805-14 811.

［9］Krishnanand K N，Ghose D.Chasing Multiple Mobile Signal Sources:A Glowworm Swarm Optimization Approach［A］.Proc of the 3rd Indian International Conference on Artificial Intelligence［C］.IEEE Press，2007.

［10］Deep K，Bansal J C.Mean particle swarnl optimization for functionoptimization［J］.IntJComputational Intelligence Studies，2009，1（1）:1-19.

［11］张军丽，周永权.人工萤火虫与差分进化混合优化算法［J］.信息与控制，2011，40（5）:608-613.

［12］郭丽萍，李向涛，谷文祥，等.改进的萤火虫算法求解阻塞流水线调度问题［J］.智能系统学报，2013，8（1）:33-38.

［13］周永权，黄正新.求解TSP的人工萤火虫群优化算法［J］.控制与决策，2012，27（12）:1 816-1 821.

［14］Krishnanand K N，Ghose D.Glowworm swarm optimization:a new method for optimizing multimodal functions［J］.International Journal of Computational Intelligence Studies，2009，1（1）:93-119.

［15］Ma Xian-min，Liu Ni.Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem［J］.Journal on Communications，2014，（1）:1-6.

［16］Kennedy J，Eberhart R C.Particle swarm optimization［A］. Proc of IEEE International Conference on Neural Network: Service Center［C］.1995.

Study on Bidirectional Distribution Scheduling with Time Window Based on Glowworm Swarm Optimization

Wang Junfeng，Li Yuhua，Zhang Kaili
（School of Management，Hefei University of Technology，Hefei 230009，China）

In this paper，we developed a new multi-objective mathematical model for the bidirectional distribution scheduling problem with time window，proposed a discrete glowworm swarm optimization and the relevant coding strategy，and further redefined the formula of the crossover，mutation and movement of the individuals.Meanwhile，according to the logical distance between the individual glowworm swarm optimization，we established the neighborhood set to improve the local search ability of the algorithm.Next we introduced the optimal historical memory function of the individuals to accelerate convergence.At the end，we used the random number and the remainder function to protect the individual codes from interference and prevent local convergence and demonstrated the validity of the algorithm through a simulated case study.

bidirectional distribution；time window；multi-objective；discrete glowworm swarm optimization

F224；F252.14

A

1005-152X（2016）04-0058-06

10.3969/j.issn.1005-152X.2016.04.016

2016-03-13

王俊峰（1957-），男，湖北黄梅人，博士，主要研究方向：工业工程、物流优化及信息化；李玉华（1990-），男，山东临沂人，硕士，研究方向：工业工程、人工智能；张凯丽（1991-），女，山东潍坊人，硕士，研究方向：物流工程、物流优化及信息化。