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

Nasser R. Sabar, Ashish Bhaskar, Edward Chung, Ayad Turky, Andy Song

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1018-1027
Number of pages10
JournalSwarm and Evolutionary Computation
Volume44
DOIs
Publication statusPublished - Feb 2019

Keywords

  • Dynamic optimisation
  • Meta-heuristics
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this