TY - JOUR

T1 - A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

AU - Yan, Shangyao

AU - Shih, Yu Lin

AU - Lee, Wang Tsang

N1 - Funding Information:
Acknowledgments This research was partially supported by a grant (NSC 96-2415-H-008-008-MY2) from the National Science Council of Taiwan. We would like to thank the anonymous referees for their helpful comments and suggestions on the presentation of the paper.

PY - 2011/4

Y1 - 2011/4

N2 - Traditionally,minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.

AB - Traditionally,minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.

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

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

U2 - 10.1007/s10898-010-9548-2

DO - 10.1007/s10898-010-9548-2

M3 - Article

AN - SCOPUS:79956081800

VL - 49

SP - 539

EP - 559

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 4

ER -