Intelligent Optimization Algorithms For The Fixed Charge Transportation Problems

The fixed charge transportation problem (FCTP) is a special linear programming problem. Just as the traditional linear transportation problem, FCTP also has the basic character that is under the constraints of supply and demand, and the character of transportation network. However, the fixed charge makes the objective function noncontinuous, then leads FCTP to be a NP-hard problem. The main objective of FCTP is that at the same time to meet the needs of destination, distributes the available supply to the source, so as to minimize the total variable cost and the fixed cost after distribution.Theoretically, there are lots of solutions to FCTP, which can be divided into two categories: exact algorithms and heuristic methods. At first, there are some exact algorithms for FCTP including cutting planes method, vertex ranking method, branch-and-bound method and so on. However, these methods are proved to be inefficient and time-consuming, and apply only to the smaller size and scale ones. Therefore, some heuristic methods have been proposed, such as Lagrangian relaxation method and adjacent extreme point search method. Even though these methods are usually computational efficiently, the quality of the obtained solutions is less than the optimum.Recently, some meta heuristic genetic algorithms for FCTP are developed, for instance, a genetic method based on matrix permutation representation, tubo search, an coding of spanning tree method based on edge sets. The experimental results show that the conclusions have their own merits and demerits.The gross structure is as following:In the first chapter, it is briefly introduced the four branchs for transportation problem. The background of FCTP is analyzed as well as the research situation, and the difference between the solutions.In the second chapter, the concepts and theorems about intelligent optimization algorithms are discussed, such as genetic algorithm, tubo search and simulated annealing etc., then, the technical methods, implemention skills and the sum total of study on the subject is contained in the chapter.In the forth chapter, the new genetic algorithm of multiple points crossover operator appending edges to forest is taken apart. The main purpose of the research is to improve the performance of genetic algorithm for FCTP, a new heuristic genetic algorithm of efficient multiple points crossover operator appending edges to forest is proposed by making use of the network structure of the FCTP. The sorted edge sets attained by root-first search of spanning tree are used to encode spanning tree in the genetic local search algorithm. The theoretical proof and computational results demonstrate that the algorithm can obtain a better solution than Raidl's genetic algorithm based on edge sets. It enrichs the solutions for FCTP and bring forth new ideas in theory and has some reference value in practice.In the fifth chapter, the immune genetic algorithm is introduced. To improve the performance of genetic algorithm for FCTP, it is compared with the genetic algorithms based on the matrix and edge sets by testing experiment, and the theoretical proof and computational results show that the immune genetic algorithm is better than both of .them. It enrichs the solutions for FCTP and bring forth new ideas in theory and has some reference value in practice.