A Competitive Co-evolutionary Optimization Method for the Dynamic Vehicle Routing Problem

In the basic vehicle routing problem, the best routes need to be found for a fleet of vehicles to serve a set of customers. The dynamic vehicle routing problem is a variant of the vehicle routing problem, in which part or all the information defining the routing problem might change over time. This requires an optimizer to perform a fast search of new routes once the change happens. For its robustness with respect to noise, evolutionary algorithms have shown great potential for the dynamic vehicle routing problem. However, the existing evolutionary methods only evolve a population of solutions online for the ever-changing problem, which might not be very efficient. In this work, we propose a new evolutionary method which combines offline computation and online optimization to solve the dynamic vehicle routing problem. It first searches for a set of good solutions for possible environmental changes in an offline way, and then searches for the new optimal solution online for the ever-changing problem through doing local search on this solution set. Competitive co-evolution is applied to search for the solution set in the proposed method. Experimental study has been conducted on one dynamic vehicle routing benchmark with the change of customers' demands. The experimental results show the efficiency of the proposed method.