多约束条件车辆路径问题的二阶段遗传退火算法  

Two-Phase Genetic-Annealing Algorithm for Vehicle Routing Problem with Multiple Constraints

作　　者：吕军[1] 冯博琴[1] 李波[1] 

机构地区：[1]西安交通大学电子与信息工程学院,西安710049

出　　处：《西安交通大学学报》2005年第12期1299-1302,共4页Journal of Xi'an Jiaotong University

基　　金：国家高技术研究发展计划资助项目(2003AA001048)

摘　　要：针对多约束条件的多配送中心有时间窗车辆路径问题,提出了一种二阶段遗传退火算法.在第1阶段,使用遗传算法对客户按供应量和路径长度进行模糊分区;在第2阶段,采用二维变长染色体编码及相应的遗传算子进行混合遗传算法的全局优化.在初始种群生成和交叉、变异算子中采用了随机贪心算法以避免无效解,并利用退火选择来提高种群的多样性.实验结果表明,二阶段遗传退火算法可加速收敛,提高搜索效率,在模糊分区上的搜索速度较之标准遗传算法提高了3～10倍.A novel two-phase genetic-annealing algorithm is proposed to solve the vehicle routing problem with time window （MDVRPTW） and multi-constraint in multiple dispatching centers. In the first phase, users are partitioned into fuzzy regions according to quantity supplied and the length of paths using genetic algorithm; in the second phase the global optimization is carried out by the hybrid genetic algorithm with 2D variable-length chromosomes and corresponding genetic operators. The random greedy algorithm is used in generating of initial population and crossover and mutation operator to avoid invalid solution, then the simulated annealing algorithm is employed to enhance the diversity of population. The experimental results show that compared with the traditional genetic algorithm the search speed of the proposed algorithm is 3410 times faster, the convergence is speed up, and search efficiency is increased.

关 键 词：车辆路径 遗传退火算法 贪心算法 

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