TSP Applications

Sonet Ring

Much of the work on the TSP is motivated by its use as a platform for the study of general methods that can be applied to a wide range of discrete optimization problems.  This is not to say, however, that the TSP does not find applications in many fields.  Indeed,  the numerous direct applications of the TSP bring life to the research area and help to direct future work.

The TSP naturally arises as a subproblem in many transportation and logistics applications, for example the problem of arranging school bus routes to pick up the children in a school district.  This bus application is of important historical significance to the TSP, since it provided motivation for Merrill Flood, one of the pioneers of TSP research in the 1940s.  A second TSP application from the 1940s involved the transportation of farming equipment from one location to another to test soil, leading to mathematical studies in Bengal by P. C. Mahalanobis and in Iowa by R. J. Jessen.   More recent applications involve the scheduling of service calls at cable firms, the delivery of meals to homebound persons,  the scheduling of stacker cranes in warehouses,  the routing of trucks for parcel post pickup, and a host of others.

Although transportation applications are the most natural setting for the TSP, the simplicity of the model has led to many interesting applications in other areas.  A classic example is the scheduling of a machine to drill holes in a circuit board or other object.   In this case the holes to be drilled are the cities, and the cost of travel is the time it takes to move the drill head from one hole to the next.  The technology for drilling varies from one industry to another, but whenever the travel time of the drilling device is a significant portion of the overall  manufacturing process then the TSP can play a role in reducing costs.

To give the reader a sample of some current applications of the TSP, we provide on the following pages a list of some of the applied (and not-so-applied, but still fun) work that has involved modules from the Concorde TSP library.

First Application