The generalized lock scheduling problem (GLSP) is a mixed integer optimization problem which consists of a ship placement (SP) and a lockage operation scheduling (LOS) sub-problem. In previous research, the GLSP is solved by different exact and heuristic methods, which are confirmed inferior with respect to computation time and solution quality. Consequently, none of those methods is efficient for handling practical large-scale GLSP. For the first time, we show that high-quality solutions of GLSP can be efficiently obtained by using an innovative approach proposed in this paper. Specifically, an ingenious solution structure of GLSP is designed, by which the GLSP is converted to a combinatorial optimization problem. Furthermore, an adaptive large neighborhood search (ALNS) heuristic based on the principle of destruction and reconstruction of solutions is proposed for solving the GLSP. Test results using a large number of instances reported in the literature are compared with those obtained by two exact methods, the mixed integer linear programming (MILP) and combinatorial Benders’ decomposition (CBD) method. The results show that our ALNS achieves optimal solutions within less time in terms of most of the small-scale instances. Much better solutions are obtained by the ALNS within a few minutes for those large-scale instances that cannot be solved to optimality by exact methods within 2 h. Especially, the advantage of the proposed method is more remarkable when there is no specific chronological rules forced, which indicates that the proposed method is capable of handling the GLSP in a broader scope of situations.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An Adaptive Large Neighborhood Search for Solving Generalized Lock Scheduling Problem: Comparative Study With Exact Methods


    Contributors:
    Ji, Bin (author) / Yuan, Xiaohui (author) / Yuan, Yanbin (author) / Lei, Xiaohui (author) / Iu, Herbert H. C. (author)


    Publication date :

    2020-08-01


    Size :

    2680219 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    The generalized lock scheduling problem: An exact approach

    Verstichel, Jannes | Online Contents | 2014


    The generalized lock scheduling problem: An exact approach

    Verstichel, Jannes / De Causmaecker, Patrick / Spieksma, Frits et al. | Elsevier | 2014


    An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem

    Wen, M. / Linde, Esben / Røpke, Stefan et al. | BASE | 2016

    Free access


    Hybridizing large neighborhood search and exact methods for generalized vehicle routing problems with time windows

    Dorian Dumez / Christian Tilk / Stefan Irnich et al. | DOAJ | 2021

    Free access