This paper deals with a partly overlapped dual traveling salesman problem which has not been dealt with in the literature, and has some application in the operation of Goliath Crain in the shipbuilding industry.
The difference of this model with the conventional traveling salesman problem is that, in addition to there being two traveling salesmen, some nodes are visited simultaneously by both salesmen. The objective is then to minimize the total traveling costs incurred for both salesmen under the above restriction.
Three heuristics for solving the problem are developed, all of which employ the existing method for solving its subproblems, namely asymmetric traveling salesman problems.
Computational results with 10 test problems are presented to demonstrate the effectiveness of the proposed heuristics.