Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prufer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.