基于免疫拉马克的道路洒水车路径问题优化

Solution of road sprinkler routing problem based on Lamarck immune algorithm

高效节能地完成道路洒水作业对改善城市环境、节约资源有着非常重要的意义.将道路洒水车路径问题转化为带容量约束的弧路径优化问题,并建立相应的数学模型.根据问题的NP难特性,提出了一种拉马克免疫算法进行求解.算法有效利用了免疫算法全局优化和拉马克学习局部搜索的优势;设计了适合问题求解的锦标赛选择法、顺序交叉法、自适应变异等免疫算子,并设计了拉马克局部搜索策略,避免算法陷入局部最优.实验结果表明,所提算法能得到代价最小的洒水路径.

It is very important to complete the road sprinkler operations efficiently and energy-saving,which improves the urban environment and saving resources.This problem was transformed into arc path optimization with capacity constraints,and the corresponding mathematical model was established.According to the NP,an immune algorithm was proposed to solve it.The tournament selection method,the sequential crossover method and the adaptive mutation were designed to solve the problem.The local search algorithm was designed to avoid the local optimum.The experimental results showed that the proposed algorithm could obtain the least cost sprinkler path.