论文部分内容阅读
【摘 要】本文通过对免疫克隆算法的研究提出一种垃圾收集车辆路径优化方案，并进行仿真实验和分析。
【关键词】垃圾收集 免疫克隆算法 路径优化
1 车辆调度问题
车辆调度问题（VRP）是由Dantzig和Rmaser提出来的，指的是考虑车辆装载能力、车辆最大行驶距离等因素的前提下，根据顾客的需求，确定车辆的行驶路线，以总费用最低为目标，追求经济效益的最大化和实现过程的最优化。如果把顾客看成一个对象，顾客所在的固定位置看成是节点，车辆调度问题可以描述为：求解在服务车辆有最大载重量和最大行驶距离的前提下，使得车辆对每一个节点的对象都能访问、并且只能访问一次的最短行程的派车方案。
2 免疫遗传算法
生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法（Genetic Algorithms）就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。
3 免疫克隆算法解决问题的算法实现
本节采用免疫克隆算法，来解决CVRP问题。通过一个实例证明该算法具有很好的全局和局部收敛能力，并且收敛速度快等特点。下面详细说明免疫克隆算法求解CVRP问题步骤。步骤1：抗体编码。本文采用简单直观的自然数编码方法，用0表示垃圾中转中心，用1，2，…，L表示各收集点。由于在垃圾中转中心有K辆汽车，则最多存在K条收集路径，每条收集路径都始于收集中心，也终于垃圾中转中心。为了在编码中反映车辆收集的路径，采用了增加K+1个虚拟垃圾中转中心的方法，分别用L+1、L+2、…、L+K-1表示。这样1，2，…，L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种收集路径方案。
4 数值实验与分析
假设有8个收集点和一个垃圾中转中心的垃圾收集系统，各个收集点的需求为（i= l，2，…，8），中转中心用两辆车（载重量为8）收集，收集点与收集中心的距离如表一所示。要求优化收集线路，使得收集成本最小化。
用基于克隆选择的免疫遗传算法对上述问题进行求解，变异率如果太小， 则產生新的染色体概率小，导致不成熟的收敛；太大，可能使优秀染色体的破坏机会增加， 甚至不能收敛， 应多次实验调整或者采用自适应方法调整变异率通过上机运算，得到的线路有：
路线1：0->4->2->6->0
路线2：0->3->7->5->8->1->0
运输总距离 = 83.5
通过分析，此方案是此问题的一个可行解。
表1 收集点间距离以及收集量
结语：本文垃圾收集中的路径最优化问题，提出了利用免疫算法求解该问题时存在的一些不足，通过改进此算法，增加了克隆选择的机制，有效的弥补了免疫遗传算法的不足。并通过较小规模的垃圾收集问题的仿真分析，得到了较好的效果。并且将这一理论思想应用到垃圾收集中转系统当中。不足之处：没有完全考虑到路径等因素对收集路径最优化问题影响，对系统的解决完全是建立在理想情况下的。
参考文献：
[1] 张震.城市货运汽车营运组织最优化的理论与方法.管理工程学报，Vol 9.No.3，P143-152.
[2] 蔡延光，钱积新，孙优贤.多重运输调度问题基于双表的并行表搜索算法.系统工程理论与实践，1998，Vol.18，No.1l，p20-26.
作者简介：
康彦（1982-），男，安徽合肥人，硕士，讲师，主要研究方向：计算机应用技术。
基金项目：
2013年高校省级自然科学研究项目“垃圾中转站HY1600-2型全封闭垃圾压缩机液压测控系统研制”（KJ2013Z011）
【关键词】垃圾收集 免疫克隆算法 路径优化
1 车辆调度问题
车辆调度问题（VRP）是由Dantzig和Rmaser提出来的，指的是考虑车辆装载能力、车辆最大行驶距离等因素的前提下，根据顾客的需求，确定车辆的行驶路线，以总费用最低为目标，追求经济效益的最大化和实现过程的最优化。如果把顾客看成一个对象，顾客所在的固定位置看成是节点，车辆调度问题可以描述为：求解在服务车辆有最大载重量和最大行驶距离的前提下，使得车辆对每一个节点的对象都能访问、并且只能访问一次的最短行程的派车方案。
2 免疫遗传算法
生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法（Genetic Algorithms）就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。
3 免疫克隆算法解决问题的算法实现
本节采用免疫克隆算法，来解决CVRP问题。通过一个实例证明该算法具有很好的全局和局部收敛能力，并且收敛速度快等特点。下面详细说明免疫克隆算法求解CVRP问题步骤。步骤1：抗体编码。本文采用简单直观的自然数编码方法，用0表示垃圾中转中心，用1，2，…，L表示各收集点。由于在垃圾中转中心有K辆汽车，则最多存在K条收集路径，每条收集路径都始于收集中心，也终于垃圾中转中心。为了在编码中反映车辆收集的路径，采用了增加K+1个虚拟垃圾中转中心的方法，分别用L+1、L+2、…、L+K-1表示。这样1，2，…，L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种收集路径方案。
4 数值实验与分析
假设有8个收集点和一个垃圾中转中心的垃圾收集系统，各个收集点的需求为（i= l，2，…，8），中转中心用两辆车（载重量为8）收集，收集点与收集中心的距离如表一所示。要求优化收集线路，使得收集成本最小化。
用基于克隆选择的免疫遗传算法对上述问题进行求解，变异率如果太小， 则產生新的染色体概率小，导致不成熟的收敛；太大，可能使优秀染色体的破坏机会增加， 甚至不能收敛， 应多次实验调整或者采用自适应方法调整变异率通过上机运算，得到的线路有：
路线1：0->4->2->6->0
路线2：0->3->7->5->8->1->0
运输总距离 = 83.5
通过分析，此方案是此问题的一个可行解。
表1 收集点间距离以及收集量
结语：本文垃圾收集中的路径最优化问题，提出了利用免疫算法求解该问题时存在的一些不足，通过改进此算法，增加了克隆选择的机制，有效的弥补了免疫遗传算法的不足。并通过较小规模的垃圾收集问题的仿真分析，得到了较好的效果。并且将这一理论思想应用到垃圾收集中转系统当中。不足之处：没有完全考虑到路径等因素对收集路径最优化问题影响，对系统的解决完全是建立在理想情况下的。
参考文献：
[1] 张震.城市货运汽车营运组织最优化的理论与方法.管理工程学报，Vol 9.No.3，P143-152.
[2] 蔡延光，钱积新，孙优贤.多重运输调度问题基于双表的并行表搜索算法.系统工程理论与实践，1998，Vol.18，No.1l，p20-26.
作者简介：
康彦（1982-），男，安徽合肥人，硕士，讲师，主要研究方向：计算机应用技术。
基金项目：
2013年高校省级自然科学研究项目“垃圾中转站HY1600-2型全封闭垃圾压缩机液压测控系统研制”（KJ2013Z011）