求解动态需求车辆调度问题的自适应量子遗传算法  

Self-adaptive quantum genetic algorithm for dynamic vehicle scheduling problem

作　　者：郑丹阳[1] 毛剑琳[1] 郭宁[1] 曲蔚贤 王昌征 

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500

出　　处：《传感器与微系统》2017年第8期130-133,共4页Transducer and Microsystem Technologies

基　　金：国家自然科学基金资助项目(61163051);云南省应用基础研究基金资助项目(2009ZC050M)

摘　　要：针对物流配送过程中存在的动态车辆调度问题,即带载车量约束的实时优化车辆路径问题,提出一种自适应量子遗传算法,用于最小化配送成本。根据搜索点目标函数的变化率,提出一种自适应量子旋转门更新方式,并通过子种群适应度值的变化确定量子旋转角的方向和大小,进而引导种群进化方向,提高算法的全局搜索广泛性;设计了一种变异操作,用于保持自适应量子遗传算法的种群多样性,进而提高算法全局搜索的宽泛性;引入基于两元素搜索原则的局部搜索方法来增强算法的局部优化能力。仿真实验和算法比较验证了所提算法的有效性和优越性。Aiming at dynamic vehicle scheduling problem that is dynamic vehicle routing problem（ DVRP） with vehicle capacity constraints in real time existed in process of logistics distribution,self-adaptive quantum genetic algorithm（ SAQGA） is proposed to minimize the distribution cost. According to change rate of search point target functions,a new update mode adaptive quantum rotation gate is presented,and direction and magnitude of the quantum rotating angle is determined by changes in fitness values of sub-propulation,thus evolutionary direction of population is guided to improve depth of global search of algorithm. A mutation operation is designed to keep the population diversity of the self-adaptive quantum genetic algorithm and width of the global search of algorithm is improved. To enhance the local optimization ability,local search method based on the principle of two elements search is introduced. Simulation experiments and algorithm comparisons demonstrate the effectiveness and the superiority of the proposed algorithm.

关 键 词：物流配送 自适应量子遗传算法 动态车辆路径问题 全局搜索 局部优化 

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