交叉变异蚁群算法在VRP问题中的应用研究

《交叉变异蚁群算法在VRP问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用2009，45（34）201交叉变异蚁群算法在VRP问题中的应用研究张锦1，2，李伟1，费腾11，2，LIWei1，FEITeng1ZHANGJin1.太原理工大学信息工程学院，太原0300242.山西医科大学第一附属医院设备处，太原0300231.CollegeofInformationEngineering，TaiyuanUniversityofTechnoloy，Taiyuan030024，China2.OfficeofEquipment，FirstHo

2、spitalofShanxiUniversityofMedicine，Taiyuan030023，ChinaE-mail：zhangjin_taiyuan@126.comZHANGJin，LIWei，FEITeng.ApplicationresearchofVRPbasedoncrossmutationantcolonyalgorithm.ComputerEngineeringandApplications，2009，45（34）：201-203.Abstract：Animprovedandcolonyalgorithmisproposed.

3、Geneticalgorithmisutilizedtooptimizetheparametersofantcolonyalgorithm.TheimprovedalgorithmisusedtosolvetheoptimizationroutingofthebasicVRP.Thealgorithmpossessessomecharacteristicssuchasstrongtotalresearchingability.Theexperimentalresultsshowthattheimprovedantcolonyalgorithm

4、possessesbetteroptimizationquantityandeffectthanthetraditionalantcolonyalgorithm.Keywords：antcolonyalgorithm；geneticalgorithm；vehicleroutingproblem；routingoptimization摘要：提出一种改进的蚁群算法，新算法利用遗传算法对蚁群算法的参数进行优化，然后利用新的蚁群算法求解基本的车辆路径问题。改进的蚁群算法具有全局搜索能力强的特点，仿真结果表明，新算法的优化质量和效率都优于传统蚁群算法。

5、关键词：蚁群算法；遗传算法；车辆路径问题；路径优化DOI：10.3778/j.issn.1002-8331.2009.34.063文章编号：1002－8331（2009）34-0201-03文献标识码：A中图分类号：TP391.91引言既要满足需求点货物量的要求，又要使配送成本最小。设有一蚁群算法（AntColonyAlgorithm，ACA）是一种概率搜索算个拥有载重量为q的车辆m辆的配送中心。在其周边共有L法，它利用信息激素为媒介进行间接的信息传递，蚂蚁根据信个地点需要送货上门，该问题转化为求出这L个点的排列顺息素的强度做出对较优解的判断

6、选择，蚁群的群体行为表现出序。在该顺序下，将L个点分成m（′m′≤m）个组合，每个组合表一种信息正反馈现象，即当算法迭代时，较优解的信息素浓度示一辆车完成一次货物运送任务，使得总的配送成本最小。增强，而其他解上信息素浓度变弱[1-2]。蚁群算法最早由意大利基本假设条件学者M.Dorigo等人[3]提出，并应用其成功求解了旅行商问题，（1）配送中心所对应的需求点以及每个需求点的需求量为取得了较好的结果。因此蚁群算法逐渐引起了其他学者的注已知。意，逐渐对其进行改进研究并应用于不同领域。（2）需求点相互之间以及需求点与配送中心的连接关系和车辆路径问

7、题是运筹学领域的一大类重要问题，是实现高距离已知。每个需求点只有一辆车并且只能服务一次。效配送的重要技术之一。它适用于牛奶配送、报纸投递、垃圾车（3）每辆车由配送中心发出，最后又回到配送中心。车辆的的线路优化及连锁商店的送货线路优化等众多社会领域。基本最大容量已知。的蚁群算法中参数的选择影响算法的收敛速度和寻优性能。为（4）车辆的平均行驶速度已知且确定，行驶的路程与车辆了改进蚁群算法的性能，文中首先利用遗传算法优化蚁群算法行驶时间成正比。在上述假设的前提下，构造数学模型如下[4]：的控制参数，进而选择最优的控制参数的蚁群算法求解车辆路LLm′

8、径问题。实验结果表明改进的蚁群算法具有较快的收敛能力和minZ=m′c+ΣΣΣcijkdijxijk（1）良好的寻优性能。i=1j=1k=1约束条件L2车辆路径问题