洗扫车路径规划问题及求解算法  

Path Planning Problem and Solving Algorithm for Cleaning and Wweeping Vehicles

作　　者：郑城钦 王剑[1] ZHENG Chengqin;WANG Jian(School of Automation,Hangzhou Dianzi University,Hangzhou 310018,China)

机构地区：[1]杭州电子科技大学自动化学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2024年第4期70-79,共10页Journal of Hangzhou Dianzi University：Natural Sciences

摘　　要：洗扫车路径规划问题是一类容量约束弧路径问题(CARP),具有NP-hard性质。为了提升求解CARP的能力,本文提出一种模拟退火算法与混合遗传算法的结合算法,简称为模拟退火混合遗传算法(SAHGA)。该算法在混合遗传算法中的局部搜索操作之后加入模拟退火算法的思想,在一定程度上优化了算法在洗扫车优化调度中求解能力。同时改进算法中的选择算法,使用更加有效的锦标赛算法。使用标准CARP算例集进行了测试,并给出了改进算法与传统混合遗传算法和其他启发式算法的效果比较。结果表明,SAHGA改进效果明显,是有效的求解CARP的方法。使用算法对杭州电子科技大学周边街道的洗扫车规划问题进行求解,验证了算法的可靠性。Sweeper path planning problem is a class of capacitated arc routing problem(CARP)with NP-hard property.In order to improve the ability to solve the problem,this paper proposes a combination algorithm of simulated annealing and hybrid genetic algorithm,referred to as simulated annealing hybrid genetic algorithm(SAHGA).The algorithm adds the idea of simulated annealing algorithm after the local search operation in the hybrid genetic algorithm,thus improving the capability of solving the optimal solution of the sweeper truck scheduling.At the same time,the selection algorithm in the algorithm is improved by using a more effective tournament.Tests were carried out using the standard CARP sets,and comparisons of the effectiveness of the improved algorithm with the traditional hybrid genetic algorithm and other heuristic methods are given.The results show that the simulated annealing hybrid genetic algorithm performs better than the original hybrid genetic algorithm in some of the arithmetic cases,and is an effective method for solving CARP.Finally,the algorithm is applied to a specific street sweeping problem around the Hangzhou Dianzi University campus,which verifies the reliability of the algorithm.

关 键 词：容量约束弧路径问题 模拟退火算法 混合遗传算法 锦标赛算法 

分 类 号：U409[交通运输工程—道路与铁道工程]