基于改进人工蜂群算法的货车载货平衡问题研究

付中华，马英钧

(1.武汉城市职业学院 初等教育学院，湖北 武汉 430000；2.华中师范大学 数统学院，湖北 武汉 430079)

基于改进人工蜂群算法的货车载货平衡问题研究

付中华1，马英钧2

(1.武汉城市职业学院 初等教育学院，湖北 武汉 430000；2.华中师范大学 数统学院，湖北 武汉 430079)

货车载货平衡问题是多约束的双目标规划问题，传统的规划算法往往具有较大的时间消耗。为此，针对ABC算法的特点，借鉴传统遗传算法求解组合优化问题上的优势、粒子群算法的历史极值与全局极值搜索机制及模拟退火的全局搜索策略，提出了一种求解该问题的新方法。在此基础上通过数值实验求解车厢个数为10、箱子个数为50的较复杂货车载货问题，并与传统的遗传算法进行对比，最终的结果表明改进算法对于货车载货平衡问题具有较高的求解效率。

改进ABC算法;货车载货平衡;遗传算法;全局搜索机制;模拟退火策略

人们在通过工业化提高自己生活水平的同时也付出了较大的环境代价，在1970年之前的200年内，人均耗能增加了9倍，在之后的40年内，人均耗能又增长了25%，因此，节能减排势在必行，是我国实现可持续发展的重要战略举措[1]。加强物流管理、完善物流流程、降低物流费用等增强企业竞争力的举措越来越得到经营者和管理者的认可,同时这也是节能减排、实现可持续发展的一个重要体现[2]。

货车载货问题属于在m台相同的机器上调度n个非抢先的任务问题，也成为m处理机调度问题，最小化货车的最大载荷即对应于最小化调度方案的总时间消耗。其是一种较复杂的NP-hard问题，若将该问题表示为线性问题，则很难解决处理机数超过3个、任务数超过30个的问题。针对两台机器和100个以内的问题，利用动态规划方法和树搜索算法处理，往往需要较长的优化时间。采用LPT(最长处理时间)启发式算法可以很快找到较好的解，该算法的基本原则是在每次迭代中将最长处理时间的任务安排在负荷最轻的机器上，但是其寻找最优解的比率很低[3]。

人工蜂群算法(ABC算法)于2005年系统被提出[4]，并在2007—2009年首次被应用于无约朿函数优化中，通过与差分进化算法、粒子群算法进行比较，验证了ABC算法的良好性能。近年来，很多学者针对蜂群算法进行多方面的改进，极大地提高了蜂群算法的优化性能。鲁建厦等[5]将遗传算法的选择、突变等操作引入ABC算法，增加了传统的ABC算法求解约束优化问题的能力。笔者借鉴遗传算法求解组合优化问题时的交叉变异操作，改进传统ABC算法中的邻域搜索机制，加入粒子群算法的全局极值和历史极值搜索，同时将模拟退火策略引入蜂群的选择机制，并通过实验仿真进一步验证改进的ABC算法的求解效率。

1 货车载货平衡问题

1.1 问题描述

货车载货平衡问题可以描述为：有n节货车车厢，其最大允许载重均为cap，使用者用n节车厢运输m个箱子，这些箱子的重量分别为wi(i=1,2,…，m)，需要解决的问题是如何分配才能使得每节车厢的实际载重均不超过最大允许载重，且使装载量最大的车厢的装载量最小,同时保证车厢能够装载尽可能多的箱子。

1.2 模型建立

(1)定义装载方案变量loadi(i=1,2,…，m)表示第i个箱子装载到第loadi个货车车厢上，根据实际条件，这些变量取整数，且应满足货车车厢总个数的约束。因此可定义约束条件(1)和约束条件(2)。

0≤landi≤n

(1)

landi∈Z

(2)

特别地，当landi=0，表示箱子i不装入任何一个车厢。

(2)每节车厢的实际载重不能超过最大允许载重cap，因此，可定义约束条件(3)。

(3)

(3)为了保证车厢间的装载量更为均衡，令f1表示当前装载量最大的车厢，只需要求f1尽可能地小就可达到，因此可表示为式(4)的形式。

(4)

(4)保证尽可能多的箱子装入车厢，即使得剩余的重量尽可能小，可定义目标函数f2：

(5)

综上，优化的最终目标是在保证约束(1)～约束(3)成立的条件下，使得目标函数f1和f2尽可能地小。

2 人工蜂群算法简介及改进

2.1 人工蜂群算法简介

ABC算法包括初始化阶段、采蜜蜂阶段、观察蜂阶段、侦察蜂阶段[6]，具体过程如下：

(1)算法的初始状态由侦查蜂生成一组随机的蜜源位置Xi=(xi1,xi2,…,xiD)其中，i=1,2，…,NS,NS表示蜜源的个数，D表示问题解的维数。

(2)算法的循环迭代过程主要包括采蜜蜂的邻域搜索、观察蜂的选择和搜索、侦查蜂的决策和选择3个阶段。采蜜蜂根据侦查蜂反馈的蜜源信息，按照式(6)对蜜源的邻域进行搜索，并利用贪婪准则进行更新；对于采蜜蜂反馈的蜜源信息，观察蜂利用轮盘赌的方式进行选择，并根据式(6)对选择的蜜源进行邻域搜索；在算法进行过程中，侦查蜂根据蜜源的开采次数Bas和控制参数Limit的关系，判断是否舍弃该蜜源，并利用式(7)进行更新。

(6)

(7)

式中：j为随机选择的维度；Xi为原始蜜源；Xk为选择的蜜源；new_Xji邻域搜索后产生的新蜜源；xjmax,xjmin分别为第j个分量的取值上界和下界。

(3)根据循环数和预设定的最大循环代数来判定是否跳出迭代。

2.2 算法改进

针对货车载货平衡问题多约束双目标规划的特点，借鉴遗传算法求解组合优化问题时交叉、变异算子、粒子群算法的全局搜索及模拟退火算法特点，将式(6)中的邻域搜索操作替换为随机基因位交叉和全局交叉相结合；贪婪选择机制改为模拟退火选择策略；将双目标规划通过加权转化为单目标优化问题。

2.2.1 生成初始可行蜜源

货车载货的车厢装载方案必须满足整数条件，因此采用整数编码的方式产生初始蜜源。对于任一蜜源X=(x1,x2,…，xm)，其中xi为第i个货箱的实际装载方案，xi∈{0,1,2,…，n}，因此随机生成[0,n]间的m维整数作为初始蜜源。例如,对于车厢的个数n=3,箱子的个数m=5，蜜源X=(1,3,1,3,2)表示第1,2,3,4,5个箱子分别装载在第1,3,1,3,2节车厢。

2.2.2 改进邻域搜索策略

传统的ABC算法中，采蜜蜂和观察蜂利用式(6)进行邻域搜索，这比较适合实数编码的蜜源搜索，但对于笔者研究的问题会产生许多非整数蜜源维度。为了减少计算的复杂度，提升蜂群邻域搜索的效率，笔者借鉴遗传算法的交叉算子和粒子群算法的全局极值更新算子对蜂群的邻域搜索操作进行改进，改进公式的简单形式如式(8)所示：

(8)

式中：F表示new_Xji与Xji,Xjk,XjP,XjG间存在着一定的关系；Xjk为随机选取的邻域蜜源；XjP为该蜜源的历史最优蜜源；XjG为全局最优蜜源。

邻域搜索的具体操作步骤为：①生成[1,m]间的随机整数j，表示邻域搜索的维度。②按照式(9)和式(10)分别计算进化因子μ和判别概率P，其中cycle为当前的代数，maxcycle为总迭代代数。③根据判别概率，确定蜜源进行局部极值更新和全局极值更新，即当P<0.5时，new_Xji=XjP；否则new_Xji=XjG。

(9)

(10)

由式(9)可以看出，迭代初期进化因子μ较小，对应的判别概率P也较小，此时进行历史极值更新，使粒子能够较自由地发散到搜索空间中,较少受到“社会意识部分”的影响,以增加群内粒子的多样性[7]；随着迭代次数cycle的增加,判别概率P逐渐变大，此时较大的概率进行全局极值更新,进而加强了粒子向全局最优点的收敛能力。

2.2.3 模拟退火的选择策略

传统的ABC算法，当采蜜蜂和观察蜂进行邻域搜索后，利用贪婪策略进行蜜源选择，尽管可以较快地找到局部最优的蜜源，但是同样会丢失暂时适应度不高、但更接近全局最优的蜜源。借鉴模拟退火策略的概率全局优化性能[8]，笔者利用模拟退火策略代替贪婪选择，具体的算法步骤为：①在算法起始设定初始温度T和退火参数k。②比较原始蜜源的适应度f(X)和邻域搜索后蜜源的适应度f(X′)，若f(X′)≤f(X)，则接受新解X′；若f(X′)>f(X)，则以概率P接受新解，其中P=e-[f(X′)-f(X)]/kT。③按照一定的方式对当前温度T进行降温。

在为期4天的游学之旅中，游学队伍先后转辗河南省上蔡金丰公社、邵店分社、韩寨分社、小岳寺分社，河南省驿城金丰公社、和岗分社、程楼分社，河北省行唐金丰公社、伏流分社、上碑分社，3个金丰公社10个观摩点，辗转1000多公里，进行现场观摩学习，各分社社长现场讲解如何建组织配机械、如何发动农户、如何实现服务本村农户的过程和关键环节，各事业合伙人现场提问，边听边记，学之所长。

模拟退火策略在一定程度上保留了贪婪策略的择优选择思想，同时也以一定的概率接受新的次优解，在一定程度上增强传统ABC算法跳出局部最优的能力[9]。

2.2.4 约束条件和多目标处理

智能算法本质上是基于区间约束优化问题提出的，由式(3)容易看出，笔者所研究问题中的约束条件较多，为了消除不同约束条件间的量级差异，笔者在对约束条件进行归一化处理的基础上，针对约束条件式(3)和目标函数式(4)、式(5)，建立蜜源的总罚值函数和适应度函数，具体过程如下：①计算蜜源关于约束条件式(3)的罚函数值qj(X)，如式(10)所示。②将约束函数和目标函数进行综合处理，根据重要性设置权重，计算总目标函数值F(X)，具体计算公式如式(11)所示。

(10)

(11)

对于该问题，首先必须满足约束条件是最为重要的，其次要求车厢里面能装载尽可能多的箱子，最后才是车厢间的平衡，权重的设置通过单位归一化和数量级的差别表示其重要性的区别。综上，得到改进的人工蜂群算法流程图,如图1所示。

图1 改进的人工蜂群算法流程图

3 仿真模拟及结果分析

设定车厢的个数n=10，箱子的个数m=50，车厢的最大容量cap=100，箱子的重量wi如表1所示，箱子的总重量为908，平均每个车厢分配的最大箱子重量的下界为90.8。

表1 箱子重量

采用Matlab 12a进行编程，分别利用笔者提出的改进人工蜂群算法和遗传算法进行求解。人工蜂群算法的参数设置为：蜜源规模NS=200,控制参数Limit=20，最大循环代数maxcycle=500；遗传算法的参数设置为：种群规模popsize=200，最大遗传代数maxgen=500，交叉概率Pc=0.8，变异概率Pm=0.2，代沟GGAP=0.9。得到的最优装载方案如表2所示。

表2 两种算法的最优装载方案结果对比

由表2可以看出，无论人工蜂群算法还是遗传算法，得到的结果都能保证满足约束条件，并且使得目标函数f1达到最小,剩余物品重量为0。但是对于目标函数f2,改进蜂群算法求得的最小值为92,遗传算法求得的最小值为99。

图2 两种算法的优化过程对比

两种算法的优化过程对比如图2所示，可以看出改进的人工蜂群算法经过500次左右的迭代已经可以找到全局最优解，而传统的遗传算法只能得到局部最优解，初步说明了改进人工蜂群算法对于货车载货平衡问题有较高的求解效率。同时，在迭代初期遗传算法和改进人工蜂群的迭代效率较为接近，但是在100代左右遗传算法基本上陷入停滞状态；而改进人工蜂群算法却能跳出局部最优解，最终达到全局最优解，进一步说明改进人工蜂群算法在求解货车载货平衡问题时的高效性。

4 结论

笔者采用改进人工蜂群算法求解货车载货平衡问题，借鉴遗传算法的编码方式和交叉变异操作、粒子群算法的全局和历史极值更新机制及模拟退火选择策略，在一定程度上提升了人工蜂群算法解决组合优化问题的性能和全局搜索的能力，通过仿真实验进一步验证了算法的有效性。将智能算法应用到货车载货方案设计中，不仅提高了车辆的运输效率，同时增强了车辆的安全性能。降低物流的费用，提升物流运输的效率，为企业管理者的决策安排提供了科学的依据。但是笔者算法的一些操作只是针对货车载货平衡问题提出的，在后续的研究中尚需进一步进行推广研究。

[1] 董奥,平星星,姜亮,等.基于能效监测的能源管理优化[J].节能技术,2013,31(3):269-273.

[2] 李德福.中小企业物流管理优化策略研究[J].物流科技,2010,33(2):53-55.

[3] GUERET C, PRINS C, SEVAUX M. Applications of optimization with Xpress-MP[M].Pairs: Dash Optimization Ltd，2006:171-195.

[4] 王艳娇.人工蜂群算法的研究与应用[D].哈尔滨：哈尔滨工程大学,2013.

[5] 鲁建厦,翁耀炜，李修琳，等.混合人工蜂群算法在混流装配线排序中的应用[J].计算机集成制造系统，2014,20(1):121-127.

[6] 马英钧.基于人工蜂群算法的约束优化问题研究[D].武汉：华中师范大学,2015.

[7] 冯翔,陈国龙,郭文忠.粒子群优化算法中加速因子的设置与试验分析[J].集美大学学报(自然科学版)，2006,11(6):146-151.

[8] 吴意乐,何庆.基于改进遗传模拟退火算法的WSN路径优化算法[J].计算机应用研究，2016,33(10):2959-2960.

[9] 卢宇婷,林禹攸.模拟退火算法改进综述及参数探究[J].大学数学，2015,31(6):97-103.

[10] 王松,李红星.基于遗传搜索策略的人工蜂群算法[J].北京联合大学学报，2017,31(1):87-91.

FU Zhonghua:Assoc. Prof.; Primary Education College,Wuhan City Vocational College, Wuhan 430000,China.

Research on Truck Load Balancing Problem Based on Improved Artificial Bee Colony Algorithm

FUZhonghua，MAYingjun

The problem of truck load balance is a bi-objective programming with multi-conditions. The traditional planning method spends a lot of time. A new method is given to solve this problem in this paper, it based on the traditional legend method and characteristics of ABC algorithm with the advantages of combinatorial optimization, the historical extremum of swarm optimization algorithm, global extremum searching mechanism and global search strategy on simulated annealing. Finally,it uses numerical experiments to solve truck load balance problem with 10 compartments and 50 cases. Comparing with the traditional method,the improved algorithm has a high efficiency for the truck load balance problem.

improved ABC algorithm;truck load balancing problem;genetic algorithm;global search mechanism;simulated annealing strategy

2095-3852(2017)04-0484-04

A

2017-02-26.

付中华(1965-)，女，湖北随州人，武汉城市职业学院初等教育学院副教授,主要研究方向为数据挖掘.

马英钧(1987-)，男，河南南阳人，华中师范大学数统学院博士研究生，主要研究方向数据挖掘.

武汉市高教局教学研2014年度重点课题基金项目(2014035).

TP301.6

10.3963/j.issn.2095-3852.2017.04.021