求解带时间窗车辆路径问题的有效混合PBIL算法  

Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows

作　　者：孟祥虎[1,2] 胡蓉[1,2] 钱斌[1,2] 

机构地区：[1]昆明理工大学信息工程与自动化学院自动化系,昆明650500 [2]云南省计算机技术应用重点实验室,昆明650500

出　　处：《系统工程理论与实践》2014年第10期2701-2709,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(60904081);云南省中青年学术技术带头人后备人才项目(2012HB011);昆明理工大学学科方向建设项目(14078212);云南省计算机技术应用重点实验室开放基金项目

摘　　要：针对带时间窗车辆路径问题(vehicle routing problem with time windows,VRPTW),提出了混合种群增量学习算法(hybrid population-based incremental learning algorithm,HPBIL),用于同时最小化车辆数和总行驶距离.在HPBIL中,通过改进标准的PBIL概率模型以提高算法的全局探索能力,同时设计了基于插入法和两点邻域交换法的两阶段局部搜索来增强算法的局部开发能力.仿真实验和算法比较验证了HPBIL的有效性和鲁棒性.A hybrid population-based incremental learning algorithm, namely HPBIL, is proposed to simultaneously minimize the number of vehicles and total travel distance for the vehicle routing problem with time windows （VRPTW）. In the presented HPBIL, the improved probability model of PBIL is devised to enhance global exploration ability, and a two-phase local search based on the insert and two points neighborhood exchange methods is developed to strengthen local exploitation ability. Simulation resultsand comparisons with other algorithms demonstrate the effectiveness and robustness of HPBIL

关 键 词：种群增量学习算法 带时间窗车辆路径问题 概率模型 全局探索 局部开发 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]