An Industrial application of the traveling salesman's subtour problem

Abstract

Practical applications of the classical traveling salesman problem are rare because in most real world situations there are constraints upon the tour. To increase the range of useful applications, the classical structure must be modified to realistically deal with these constraints. In this application an industrial scheduling problem, called the traveling salesman's subtour problem, is formulated and defined. A time constraint restricts the salesman to a small subset of his total customers per planning period. Hence, the solution requires the simultaneous selection of the proper subset and the identification of the calling order. The problem is formulated to maximize expected sales subject to the time constraint. Lagrangean relaxation is used and by taking advantage of the underlying transportation structure of the problem the “gaps” are taken into account, thus providing a tight upper bound for the optimizing branch and bound routine in the algorithm.