Model And Method Research For Lock-quay Co-scheduling Problem At Hydro-junction

Inland waterway transport as one of the cheapest and most environmentally friendly modes of transport plays an important role in sustainable development because of its relatively low power consumption,low emissions of air pollutants and low cost.However,many of the inland waterway locks and dam facilities,such as the lock system in the Upper Mississippi River and the Three Gorges Dam in Yangtze River,have become a major constraint to navigation due to increased waterway traffic and insufficient throughput capacity of locks,engendering costly delay of ships.The delay sometimes becomes unacceptable,especially for those ships with a tight deadline.To deal with this problem,different countermeasures are presented.Except enhancing operation efficiency of the existing locks,adding water-land transshipment as a parallel channel to lock is also regarded as an important measurement to decrease the undesirable tardiness resulted from the insufficient throughput capacity of the locks.Based on these considerations,our research focus on the lock scheduling,berth allocation as well as lock and quay co-scheduling problem in order to improve the throughput performance of the comprehensive hydro project at inland waterway.The main contributions of the research can be summarized as following:(1)An ingenious solution structure of lock scheduling problem(LSP)is designed,by which the mixed integer-continuous LSP is converted to a combinatorial optimization problem.After that,an adaptive large neighborhood search(ALNS)heuristic based on the principle of destruction and reconstruction of solutions is proposed for solving the combinatorial LSP.Testing results using a large number of instances released in literature are compared with those obtained by two exact methods,the mixed integer linear programming(MILP)and Combinatorial Benders decomposition(CBD)method,which show that the proposed algorithm is capable of generating high-quality solutions with much less computation time compared with the exact methods.Especially,the advantage of the proposed method is more remarkable when there is no special sequence rules forced,which indicates the proposed method is capable of handling LSP in a broader scope of situations.(2)The solution mechanisums and constraint handling strategies of the discrete berth allocation problem(BAPD)as well as the continuous berth allocation problem(BAPC)is studied,especially the strategy for dealing with the non-overlapping constraint of BAPC at the quay-time coordinates.Based on the multi-objective constraint handling(MOCH)theory,the constrained single-objective BAPC(SBAPC)model is transformed into an unconstrained bi-objective BAPC(BBAPC)model by converting the constraints of BAPC into an independent objective.Then a bias selection modified non-dominated sorting genetic algorithm II(MNSGA-II)is proposed to optimize the BBAPC,in which an archive is designed as an efficient complementary mechanism to provide search bias toward the feasible solution so that the balance between the objective optimization and the constraint handling processes can be achieved.Finally,the proposed BBAPC model and the MNSGA-II approach are tested on instances from literature and generation.We compared the results obtained by MNSGA-II with other MOO algorithms under the BBAPC model and the results obtained by single-objective oriented methods under the SBAPC model.The comparison shows the feasibility of the BBAPC model and the advantages of the MNSGA-II algorithm.(3)Lock and quay co-scheduling problem(LQCP)is studied which can be regarded as a main problem where a transport mode for a ship(i.e.,to pass through the lock or be transshipped at the quay)is determined followed by solving two sub-problems of lock scheduling and berth allocation.A MILP model is proposed for LQCP,in which the delay time of ships at a lock and the quay as well as a transshipment penalty that indicates the unwillingness of a ship for transshipment is formulated as the objective.Lots of instances ranging from small to large are generated in order to test the feasibility and performance of the MILP model.The MILP is tested on these instances by implementing in Gurobi 7.5.1,which shows the small instances could be solved to optimality by MILP in short time.Analysis of co-scheduling results indicates that the MILP model is capable of handling different traffic situations.(4)Fuzzy logic control based hybrid heuristic approach is proposed to handle large scale LQCP where MILP may be unsuitable.Specifically,the solution mechanism can be decomposed into two layers,where the main problem in the outer layer is optimized by iteration of the proposed fuzzy-controlled quantum inspired gravitational search algorithm(FQBGSA)while in each iteration,two sub-problems in the inner layer are solved independently by heuristics.The hybrid heuristic approach is tested on instances ranging from small to large number of ships,the results of which are compared with those of MILP.The proposed heuristic method shows a tiny optimality gap for small instances and outperforms the MILP method on most of medium and large size instances with respect to solutions and computation times.Furthermore,comparison between different heuristics on medium and large instances confirms that the fuzzy logic control based heuristic improves the performance of the original heuristic and outperforms other heuristic methods.