Improved genetic algorithm for generalized transportation problem

In this paper, we introduce the genetic algorithm approach to the generalized transportation problem (GTP) and GTP with a fixed charge (fc-GTP). We focus on the use of Prüfer number encoding based on a spanning tree, which is adopted because it is capable of equally and uniquely representing all possible trees. From this point, we also design the criteria by which chromosomes can always be converted to a GTP tree. The genetic crossover and mutation operators are designed to correspond to the genetic representations. With the spanning-tree-based genetic algorithm, less memory space will be used than in the matrix-based genetic algorithm for solving the problem; thereby computing time will also be saved. In order to improve the efficiency of the genetic algorithm, we use the reduced cost for the optimality of a solution and the genetic algorithm to avoid degeneration of the evolutionary process. A comparison of results of numerical experiments between the matrix-based genetic algorithm and the spanning-tree-based genetic algorithm for solving GTP and fc-GTP problems is given. This work was presented, in part, at the Fourth International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–22, 1999