Polynomial constraints to eliminate the sub-tours for the Traveling Salesman Problem

국문 초록 (Abstract)

Ⅰ. 머리말
Ⅱ. 부문별 經濟成果와 영국과의 競爭關係
Ⅲ. 독일경제의 浮上 및 輸出增加의 원인
Ⅳ. 保護貿易 정책이 농업 및 공업부문에 미친 영향
Ⅴ. 맺음말

다국어 초록 (Multilingual Abstract)

One of the most notorious optimization problem in combinatorial family is the Traveling Salesman Problem(TSP). On the several cities, the TSP is to find the shortest traveling order to visit each city exactly only once. It is a well known NP-complete problem to find shortest Hamiltonian circuit. It is an assignment problem with the additional condition that, the assignments chosen must constitue a tour. A major survey of research on the TSP is in the book by Lawler, Lenstra, Rinooy Kan & Shmoys [12]. Since Euler(1759) and Vandermonde(1771) discussed the problem of the "knight's tour", Kirkman(1856) is the first to consider Hamiltonian circuits in a general context. The TSP is a special case of Hamiltonian circuit with minimum cost. The first use of the term "Traveling Salesman Problem" in mathematical cycles may have been in 1931-32 by Hassler Wtitney. Merrill Flood popularized the TSP at the RAND Corporation in 1948 with a prize offered for a significant theorem on the TSP [9]. The TSP has a lot of theoretical importance and wide range of applicabilty as well [1, 2]. The TSP model applies directly to the Vehicle Routing, Crew Scheduling, Computer Wiring, Cutting Wallpaper, Job Sequencing, Machine Scheduling, Data Clustering, Material Flow System Design and so on. A wide variety of combinatorial optimization problems can be modelled as TSP's. A lot of seemingly unrelated problems are also solved by formulating them as instances of the TSP [8, 11, 17].

목차 (Table of Contents)

• Ⅰ. Introduction
• Ⅱ. Model
• 1. Basic Concepts
• 2. Algorithm
• 3. Comments
• Ⅲ. Numerical Example
• Ⅳ. Computational Results
• Ⅴ. Concluding Remarks
• References