Travelling salesman problem

A somewhat more robust measure may be defined by invoking the universal Turing machine. Let be the initial state of a computation that is designed to solve a size-N problem. If the problem is to find a solution to the Traveling-Salesman problem, for example, N would correspond to the number of cities that the salesman must visit. 

J.B. Kruskal Jr., On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc., 7 (1956) 48-50. 

Cemy, V., "Thermodynamic Approach to the Travelling Salesman Problem An Efficient Simulation Algorithm", J. Opt. Theory Applic., 45,41-51 (1985). 

The traveling salesman problem. The problem is to assign values of 0 or 1 to variables where ytj is 1 if the salesman travels from city i to city j and 0 otherwise. The constraints in the problem are that the salesman must start at a particular city, visit each of the other cities only once, and return to the original city. A cost (here it is distance) c j is associated with traveling from city i to city j, and the objective function is to minimize the total cost of the trips to each city visited, that is... 

Heuristic search procedures can be applied to certain types of combinatorial problems when BB and OA are difficult to apply or converge too slowly. In these problems, it is difficult or impossible to model the problem in terms of a vector of decision variables, which must satisfy bounds on a set of constraint functions, as required by OA. One example is the traveling salesman problem, in which the feasible region is the set of all tours in a graph, that is, closed cycles or paths that visit every node only once. The problem is to find a tour of minimal distance or cost,... 

These combinatorial problems, and many others as well, have a finite number of feasible solutions, a number that increases rapidly with problem size. In a job-shop scheduling problem, the size is measured by the number of jobs. In a traveling salesman problem, it is measured by the number of arcs or nodes in the graph. For a particular problem type and size, each distinct set of problem data defines an instance of the problem. In a traveling salesman problem, the data are the travel times between cities. In a job sequencing problem the data are the processing and set-up times, the due dates, and the penalty costs. 

M. Padberg and G. Rinaldi. A branch-and-cut algorithm for the resolution of large scale symmetric travelling salesman problems. SIAM Rev., 33 60,1991. 

Thrombospondin traveling salesman problem Transmembrane-type serine proteases Trait utility system for com Polyoxyethylsorbitan monolaurate Thromboxane treatment... 

Seminal work by Adleman demonstrated that molecular biological methods could be successfully employed to solve a mathematical problem [84, 85]. The problem he solved was a Hamiltonian path problem, in common parlance referred to as a travelling salesman problem. This is a hard computational problem for which no satisfactory algorithm is known allowing solution with electronic computers in polynomial time [86]. The potential of this DNA-based methodology relies on the inherent parallelism a DNA molecule affords. 

J.K. Lenstra, 1974, Clustering a data array and the traveling-salesman problem. Operations Research, 22(2), 413-414. 

V. Cemy and S.E. Dreyfus, Thermodynamical Approach to the Traveling salesman problem An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45 (1985) 41. 

Lin S, Kernighan BW (1973) An effective heuristic for the traveling-salesman problem. Operation Research 21 498... 

Little JDC, Murty KG, Sweeney DW, Karel C. An algorithm for the traveling salesman problem. Oper Res 1963 11 972-989. 

A number of optimization problems can be expressed in terms of ordered sets of numbers. The classic example is the traveling salesman problem (TSP). In the TSP, a salesman needs to visit a series of cities, with the constraint that each city must be visited once and only once. The object is to minimize the total distance traveled. An (integer) chromosome describing a trial route among eight cities could be... 

The pickup-and-delivery problem can be modeled as a variation of the vehicle routing problem with time windows (VRPTW) and a single depot. Inputs for the VRPTW include matrices that specify the distance and travel time between every pair of customers (including the depot) service time and time window for each customer maximum (or specified) number of drivers starting time of the workday and maximum on-road time of the workday. The maximum on-road time of the workday can be implemented as a time window on the depot, so that the pickup and delivery problem described above can be considered as a traveling salesman problem with time windows and multiple routes (m-TSPTW). However, the term VRPTW will be used in this section for this uncapadtated pickup-and-delivery problem. 

Jaillet, P. (1988), A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited, Operations Research, Vol. 36, pp. 929-936. 

Lawler, E., Lenstra, J., Rinnooy Kan, A., and Shmoys, D., Eds. (1985), The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization, John Wiley Sons, New York. 

---