期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：7A
页码：182-189
出版社：International Journal of Computer Science and Network Security
摘要：We investigate a transportation problem with discontinuous piecewise linear cost function in this paper. The basic feasible solution for the transportation problem, in which flow bounds on edges are uncertain, is obtained by disaggregating piecewise linear cost function. A genetic algorithm is proposed to solve the transportation problem based on the network representation of the basic feasible solution. A basic feasible solution is represented by the spanning tree that consists of all basic edges and nonbasic edges with positive flow amount. Sorted edge set is used to represent the spanning tree. Edges of a spanning tree are sorted by root first search pattern in the representation. Single point crossover operator and random pivot mutation operator are developed for effective and efficient evolution. Computational tests demonstrate our genetic algorithm not only can obtain better solution quality, but also is more efficient than the previous proposed genetic algorithm based on the matrix encoding.
关键词：Transportation problem, discontinuous piecewise linear cost function, genetic algorithm, spanning tree
