A traveling salesman problem (1,2) application arising in cable assembly shops

One of the main operations in producing cable systems in the automotive industry is that of cutting/stripping/crimping. The most time-consuming activity in this operation is changing the heads whenever a different connecter is to be crimped at either one of the ends. This set-up time is practically doubled when the heads at both ends are to be changed. Thus, one is faced with the problem of minimizing the total machine set-up time; which turns out to be a TSP where the distances between the nodes are either one or two. A simple and effective heuristic algorithm is developed that yields solutions, which are only a few percent above the optimum in the worst case.