A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion

Abstract

The Dynamic Vehicle Routing Problem (DVRP) is a complex variation of classical Vehicle Routing Problem (VRP). The aim of DVRP is to find a set of routes to serve multiple customers at minimal total travelling cost while the travelling time between point to point may vary during the process because of factors like traffic congestion. To effectively handle DVRP, a good algorithm should be able to adjust itself to the changes and continuously search for the best solution under dynamic environments. Because of this dynamic nature of DVRP, evolutionary algorithms (EAs) appear highly appropriate for DVRP as they search in a parallel manner with a population of solutions. Solutions scattered over the search space can better capture the dynamic changes. Solutions for new changes are not built from scratch as they can inherit problem-specific knowledge from parent solutions. However, the performance of EA is highly dependent on the utilised configuration. To address this issue, we propose a self-adaptive EA for DVRP. The proposed EA evolves a set of configurations including parameter values, operator types, combination of operators and order of operator invocation. The configurations are then encoded into DVRP solutions. So the search can use different configuration during a search process to effectively handle the dynamic changes and guide the search process towards promising areas. Two well known routing problems with traffic congestion, vehicle routing and the travelling salesman, were used to evaluate the performance of the proposed EA. The results demonstrate that under same conditions on both problems the proposed self-adaptive EA is better than standard EA and other algorithms from literature.