An adaptive amoeba algorithm for constrained shortest paths

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

doi:10.1016/j.eswa.2013.07.054

An adaptive amoeba algorithm for constrained shortest paths

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

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	7607-7616
Number of pages	10
Journal	Expert Systems with Applications
Volume	40
Issue number	18
DOIs	https://doi.org/10.1016/j.eswa.2013.07.054
Publication status	Published - 2013
Externally published	Yes

Keywords

Adaptive amoeba algorithm
Constrained shortest path
Lagrangian relaxation
Optimization

ASJC Scopus subject areas

Engineering(all)
Computer Science Applications
Artificial Intelligence

More information

10.1016/j.eswa.2013.07.054

Cite this

@article{c87d9f8b2d11479f999ffdd047072569,

title = "An adaptive amoeba algorithm for constrained shortest paths",

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.",

keywords = "Adaptive amoeba algorithm, Constrained shortest path, Lagrangian relaxation, Optimization",

author = "Xiaoge Zhang and Yajuan Zhang and Yong Hu and Yong Deng and Sankaran Mahadevan",

note = "Funding Information: The Ph.D candidates of the corresponding author in Shanghai Jiao Tong University, Xiaoyan Su and Peida Xu, provide valuable discussions on bio-inspired optimization. The work is partially supported by National Natural Science Foundation of China , Grant Nos. 61174022 and 71271061 , Chongqing Natural Science Foundation (for Distinguished Young Scholars) , Grant No. CSCT, 2010BA2003, National High Technology Research and Development Program of China (863 Program) (No. 2012AA041101 ), Science and Technology Planning Project of Guangdong Province, China ( 2010B010600034 , 2012B091100192 ), Business Intelligence Key Team of Guangdong University of Foreign Studies (TD1202), Doctor Funding of Southwest University Grant No. SWU110021 , China State Key Laboratory of Virtual Reality Technology and Systems , the Fundamental Research Funds for the Central Universities Grant No. XDJK2013D010 . ",

year = "2013",

doi = "10.1016/j.eswa.2013.07.054",

language = "English",

volume = "40",

pages = "7607--7616",

journal = "Expert Systems with Applications",

issn = "0957-4174",

publisher = "Elsevier Ltd",

number = "18",

}

TY - JOUR

T1 - An adaptive amoeba algorithm for constrained shortest paths

AU - Zhang, Xiaoge

AU - Zhang, Yajuan

AU - Hu, Yong

AU - Deng, Yong

AU - Mahadevan, Sankaran

N1 - Funding Information: The Ph.D candidates of the corresponding author in Shanghai Jiao Tong University, Xiaoyan Su and Peida Xu, provide valuable discussions on bio-inspired optimization. The work is partially supported by National Natural Science Foundation of China , Grant Nos. 61174022 and 71271061 , Chongqing Natural Science Foundation (for Distinguished Young Scholars) , Grant No. CSCT, 2010BA2003, National High Technology Research and Development Program of China (863 Program) (No. 2012AA041101 ), Science and Technology Planning Project of Guangdong Province, China ( 2010B010600034 , 2012B091100192 ), Business Intelligence Key Team of Guangdong University of Foreign Studies (TD1202), Doctor Funding of Southwest University Grant No. SWU110021 , China State Key Laboratory of Virtual Reality Technology and Systems , the Fundamental Research Funds for the Central Universities Grant No. XDJK2013D010 .

PY - 2013

Y1 - 2013

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

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

KW - Adaptive amoeba algorithm

KW - Constrained shortest path

KW - Lagrangian relaxation

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=84882343117&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2013.07.054

DO - 10.1016/j.eswa.2013.07.054

M3 - Journal article

AN - SCOPUS:84882343117

VL - 40

SP - 7607

EP - 7616

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 18

ER -

An adaptive amoeba algorithm for constrained shortest paths

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Cite this