改进遗传算法对带服务时间约束的弧路径问题的求解  

An Improved Genetic Algorithm for Arc Routing Problem with Service Time Constraint

作　　者：徐凯[1] 朱征宇[1] 

机构地区：[1]重庆大学,重庆400044

出　　处：《微处理机》2010年第5期58-62,共5页Microprocessors

基　　金：国家科技支撑计划项目(0216002343012)

摘　　要：弧路径问题(ARP)出现在一些需要对路径进行服务的应用中,在此类应用中精确的求解算法只能应用于小规模的问题,在大规模的应用中只能借助于启发式算法才能得到求解。介绍了一种改进的遗传算法对于含有限制条件如服务时间约束的ARP问题的求解,该算法改进了种群结构和染色体的组织模型,设计了几个简单而高效的进化算子,较好地避免了在迭代过程中出现的早熟收敛。并通过实验表明了算法求解问题的有效性。The Arc Routing Problem（ARP） appears on the applications where it is the routes not the spots that need to be serviced.In such applications,exact algorithms can only be applied to small-scale problems,however large-scale applications can only be solved by heuristic algorithms.This paper introduces an improved genetic algorithm（GA） to solving the ARP problems including constraints such as time window.This algorithm improves the population structure and chromosome organization model and designs a few simple and efficient evolutionary operators to avoid premature convergence occurred in the course.

关 键 词：遗传算法 进化算子 服务时间约束 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]