To search, Click below search items.


All Published Papers Search Service


Genetic Algorithm for the Transportation Problem with Discontinuous Piecewise Linear Cost Function


Su Sheng, Zhan Dechen, Xu Xiaofei


Vol. 6  No. 7  pp. 182-189


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