A novel hybrid ant colony optimization algorithm for emergency transportation problems during post-disaster scenarios

Xinyu Wang, Tsan Ming Choi, Haikuo Liu, Xiaohang Yue

Research output: Journal article publicationJournal articleAcademic researchpeer-review

37 Citations (Scopus)

Abstract

The increasing impacts of natural disasters have led to concerns regarding predisaster plans and post-disaster responses. During post-disaster responses, emergency transportation is the most important part of disaster relief supply chain operations, and its optimal planning differs from traditional transportation problems in the objective function and complex constraints. In disaster scenarios, fairness and effectiveness are two important aspects. This paper investigates emergency transportation in real-life disasters scenarios and formulates the problem as an integer linear programming model (called cum-MDVRP), which combines cumulative vehicle routing problem and multidepot vehicle routing problem. The cum-MDVRP is NP-hard. To solve it, a novel hybrid ant colony optimization-based algorithm is proposed by combining both saving algorithms and a simple two-step 2-opt algorithm. The proposed algorithm allows ants to go in and out the depots for multiple rounds, so we abbreviate it as ACOMR. Moreover, we present a smart design of the ants' tabus, which helps to simplify the solution constructing process. The ACOMR could yield good solutions quickly, then the decision makers for emergency responses could do expert planning at the earliest time. Computational results on standard benchmarking data sets show that the proposed cum-MDVRP model performs well, and the ACOMR algorithm is more effective and stable than the existing algorithms.

Original languageEnglish
Pages (from-to)545-556
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume48
Issue number4
DOIs
Publication statusPublished - 1 Apr 2018

Keywords

  • Ant colony optimization (ACO)
  • cumulative multidepot vehicle routing problem (cum-MDVRP)
  • emergency transportation
  • fairness and efficiency
  • integer linear programming

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this