改进蚁群算法优化周期性车辆路径问题

摘要

周期性车辆路径问题（PVRP）是标准车辆路径问题（VRP）的扩展，PVRP将配送期由单一配送期延伸到T（ T＞1）期，因此，PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题，其比标准VRP问题更加复杂，难于求解。本文采用蚁群算法对PVRP进行求解，并提出采用两种改进措施---多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后，通过9个经典PVRP算例对该算法进行了数据实验，结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的，同时也表明两种改进措施可以显著提高算法的性能。%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 .