Global and local search algorithms for concave cost transshipment problems

Shangyao Yan, Der Shin Juang, Chien Rong Chen, Wei Shen Lai

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.

Original languageEnglish
Pages (from-to)123-156
Number of pages34
JournalJournal of Global Optimization
Issue number1
StatePublished - Sep 2005


  • Concave cost
  • Genetic algorithm
  • Global search
  • Local search
  • Transshipment problems


Dive into the research topics of 'Global and local search algorithms for concave cost transshipment problems'. Together they form a unique fingerprint.

Cite this