dc.description.abstract | Traditionally, the minimum cost transshipment problems are formulated as a linear cost problem, in order to reduce problem complexity. In reality, the unit cost decreases as the amount transported increases, resulting in a concave cost function. Recently, a research started to use advanced neighborhood search algorithms, such as threshold accepting (TA) and great deluge algorithm (GDA), to solve concave cost network problems in order to find better solutions than traditional heuristics. However, such neighborhood search algorithms easily encounter degeneracy problems, resulting in decreased solution efficiency. It is wondered if such algorithms can explore the whole domain area to find better solutions. In addition, most past research on solving concave cost network problems is confined to specific network problems. Therefore, a global search algorithm, based on genetic algorithm (GA), was recently developed to solve minimum concave cost transshipment problems.
Ant colony system algorithm (ACS) is a new popular heuristic which searches feasible solutions by using spread exploration. In some cases, its efficiency was found to be better than GA. Since there has not yet ACS developed to slove minimum cost transshipment problems with concave arc costs, in this research we developed an analogus ant colony system algorithm (AACS) to solve minimum cost transshipment problems with concave arc costs, based on ACS, incorporating the merits of GA, TA and concave cost network heuristics, that were applied for solving minimum cost transshipment problem with concave arc costs in literature. In order to evaluate this AACS, we referred to TA, GDA and GA to perform tests and comparison. The results can hopefully be useful reference for practitioners to solve their real problems.
The preliminary idea of our algorithm development was as follows: We first design several initial solution methods. In the feasible solution generation process, we developed several state transition rules to generate several paths, which did then be modified as feasible spanning trees by using a flow argumentation algorithm. For updating arc pheromones, we combined local and global pheromone updating rules, incorporating the TA search strategy, to develop several new pheromone updating rules. Besides, we referred to the elite strategy typically used in GA to speed up computations. In order to evaluate AACS for different problem scales and parameters, we designed a randomized network generator to produce many test problems. Finally, the tests were performed on personal computers with the assistance of C++ computer language for coding all necessary programs. | en_US |