Robust optimization for a class of ship traffic scheduling problem with uncertain arrival and departure times

The scheduling of ship traffic in the port is an important operation that aims to improve the navigation efficiency of the port, which is greatly affected by a variety of unpredictable events. In line with this research direction, this paper explores the ship traffic scheduling problem (STSP) with uncertain arrival and departure times (STSP-UN). STSP-UN treats arrival and departure times as random variables, with the objective of generating a schedule plan that minimizes the total waiting time of ships in the port while accommodating all possible variations in arrival and departure times within predefined uncertainty sets. A robust counterpart of the deterministic STSP formulation is derived where the uncertain arrival and departure times are confined within budget uncertainty sets. To obtain solutions for the proposed model, a hybrid optimization method (MAVNS) is used, combining a memetic algorithm (MA) for global exploration with a variable neighborhood search algorithm (VNS) that utilizes problem-specific neighborhood operators for local search. Numerical experiments are carried out at the Comprehensive port in Huanghua based on various instance sizes. The results validate the rationality and effectiveness of both the proposed robust optimization model and the algorithm. Specifically, the solution produced by MAVNS is 44.40% and 27.65% superior to that of the genetic algorithm (GA) and MA, respectively, for small-scale instances. For large-scale instances, the improvement rate is 41.25% and 30.02% compared to GA and MA, respectively. The MAVNS algorithm is a superior approach compared to an adaptive heuristic algorithm based on reinforcement learning (GSAA-RL), with consistently better performance across all instances and an impressive average gap of 31.20%. Furthermore, compared to the First-Come-First-Served (FCFS) strategy, MAVNS consistently exhibits superior performance in all instances, highlighting a remarkable average gap of 98.67%. The research enables ports to better respond to unexpected situations and reduce the negative impacts caused by uncertainty.