带硬时间窗车辆路线问题的混合遗传启发式算法

Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows

为了提高物流配送效率,建立了集货和配送一体化的带硬时间窗的车辆路线问题的数学模型,提出了混合遗传启发式算法,并对模型进行了求解。采用改进节约法与随机法相结合的手段构造了初始解群体以增加解的多样性,对遗传算法中较优的一部分染色体进行了禁忌搜索以使搜索更容易跳出局部最优,同时加快搜索初期的搜索速度。仿真计算结果表明:混合遗传启发式算法具有更好的适应性,采用改进交叉算子使解的精度提高11.0%;在宽时间窗情形下采用倒位变异可使解的精度提高11.6%。

In order to improve the efficiency of logistics distribution, a mathematic model of vehicle routing problem with pickups, deliveries and hard time-windows was set up, and a hybrid-genetic-heuristic algorithm is designed to solve the model. In the algorithm, improved C-W method and random producing method were used to produce the initial group of solutions to increase its varieties, and the tabu search was used for some better chromosomes of genetic algorithm to avoid local optimization and increase search beginning speed. Simulation result shows that the algorithm has better adaptability, the solution＇s precision is improved by 11.0% when improved cross operator is used, and the solution＇s precision is improved by 11.6%o when reversed variation tactic is used under big time-windows condition. 5 tabs, 3 figs, 14 refs.