A Bio-Inspired Method for the Constrained Shortest Path Problem. (14th May 2014)

• Record Type: Journal Article
• Authors: Wang, Hongping; Lu, Xi; Zhang, Xiaoge; Wang, Qing; Deng, Yong
• Other Names: Lee Wen-Chiung Academic Editor.
• Is Part Of: TheScientificWorldjournal. Volume 2014(2014)
• Publication Date: 2014-05-14
• Subjects: Science -- Periodicals; Technology -- Periodicals; Medicine -- Periodicals; 505
• DOI: 10.1155/2014/271280
• Languages: English
• ISSNs: 2356-6140

Abstract

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.