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.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Title :

    Sequential ordering problems for crane scheduling in port terminals


    Additional title:

    Sequentielle Bereitstellungsprobleme für die Kraneinsatzplanung in Hafenterminals


    Contributors:


    Publication date :

    2008


    Size :

    10 Seiten, 3 Tabellen, 22 Quellen


    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English





    Simultaneous Load Scheduling of Quay Crane and Yard Crane in Port Container Terminals

    Lee, Der-Horng / Cao, Zhi / Chen, Jiang Hang et al. | Transportation Research Record | 2009


    Quay crane scheduling with non-interference constraints in port container terminals

    Lee, Der-Horng / Wang, Hui Qiu / Miao, Lixin | Elsevier | 2006