The Research Of Transportation,Assignment And Travelling Salesman Problem

Transportation, assignment and travelling salesman problems(TSP) are classical problems of operational research. There are some tranditional methods about these problems, such as simplex algorithm, minimal element algorithm, northwest corner algorithm,vogel approximate method, hungarian method, branch and bound algorithm etc. But the solutions which are gotten by these methods are often not perfect, and it must be verified and adjusted many times. Or the process is too complicated to Computerize the corresponding methods,so they can only solve problem on the less size.Even now the new methods which use the theory of ANN(artifical neural net) or AI(artificial intelligence) are approximative solution.Even their amount of calculation is so large that it must cost much time to solve them with microcomputer. On the other hand,by analyzing the three kinds of problem,we know the transportation problem is a linear programming problem, and the assignment one is one case of 0-i programming problem,so it can be solved as a special transportation problem since it belong to linear programming problem.Moreover, TSP also can be regarded as transportation problem which have been added restriction, though it is a representational NP problem. Consequently, we suppose that there is a method which is current to the three kinds of problem in a certain extent.With studing we preliminarily bring forward a current method about the three kinds of problem, that is distinguishing value of element alloting algorithm(DVEAA). Whereas it need further improvement, the purpose of this thesis is to analyse the deficiencies of the original DVEAA and to complete it, and besides, we developed a current software for the three kinds of problem to test the algorithm practicability. The main tasks are as follows. (1)The procedure and the definitions about DVEAA are expatiated completely and systematically on a certain degree. (2)Because of finding that we cann always get the optimal solution with DVEAA, the steps of checking and adjusting feasible solutions are supplemented. (3)We give the corresponding computer algrithm for every steps, thus the process of solving problem is almost computerized, All the while searching close-loop in the step of adjusting is one of the great obstacles to comuterize many traditional algrithms, and the algorithm for searching close-loop have rather more applied value. (4)We analyse the comutational comlexity of DVEAA and test it with large scale problems.Our study indicates that the DVEAA possess the excellent characteristic of general purpose. It doesn demand particularity about the problem structure. It can solve balanceable and inbalanceable transportation problems, standard and nonstandard assignment problems, symmetrical and dissymmetrieal TSP, trigonal and nontrigonal TSP. It also can be used of solving these three kinds of problem in maximal and minimal condition and such problems in large or small scale. Synchronously, it has other advantages such as its solution is very colse to the optimal one. So DVEAA is a effective and reliable general-purpose algorithm, It has considerably practicable worthiness ,academic significance, and wide foreground.