A Cutting Planes Algorithm for the m-Salesmen Problem

Abstract

The existence of reliable and flexible FORTRAN programs for integer linear programming has recently enabled the development of very efficient algorithms for the travelling salesman problem. The main characteristic of these algorithms is the relaxation of most of the constraints of the problem during its solution. The same approach can be used for the solution of the m-salesmen problem in which m salesmen starting from the same city must visit only once n cities at minimum cost. The number of salesmen can be fixed in advance or allowed to vary, upper and lower bounds set on the number of salesmen and even fixed costs associated with the salesmen. The results obtained so far are very encouraging. Problems of up to 100 cities have been solved optimally for the m-travelling salesmen case and other more complex problems are currently under study.