Title :
Polynomial heuristics for the k-stacker crane problem
Author :
Zhang, Lei ; Zhang, Rui
Author_Institution :
Dept. of Inf. Sci., Nat. Natural Sci. Found. of China, Beijing, China
Abstract :
The k-stacker crane problem (k-SCP), a generalization of the stacker crane problem (1-SCP) originated from the travelling salesman problem, is studied in this paper such that Two approximate O(max{|V| 3, |A|3}) heuristics are first presented under the objective of minimizing the total length of k stacker crane tours, where V stands for a set of modes (or cities), A is a set of arcs, and each arc is an ordered pair of cities to be visited. Not only the heuristics but also their compounds provide a worst-case guarantee similar to those of Fredericksons´ 1-SCP, and better than the k-SCP to minimize the longest of k stacker crane tour
Keywords :
computational complexity; operations research; optimisation; travelling salesman problems; Fredericksons´ 1-SCP; approximate heuristics; k-stacker crane problem; polynomial heuristics; travelling salesman problem; worst-case guarantee; Approximation algorithms; Cities and towns; Cost function; Cranes; Information science; Polynomials; Traveling salesman problems; Tree graphs;
Conference_Titel :
Systems, Man and Cybernetics, 1993. 'Systems Engineering in the Service of Humans', Conference Proceedings., International Conference on
Conference_Location :
Le Touquet
Print_ISBN :
0-7803-0911-1
DOI :
10.1109/ICSMC.1993.390861
