关键词: 周期性车辆路径问题, 蚁群算法, 多维信息素, 扫描法

Abstract: Period Vehicle Routing Problem(PVRP)is a generalized classic vehicle routing problem(VRP), in which the planning period is extended to a t-day period. Therefore, custom group and route should be optimized every day in PVRP. Embedded in VRP, PVRP is too complicated to be solved. As many route operations are formulated in a certain period, PVRP is very popular in practice. In recent years, distribution centers have paid much attention to the problem of vehicle delivery with the growing fuel cost and fierce supply chain competition. Especially in some situations, vehicles have to serve some fixed customers in a given period, and besides, the service times of each customer are settled in advance. Optimization of the repetitive operations will significantly save cost. Many researches have shown that the heuristic method based on the simulation of biological is very suitable for solving large-scale combinatorial optimization problem. Ant colony optimization(ACO)is founded on the behavior of ant colony foraging in nature, which has been proved to be feasibility for solving VRP problems in lots of research. Therefore, this paper presents an improved ant colony optimization(IACO), in which a multi-dimension pheromone matrix and a local optimization strategy based on scanning method are introduced. To test the two strategies for IACO, this paper designs four groups of contrast tests, in which ACO+SP,ACO+MP,ACO+MPB and IACO are used when optimizing the period vehicle routing problem in 9 classical examples. The results show that the two strategies can improve the performance of ACO effectively and IACO is an effective tool for PVRP. Besides, after comparing the results of IACO, CGW algorithm and CGL algorithm, IACO is proved to be effective method in simple optimization problems.

Key words: period vehicle routing problem, ant colony optimization, multi-dimension pheromone, scanning method