Graph Neural Networks for Inland Waterway Ship Scheduling

Abstract

Inland waterway shipping, marked by its unpredictable and variable nature, plays a crucial role in transportation. This research's objective is to address these inconsistencies by constructing a robust scheduling model tailored to waterway systems' specific needs and challenges. The model is enhanced with predictive analytics and optimisation methods to ensure efficient and reliable operations. Within this framework, the research delves deep into four distinct optimisation problems: the Travelling Salesman Problem (TSP), the Job Shop Scheduling Problem (JSSP), the Resource-Constrained Project Scheduling Problem (RCPSP), and the Waterway Ship Scheduled Problem (WSSP). The underlying theme connecting these problems is the application of Graph Neural Networks (GNN) as a tool to model these complex systems.

The TSP is a cornerstone in combinatorial optimisation. Specifically, for this research, TSP serves as a means of understanding the challenges and intricacies of inland waterway networks. Employing the GNN model, the research provides insights into potential solutions for TSP within this context. When comparing various TSPLIB instances, the GNN model showcases its efficiency and potential for further refinement, especially in real-world routing and logistics.

Shifting the focus towards production planning, the JSSP emerges as a pivotal problem. It aims to optimise the order and timing of tasks for various ships, ensuring minimal usage of time and resources. By implementing the GNN architecture, the research offers a fresh perspective on JSSP. When applied to real-world scenarios, it is evident that the model can predict optimal scheduling sequences, matching the actual time frames and resource allocation required, thereby promising significant advancements in maritime trade efficiency.

Diving deeper into operations research, the RCPSP surfaces as a challenge that focuses on optimising project schedules, considering resource constraints and task precedents. The research introduces an approach to address this problem, especially concerning cargo operations within port networks. The research promises efficiency, reliability, and adaptability in Inland Waterway Transport (IWT) scheduling practices by integrating renewable resources and managing precedence relationships.

Lastly, the WSSP centres on managing ship movements within a defined time frame, optimising the sequence and timing of vessels to minimise delays and maximise the utilisation of waterway infrastructure and resources. Building upon the foundational work of previous research, this problem was translated and redefined in the context of the Resource-Constrained Project Scheduled Problem. Using this foundation, distinct RCPSP problems were formulated to reflect real-world scenarios, particularly emphasising the port of Duisburg. Drawing upon the results, the GNN model demonstrates high efficiency and accuracy in addressing the WSSP. While traditional tools like OR TOOLS provided optimal results, the GNN model closely mirrored these benchmarks, solidifying its position as a formidable solution for complex scheduling issues, especially given its rapid computation times.

In conclusion, this research presents a cohesive understanding of various optimisation problems within the realm of inland waterway shipping, all while harnessing the power of GNNs. Through systematic exploration and application, the research underscores the potential of GNNs to revolutionise how we approach and solve these challenges, promising a future of enhanced efficiency and reliability in waterway shipping operations.