travelling saleman probelm
The travelling saleman proeblm is the most notorious probelm Np- complete probelm .In the simplest sense TSp can be defined as the saleman spends his time to visit a number of cities.many pratical probelm can be modelled as TSp such as drilling of circuit board ,real world routing of airlines and postal carrier etc.in 1800 it was first treated by irish mathematican Sir william . for over last 50 years studies has lead to improvement in the method and solution to the TSP probelm.computer code for the TSp probelm are more sophicated.
The traveling salesman problem (TSP) is one which has commanded much attention of mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is cij) and then return to the home city, what is the least costly route the traveling salesman can take? A complete historical development of this and related problems can be found in Hoffman and Wolfe (1985).
The importance of the TSP is that it is representative of a larger class of problems known as combinatorial optimization problems. The TSP problem belongs in the class of combinatorial optimization problems known as NP-complete. Specifically, if one can find an efficient algorithm (i.e., an algorithm that will be guaranteed to find the optimal solution in a polynomial number of steps) for the traveling salesman problem, then efficient algorithms could be found for all other problems in the NP-complete class. To date, however, no one has found a polynomial-time algorithm for the TSP. Does that mean that it is impossible to solve any large instances of such problems? Many practical optimization problems of truly large scale are solved to optimality routinely. In 1994, Applegate, et. al. solved a traveling salesman problem which models the production of printed circuit boards having 7,397 holes (cities), and, in 1998, the same authors solved a problem over the 13,509 largest cities in the U.S. So, although the question of what it is that makes a problem "difficult" may remain open, the computational record of specific instances of TSP problems coming from practical applications is optimistic.
How are such problems tackled today? Obviously, one cannot consider a brute force approach. In one example of an 16 city traveling salesman problem -- the problem of Homer's Ulysses attempting to visit the cities described in The Odyssey exactly once -- there are 653,837,184,000 distinct routes, (Grötschel and Padberg, 1993)! Enumerating all such roundtrips to find a shortest one took 92 hours on a powerful workstation. Rather than enumerating all possibilities, successful algorithms for solving the TSP problem have been capable of eliminating most of the roundtrips without ever explicitly considering them.
Formulations: The first step to solving instances of large TSPs must be to find a good mathematical formulation of the problem. In the case of the traveling salesman problem, the mathematical structure is a graph where each city is denoted by a point (or node) and lines are drawn connecting every two nodes (called arcs or edges). Associated with every line is a distance (or cost). When the salesman can get from every city to every other city directly, then the graph is said to be complete. A round-trip of the cities corresponds to some subset of the lines, and is called a tour or a Hamiltonian cycle in graph theory. The length of a tour is the sum of the lengths of the lines in the round-trip.
Depending upon whether or not the direction in which an edge of the graph is traversed matters, one distinguishes the asymmetric from the symmetric traveling salesman problem. To formulate the asymmetric TSP on m cities, one introduces zero-one variables
and given the fact that every node of the graph must have exactly one edge pointing towards it and one pointing away from it, one obtains the classic assignment problem. These constraints alone are not enough since this formulation would allow "subtours", that is, it would allow disjoint loops to occur. For this reason, a proper formulation of the asymmetric traveling salesman problem must remove these subtours from consideration by the addition of "subtour elimination" constraints. The problem then becomes
where K is any nonempty proper subset of the cities 1,...,m. The cost cij is allowed to be different from the cost cji. Note that there are m(m-1) zero-one variables in this formulation.
To formulate the symmetric traveling salesman problem, one notes that the direction traversed is immaterial, so that cij = cji. Since direction does not now matter, one can consider the graph where there is only one arc (undirected) between every two nodes. Thus, we let xj e {0,1} be the decision variable where j runs through all edges E of the undirected graph and cj is the cost of traveling that edge. To find a tour in this graph, one must select a subset of edges such that every node is contained in exactly two of the edges selected. Thus, the problem can be formulated as a 2-matching problem in the graph Gv having m(m-1)/2 zero-one variables, i.e. half of the number of the previous formulation. As in the asymmetric case, subtours must be eliminated through subtour elimination constraints. The problem can therefore be formulated as:
where J(j) is the set of all undirected edges connected to node j and E(K) is the subset of all undirected edges connecting the cities in any proper, nonempty subset K of all cities. Of course, the symmetric problem is a special case of the asymmetric one, but practical experience has shown that algorithms for the asymmetric problem perform, in general, badly on symmetric problems. Thus, the latter need a special formulation and solution treatment.
Algorithms:
Exact approaches to solving such problems require algorithms that generate both a lower bound and an upper bound on the true minimum value of the problem instance. Any round-trip tour that goes through every city exactly once is a feasible solution with a given cost which cannot be smaller than the minimum cost tour. Algorithms that construct feasible solutions, and thus upper bounds for the optimum value, are called heuristics. These solution strategies produce answers but without any quality guarantee as to how far off they may be from the optimal answer. Heuristic algorithms that attempt to find feasible solutions in a single attempt are called constructive heuristics while algorithms that iteratively modify and try to improve some given starting solution are called improvement heuristics. When the solution one obtains is dependent on the initial starting point of the algorithm, the same algorithm can be used multiple times from various (random) starting points. For an excellent survey of randomized improvement heuristics, see Jünger, Reinelt and Rinaldi (1994). Often, if one needs a solution quickly, one may settle for a well-designed heuristic algorithm that has been shown empirically to find "near-optimal" tours to many TSP problems. Research by Johnson (1990), and Jünger, Reinelt and Rinaldi (1994) describes algorithms that find solutions to extremely large TSPs (problems with tens of thousands, or even millions of variables) to within 2% of optimality in very reasonable times. For genetic algorithmic approaches to the TSP, see Potvin (1996), for simulated annealing approaches see Aarts, et al. (1988), for neural net approaches, see Potvin (1993), and for tabu search approaches, see Fiechter (1990). Performance guarantees for heuristics are given in Johnson and Papadimitriou (1985); probabilistic analysis of heuristics are discussed in Karp and Steele (1985); and the development and empirical testing of heuristics is reported in Golden and Stewart (1985).
In order to know about the closeness of the upper bound to the optimum value, one must also know a lower bound on the optimum value. If the upper and lower bound coincide, a proof of optimality is achieved. If not, a conservative estimate of the true relative error of the upper bound is provided by the difference of the upper and the lower bound divided by the lower bound. Thus, one needs both upper and lower bounding techniques to find provably optimal solutions to hard combinatorial problems or even to obtain solutions meeting a quality guarantee.
So how does one obtain and improve the lower bound? A relaxation of an optimization problem is another optimization problem whose set of feasible solutions properly contains all feasible solution of the original problem and whose objective function value is less than or equal to the true objective function value for points feasible to the original problem. Thus we replace the "true" problem by one with a larger feasible region that is more easily solvable. This relaxation is continually refined so as to tighten the feasible region so that it more closely represents the true problem. The standard technique for obtaining lower bounds on the TSP problem is to use a relaxation that is easier to solve than the original problem. These relaxations can have either discrete or continuous feasible sets. Several relaxations have been considered for the TSP. Among them are the n-path relaxation, the assignment relaxation, the 2-matching relaxation, the 1-tree relaxation, and the linear programming relaxation. For randomly generated asymmetric TSPs, problems having up to 7500 cities have been solved using an assignment relaxation which adds subtours within a branch and bound framework and which uses an upper bounding heuristic based on subtour patching, (Miller and Pekny, 1991). For the symmetric TSP, the 1-tree relaxation and the 2-matching relaxations have been most successful. These relaxations have been embedded into a branch-and-cut framework.
The process of finding constraints that are violated by a given relaxation, is called a cutting plane technique and all successes for large TSP problems have used cutting planes to continuously tighten the formulation of the problem. It is important to stress that all successful computational approaches to the TSP utilize facet-defining inequalities as cutting planes. General-type cutting planes of the integer programming literature that use the simplex basis-representation to obtain cuts, such as Gomory or intersection cuts, have long been abandoned because of poor convergence properties.
One of the simplest cuts that have been shown to define facets of the underlying TSP polytope are the subtour elimination cuts. Besides these constraints, comb inequalities, clique tree inequalities, path, wheelbarrow and bicycle inequalities, ladder inequalities and crowns have also been shown to define facets of this polytope. The underlying theory of facet generation for the symmetric traveling salesman problem is provided in Grötschel and Padberg (1985) and Jünger, Reinelt and Rinaldi (1994). The algorithmic descriptions of how these are used in cutting plane approaches are discussed in Padberg and Rinaldi (1991) and Jünger, Reinelt and Rinaldi (1994). Parallel processing implementations are presented in Christof and Reinelt (1995) and Applegate, et al. (1998). Cutting plane procedures can then be embedded into a tree search referred to as branch and cut. Some of the largest TSP problems solved have used parallel processing to assist in the search for optimality. As our understanding of the underlying mathematical structure of the TSP problem improves, and with the continuing advancement in computer technology, it is likely that many difficult and important combinatorial optimization problems will be solved using a combination of cutting plane generation procedures, heuristics, variable fixing through logical implications and reduced costs and tree search.
Applications:
One might ask, however, whether the TSP problem is important enough to have received all of the attention it has. Besides being a "polytope" of a difficult combinatorial optimization problem from a complexity theory point of view, there are important cases of practical problems that can be formulated as TSP problems and many other problems are generalizations of this problem. Besides the drilling of printed circuits boards described above, problems having the TSP structure occur in the analysis of the structure of crystals, (Bland and Shallcross, 1987), the overhauling of gas turbine engines (Pante, Lowe and Chandrasekaran, 1987), in material handling in a warehouse (Ratliff and Rosenthal, 1981), in cutting stock problems, (Garfinkel, 1977), the clustering of data arrays, (Lenstra and Rinooy Kan, 1975), the sequencing of jobs on a single machine (Gilmore and Gomory, 1964) and the assignment of routes for planes of a specified fleet (Boland, Jones, and Nemhauser, 1994). Related variations on the traveling salesman problem include the resource constrained traveling salesman problem which has applications in scheduling with an aggregate deadline (Pekny and Miller, 1990). This paper also shows how the prize collecting traveling salesman problem (Balas, 1989) and the orienteering problem (Golden, Levy and Vohra, 1987) are special cases of the resource constrained TSP. Most importantly, the traveling salesman problem often comes up as a subproblem in more complex combinatorial problems, the best known and important one of which is the vehicle routing problem, that is, the problem of determining for a fleet of vehicles which customers should be served by each vehicle and in what order each vehicle should visit the customers assigned to it. For relevant surveys, see Christofides (1985) and Fisher (1987).
For the interested reader seeking more information on this important problem, we suggest starting with the seminal paper on the problem by Dantzig, Fulkerson and Johnson (1954) and the text The TSP: A Guided Tour of Combinatorial Optimization, edited by Lawler, Lenstra, Rinnooy Kan and Shmoys (1985), which summarizes most of the research up through 1984. For more recent results, see the excellent survey by Jünger, Reinelt and Rinaldi (1994), and G. Reinelt (1994) and the extensive references provided there. A problem library containing numerous test problems is available electronically (Reinelt, 1991), and is distributed by Rice University, Houston, Texas.
See Assignment problem; Branch and bound; Branch and cut; Chinese postman; Combinatorics; Combinatorial and integer optimization; Computational complexity; Graph theory; Heuristics; Linear programming; Networks
The traveling salesman problem (TSP) is one which has commanded much attention of mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is cij) and then return to the home city, what is the least costly route the traveling salesman can take? A complete historical development of this and related problems can be found in Hoffman and Wolfe (1985).
The importance of the TSP is that it is representative of a larger class of problems known as combinatorial optimization problems. The TSP problem belongs in the class of combinatorial optimization problems known as NP-complete. Specifically, if one can find an efficient algorithm (i.e., an algorithm that will be guaranteed to find the optimal solution in a polynomial number of steps) for the traveling salesman problem, then efficient algorithms could be found for all other problems in the NP-complete class. To date, however, no one has found a polynomial-time algorithm for the TSP. Does that mean that it is impossible to solve any large instances of such problems? Many practical optimization problems of truly large scale are solved to optimality routinely. In 1994, Applegate, et. al. solved a traveling salesman problem which models the production of printed circuit boards having 7,397 holes (cities), and, in 1998, the same authors solved a problem over the 13,509 largest cities in the U.S. So, although the question of what it is that makes a problem "difficult" may remain open, the computational record of specific instances of TSP problems coming from practical applications is optimistic.
How are such problems tackled today? Obviously, one cannot consider a brute force approach. In one example of an 16 city traveling salesman problem -- the problem of Homer's Ulysses attempting to visit the cities described in The Odyssey exactly once -- there are 653,837,184,000 distinct routes, (Grötschel and Padberg, 1993)! Enumerating all such roundtrips to find a shortest one took 92 hours on a powerful workstation. Rather than enumerating all possibilities, successful algorithms for solving the TSP problem have been capable of eliminating most of the roundtrips without ever explicitly considering them.
Formulations: The first step to solving instances of large TSPs must be to find a good mathematical formulation of the problem. In the case of the traveling salesman problem, the mathematical structure is a graph where each city is denoted by a point (or node) and lines are drawn connecting every two nodes (called arcs or edges). Associated with every line is a distance (or cost). When the salesman can get from every city to every other city directly, then the graph is said to be complete. A round-trip of the cities corresponds to some subset of the lines, and is called a tour or a Hamiltonian cycle in graph theory. The length of a tour is the sum of the lengths of the lines in the round-trip.
Depending upon whether or not the direction in which an edge of the graph is traversed matters, one distinguishes the asymmetric from the symmetric traveling salesman problem. To formulate the asymmetric TSP on m cities, one introduces zero-one variables
and given the fact that every node of the graph must have exactly one edge pointing towards it and one pointing away from it, one obtains the classic assignment problem. These constraints alone are not enough since this formulation would allow "subtours", that is, it would allow disjoint loops to occur. For this reason, a proper formulation of the asymmetric traveling salesman problem must remove these subtours from consideration by the addition of "subtour elimination" constraints. The problem then becomes
where K is any nonempty proper subset of the cities 1,...,m. The cost cij is allowed to be different from the cost cji. Note that there are m(m-1) zero-one variables in this formulation.
To formulate the symmetric traveling salesman problem, one notes that the direction traversed is immaterial, so that cij = cji. Since direction does not now matter, one can consider the graph where there is only one arc (undirected) between every two nodes. Thus, we let xj e {0,1} be the decision variable where j runs through all edges E of the undirected graph and cj is the cost of traveling that edge. To find a tour in this graph, one must select a subset of edges such that every node is contained in exactly two of the edges selected. Thus, the problem can be formulated as a 2-matching problem in the graph Gv having m(m-1)/2 zero-one variables, i.e. half of the number of the previous formulation. As in the asymmetric case, subtours must be eliminated through subtour elimination constraints. The problem can therefore be formulated as:
where J(j) is the set of all undirected edges connected to node j and E(K) is the subset of all undirected edges connecting the cities in any proper, nonempty subset K of all cities. Of course, the symmetric problem is a special case of the asymmetric one, but practical experience has shown that algorithms for the asymmetric problem perform, in general, badly on symmetric problems. Thus, the latter need a special formulation and solution treatment.
Algorithms:
Exact approaches to solving such problems require algorithms that generate both a lower bound and an upper bound on the true minimum value of the problem instance. Any round-trip tour that goes through every city exactly once is a feasible solution with a given cost which cannot be smaller than the minimum cost tour. Algorithms that construct feasible solutions, and thus upper bounds for the optimum value, are called heuristics. These solution strategies produce answers but without any quality guarantee as to how far off they may be from the optimal answer. Heuristic algorithms that attempt to find feasible solutions in a single attempt are called constructive heuristics while algorithms that iteratively modify and try to improve some given starting solution are called improvement heuristics. When the solution one obtains is dependent on the initial starting point of the algorithm, the same algorithm can be used multiple times from various (random) starting points. For an excellent survey of randomized improvement heuristics, see Jünger, Reinelt and Rinaldi (1994). Often, if one needs a solution quickly, one may settle for a well-designed heuristic algorithm that has been shown empirically to find "near-optimal" tours to many TSP problems. Research by Johnson (1990), and Jünger, Reinelt and Rinaldi (1994) describes algorithms that find solutions to extremely large TSPs (problems with tens of thousands, or even millions of variables) to within 2% of optimality in very reasonable times. For genetic algorithmic approaches to the TSP, see Potvin (1996), for simulated annealing approaches see Aarts, et al. (1988), for neural net approaches, see Potvin (1993), and for tabu search approaches, see Fiechter (1990). Performance guarantees for heuristics are given in Johnson and Papadimitriou (1985); probabilistic analysis of heuristics are discussed in Karp and Steele (1985); and the development and empirical testing of heuristics is reported in Golden and Stewart (1985).
In order to know about the closeness of the upper bound to the optimum value, one must also know a lower bound on the optimum value. If the upper and lower bound coincide, a proof of optimality is achieved. If not, a conservative estimate of the true relative error of the upper bound is provided by the difference of the upper and the lower bound divided by the lower bound. Thus, one needs both upper and lower bounding techniques to find provably optimal solutions to hard combinatorial problems or even to obtain solutions meeting a quality guarantee.
So how does one obtain and improve the lower bound? A relaxation of an optimization problem is another optimization problem whose set of feasible solutions properly contains all feasible solution of the original problem and whose objective function value is less than or equal to the true objective function value for points feasible to the original problem. Thus we replace the "true" problem by one with a larger feasible region that is more easily solvable. This relaxation is continually refined so as to tighten the feasible region so that it more closely represents the true problem. The standard technique for obtaining lower bounds on the TSP problem is to use a relaxation that is easier to solve than the original problem. These relaxations can have either discrete or continuous feasible sets. Several relaxations have been considered for the TSP. Among them are the n-path relaxation, the assignment relaxation, the 2-matching relaxation, the 1-tree relaxation, and the linear programming relaxation. For randomly generated asymmetric TSPs, problems having up to 7500 cities have been solved using an assignment relaxation which adds subtours within a branch and bound framework and which uses an upper bounding heuristic based on subtour patching, (Miller and Pekny, 1991). For the symmetric TSP, the 1-tree relaxation and the 2-matching relaxations have been most successful. These relaxations have been embedded into a branch-and-cut framework.
The process of finding constraints that are violated by a given relaxation, is called a cutting plane technique and all successes for large TSP problems have used cutting planes to continuously tighten the formulation of the problem. It is important to stress that all successful computational approaches to the TSP utilize facet-defining inequalities as cutting planes. General-type cutting planes of the integer programming literature that use the simplex basis-representation to obtain cuts, such as Gomory or intersection cuts, have long been abandoned because of poor convergence properties.
One of the simplest cuts that have been shown to define facets of the underlying TSP polytope are the subtour elimination cuts. Besides these constraints, comb inequalities, clique tree inequalities, path, wheelbarrow and bicycle inequalities, ladder inequalities and crowns have also been shown to define facets of this polytope. The underlying theory of facet generation for the symmetric traveling salesman problem is provided in Grötschel and Padberg (1985) and Jünger, Reinelt and Rinaldi (1994). The algorithmic descriptions of how these are used in cutting plane approaches are discussed in Padberg and Rinaldi (1991) and Jünger, Reinelt and Rinaldi (1994). Parallel processing implementations are presented in Christof and Reinelt (1995) and Applegate, et al. (1998). Cutting plane procedures can then be embedded into a tree search referred to as branch and cut. Some of the largest TSP problems solved have used parallel processing to assist in the search for optimality. As our understanding of the underlying mathematical structure of the TSP problem improves, and with the continuing advancement in computer technology, it is likely that many difficult and important combinatorial optimization problems will be solved using a combination of cutting plane generation procedures, heuristics, variable fixing through logical implications and reduced costs and tree search.
Applications:
One might ask, however, whether the TSP problem is important enough to have received all of the attention it has. Besides being a "polytope" of a difficult combinatorial optimization problem from a complexity theory point of view, there are important cases of practical problems that can be formulated as TSP problems and many other problems are generalizations of this problem. Besides the drilling of printed circuits boards described above, problems having the TSP structure occur in the analysis of the structure of crystals, (Bland and Shallcross, 1987), the overhauling of gas turbine engines (Pante, Lowe and Chandrasekaran, 1987), in material handling in a warehouse (Ratliff and Rosenthal, 1981), in cutting stock problems, (Garfinkel, 1977), the clustering of data arrays, (Lenstra and Rinooy Kan, 1975), the sequencing of jobs on a single machine (Gilmore and Gomory, 1964) and the assignment of routes for planes of a specified fleet (Boland, Jones, and Nemhauser, 1994). Related variations on the traveling salesman problem include the resource constrained traveling salesman problem which has applications in scheduling with an aggregate deadline (Pekny and Miller, 1990). This paper also shows how the prize collecting traveling salesman problem (Balas, 1989) and the orienteering problem (Golden, Levy and Vohra, 1987) are special cases of the resource constrained TSP. Most importantly, the traveling salesman problem often comes up as a subproblem in more complex combinatorial problems, the best known and important one of which is the vehicle routing problem, that is, the problem of determining for a fleet of vehicles which customers should be served by each vehicle and in what order each vehicle should visit the customers assigned to it. For relevant surveys, see Christofides (1985) and Fisher (1987).
For the interested reader seeking more information on this important problem, we suggest starting with the seminal paper on the problem by Dantzig, Fulkerson and Johnson (1954) and the text The TSP: A Guided Tour of Combinatorial Optimization, edited by Lawler, Lenstra, Rinnooy Kan and Shmoys (1985), which summarizes most of the research up through 1984. For more recent results, see the excellent survey by Jünger, Reinelt and Rinaldi (1994), and G. Reinelt (1994) and the extensive references provided there. A problem library containing numerous test problems is available electronically (Reinelt, 1991), and is distributed by Rice University, Houston, Texas.
See Assignment problem; Branch and bound; Branch and cut; Chinese postman; Combinatorics; Combinatorial and integer optimization; Computational complexity; Graph theory; Heuristics; Linear programming; Networks
Comments