A Bio-Inspired Method for the Constrained Shortest Path Problem

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 amoe...

Descripción completa

Detalles Bibliográficos
Autores principales: Wang, Hongping, Lu, Xi, Zhang, Xiaoge, Wang, Qing, Deng, Yong
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4052047/
https://www.ncbi.nlm.nih.gov/pubmed/24959603
http://dx.doi.org/10.1155/2014/271280
_version_ 1782320176456269824
author Wang, Hongping
Lu, Xi
Zhang, Xiaoge
Wang, Qing
Deng, Yong
author_facet Wang, Hongping
Lu, Xi
Zhang, Xiaoge
Wang, Qing
Deng, Yong
author_sort Wang, Hongping
collection PubMed
description 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.
format Online
Article
Text
id pubmed-4052047
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-40520472014-06-23 A Bio-Inspired Method for the Constrained Shortest Path Problem Wang, Hongping Lu, Xi Zhang, Xiaoge Wang, Qing Deng, Yong ScientificWorldJournal Research Article 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. Hindawi Publishing Corporation 2014 2014-05-14 /pmc/articles/PMC4052047/ /pubmed/24959603 http://dx.doi.org/10.1155/2014/271280 Text en Copyright © 2014 Hongping Wang et al. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Wang, Hongping
Lu, Xi
Zhang, Xiaoge
Wang, Qing
Deng, Yong
A Bio-Inspired Method for the Constrained Shortest Path Problem
title A Bio-Inspired Method for the Constrained Shortest Path Problem
title_full A Bio-Inspired Method for the Constrained Shortest Path Problem
title_fullStr A Bio-Inspired Method for the Constrained Shortest Path Problem
title_full_unstemmed A Bio-Inspired Method for the Constrained Shortest Path Problem
title_short A Bio-Inspired Method for the Constrained Shortest Path Problem
title_sort bio-inspired method for the constrained shortest path problem
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4052047/
https://www.ncbi.nlm.nih.gov/pubmed/24959603
http://dx.doi.org/10.1155/2014/271280
work_keys_str_mv AT wanghongping abioinspiredmethodfortheconstrainedshortestpathproblem
AT luxi abioinspiredmethodfortheconstrainedshortestpathproblem
AT zhangxiaoge abioinspiredmethodfortheconstrainedshortestpathproblem
AT wangqing abioinspiredmethodfortheconstrainedshortestpathproblem
AT dengyong abioinspiredmethodfortheconstrainedshortestpathproblem
AT wanghongping bioinspiredmethodfortheconstrainedshortestpathproblem
AT luxi bioinspiredmethodfortheconstrainedshortestpathproblem
AT zhangxiaoge bioinspiredmethodfortheconstrainedshortestpathproblem
AT wangqing bioinspiredmethodfortheconstrainedshortestpathproblem
AT dengyong bioinspiredmethodfortheconstrainedshortestpathproblem

Ejemplares similares