Simple heuristics for some variants on the traveling salesman problem

Two O(|V|²) heuristics are presented for the stacker crane problem (SCP) and its variant, the k-stacker crane problem (k-SCP), both originating from the traveling salesman problem, where V stands for a set of cities to be visited. One heuristic not only is simpler than those of G. N. Frederickson et al. (1978) for SCP with the complexity of an O(|V|³) time bound, but also provides a worst-case guarantee of twice the optimal solution for this problem, which results from one of Frederickson´s. The other heuristic is the first for k-SCP with the object of minimizing the total length of k stacker crane tours