Models And Solution Algorithms For Seaport Berth And Channel Planning Problems Under Complex Navigation Environment

With the rapid development of trade globalization,the demand for shipping continues to increase.As a resut,many seaports worldwide are operating at overload.The traffic congestion in seaports is becoming increasingly serious because of the imbalance between the strong shipping demand and the limited berth and channel capacity of the port.The service efficiency of the berth and channel has become a bottleneck restricting the development of the port.However,the harbor basins and anchorages of most seaports are arranged in different port areas due to the topographical and geomorphological conditions.The channel is shared by these areas,resulting in a complex ship navigation environment.In view of the difficulties in the practical operation of seaports at the present stage,this paper studies the seaport berth and channel planning problems under complex navigation environment.The results of the study can provide a theoretical and scientific basis for port operation and management.Fisrt,this paper investigates the integrated planning of berth allocation and ship sequencing in a seaport with one-way navigation channel,in which only one direction is allowed to sail through at a time and ships thus have to queue up to enter and leave the port alternately.Several realistic factors such as heterogeneous sailing speed,the safety clearance of ships,berth-ship matching constraints,tides,and the distribution of multiple harbor basins and multiple anchorages are taken into consideration.A mixed-integer linear programming(MILP)model for the problem is proposed,aiming to minimize weighted dwelling time of all ships.By analyzing the characteristics of the model,an improved adaptive large neighborhood search algorithm is designed for solving the problem.To evaluate the solution quality,a lower bound of the solution of the problem is given by a column generation algorithm that solves a set-partitioning model adapted from the MILP model.Numerical experiments on Jingtang port of China show the effectiveness of the proposed algorithm.Second,this paper addresses the short-term berth planning and ship scheduling issues for a busy seaport with two-way navigation channel,in which the channel width of the port can accommodate one large-sized ship only or two small-sized ships in its two-way navigation(inbound and outbound).Given the mid-and long-term berthing plan,a rolling planning method is proposed from a short-term perspective to make real-time adjustments and improvements to the existing plan by comprehensively considering the accurate arrival and departure information of the ships and the latest status of the port resources.In the rolling planning,the ships moored at deep-water berths need to be lightened and thus be shifted to other shallow-water berths so as to vacate the limited deep-water berths for other large-sized ships.When some ships need to stay in the port due to some unexpected reasons,or cargo handling equipment of the berth works improperly,the ships also need to be shifted to other idle berths.A mixed-integer linear programming model is presented for the problem,and a column generation(CG)algorithm is developed to solve the model.Several efficient methods are also proposed to improve the performance of the CG algorithm.Computational experiments show that the proposed CG algorithm significantly outperforms truncated column generation,row-column generation,and the port scheduling schemes adopted in reality.Finally,in order to cope with the impact of uncertain factors such as severe weather and equipment faults on the arrival and handling times of ships,this paper studies the berth and channel planning for a seaport with compound navigation channel.Such a channel has multiple one-way lanes,and any two adjacent lanes can be occupied and regarded as one-way for a two-lane/large-sized ship.A two-stage stochastic programming model is presented for the problem,with an objective of minimizing the expected total weighted completion times of ships under uncertain ship arrival times and ship handling durations.The first stage decides the berth allocation of ships under uncertainty.In the second stage,the channel planning,including the selection of lanes,assignment of tugboats,and sequencing of ships,is determined after the uncertainty has been realized.Two tailored decomposition methods,that is,the Benders decomposition algorithm and the decomposition-based heuristic algorithm are proposed for effectively solving the model.Several efficient methods are also presented to improve the performance of the algorithms.By reformulating the original model into a set of scenario-based models,the lower bound of the solution of the original problem is obtained.Numerical experimental results verify the effectiveness of the proposed algorithm and demonstrate the benefits of the integrated decision model.