|
چکیده
|
The travelling salesman problem (TSP) is the problem to find the shortest path of the Hamilton cycle in a given set of nodes. Very few problems have as wide applicability as Travelling Salesman Problem and are as well studied as Travelling Salesman Problem. Practically, any problem that consist of finding a sequential actions, operations, tasks. Can have a TSP side to it. Over the last few decades, problems of numerous optimizations have been studied by a lot of researchers. Problems containing TSP aspect have a big share in these problems. In spite of the aspect of travelling salesman problem in these problems, it is not always possible to formulate it directly as a TSP because additional constraints are involved or TSP only occurs as a sub-problem in it. To address such problem, many different of TSP have been proposed in the literature by many researchers from variant fields. Away from real-world applications, these variables pose a serious challenge theoretically also. Any improvement that can be made in solving a TSP variant will have a direct impact on associated real world applications. Further, many TSP variants are not as widely studied as the TSP itself. Motivated by these facts, in this thesis, we have present some of the NPhard variants of the TSP through eight Formulations owned to Dantzig, Fulkerson, and Johnson, Miller-Tucker-Zemlin, Gavish-Graves, Finke- Cluse – Gunn, Wong-Cluse, Fox – Gavish – Graves (T1,T2) and Vajda. Eight NP-hard TSP variants covering a wide range of TSP variants have been addressed in this thesis. These eight TSP variants are as follows: conventional formulation, sequential formulation, single-commodity-flow formulation, two-commodity-flow formulation, multi-commodity-flow formulation, 1st time-stage-dependent formulation, 2nd tim- stage-dependent formulation, 3rd timestage-dependent formulation. These problems not only pose a serious challenges from theoretical point of view, but also have many real-world applications in diverse domains like transportation, logistics, manufacturing, networks, planning & scheduling, healthcare etc. These formulation are classified as MIP formulations. To facilitate the compression between the formulations they introduced some extra variable, thus enable us the compression linear programming relaxation of the eight formulation in the same space to project the extra variable. The results of the compression shows that DFJ formulation is better than MTZ formulation, F1 formulation is better than MTZ formulation, the modified F1’ formulation is better than T1 formulation, MTZ formulation is better than T1, T2 formulations is better than F1’ formulation, T3 formulation is better than T2iii formulation. Which means the result of LP relaxation of the DFJ model is closest to the optimal value.
|