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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Ji, Bin (Autor:in) / Yuan, Xiaohui (Autor:in) / Yuan, Yanbin (Autor:in) / Lei, Xiaohui (Autor:in) / Iu, Herbert H. C. (Autor:in)


    Erscheinungsdatum :

    2020-08-01


    Format / Umfang :

    2680219 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    The generalized lock scheduling problem: An exact approach

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


    The generalized lock scheduling problem: An exact approach

    Verstichel, Jannes | Online Contents | 2014


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

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

    Freier Zugriff

    An Adaptive Large Neighborhood Search Algorithm for the Satellite Data Transmission Scheduling Problem

    Yingguo Chen / Ming Chen / Jun Wen et al. | DOAJ | 2020

    Freier Zugriff

    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

    Freier Zugriff