灾变遗传算法求解带时间窗的车辆调度问题  

Cataclysm genetic algorithm for solving vechicle scheduling problem with time windows

作　　者：肖世昌[1] 孙树栋[1] 国欢 

机构地区：[1]西北工业大学机电学院,西安710072

出　　处：《计算机应用研究》2014年第12期3568-3571,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(51075337)

摘　　要：提出一种可以有效求解带时间窗的车辆调度问题的灾变遗传算法。遗传算法作为一种高效的启发式算法被用于解决这类组合优化问题,但是该算法存在过早收敛、易陷入局部最优等缺陷。针对此问题,在搜索过程中采用灾变算子使遗传算法跳出局部最优,并针对车辆调度问题设计一种可以直接产生可行解的交叉算子,避免染色体交叉过程中产生不可行的子代。通过仿真算例验证了所提出的算法求解带时间窗的车辆调度问题的有效性;通过与标准遗传算法、改进遗传算法和粒子群算法的比较,进一步验证了灾变遗传算法在优化性能以及算法鲁棒性方面的优势。This paper proposed a new cataclysm genetic algorithm for the VSP with time window constraints,and then adopted genetic algorithm（ GA）,an efficient heuristic algorithm,to solve this kind of combinatorial optimization problem. However,GA had the drawbacks of premature convergence and easy to fall into local optimum. To solve this problem,it adopted cataclysm operator in the searching process to guarantee the GA jump out of local optimum. To avoid the infeasible offspring in the cross process of the chromosome,it designed a crossover operator which could generate the feasible solution directly focused on this VSP. In the end,according to the computational simulation,it verified the effectiveness of the proposed algorithm in solving the VSP with time windows. Through the comparison of the results obtained with the benchmark GA,the modified GA and the particle swam optimization（ PSO）,verifying that the catastrophe genetic algorithm is robust and can obtain superior optimization performance.

关 键 词：车辆调度问题 灾变算子 遗传算法 时间窗 

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]