大规模客户车辆调度问题启发式算法研究

Heuristic Method for Vehicle Routing Problem with Large Scale Customers

为进一步扩大车辆优化调度问题的研究规模,将最佳客户插入原则(PFIH-Push Forward Insertion Heuristic)与遗传算法相结合,解决了以往初始种群中可行解概率低等问题;并实现了以路径首客户编码方式代替传统的全部客户编码,缩短了染色体长度,从而提高了遗传算法优化大规模客户车辆调度问题的效率。将该方法应用于有时间窗车辆调度问题,并采用Solomon数据验证,通过与其它算法结果比较,说明了该方法的可行性与优越性。

In order to enlarge the customer scale of vehicle routing problem, the Push Forward Insertion Heuristic and Genetic Algorithm were combined which solved the problem of low probability of feasible solution in initializing swarm. Furthermore, the conventional code was replaced by the code which was made up of first-customers in all routes of an individual, which shortened the length of chromosome and improved the efficiency of Genetic Algorithm in solving large scale vehicle routing problem. The combined algorithm to the data defined by Solomon, the performances prove the feasibility and efficiency of this algorithm.