i. Drilling of printed circuit boards
A direct application of the TSP is in the drilling problem of printed circuit boards (PCBs). To connect a conductor on one layer with a conductor on anotherlayer, or to position the pins of integrated circuits, holes have to be drilled through theboard. The holes may be of different sizes. To drill two holes of different diameters consecutively, the head of the machine has to move to a toolbox and change the drillingequipment. This is quite time consuming. Thus,it is clear that one has to choose somediameter, drill all holes of the same diameter, change the drill, drill the holes of the nextdiameter, etc. Thus, this drilling problem can be viewed as a series of TSPs, one for each holediameter, where the 'cities' are the initial position and the set of all holes that can be drilledwith one and the same drill. The 'distance' between two cities is given by the time it takes to move the drilling head from one position to the other. The aim is to minimize the travel time for the machine head.
ii. Overhauling gas turbine engines
It is reported this application and it occurs when gas turbine engines of aircraft have to be overhauled. To guarantee a uniform gas flow through the turbines thereare nozzle-guide vane assemblies located at each turbine stage. Such an assembly basicallyconsists of a number of nozzle guide vanes affixed about its circumference. All these vaneshave individual characteristics and the correct placement of the vanes can result insubstantial benefits (reducing vibration, increasing uniformity of flow, reducing fuel consumption). The problem of placing the vanes in the best possible way can be modeled as a TSP with a special objective function.
iii. X-Ray crystallographyAnalysis of the structure of crystalsis
an important application of the TSP. Here an X-ray diffractometer is used to obtain information about the structure of crystalline material. To this end a detector measures the intensity of X ray reflections of the crystal from various positions. Whereas the measurement itself can be accomplished quite fast, there is a considerable overhead in positioning time since up to hundreds of thousands positions have to be realized for some experiments. In the two examples that we refer to,
the positioning involves moving four motors. The time needed to move from one position to the other can be computed very accurately. The result of the experiment does not depend on the sequence in which the measurements at the various positions are taken. However, the total time needed for the experiment depends on the sequence. Therefore, the problem consists of finding a sequence that minimizes the total positioning time. This leads to a traveling salesman problem.
iv. Computer wiring
It is reported a special case of connecting components on a computer board. Modules are located on a computer board and a given subset of pins has to be connected. In contrast to the usual case where a Steiner tree connection is desired, here the requirement is that no more than two wires are attached to each pin. Hence we have the problem of finding a shortest Hamiltonian path with unspecified starting and terminating points. A similar situation occurs for the so-called test bus wiring. To test the manufactured board one has to realize a connection which enters the board at some specified point, runs through all the modules, and terminates at some specified point. For each module we also have a specified entering and leaving point for this test wiring. This problem also amounts to solving a Hamiltonian path problem with the difference that the distances are not symmetric and that starting and terminating point are specified.
v. The order-picking problem in warehouses This problem is associated with material handling in a warehouse. Assume that at a warehouse an order arrives for a certain subset of the items stored in the warehouse. Some vehicle has to collect all items of this order to ship them to the customer. The relation to the TSP is immediately seen.The storage locations of the items correspond to the nodes of the graph. The distance between two nodes is given by the time needed to move the vehicle from one location to the other. The problem of finding a shortest route for the vehicle with minimum pickup time can now be solved as a TSP. In special cases this problem can be solved easily, vi. Vehicle routing Suppose that in a city n mail boxes have to be emptied every day within a certain period of time, say 1 hour. The problem is to find the minimum number of trucks to do this and the shortest time to do the collections using this number of trucks. As another example,
suppose that n customers require certain amounts of some commodities and a supplier has to satisfy all demands with a fleet of trucks. The problem is to find an assignment of customers to the trucks and a delivery schedule for each truck so that the capacity of each truck is not exceeded and the total travel distance is minimized. Several variations of these two problems, where time and capacity constraints are combined, are common in many real world applications. This problem is solvable as a TSP if there are no time and capacity constraints and if the number of trucks is fixed (say m ). In this case we obtain an m -salesmen problem. Nevertheless, one may apply methods for the TSP to find good feasible solutions for this problem.
vii. Mask plotting in PCB production
For the production of each layer of a printed circuit board, as well as for layers of integrated semiconductor devices, a photographic mask has to be produced. In our case for printed circuit boards this is done by a mechanical plotting device. The plotter moves a lens over a photosensitive coated glass plate. The shutter may be opened or closed to expose specific parts of the plate. There are different apertures available to be able to generate different structures on the board. Two types of structures have to be considered. A line is exposed on the plate by moving the closed shutter to one endpoint of the line, then opening the shutter and moving it to the other endpoint of the line. Then the shutter is closed. A point type structure is generated by moving (with the appropriate aperture) to the position of that point then opening the shutter just to make a short flash, and then closing it again. Exact modeling of the plotter control problem leads to a problem more complicated than the TSP and also more complicated than the rural postman problem.
