论文部分内容阅读
车辆路径问题(Vehicle Routing Problem,VRP)是对一系列己知需求量的客户,组织适当的行车线路进行服务,在不违反约束条件下,优化路线使总成本最小。有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)因其重要的现实意义备受关注,所谓时间窗即客户接受服务的时间范围。由于车辆路径问题是典型的NP难题,传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向。本文重点研究了基于混合遗传算法求解有时间窗车辆路径问题。详细分析了VRPTW的特点,界定了所研究VRPTW的基本条件,建立了相应的数学模型。根据特定的时间窗、车辆容量等条件约束,设计了VRPTW的遗传算法(Genetic Algorithm,GA)。通过对遗传算法、禁忌搜索算法(Tabu Search,TS)及模拟退火算法(Simulated Annealing,SA)的分析比较,以遗传算法为框架,融合其它两者,提出了用于VRPTW的混合遗传模拟退火算法(Genetic-SimulatedAnnealing Algorithm,GSA)及混合遗传禁忌搜索模拟退火算法(Genetic-TabuSearch-Simulated Annealing Algorithm,GTSA)。在GSA中,将模拟退火算法的Metropolis规则应用到GA的交叉操作中,让GA能够同时接收较优解和劣解,使得父代个体也参加竞争,这样不但避免了GA陷入局部最优,同时又消除了基本遗传算法由于无选择的接收新解而可能会出现的随机搜索现象;在GTSA中,把TS引入到GA的复制操作中产生新的个体,使得遗传算法中每代个体具有尽可能的多样性,从而避免了GA陷入局部最优而出现“早熟”现象,在遗传操作产生新的种群后,对新种群使用SA,以大大增加接受较优解的概率,进而提高GA的收敛性能,加速了算法的收敛。通过实例,用MATLAB编程实现了所提出的GA、GSA、GTSA三种算法,并对三者性能作了比较。可以得出,所设计的混合遗传模拟退火算法和混合遗传禁忌搜索模拟退火算法具有良好的搜索能力及计算效率,算法性能稳定、可靠。