Title: Sequential ordering problems for crane scheduling in port terminals

Authors: R. Montemanni, D.H. Smith, A.E. Rizzoli, L.M. Gambardella

Addresses: Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), CH-6928 Lugano-Manno, Switzerland. ' Division of Mathematics and Statistics, University of Glamorgan, Pontypridd, CF37 1DL, Wales, UK. ' Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), CH-6928 Lugano-Manno, Switzerland. ' Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), CH-6928 Lugano-Manno, Switzerland

Abstract: The Sequential Ordering Problem (SOP) is a version of the Asymmetric Travelling Salesman Problem (ATSP) where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost. The SOP models many real world applications, mainly in the fields of transportation and production planning. In particular, it can be used to optimise quay crane assignments. In this paper, we experimentally evaluate the contributions of the basic ingredients of the state-of-the-art algorithm for the SOPs: Local Searches (LSs), ant colony and heuristic manipulation.

Keywords: quay cranes; ant colony optimisation; sequential ordering; heuristic algorithms; crane scheduling; port terminals; ports; ACO; local search.

DOI: 10.1504/IJSPM.2009.032597

International Journal of Simulation and Process Modelling, 2009 Vol.5 No.4, pp.348 - 361

Received: 30 Oct 2008
Accepted: 09 Sep 2009
Published online: 08 Apr 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article