带时间窗车辆路径问题的启发式遗传算法

Heuristic genetic algorithm of vehicle routing problem with time windows

为了在运输生产中按时间要求合理安排车辆路径,建立了带时间窗车辆路径问题数学模型,用启发式遗传算法进行求解。先构造染色体,产生初始群,再对其进行优化,根据个体生存能力的体现进行性能估计,并计算优化值。运用VisualBasic编写相应计算程序,设定迭代代数为100,运算次数为10次,对有时间窗限制的有1个中心仓库与8个分仓库的实际问题进行求解。模拟结果显示需要3辆车按照3条运输线路进行物流配送服务,总运行距离为483km,总运行时间为15.55h,车辆未出现闲置时间,且全部仓库得到及时服务。可见启发式遗传算法有效、可行。

In order to reasonably arrange vehicle routes according to time request in transportation production, a mathematical model for vehicle routing problem with time windows（VRPTW） was constructed, and a heuristic genetic algorithm was put forward to solve it. In the algorithm, chromosomes were constructed, initial groups were produced and optimized, their capability was estimated by the existent ability of individual, and the optimized value was computed. The number of evolving offspring is 100, operating time is 10, VRPTW with one center depot and eight branch depots was solved by correspond program. The result indicates that goods are distributed with three trucks in three routes, total distance is 483 km, total time is 15.55 h, there is no idle time for truck, and all warehouses are served on time. Obviously, the algorithm is effective and feasible. 1 tab, 3 figs, 11 refs.