New Genetic Algorithm for the Fixed Charge Transportation Problem

A new genetic algorithm for the fixed charge transportation (FCT) problem was developed making use of the special network structure of the FCT problem. The sorted set of edge (S-ES) is used to encode spanning tree in the genetic algorithm. New initialization and single point crossover and mutation operators were proposed for effective and efficient evolutionary search. Evolutionarily stable strategy was used to avoid the problem of local optimum. Our genetic algorithms and Raidl´s genetic algorithm were evaluated computationally on randomly generated problems. The results of computations demonstrate that our algorithm can obtain better solution quality at a cost of less CPU times than Raidl´s genetic algorithm. The differences of solution quality and CPU times between our approach and Raidl´s genetic algorithm become larger and larger with the increase of the problem size. For the 50times50 problem, our approach can save about 20% CPU times than Raidl´s genetic algorithm