Estimation of the Distribution Algorithm with a Stochastic Local Search for Uncertain Capacitated Arc Routing Problems

Juan WANG, Ke TANG, Jose A. LOZANO, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

66 Citations (Scopus)

Abstract

The uncertain capacitated arc routing problem is a challenging problem in which the demands of tasks, the costs of edges, and the presence of tasks and edges are uncertain. The objective of this problem is to find a robust optimal solution for a finite set of possible scenarios. In this paper, we propose a novel robust optimization approach, called an estimation of distribution algorithm (EDA) with stochastic local search (SLS), to tackle this problem. The proposed method integrates an EDA with a novel two phase SLS procedure to minimize the maximal total cost over a set of different scenarios. The SLS procedure avoids excessive fitness evaluations of unpromising moves in local search. Our experimental results on two sets of benchmark problems (a total of 55 problem instances) showed that the proposed approach outperformed existing state-of-the-art algorithms. © 1997-2012 IEEE.
Original languageEnglish
Article number7098374
Pages (from-to)96-109
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume20
Issue number1
Early online date30 Apr 2015
DOIs
Publication statusPublished - Feb 2016
Externally publishedYes

Bibliographical note

This work was supported in part by the 973 Program of China under Grant 2011CB707006, in part by the National Natural Science Foundation of China under Grant 61175065 and Grant 61329302.

Keywords

  • Estimation of Distribution Algorithm
  • Local Search
  • Robust Optimization
  • Uncertain Capacitated Arc Routing Problem;

Fingerprint

Dive into the research topics of 'Estimation of the Distribution Algorithm with a Stochastic Local Search for Uncertain Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this