PROCEDURES FOR TRAVELING SALESMAN PROBLEMS WITH ADDITIONAL CONSTRAINTS

In the real world problems occur that can be regarded as travelling salesman problems in which the solution must have some predescribed structure. For example it can be obligatory that some cities must be visited before others or some cities must be visited contiguously. Exact branch and bound procedures will de described for solving general travelling salesman problems with additional constraints. The travelling salesman problem is expanded to include the following situations. 1. 1. A subset (or subsets) of cities - called a cluster - must be visited contiguously. 2. 2. Precedence relations are imposed on some points. 3. 3. Situation 1 and precedence relations are imposed on some clusters. Some real world applications of these constrained travelling salesman problems are mentioned. © 1979.