A bio-inspired method for the constrained shortest path problem

Hongping Wang, Xi Lu, Xiaoge Zhang, Qing Wang, Yong Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

Abstract

The constrained shortest path (CSP) problem has been widely used in transportation optimization, crew scheduling, network routing and so on. It is an open issue since it is a NP-hard problem. In this paper, we propose an innovative method which is based on the internal mechanism of the adaptive amoeba algorithm. The proposed method is divided into two parts. In the first part, we employ the original amoeba algorithm to solve the shortest path problem in directed networks. In the second part, we combine the Physarum algorithm with a bio-inspired rule to deal with the CSP. Finally, by comparing the results with other method using an examples in DCLC problem, we demonstrate the accuracy of the proposed method.

Original languageEnglish
Article number271280
JournalScientific World Journal
Volume2014
DOIs
Publication statusPublished - 2014
Externally publishedYes

ASJC Scopus subject areas

  • Biochemistry, Genetics and Molecular Biology(all)
  • Environmental Science(all)

Cite this