An adaptive amoeba algorithm for constrained shortest paths

Xiaoge Zhang, Yajuan Zhang, Yong Hu, Yong Deng, Sankaran Mahadevan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)

Abstract

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.

Original languageEnglish
Pages (from-to)7607-7616
Number of pages10
JournalExpert Systems with Applications
Volume40
Issue number18
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Adaptive amoeba algorithm
  • Constrained shortest path
  • Lagrangian relaxation
  • Optimization

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Cite this