Robust Optimization in Uncertain Capacitated Arc Routing Problems: Progresses and Perspectives [Review Article]

Jialin LIU, Ke TANG, Xin YAO

Research output: Journal PublicationsReview articleOther Review

14 Citations (Scopus)

Abstract

The capacitated arc routing problem is an important NP-hard problem with numerous realworld applications. The capacitated arc routing problem with uncertainties refers to those instances where there are uncertainties in decision variables, objective functions and/or constraints. The capacitated arc routing problem with uncertainties captures real-world situations much better than a static capacitated arc routing problem because few real-world problems are static and certain. Uncertainties in the capacitated arc routing problem pose new research challenges. Algorithms that work well for a static and certain capacitated arc routing problem may not work on the version with uncertainties. There have been increasing progresses in studying the capacitated arc routing problem with uncertainties during the past two decades. However, the papers on the capacitated arc routing problem with uncertainties have been scattered around in different journals and conferences in artificial intelligence, computer science, and operational research. Different definitions and formulations of capacitated arc routing problem with uncertainties are used by different papers, making comparisons difficult. In order to better understand the state-of-the-art in solving the capacitated arc routing problem with uncertainties, this paper presents a comprehensive review of the problem and its key research issues. Not only has the paper summarized the progresses so far, key research issues are identified, including scalability of the algorithms, performance measures, common benchmarks, etc. Future research directions are also identified at the end of this review. © 2021 Institute of Electrical and Electronics Engineers Inc.. All rights reserved.
Original languageEnglish
Article number9321764
Pages (from-to)63-82
Number of pages20
JournalIEEE Computational Intelligence Magazine
Volume16
Issue number1
Early online date20 Jan 2021
DOIs
Publication statusPublished - Feb 2021
Externally publishedYes

Fingerprint

Dive into the research topics of 'Robust Optimization in Uncertain Capacitated Arc Routing Problems: Progresses and Perspectives [Review Article]'. Together they form a unique fingerprint.

Cite this