Improved Genetic Algorithm for Fixed Charge Transportation Problem

To improve the performance of genetic algorithm based on edge sets code (ES) for solving the fixed charge transportation problem (FCTP), an improved genetic algorithm which has a multi-point crossover operator appending edges to forest (MPC-ES) is developed for the spanning tree based on the sorted edge sets code attained by root-first search. The algorithm complexity of MPC-ES is analyzed, and the computational results demonstrate that along with the increase of FCTP sizes and types, the solution quality among ES, sorted edge sets (S-ES) and MPC-ES code shows descending tendency. But MPC-ES can obtain better solutions than those based on ES and S-ES code; and the cost of CPU time among them become longer, S-ES is less than ES, and MPC-ES appreciably less than S-ES.