The sequential ordering problem is aversion of the asymmetric travelling salesman problem 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 sequential ordering problem 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 sequential ordering problems: local searches, ant colony and heuristic manipulation. The sequential ordering problem, which is faced in many practical applications, has been studied. The state-of-theart algorithm for this problem is composed of different components, namely local searches, an ant colony system and a heuristic manipulation technique. In this paper we have studied - from an experimental point of view - the impact of the different components on the performance of the full method. Specifically, we have run experiments with different combinations of components switched off, and we have analyzed how the results of the method were affected. The conclusion was that the heuristic manipulation technique is able to slightly improve the results achieved by both the local searches alone, and the combination of local searches and the ant colony system. However, what appears to be crucial is the interaction between the ant colony system and the local search routines. This results was expected. Heuristic manipulation can be seen as a tool useful to further refine already good results, but here it is shown that it needs to be run on a very efficient underlying heuristic method (ant colony system plus local search, in our case) in order to obtain good results.
Sequential ordering problems for crane scheduling in port terminals
Sequentielle Bereitstellungsprobleme für die Kraneinsatzplanung in Hafenterminals
2008
10 Seiten, 3 Tabellen, 22 Quellen
Conference paper
English
Simultaneous Load Scheduling of Quay Crane and Yard Crane in Port Container Terminals
Online Contents | 2009
|Simultaneous Load Scheduling of Quay Crane and Yard Crane in Port Container Terminals
Transportation Research Record | 2009
|Quay crane scheduling with non-interference constraints in port container terminals
Online Contents | 2008
|An Optimal Routing Algorithm for a Transfer Crane in Port Container Terminals
Online Contents | 1999
|