In this paper tour construction algorithms for the Asymmetric Traveling Salesman Problem (ATSP) are investigated. In Glover et al. a new algorithm was introduced, called Contract-or-Patch (COP). The algorithm has been tested together with other well-known and new heuristics on a variety of families of ATSP instances. In this study, COP has demonstrated good performance, clearly outperforming all other algorithms on robustness. It has either produced the shortest tours or came close to the leader on each of the seven families tested, while each of the remaining algorithms failed on at least two families of instances. In this paper three new variants of the COP algorithm were introduced, and an extensive computational study of the original as well as new versions of the algorithm on a variety of ATSP instances were performed. The study concludes by recommending one of the new versions of COP as a replacement for the original algorithm.
