改进类电磁算法在车辆调度问题中的应用

摘　要：摘要：车辆调度问题（VRP）属于组合优化问题，也属于NP难问题，用传统方法来解决车辆调度问题，通常会耗费大量时间，甚至不能找到最优解。Birbil和Fang受电磁场中带电粒子间吸引排斥机制的启发，提出了类电磁机制算法（EM）[1]，EM算法能够避免搜索粒子陷入局部最优，并朝全局最优移动，本文对原始EM算法作了改进，应用其求解VRP问题。

关键词：关键词：类电磁机制算法；车辆调度；合力计算

中图分类号：TP301      文献标识码：A      文章标识码：

    0．引言
    车辆调度问题是物流管理和智能交通的核心问题，一直是研究的热点，许多方法被用于VRP问题研究，类电磁机制算法具有全局优化能力强，编程简单，收敛性好等优点，广泛应用于函数优化[2]、水电站经济运行问题[3]和武器目标分配问题[4]等研究，取得了较好效果，本文将改进的EM算法应用于求解VRP问题，并与原始EM算法进行仿真对比。
    1．EM算法介绍
    EM算法模拟电磁场中吸引和排斥机制，将每个解比作一个带电粒子，每个粒子的电荷由待优化的目标函数的函数值决定，电荷值也决定了该粒子对其他粒子的吸引或排斥的强弱，目标函数值越优，吸引越强。
    以如下形式的非线性、无约束（变量有界）的优化问题为例，具体介绍EM算法的四个基本步骤[5]：

    5．结束语
    降低车辆运输成本，是物流运输企业提高企业竞争力的有效途径之一，而鉴于传统方法的效率不高，将EM算法引入车辆调度问题的研究是一个新的领域。从前面仿真结果可看出，虽然改进后的EM算法性能得到优化，但与已知最优还存在差距，总的来说，当前对EM算法的研究还不十分成熟，有很多方面需要继续探讨，比如针对特定问题继续改进电量、合力计算方式，与其他种类算法进行混合研究以及将EM算法并行化等。

参考文献：
[1]Birbil S I, S C Fang. An Electromagnetism-like Mechanism for Global Optimization [J]. Journal of Global Optimization, 2003, 25:263-282.
[2]韩丽霞，王宇平．求解无约束优化问题的类电磁机制算法[J]．电子学报，2009，37（3）：664-668．
[3]张智晟，龚文杰，段晓燕，等．类电磁机制算法在水电站厂内经济运行的应用研究[J]．电工电能新技术，2011，30（4）：17-20．
[4]杨晓凌，邱涤珊，彭黎，等．改进类电磁算法在武器目标分配问题中的应用[J] ．国防科技大学学报，2011，33（6）：150-153．
[5]王晓娟，高亮，陈亚洲．类电磁机制算法及其应用[J]．计算机应用研究，2006，23（6）：67-70．

附项目基金：
国家自然科学基金项目（61074147，60374062）；广东省自然科学基金项目（S2011010005059）；广东省教育部产学研结合项目（2011B090400460）；广东省自然科学基金团队项目（8351009001000002）。