带时间窗的车辆路由问题的改进遗传算法

提出了一种改进的遗传算法,使用了一种新的染色体编码方式,和与之对应的启发式交叉算子,同时采取了竞争选择的淘汰机制,通过对Solomon提出的100个点的标准算例的计算验证,证明了该算法能够很好地解决各类带时间窗的车辆路由问题,通过和混和遗传算法的比较,证明了该算法在计算时间、收敛速度上都有大的优势.该算法计算得到的解在总行驶距离相差不大的情况下使用车辆数较少.

An Improved Genetic Algorithm(GA) for Vehicle Routing Problem with Time Windows

An improved GA for vehicle routing problem with time windows was presented in this paper.A new kind of chromosome coding and the new crossover operator corresponding to it were applied,with the tournament selection.The new GA was checked by the Solomon's 100-customer instances.Through the comparison with the hybrid genetic algorithm,not only was it proved to be a valid method to solve the vehicle routing problem with time windows,but also had better performance in computing time and speed of convergence.The solutions computed by the improved GA have total moving distance close to the hybrid genetic algorithm,but at the same time use less vehicles.