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. © 2020 IEEE.
|Title of host publication
|2020 IEEE Symposium Series on Computational Intelligence, SSCI 2020
|Institute of Electrical and Electronics Engineers Inc.
|Number of pages
|Published - 1 Dec 2020
- Competitive co-evolution
- Dynamic optimization
- Dynamic vehicle routing problem
- Evolutionary algorithms