Paper Info
Title
An Adaptive Large Neighborhood Search for Solving Generalized Lock Scheduling Problem: Comparative Study With Exact Methods
Abstract
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.
Year
DOI
Venue
2020
10.1109/TITS.2019.2926405
IEEE Transactions on Intelligent Transportation Systems
Keywords
DocType
Volume
Lock scheduling problem,exact method,heuristic,adaptive large neighborhood search (ALNS)
Journal
21
Issue
ISSN
Citations 
8
1524-9050
1
PageRank 
References 
Authors
0.36
0
5
Name
Order
Citations
PageRank
Bin Ji181.12
Xiao-Hui Yuan253475.44
Yanbin Yuan314017.67
Xiaohui Lei4208.10
Herbert H. C. Iu533460.21