Optimal navigation management in natural inland waterways

School of Engineering, University of Seville Department of Automation and Systems Engineering Estimation, Prediction, Optimization and Control Group Ph.D. Thesis Optimal Navigation Management in Natural Inland Waterways Application to the Guadalquivir River Juan Moreno Nadales Supervised by Prof. David Mu˜noz de la Pe˜na, Prof. Daniel Limon and Prof. Teodoro Alamo Thesis submitted for the degree of Doctor of Philosophy in Automation, Electronics, and Telecommunications Engineering Seville (Spain), December 2023 Mention in Industrial Ph.D. Project supported by Fondo Europeo de Desarrollo Regional FEDER under Programa Interreg V-A Esp˜ana-Portugal (POCTEP) 2014-2020 and by Portel Logistic Tehcnologies Industrial Ph.D. Thesis Optimal Navigation Management in Natural Inland Waterways Application to the Guadalquivir River Juan Moreno Nadales Seville (Spain), December 2023 Mention in International Ph.D. Part of the work on this thesis has been carried out in collaboration with the Control and Optimization Research Lab. led by Professor Insoon Yang at Seoul National University, Seoul, Republic of Korea International Ph.D. Thesis Optimal Navigation Management in Natural Inland Waterways Application to the Guadalquivir River Juan Moreno Nadales Seville (Spain), December 2023 Contents Acknowledgements ii Abstract v Notation vii 1 Introduction 1 1.1 Context ................................. 1 1.2 Scheduling and navigation in the Guadalquivir River . . . . . . . . 2 1.3 Motivation and objectives . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Literaturereview............................ 10 1.4.1 Scheduling in inland waterways . . . . . . . . . . . . . . . . 10 1.4.2 Safety-oriented rescheduling in natural inland waterways . . 16 1.4.3 Navigation control . . . . . . . . . . . . . . . . . . . . . . . 20 1.5 Thesisoverview............................. 24 1.6 Publications............................... 27 2 Optimal scheduling in inland waterways 31 2.1 Introduction............................... 31 2.2 Vessel planning in natural inland waterways . . . . . . . . . . . . . 32 2.2.1 Proposed two-step solution . . . . . . . . . . . . . . . . . . 34 2.3 Safe tube calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4 Optimal vessel planning . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4.1 Costfunction.......................... 41 2.4.2 Speed constraint . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.3 Safe tube selection . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.4 Encountering situations constraint . . . . . . . . . . . . . . 43 2.4.5 Optimization problem . . . . . . . . . . . . . . . . . . . . . 45 2.5 Simulationresults ........................... 46 2.5.1 Model parameters . . . . . . . . . . . . . . . . . . . . . . . 46 2.5.2 Scenario generation . . . . . . . . . . . . . . . . . . . . . . 47 2.5.3 Simulation results . . . . . . . . . . . . . . . . . . . . . . . 47 2.6 Conclusions............................... 53 3 Safe optimal rescheduling in inland waterways 55 3.1 Introduction............................... 55 3.2 Monitoringsystem ........................... 56 3.3 Anomalies detection and identification . . . . . . . . . . . . . . . . 57 3.4 Rescheduling strategy . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4.1 Isolated rescheduling . . . . . . . . . . . . . . . . . . . . . . 62 3.4.2 Global rescheduling . . . . . . . . . . . . . . . . . . . . . . 64 3.4.3 Multi-objective rescheduling . . . . . . . . . . . . . . . . . . 66 3.5 CaseStudy ............................... 67 3.6 Conclusions............................... 77 4 Risk-aware distributionally robust control in inland waterways 79 4.1 Introduction............................... 79 4.2 Preliminaries .............................. 80 4.2.1 System and obstacles modeling . . . . . . . . . . . . . . . . 80 4.2.2 Empirical distribution generation . . . . . . . . . . . . . . . 82 4.3 Wassertein distributionally robust motion control . . . . . . . . . . 84 4.3.1 Measuring the risk of unsafety using CVaR . . . . . . . . . 84 4.3.2 Motion control via DR-MPC . . . . . . . . . . . . . . . . . 85 4.3.3 Finite-dimensional reformulation via the Kantorovich duality 88 4.4 Casestudy ............................... 91 4.4.1 Setup .............................. 91 4.4.2 Vessel motion control . . . . . . . . . . . . . . . . . . . . . 92 4.5 Conclusions............................... 95 5 Wplanpy. A tool for scheduling vessels in inland waterway 97 5.1 Introduction............................... 97 5.2 Tooloverview.............................. 98 5.2.1 Toolschema...........................100 5.3 Software architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.3.1 Cloud database . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.3.2 Safe tubes calculation . . . . . . . . . . . . . . . . . . . . . 104 5.3.3 Planning module . . . . . . . . . . . . . . . . . . . . . . . . 106 5.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.5 Conclusions...............................108 Conclusions 109 Future work 111 Bibliography 112 List of Figures 121 List of Tables 125 i Nk p— Safe crossing region kdefined at section p. tentry p— Earliest time to entry section pwhen defining a safe crossing region. tlatest p— Latest time to entry section pwhen defining a safe crossing region. tearliest p— Earliest time to exit section pwhen defining a safe crossing region. texit p— Latest time to exit section pwhen defining a safe crossing region. tmin i,k,p — Earliest time when vessel iis allowed to cross waypoint pfollowing safe tube k. tmax i,k,p — Latest time when vessel iis allowed to cross waypoint pfollowing safe tube k. Optimization variables ti— Trip plan for vessel i. ti,p — Time when vessel icrosses waypoint p. taux i— Time for a damaged vessel ito return to sail. ci,j,p — Crossing decision variable for vessels i,jat section p. ri,k — Decision variable for each vessel ifollowing safe tube k. Other variables tcurrent — Current time. trepair i— Time when vessel iis repaired. t×— Time when an incident is detected. p× i— Section where vessel isuffers an incident. zi— Expected location of vessel iaccording to plan ti. z† i— Real location of vessel i. ¯vi— Average speed of vessel i. Scenario configuration parameters N— Number of vessels. Nu— Number of vessels sailing upstream. Nd— Number of vessels sailing downstream. viii ∆0— Minimum time interval between the crossing of two vessels at the same waypoint. tinit — Initial time for the generation of vessel arrival times. λ— Characteristic parameter of the Poisson distribution that models the vessel arrival times. DL— Period of time for arriving to final destination. vbreak — Speed reduction incident threshold. ρspeed — Probability of speed reduction incident. ρdelay — Probability of arrival delay incident. ρbreak — Probability of break down incident. νi— Speed reduction coefficient of vessel i. ϵz— Incident detection threshold. αi— Weight of the waiting cost associated with vessel i. βi— Weight of the navigation cost assosiated with vessel i. ηi— Rescheduling Weight for vessel i. Other J— Aggregated waiting and navigation costs. CW— Waiting cost. CN— Navigation cost. JS— Sailing cost. JR— Rescheduling cost. Wasserstein distributionally robust optimization notation Indexes k— Index for time step. t— Index for initial time. l— Index for obstacle. ix i— Index for observation of an obstacle. Sets X— State constraint set. U— Control input constraint set. D— Noisy sample dataset of wl,t,k. Dl,t,k — Set of probability distributions of wl,t,k. Ambiguity set. P(W) — Set of Borel probability measures on support W. Parameters N— Number of data samples for wl,t,k. K— Prediction horizon for DR-MPC problem. Q— DR-MPC output weighting matrix. R— DR-MPC state weighting matrix. P— DR-MPC terminal state weighting matrix. System and obstacles modeling x(t) — State of the system at time t. u(t) — Control input applied at time t. y(t) — Output of the system at time t. f(·,·) — State transition function. h(·) — Measured output function. wl,t,k — Radius of the ball defining obstacle lat time t+k. ˆwl,t,k — Noisy sample of wl,t,k. Ol(t+k) — Region occupied by obstacle lat time t+k. Oc l— Center of obstacle l. O◦ l— Interior of obstacle l. Yl(t+k) — Safe region of obstacle t+kassociated to obstacle l. µl,t,k — True probability distribution of wl,t,k. x νl,t,k — Empirical probability distribution of wl,t,k. δwl,t,k — Dirac delta function concentrated at wl,t,k. Distributionally robust MPC κ— Probability transportation plan. Πiκ—ith marginal probability distribution of transportation plan κ. δl— Risk tolerance assigned to obstacle l. α— Parameter that defines the worst-case quantile of the safety loss distribution. θ— Radius of an ambiguity set modelled as an statistical ball around a nominal distribution. xk— Predicted state at time instant k. yk— Predicted output at time instant k. uk— Calculated control input at time instant k. τk— Reference trajectory at time instant k. zl,k — Reformulation variable for obstacle lat time k. ρl,k — Reformulation variable for obstacle lat time k. λl,k — Reformulation variable for obstacle lat time k. sl,k,i — Reformulation variable for obstacle lat time kand for measure iof ˆwl,t,k. Symbols and Operations R— Set of real numbers. Ib a— Set of integer numbers in the interval [a, b]. E(X) — Expected value of a random variable X. Q⪰0 — Positive definite matrix Q. Q⪰0 — Positive semi-definite matrix Q. A\B— Set difference between sets Aand B. A⊆Rn— n-dimensional set A. xi A∪B— Union of sets Aand B. A∩B— Intersection of sets Aand B. a⊺— Vector atransposed. ¯a— Average value of a. em—m-dimensional vector of ones. a∈A— Element abelongs to set A. P a∈A — Sum of all elements ain set A. a≥b— element ais greater or equal than b. a≤b— element ais less or equal than b. min aJ(a) — Minimum value of function Jwith respect to a. max aJ(a) — Maximum value of function Jwith respect to a. sup aJ(a) — Supremum of function Jwith respect to a. sup aJ(a) — Infimum of function Jwith respect to a. arg min aJ— Value of afor which Jis minimum. |·| — Elementwise absolute value. ∥·∥ — Euclidean norm. (a)+— Maximum between aand 0. ∀a— For all values of a. dist (a, b) — Euclidean distance between aand b. CVaRµ α— Conditional value at risk within the (1 −α) worst-case quantile of a random loss following a distribution µ. Wp(µ, ν) — p-order Wasserstein distance between two probability measures µ and ν. xii xiii xiv 1 Chapter 1 Introduction 1.1 Context The present doctoral thesis has being conducted to obtain the title of Doctor in Automation and Control Engineering within the Doctoral Program in Automatic, Electronics, and Communications Engineering. This work has been developed in the context of an industrial thesis under the supervision of the company Portel Logistics Technologies. This company is well known for its specialization in developing cutting-edge software solutions tailored to the precise requirements of information management within the intricate world of maritime transportation and port logistics. Their expertise spans a wide spectrum of services in the logistics sector, making them a prominent player in Spanish port industry. The initiative for the development of this thesis arises from the CIU3A project, which aims to build and set up the University Innovation Center for Andalusia, Alentejo, and Algarve, an innovation and research center of the University of Seville, University of Evora, and University of Algarve. The objective of this center is to promote the transfer of knowledge through collaboration between universities and private organizations to promote industrial development and digitalization in the southern regions of the Iberian Peninsula. In brief, a specialized, international university center that promotes economic development in the region through a focus on innovation and technological development. In the initial stage of this center, four distinct research lines have been established, namely industry 4.0, materials science, sustainability, and maritime and port logistics. Each and every one of these research lines has a common meeting point, which is the development and implementation of technological solutions in the scope of each of the singular projects for industrial improvement in the port environment, particularly in the inland Port of Seville, the place in which the research center’s facilities are located. Specifically, this research work, along with the rest of associated projects, focuses on improving management methods in port infrastructures, with the primary goal of enhancing the management of 2Chapter 1. Introduction Figure 1.1: Spectrum of management and planning problems in inland ports. the Port of Seville. 1.2 Scheduling and navigation in the Guadalquivir River Managing river ports poses a complex challenge due to the intricate nature of coordinating various tasks and resources (see Figure 1.1). The berth allocation problem focuses on optimizing the assignment of berths for incoming ships, ensuring a streamlined flow of vessels. Quay crane scheduling tackles the efficient scheduling of cranes responsible for loading and unloading containers onto and from ships, enhancing overall operational efficiency. Yard crane scheduling addresses the movement and storage of containers within the port’s yard, optimizing crane utilization. Tubgoat scheduling addresses the optimal planning of tugboats, crucial for assisting ships in navigating the river. The container stacking problem involves strategic placement of containers in the yard to maximize space and accessibility. The container drayage problem focuses on planning the transportation of containers between the port and its inland destinations. These challenges underscore the need for sophisticated solutions in port management to minimize delays and enhance overall effectiveness. Within the broad spectrum of management problems in river ports, the focus of this thesis is to concentrate on the challenge of optimal planning and management of navigation in the channel. The objective is to provide detailed insights and information specifically related to this aspect, addressing the complexities and strategies associated with ensuring efficient and effective navigation within natural waterways connected to inland ports. 1.2. Scheduling and navigation in the Guadalquivir River 3 Figure 1.2: Satellite image of the Guadalquivir River connecting the city of Seville and the Atlantic Ocean as it passes through Do˜nana National Park. The Guadalquivir River, flowing through the heart of Andalusia in southern Spain, is one of the Iberian Peninsula’s major waterways. Originating in the Sierra de Cazorla mountains, the river embarks on a journey of over 650 kilometers, meandering through diverse landscapes before emptying into the Gulf of C´adiz. Beginning at the Port of Seville, the Guadalquivir becomes a conduit for maritime activities, connecting the city to the vast network of waterborne trade. The port has been a strategic hub for centuries, facilitating the transport of goods and fostering cultural exchanges. Today, as one of Spain’s principal river ports, Seville’s harbor accommodates a diverse array of vessels, reflecting the river’s enduring role in regional commerce. A satellite image of the Guadalquivir River from the Port of Seville to the river’s estuary is depicted in Figure 1.2. Navigation in the Guadalquivir River is significantly influenced by two key factors: the effect of tides and the bathymetric profile of the watercourse. The influence of tides, with their constant ebb and flow, creates a dynamic and variable environment that directly impacts maritime navigation. The height of tides and their periodic changes affect the river’s depth, posing challenges for navigation, especially in narrower stretches and shallow areas. A detailed description of the effect of the tide on the depth of the river can be found in [1]. Examples of tide measurements at different locations along the Guadalquivir River are shown in Figure 1.3. The sensor locations are not displayed for confidentiality reasons. Furthermore, the bathymetric profile, or the configuration of the riverbed, adds another layer of complexity. This problem is particularly acute in canals that flow 10 Chapter 1. Introduction by varying depths and encounter situations. Specifically, the tool must implement two main functions. On the one hand, we need to calculate safe paths to ensure the existence of feasible routes that do not violate any of the imposed restrictions. Secondly, the tool must be able to implement scheduling algorithms for the optimal planning of navigation in the channel. Furthermore, in order to provide the system with greater flexibility, all the information required by the tool to carry out the planning must be stored in a cloud-based database, so that all information can be accessed in real-time through a query from the tool. 1.4 Literature review 1.4.1 Scheduling in inland waterways In the consumer society we live in, maritime transport is one of the sectors with a greater impact on countries’ development and the growth of global economy [3]. As it has been demonstrated [4], the pace of growth of a country’s economy is directly and highly correlated with the amount of investment on logistic infrastructures and the improvement of maritime transport. Thus, it is of utmost importance to design a road map to adapt existing port systems to meet the requirements of today’s society. This requires not only the modernization of port facilities and the use of new technologies [5], but also the development of more efficient management strategies to improve the efficiency of the overall logistic process [6]. Many research lines have focused on improving the efficiency of different port operations. This is the case of the berth allocation problem (BAP) [7, 8, 9, 10], which deals with optimizing berthing times, or the quay crane scheduling problem (QCSP), which aims at scheduling quay cranes for loading and unloading containers in such a way that vessels’ turnaround times are minimized [11, 12, 13, 14, 15]. In addition, in inland ports connected to the sea coast through some channel or waterway, as in the case of the Port of Seville, the navigation-oriented trip planning of vessels plays a key role in port efficiency. This problem is known as the waterway ship scheduling problem, whose objectives include deciding the optimum entry times into the navigation channel for each of the vessels, as well as the guidelines to be followed by the vessel pilots to navigate optimally through the channel. This problem does not only need to consider matters relating to vessels’ characteristics, but also different exogenous factors that may affect the waterway, such as the effect of the tide on the depth. Due to its great importance in the current economics of maritime transport in this type of channels, several studies have been carried out in the academy during the last years dealing with this problem. 1.4. Literature review 11 In [16], authors aim at enhancing the efficiency of vessel transportation through vessel scheduling in inland ports by effectively coordinating the use of channels and berths. It establishes a mathematical model with the objective of minimizing the total waiting time, considering factors such as scheduling order, travel direction, and berth distance. To address this scheduling challenge, the study employs simulated annealing and multiple population genetic algorithm. By comparing the results to conventional methods, the study demonstrates that the proposed approach significantly reduces waiting times, scheduled time, and maximum waiting time, simultaneously ensuring both safety for vessels and efficiency. In [17] authors introduce a ship traffic scheduling model designed to significantly improve traffic efficiency in constrained waterways. The model assumes that two-way traffic is not allowed when large ships are present. It proposes a mathematical model aimed at minimizing the weighted average of mean and maximum waiting times while considering safety restrictions. To solve this problem, a sequential scheduling algorithm is presented, where ships are organized into rounds, and ships within each round are scheduled simultaneously. This approach enhances traffic efficiency by balancing the priorities between small and large ships. The article also includes experiments comparing the sequential scheduling method with a first-come-first-serve model. The results show that the proposed algorithm reduces waiting times for ships, particularly in cases with a higher proportion of large vessels. It ensures that ships’ waiting times remain at an acceptable level, whereas the first-come-first-serve approach results in long waiting times. In [18] authors develop a fuzzy scheduling optimization method for one-way waterways, aiming to enhance port competitiveness by minimizing ship waiting times, improving traffic efficiency, and accommodating uncertain factors. It extends previous research on one-way waterways scheduling by introducing triangular fuzzy numbers to address ship speed and crossing time times, especially considering tide height constraints. The research employs a genetic algorithm to construct a mathematical model for fuzzy vessel scheduling based on time optimization, and it uses the minimum delay strategy for service sequence determination. The study conducts experimental comparative analyses and concludes that this fuzzy vessel scheduling algorithm enhances efficiency and traffic safety, reduces dependence on port conditions, and avoids issues encountered with manual scheduling methods. Other research lines have focused on solving all the different problems affecting the traffic scheduling problem for some particular waterway or port to provide a global solution, such as the Port of Shanghai. For this, the authors of [19] address the challenge of efficiently managing vessel traffic in a seaport to minimize delays and the number of vessels unable to berth or depart due to congestion. It 12 Chapter 1. Introduction proposes an approach that utilizes a mixed-integer linear program (MILP) and a set-partitioning formulation to optimize traffic scheduling, along with a column generation algorithm and performance enhancement strategies. Computational results were evaluated using data from a specific port, highlighting the effectiveness of the proposed algorithm in reducing computation times. Furthermore, future extensions of the model are suggested, including the integration of berth allocation decisions and the consideration of uncertainties in port operations. As an extension of this work, the authors of [20] address the optimization of capacity and availability in navigation channels and anchorage areas within a container port. The focus of the article is to develop a mathematical model that simultaneously optimizes traffic in the navigation channels, and the utilization of anchorage areas. A mixed-integer programming formulation of the problem is presented, its complexity is analyzed, and a Lagrangian relaxation heuristic is proposed. The computational performance of this heuristic is evaluated on problem instances generated from operational data of a port in Shanghai. The obtained results indicate that the proposed heuristic achieves satisfactory performance within a reasonable computation time, further advancing the research in the efficient management of maritime traffic in ports. In [21], a step further is taken, and navigation management is done taking pilot assignments into account. This article builds upon previous research and addresses the integrated problem of scheduling vessel traffic and pilot assignments in the busiest seaports. It focuses on optimizing the utilization of navigation channels and anchorage areas in the port terminal, aiming to mitigate congestion and enhance vessel service. The problem is formulated on a time-space network with arc costs dependent on both vessels and pilots, and an integer programming model is developed to minimize various associated costs. To solve the problem, feasible vessel paths are enumerated in advance, and the Lagrangian relaxation algorithm proposed in the previous work is employed to decompose the problem into subproblems for vessel and pilot path assignments. The computational performance of the Lagrangian relaxation algorithm is evaluated using problem instances generated from the physical layout and operational data of the Waigaoqiao Port in Shanghai. This approach, which integrates the vessel traffic management problem with pilot planning problem, is also treated in in [22]. This work focuses on the pilotage planning problem in seaports, which involves scheduling vessel traffic, assigning work shifts to pilots, and scheduling pilots for vessel navigation. The problem is formulated as a mixed-integer linear programming model with the objective of minimizing the cost associated with sailing operations. The study shows that this problem is strongly NP-hard. To solve it, a branch-and-bound algorithm is developed, featuring a novel dynamic programming algorithm for pricing. Several acceleration techniques are proposed to enhance the algorithm’s efficiency. Computational experiments reveal that the branch-and-bound algorithm is capable of solving practical-sized problem instances and outperforms both standard commercial solvers . This work is complemented by the work developed in [23], where a problem 1.4. Literature review 13 for scheduling tugboats for mooring and unmooring operations in busy seaports is proposed. In a busy port with a limited number of tugboats, effective scheduling of tugboats is crucial for the execution of vessels’ berth plans. This paper addresses the tugboat scheduling problem, utilizing a network representation and an integer programming formulation that considers vessel berth plans, tugboats, and power requirements. The objective is to minimize the weighted sum of vessel berthing and departure lateness, tugboat operating costs, and the number of vessels that cannot be successfully served. The authors also introduce a novel iterative solution method involving Lagrangian relaxation and Benders decomposition for generating near-optimal solutions. Computational experiments assess the performance of this solution method using operational data from a container port in Shanghai. In the same vein, in [24], authors propose a scheduling problem that aims at addressing inter-shipping line equity in the navigation channel of a seaport while trying to find the best compromise between two conflicting objectives, equity and efficiency, again considering tidal windows to access and sail through the channel. Unlike traditional approaches focused solely on minimizing vessel delays, this study prioritizes addressing inter-shipping line fairness. An innovative lexicographic optimization model is developed, balancing the conflicting goals of efficiency, favoring total vessel delay reduction, and equity, ensuring a fair distribution of delays among shipping lines. The model allows port operators to quantify the trade-off between efficiency and equity and make informed scheduling decisions. To solve this problem, a two-stage solution method is presented. First efficiency and equity are optimized separately. Then the best trade-off between both objectives is determined. The model and solution method are applied to real-world data from the Port of Shanghai, and computational results reveal that an equity-oriented approach can achieve satisfactory service at both the vessel and shipping line levels with minimal losses in efficiency, demonstrating the significance of considering inter-shipping line equity in vessel traffic scheduling. Similar cases can be found for other locations, each with the unique characteristics and circumstances of each waterway. An example could be the numerous works that can be found in the literature focused on the Kiel Canal, the world’s busiest artificial waterway. Under this scenario, in [25], authors introduce a practical optimization problem known as the ship traffic control problem. The canal operates bidirectionally, with large ships only able to pass each other in designated sidings. The objective is to minimize the total waiting times of all ships, necessitating complex decisions about ship priorities, waiting locations, and duration, considering various operational constraints. The authors integrate algorithmic concepts from collision-free routing of automated guided vehicles, providing a unified approach to scheduling and dynamic routing. Their traffic control tool, utilizing combinatorial algorithms, significantly improves scheduling over manual planning and plays a vital role in a canal enlargement project to ensure continued 14 Chapter 1. Introduction operability as traffic volume and vessel sizes increase. In [26], the authors address the ship traffic management challenge in the same canal, focusing on efficient and safe transits. The paper introduces a set of optimization models that consider factors such as variable ship speeds, siding segment capacities, and ship waiting time limits, while adhering to traffic rules and safety requirements. The primary objective across these models is to minimize the total transit time for ships. The authors propose a metaheuristic approach and validate its excellent performance through experiments with real-world data, underscoring its potential to provide high-quality service for ships using the canal. However, regardless of the great interest that this problem has raised, most works focusing on natural waterways do not pay particular attention to the effect of natural phenomena such as the irregular bathymetric profile and tidal effect, which complicates the problem including dynamic constraints. Regarding this issue, in [27], the authors address the waterway ship scheduling problem in the Yangtze River, which is affected by tidal effects. The proposed problem aims to schedule ship traffic along waterways to minimize waiting times, thus addressing congestion and reducing emissions. The authors propose a mixed-integer linear programming model implemented using CPLEX, along with the introduction of greedy heuristics and a simulated annealing algorithm. Computational experiments reveal the inherent complexity of the problem, even with the utilization of a general-purpose solver, while demonstrating that the simulated annealing approaches provide efficient solutions in a short computational time. Comparisons with common queue policies highlight the substantial improvements in reducing unnecessary ship waiting times, resulting in enhanced traffic flow, economic benefits, operational efficiency, and environmental savings. This study emphasizes the adaptability and practical relevance of SA, especially for scenarios affected by tidal effects, offering advantages for terminal competitiveness, cost reduction, and expedited negotiations between terminal operators and shipping companies by quickly generating feasible schedules without compromising performance. This problem is revisited by the same authors in [28]. There, the authors propose a reformulation of waterway ship scheduling problem as a variant of the multi-mode resource-constrained project scheduling problem, incorporating time-dependent resource capacities and time constraints. They solve this problem using integer programming, achieving optimality for all instances in the existing literature. The paper offers a dual contribution by introducing the multi-mode resourceconstrained modeling approach, transferable to maritime logistics applications, and by enhancing results for real-world-based instances. Computational studies demonstrate the benefits of their approach over previous methods, suggesting its suitability for real-time decision support environments. In [29] the authors tackle the issue of efficient vessel scheduling through a one-way tidal channel, with a focus on improving port operational efficiency and addressing delays caused by tidal cycles. They present a model and algorithm 1.4. Literature review 15 designed to optimize vessel scheduling, ensuring the shortest total waiting time for vessels entering the channel. The model and algorithm are validated using real data from the Yangtze River estuary, demonstrating their superior scheduling efficiency compared to alternative strategies, including first-come, first-served, random scheduling, larger draft vessels priority scheduling, and manual scheduling. Furthermore, the adaptable nature of the proposed model and algorithm allows for their application to vessel scheduling in other channels with tide-affected depth. Extensions of this work for two-way and compound tidal channels are proposed in [30] and [31], respectively. In [32], the authors address the challenges of scheduling vessels on restricted waterways due to the increasing size of vessels and the limited possibilities for waterway expansion. The study focuses on a tide-dependent waterway scheduling problem with a passing box, where wide vessels can only pass within the passing box, and vessels with deep drafts are constrained to specific time windows around high tide. The authors present a mixed-integer program for this problem and introduce techniques to enhance the model formulation by minimizing Big- Mvalues, fixing variables, and reducing the number of variables and constraints. The proposed model formulations are evaluated through a comprehensive computational study using real-world data from the Elbe River near Hamburg, Germany. The results indicate that the passing box’s capacity is not restrictive in the studied setting. However, further research is needed to explore the implications of smaller passing boxes, increased passing box capacity, and the development of effective heuristics and meta-heuristics for solving tide-dependent waterway scheduling problems, especially when multiple passing boxes are considered. The refined model formulation can serve as a valuable resource for researchers designing heuristic solutions for such problems. Finally, and given its significant relevance to the present work due to its application to the Guadalquivir River, the reader is referred to [33], where the planning problem in the Guadalquivir waterway is addressed. This paper addresses the complex task of planning vessel navigation along a tidal river, which significantly impacts the efficiency of inland ports and intermodal chains. The study introduces a heuristic procedure designed to schedule vessels on a tidal waterway, aiming to optimize navigation based on a multi-criteria objective function. This function combines various factors, including the number of vessels serviced, total waiting time, waterway occupation time, and the count of crossing operations. The procedure incorporates depth estimation to identify critical navigation points and potential bottlenecks, considering scenarios where vessels may need to anchor and wait for the next tidal window. The procedure is validated through application to simulation scenarios, demonstrating reliable results in terms of performance and solution quality. 16 Chapter 1. Introduction Thesis contribution Despite all the work that has been carried out in the field of scheduling in inland waterways, as reflected, most of the different formulations lead to complex optimization problems that require the application of heuristic methods to be solved. Furthermore, in most cases, either the effect of the tide is not taken into account, or it is considered through complex prediction models that hinder the resolution of the planning problem or through the consideration of crossing windows that do not guarantee the safety of navigation in intermediate sections. All of this leads to the need to develop optimal trip planning for vessels while considering the tide’s effect along the route in a manageable and easily solvable manner by current commercial software, which is one of the main contributions of this work. 1.4.2 Safety-oriented rescheduling in natural inland waterways While a substantial body of research has focused on the planning of vessels in inland waterways, the majority of these studies primarily center on developing scheduling plans optimized for ideal operational conditions. As a result, they may not guarantee optimal outcomes and the safety of various operations when unforeseen events, such as delays or mechanical breakdowns, occur. In recent years, some scholars have advocated for considering decision-making uncertainty, leading to complex optimization challenges, as reflected on the following examples. The importance of proper management of navigation safety in inland waterways is becoming evident and is reflected in the high level of interest generated within academia for developing safety management strategies and accident risk assessment in this type of channels. In [34], the authors introduce an innovative and multifaceted safety evaluation model for the navigation of ships in inland waterways. This model operates at a three-level framework, incorporating advanced principles of fuzzy theory and evidential reasoning. The three-level structure integrates various safety indicators and takes into account both qualitative and quantitative data, resulting in a robust assessment of navigation safety. This pioneering model represents a significant milestone in the field of maritime safety management. It plays a crucial role in preventing potential accidents and providing early warnings for inland waterway transportation. One of the standout features of this research is its recognition of the immense value of real-time monitoring and the utilization of real-time data. Despite occasional gaps in data availability, the research underscores the pivotal role played by real-time information in enhancing safety management. Moreover, it highlights the model’s potential to seamlessly integrate with waterway traffic management platforms. The essential data needed for this model’s operation is sourced from the automatic identification system (AIS) [35]. AIS is a transponder technology that automatically provides vital information, including vessel position data, vessel identification, and other 1.4. Literature review 17 pertinent details, to both fellow vessels and coastal authorities. This comprehensive and multi-level safety evaluation model has the potential to enhance safety practices in inland waterway navigation, making it a valuable asset in the realm of maritime safety management and navigation risk mitigation. Another noteworthy study emphasizing the significance of real-time monitoring and the utilization of AIS data for enhancing navigation safety management in inland waterways can be found in [36]. This article delves into the technical intricacies of enhancing navigation for inland waterway vessels through driverassistance functionalities, with a primary focus on the architectural framework for the delivery of precise and dependable position, navigation, and timing data. The proposed approach integrates AIS communication protocols to facilitate the transmission of global navigation satellite system (GNSS) correction data. The navigation algorithm employs code and phase GNSS observations in conjunction with differential correction data to accurately estimate positioning with centimeterlevel precision. Furthermore, an integrity monitoring algorithm is implemented to ensure data reliability. The research underscores the critical importance of GNSS correction data transmission and explores the potential utilization of AIS as a communication medium. The importance of addressing unexpected events in maritime operations cannot be overstated. These events can significantly impact the optimality and safety of vessel operations, which are critical in natural estuaries. When we look at the planning algorithms that have been developed in this domain, it becomes evident that most of them lack robustness when faced with the inherent uncertainty associated with the diverse range of scenarios that can unfold during a vessel’s journey through a natural estuary. These scenarios can include adverse weather conditions, sudden equipment failures, changes in traffic congestion, and unexpected navigational hazards, among others. These unforeseen events demand a more comprehensive and dynamic approach to planning and safety management, one that can adapt in real-time to minimize the risk of accidents and maintain operational efficiency. Many existing replanning strategies predominantly focus on re-routing vessels between logistic nodes. While this is an essential aspect of maritime operations, it doesn’t adequately address the dynamic challenges vessels encounter along their entire route through a canal. These challenges may involve rapidly changing conditions that necessitate continuous monitoring and decision-making. To overcome these limitations, it is imperative to develop replanning methodologies and safety management systems that are capable of addressing incidents as they occur in real-time. This requires a holistic approach to maritime operations that integrates the principles of safety management, risk assessment, and dynamic replanning. One key aspect of these new methodologies is the incorporation of advanced sensor technologies and data analytics. These technologies can provide 18 Chapter 1. Introduction real-time data on vessel position, weather conditions, water depth, and other critical parameters. By analyzing these data, algorithms can continuously assess the operational context and potential risks, allowing for adaptive decision-making. Moreover, the human element in maritime operations should not be overlooked. Crew members play a crucial role in ensuring the safety and efficiency of operations. Hence, training and education programs should be designed to equip them with the skills to handle unexpected events effectively and make informed decisions under pressure. In addition to the technical and human factors, a regulatory framework must be established to ensure that these rescheduling methodologies and safety management systems are implemented effectively across the maritime industry. Regulations should set standards for real-time incident response, vessel monitoring, and reporting procedures. In [37] the authors delve into the intricacies of ship scheduling within the Kiel Canal, specifically addressing the challenges posed by the uncertainty of ship arrival times and the resulting frequent need for schedule adjustments to ensure feasibility. To mitigate these issues, the authors propose a sophisticated mathematical model that incorporates the concept of time-corridors. These timecorridors act as flexible windows within which ships must arrive, allowing for dynamic scheduling while maintaining the validity of the plans. To efficiently solve this complex problem in practical scenarios, they introduce a heuristic approach that systematically minimizes the necessity for rescheduling. This approach is compared to the prevailing simple waiting heuristic, revealing its superiority in reducing both the frequency of daily reschedules and the overall time it takes for ships to traverse the canal. Furthermore, the study meticulously explores the determination of optimal time-corridor widths, offering insights into the trade-off between minimizing reschedules and ensuring efficient ship transit times. It also investigates the influence of notice time, which represents the advance notice ships provide regarding their estimated arrival times, on the scheduling process. The results show that notice time has a significant impact on rescheduling frequency, underscoring the importance of this parameter in canal scheduling operations. Additionally, the article scrutinizes the effects of upgrading narrow transit segments along the canal. The findings indicate that enhancing these segments, particularly when done collectively, can yield substantial reductions in the average traversing times for ships. For instance, upgrading all the narrow transit segments together can result in a remarkable reduction of more than 19 minutes, equivalent to a 4.4%. In summary, this comprehensive research highlights the advantages of using time-corridors to address scheduling uncertainties, reduce rescheduling requirements, and improve overall efficiency in managing ship traffic through the Kiel Canal. In [38], the authors address the challenging problem of ship sequencing and scheduling in the context of Yangtze River traffic management, especially in restricted waterways. The authors propose an innovative sliding window-based on- 1.4. Literature review 19 line ship sequencing and scheduling algorithm (OSS-SW) to tackle this issue effectively. The OSS algorithm introduces the concept of position shift, capitalizing on differences in ships’ sailing times within the restricted waterway to generate a more efficient ship sequence. The sliding window mechanism is incorporated to handle traffic uncertainties and reduce computational complexity. The study also investigates the impact of congestion in restricted waterways on the performance of the OSS-SW algorithm and thoroughly explores parameter settings. Through both simulation studies and real data applications, the authors demonstrate that the proposed OSS-SW algorithm outperforms existing methods, including the traffic signal revealing system (TSRS) and the expert system-based algorithm (ES), in solving ship sequencing and scheduling challenges in the Yangtze River traffic management. The paper proposes a novel approach by incorporating the sliding window scheme to reduce computational burden and improve solution quality under various uncertain scenarios. The experiments confirm that the proposed OSSSW method achieves similar or better performance than the OSS-only method and outperforms TSRS and ES methods. The algorithm demonstrates its effectiveness in obtaining optimal ship sequences for both upstream and downstream traffic, significantly reducing computational complexity. Additionally, Monte Carlo simulations reveal the algorithm’s robustness under different scenarios and parameter settings, suggesting that it can handle ship sequencing and scheduling challenges effectively in restricted waterways. The study concludes by highlighting the potential for further development of online optimization methods in the future to enhance inland waterway capacity, such as the Yangtze River, despite the inherent complexity of the ship sequencing and scheduling problem. In [39], the authors focus on the problem of optimizing vessel speeds, particularly when faced with uncertainties related to waiting times at locks due to unpredictable processing time estimations of other vessels. The primary objective is to minimize fuel consumption for approaching ships while adhering to predefined deadlines for traversing river segments. To tackle this challenge, the authors introduce a sophisticated mathematical optimization model that takes into account the uncertainties inherent in lock operations. This mathematical model forms the basis for two distinct solution approaches: an optimal solution employing complex mathematical algorithms to determine the most fuel-efficient speeds, and a simplified heuristic offering practical guidance for skippers to make informed speed choices that balance fuel efficiency with transit times. These approaches are developed to empower skippers with effective strategies for decision-making amid unpredictable lock waiting times, ultimately aiming to enhance operational efficiency and sustainability in inland waterway transportation. Thesis contribution As shown above, several attempts have been made to develop real-time monitoring systems for vessel navigation. In addition, different works have been carried out 26 Chapter 1. Introduction Figure 1.5: Chapter organization. measures the average worst-case loss. With this purpose, we introduce a distributionally robust risk-aware model predictive control (DR-MPC), which is robust against distributional inaccuracies within an ambiguity set of probability distributions. This approach aims to ensure high-performance and safe control actions even with inaccurate information. The ambiguity set is designed as a statistical ball around a nominal distribution, and the distance between distributions is measured using the Wasserstein distance. To address the intractable nature of the DR-MPC problem, a Kantorovich duality-based strategy is employed to reformulate it into a finite-dimensional nonconvex optimization problem, solvable with standard commercial solvers. This work represents a pioneering application of distributionally robust optimization (DRO) and distributionally robust control (DRC) in the field of maritime transportation. Using depth sensor data collected in the Guadalquivir River, we empirically demonstrate the performance of our risk-aware Wasserstein DR-MPC approach that solves the navigation control problem of vessels in the presence of inaccuracies in the empirical distribution. Our findings indicate that the approach successfully controls the vessel along the waterway without any collisions, even with a limited dataset of only six observations, while the standard non-robust, risk-aware model predictive controllers result in high collision rates. 1.6. Publications 27 •In Chapter 5 it is presented the implementation of an open source software tool for the scheduling of vessels in natural inland waterways, taking the Guadalquivir River as an example. This tool implements two main functionalities. On the one hand, it performs the calculation of the safe navigation tubes for each of the vessels taking into account the restrictions imposed by the channel depth and the maximum speed in each location of the river as presented in Chapter 2. To this end, a software architecture using Python programming language and a cloud-based data storage system is presented. First, the overall system architecture and the different functionalities of the tool are detailed. Secondly, each and every module and function of the tool is analyzed in detail, showing special interest in the interconnection between the different modules and the management of input and output data of each module. The performance of the tool is shown through a real example of application in the Guadalquivir River. This tool has been made available to the community through a free distribution system. The access procedure is detailed at the end of the chapter. 1.6 Publications The contributions of this dissertation are supported by several journal and congress publications, some of which are currently under review. The scheduling methodology proposed for planning vessels’ trip plans in natural inland waterways, together with the algorithm and reachability analysis for finding optimal navigation tubes can be found in: Tube Based Safe Planning on Natural Inland Waterways Published in: 2022 European Control Conference (ECC). Date of publication: 5 August 2022. DOI:10.23919/ECC55457.2022.9838018. Safe navigation through waterways of time-varying depth based on reachability analysis Published in: 2023 European Control Conference (ECC). Date of publication: 17 July 2023. DOI:10.23919/ECC57647.2023.10178411. 28 Chapter 1. Introduction Safe Optimal Vessel Planning on Natural Inland Waterways Published in: IEEE Transactions on Intelligent Transportation Systems. Date of publication: 18 April 2023. DOI:10.1109/TITS.2023.3266563. The rescheduling methodology for incident management in natural waterways can be found in: Real-time monitoring and optimal vessel rescheduling in natural inland waterways Published in: IFAC Papers Online from IFAC World Congress 2023. Date of publication: 17 July 2023. DOI:10.1016/j.ifacol.2023.10.023. Dynamic Rescheduling for Optimal Transportation Incident Management in Inland Waterways Published in: IEEE Transactions on Intelligent Transportation Systems. Date of publication: Under review. DOI: To be determined. The risk-aware Wasserstein distributionally robust control of vessels in natural inland waterways can be found in: Risk-Aware Wasserstein Distributionally Robust Control of Vessels in Natural Waterways Published in: IEEE Transactions on Control Systems Technology. Date of publication: To be determined. DOI: 10.1109/TCST.2024.3355014. The practical implementation of a software tool for vessels scheduling in natural inland waterways can be found in: WPlanPy: A Tool for Safe Navigation Planning in Natural InlandWaterways 1.6. Publications 29 Published in: 2024 European Control Conference (ECC). Date of publication: to be determined. DOI: to be determined. 30 Chapter 1. Introduction 31 Chapter 2 Optimal scheduling in inland waterways 2.1 Introduction Most formulations of the scheduling problem in artificial or natural waterways affected by natural phenomena do not consider the effect of time-changing depth at each location of the waterway but rather focus on finding tidal windows to access or leaving the channel. In the present chapter, we propose a more general formulation of the planning and scheduling problem in inland waterways while ensuring the existence of a feasible trajectory considering all the different natural and operational constraints affecting navigation in this type of waterways. A two-step solution is proposed. In the first step, a series of tubes (collection of time windows) that ensure the existence of a feasible solution are found. In the second step, a planning problem is proposed, where we take as decision variables the times when each vessel crosses a series of waypoints contained in the tubes found in the previous step. We take as example the case of the Guadalquivir River, where navigation is hampered by its location in a highly protected natural area. This affects the overall management of the Port of Seville, which is the main intermodal logistic node connecting the Canary Islands to the rest of Spain [50]. Because of the impossibility of carrying out almost any adaptation work in such a vulnerable area, the only way of expanding the capacity of the waterway is by improving the management of vessels, something that requires adopting new technologies and managing strategies in the context of smart ports and industry 4.0 [51]. The objective is to find, for a given set of vessels arriving at both extremes of the waterway, the optimal trip plans that minimize some performance criteria that depends on the time vessels spend waiting and navigating through the waterway while satisfying a series of operational constraints. For each vessel, its optimal trip plan is a series of times when each vessel should cross a series of boundaries 32 Chapter 2. Optimal scheduling in inland waterways that divide the waterway into different sections, minimizing some performance index and ensuring that, for any vessel adhering to its optimal trip plan, there exists at least one feasible trajectory that satisfies all operational constraints. We show that the proposed two-step solution can be implemented using offthe-shelf solvers in real time for a number of vessels much higher than the current demands of the Port of Seville. In addition, we demonstrate that it also outperforms a commonly employed solution in which the trip plans of the vessels are planned by means of a first-arrived first-served policy. This policy not only leads to suboptimal decisions, but also increments the probability of suffering an accident due to the human component in the process [52]. This issue will be extensively addressed in Chapter 3. It is important to remark that the objective of this chapter is not to control vessels’ motion in the waterway, a topic extesivley addressed in Chapter 4, but to develop a planning tool to provide a set of indicative times when each vessel should cross each boundary in the waterway. Thus, the problem of vessels’ motion control is not addressed in this chapter, and it is assumed that it is the pilot’s responsibility to control the vessel and adhere to the provided trip plan. 2.2 Vessel planning in natural inland waterways In this section we focus on planning the trips of the vessels according to the demands of the port authorities. Navigation issues are assumed to be handled by the vessel pilots in order to follow the trip plan. One of the main difficulties when planning the trips of the vessels through a natural waterway is the irregular bathymetric profile because it restricts their maximum allowable draught. In the case of the Guadalquivir River, due to the regulatory measures for the conservation of the area where the waterway is located, dredging operations are not allowed [53], something that would greatly simplify the planning problem. The bathymetric profile of the Guadalquivir can be found in [2], where it was obtained by making use of a multibeam echo sounder. The other critical natural factor that influences navigation in the waterway is the effect of the tide. To obtain a map of the tide for a period of one week, we use predictions obtained using the first principle models developed in [54]. Combining these predictions with the bathymetric profile, the map shown in Figure 2.1 has been obtained. Note that this map is a graphical representation of a matrix D whose elements dm,n provide the depth of the waterway at time min location n. The number of rows and columns of Ddepend on the time-space discretization employed (one value every 6 minutes (1/10 h) and every 100 meters (1/10 km)). This map will be employed to carry out all the experiments presented in Section 2.5. 2.2. Vessel planning in natural inland waterways 33 Figure 2.1: Prediction of the depth of the Guadalquivir waterway for the week considered. Using the map represented in Figure 2.1, it is possible to find, for a given vessel, the time-space points in which it can sail taking into account its draught. The map depicted in Figure 2.2 has been obtained for vessels with a draught of 7.5 meters, where the dark blue zones represent those regions to be avoided by the vessels in order to prevent a grounding accident. Besides the constraints imposed by the time-varying depth of the waterway, it is important to guarantee safe encountering situations among vessels, i.e., it must be ensured that the sum of beams of any two vessels undergoing an encountering situation fits to the width of the channel at the point where the maneuver occurs while following the international regulations for preventing collisions [55]. A feasible trip plan for a set of vessels adapts the sailing speed of the vessels in such a way that shallow sections are crossed during high tide windows and that head-on and overtaking encounters occur in wide sections. Currently, in the port of Seville, the trip plans are obtained manually and sent to the vessel pilots. Calculating the trip plans is time consuming and may lead to non-optimal trip plans. The objective of the proposed scheduling algorithm is to solve this problem automatically minimizing waiting and sailing times while reducing the risk of accident due to human errors. 34 Chapter 2. Optimal scheduling in inland waterways Figure 2.2: Map of time-space regions in which a 7.5 m draught vessel may sail for the week considered. 2.2.1 Proposed two-step solution The objective is to find the optimal trip plans for a set of Nvessels that have to cross a natural waterway. We do not consider anchorage areas inside the waterway. Each of these vessels is characterized by its beam bi, its maximum speed vi, its draught δi, and the time when they arrive to the waterway tready i, where the integer i∈ I =NN 1={1, ..., N}denotes the index of the vessel. The set Iuincludes all vessels sailing upstream, while the set Idincludes all vessels travelling downstream. Thus, I=Iu∪ Id. We assume there is an anchoring area at each extreme of the waterway in which vessels can wait until they are scheduled to enter the waterway. One possible option to solve the planning problem is to decide the speed of each vessel using a time-space discretisation. However, this approach leads, in general, to highly complex problems. To overcome this issue, in the proposed solution we take as decision variables the times in which each vessel crosses a series of boundaries. To this end, we consider that the waterway is divided into Zsections, where the first section corresponds to the river estuary and the last one to the entry lock of the Port of Seville. Each section p∈NZ 1is characterized by its length, dp, by the maximum speed at which vessels can sail through it, µp, and by the practical width of the section, wp. Because of safety reasons, the sum of the beams of any two vessels undergoing an encountering situation is limited by the practical width of the section. 2.2. Vessel planning in natural inland waterways 35 The trip plan of each of the vessels is defined by the times in which the vessel must cross each of the boundaries between the different sections, including both extremes of the waterway, p= 0 and p=Z, respectively. With a slight abuse of notation, we denote these times as ti,p, where in this case p∈NZ 0denotes the northernmost boundary of section pincluding both extremes of the waterway located in the river estuary and the entry lock of the Port of Seville, which are boundaries p= 0 and p=Z, respectively. The sequence of times ti,p is increasing in pwhen a vessel sails upstream and decreasing in pwhen a vessel sails downstream. With this choice of the decision variables, all constraints considered can be modelled in an efficient way as presented in the following sections. Knowledge of these times and the length of each of the sections allows river pilots to estimate the speed at which vessels should sail through each of the sections to meet the optimal plan. To solve this problem, we propose a two-step approach. First we calculate the sets of time windows in which each vessel is allowed to cross each of the boundaries of the waterway given their arrival times and the maximum trip duration. An algorithm is presented to calculate these sets for a single vessel, in a way such that for any travel plan that lies inside one of these sets, it is always possible to cross the waterway satisfying both the time-varying depth constraint, given by the irregular bathymetric profile and the prediction of the tide, and the maximum speed constraint. Once these sets are computed for all vessels, a mixed-integer linear program is proposed to decide the optimal trip plans for all vessels taking into account the variable width of the waterway. This restricts the sections of the channel where encountering situations can occur according to the beam of the vessels and the width of the waterway. As an additional operation constraint, vessels must complete their trip in less than DLhours from their arrival to the waterway at tready i. Limiting the length of the trip to DLis an indirect way of limiting the minimum speed of the vessels. Also, it is assumed that encountering situations are handled following the international regulations for preventing collisions at sea [55] by the river pilots and that encountering situations do not affect the mean sailing speed of the vessels. In the proposed solution we do not consider the length of the vessels in the crossing times. To take into account this issue, we consider an additional constraint on the crossing times at each boundary. That is, a time gap ∆0between two vessels crossing the same boundary is included in the planning problem. Remark 2.1. Note that, because the objective of this work is not to control vessels’ motion but to develop a tool for scheduling vessels in natural waterways and provide an indicative safe crossing time through each boundary, nautical effects 42 Chapter 2. Optimal scheduling in inland waterways Figure 2.7: Safe tube tree for the three section example waterway. J=α·"X i∈Iuti,Z −ti,0+X i∈Idti,0−ti,Z | {z } Navigation cost(CN) # +β·"X i∈Iuti,0−tready i+X i∈Idti,Z −tready i | {z } Waiting cost(CW) #, (2.1) where αand βcan be chosen to weight differently navigation and waiting costs. 2.4.2 Speed constraint In each section of the waterway, there is a maximum speed that vessels can not exceed given by ¯µi(p). This speed determines the minimum period of time needed for any vessel to sail through section p. To model this issue, for each section p∈NZ 1, and for each vessel i∈ Iu, the following constraints are included (ti,p −ti,p−1)·¯µi(p)≥dp,(2.2) ti,0≥tready i.(2.3) 2.4. Optimal vessel planning 43 In addition, for each section p∈NZ 1and for each vessel i∈ Idthe following constraints are included (ti,p−1−ti,p)·¯µi(p)≥dp,(2.4) ti,Z ≥tready i.(2.5) 2.4.3 Safe tube selection To select the safe tube in which vessel i∈ I sails among the ones found using the algorithm presented in the previous section, Ki, a set of binary decision variables ri,k is considered, with k∈ Ki. If ri,k takes value 1, then the trip of vessel imust be contained inside tube k. The rest of the variables corresponding to other safe tubes must take value zero. To this end, for each vessel iand for each p∈NZ 0the following set of constraints is considered ti,p ≤tmax i,k,p +M·(1 −ri,k),(2.6) ti,p ≥tmin i,k,p −M·(1 −ri,k),(2.7) X k∈Ki ri,k = 1.(2.8) 2.4.4 Encountering situations constraint Finally, it is important to guarantee that encountering situations between vessels, both overtaking and head-on maneuvers, occur at points with a practical width greater than the sum of the beams of the vessels involved. To this end, for each pair of vessels iand jwith i, j ∈ I and i < j a binary decision variable ci,j,p is included for each boundary p∈NZ 0in the optimization problem. This variable is equal to one if both vessels encounter head-on or overtake each other in section p. The value of the variables corresponding to forbidden manoeuvres is set to zero; that is ci,j,p = 0 ∀i, j, p such that bi+bj> wp.(2.9) We assume that each vessel iarrives at all boundaries of the waterway before vessel j > i up to the boundary pin which ci,j,p takes value 1. After this event, vessel jarrives at the following boundaries before vessel i. If the values of these variables for all sections pare equal to zero or if ci,j,0= 1, vessels never encounter each other. In addition, a minimum time gap ∆0between two vessels crossing the same boundary is considered. 44 Chapter 2. Optimal scheduling in inland waterways Figure 2.8: Example of all possible values ci,j,p can take for a 3 section waterway. To model these issues the following constraints are included in the optimization problem: ti,p + ∆0≤tj,p +M·X l∈Np 0 ci,j,l,(2.10) tj,p + ∆0≤ti,p +M· 1−X l∈Np 0 ci,j,l!,(2.11) where Mis a number significantly larger than the value of ti,p and ∆0is the minimum time difference between the crossing times of both vessels. To guarantee that each pair of vessels i, j can only encounter each other once during their trip, the following constraint is included X p∈NZ 0 ci,j,p ≤1.(2.12) 2.4. Optimal vessel planning 45 In Figure 2.8, all possible encountering scenarios for two vessels sailing in opposite directions are shown for a simple example of a waterway divided into three sections. In this figure, the horizontal axis represents the distance between both extremes of the waterway. The boundaries of the sections are shown in continuous blue lines. The vertical axis represents time, being the initial time of the scheduling at the top of the figure. Vessel trajectories are represented by dashed black and green lines with encounters highlighted by red stars. For vessels travelling in the same direction, a similar figure can be drawn. In the left of the figure, the corresponding value of the binary variables for each scenario is shown. Remark 2.5. The encountering situations constraint can be modified to allow several overtaking or head-on maneuvers among two vessels. This option is not taken into account in this thesis. Remark 2.6. It is assumed that vessels undergoing any encountering situation do not change their speed during the maneuver. 2.4.5 Optimization problem Using the previously described constraints, (2.2) to (2.12), the optimization problem proposed to find the optimal values of the decision variables that define the optimal sailing plan, t∗,c∗and r∗can be formulated as t∗, c∗, r∗= arg min t,c,r Js.t (2.2) −(2.12).(2.13) In the proposed optimization problem, we assume that the objective is to decide the trip plans for all vessels considered. However it is also possible to consider vessels with trip plans that cannot be modified. This allows to address different scenarios that arise in normal operation conditions, such as including a newly arrived vessel to a waterway in which there are vessels already sailing or even when rescheduling is needed due to unexpected events. Also note that the arrival time of any vessel could be imposed by adding a new constraint that fixes the value of ti,Z or ti,0to the desired time for vessels travelling upstream and downstream, respectively. Remark 2.7. The proposed procedure is based on an NP-hard optimization problem, and hence, it may not be appropriate for a high number of vessels or waterway sections. In the simulation section we demonstrate that the proposed solution can be applied to the current demands of the Port of Seville. The complexity of the optimization problem depends mainly on the number of vessels N, the number of sections Zand the number of safe tubes for each ship. In particular, the number of constraints and binary variables grow with the square of Nand linearly with Z and the number of tubes. 46 Chapter 2. Optimal scheduling in inland waterways Table 2.1: Guadalquivir waterway parameters. id d(km)µ(km/h)wid d(km)µ(km/h)w 11.9 10.1860 1 13 4.2 19.4460 8 21.4 16.6680 4 14 4.5 19.4460 1 34.5 16.6680 2 15 3.5 22.2240 8 44.2 17.5940 4 16 1.2 18.5200 4 52.0 17.5940 4 17 3.4 21.2980 4 65.2 18.5200 4 18 1.7 23.1500 4 76.6 21.2980 4 19 2.0 23.1500 4 83.5 21.2980 4 20 4.2 23.1500 4 95.9 21.2980 2 21 3.0 22.2240 1 10 5.4 22.2240 4 22 2.2 18.5200 8 11 2.1 22.2240 4 23 4.8 21.2980 1 12 4.7 22.2240 1 24 4.9 21.2980 2 2.5 Simulation results In this section, we apply the proposed trip planning method to the case of the Guadalquivir River. To validate the proposed approach, a series of randomly generated scenarios are considered. All optimization problems have been solved using Gurobi solver [57]. The simulations have been carried out on an AMD Ryzen 5 platform working at 3 GHz. 2.5.1 Model parameters The Guadalquivir River is divided into a total of Z= 24 sections, and hence, there are a total of 25 boundaries. Each of these sections pis characterised by its length dp, the maximum speed at which vessels can sail through it µp, and its width wp, whose values are detailed in Table I 1. The beams of the vessels are categorised in three categories, namely small, medium and large, which are quantified as 1, 2 and 4, respectively. The width of each section, rather than its real measure, receives a value contained in the discrete set {2,4,8}. Only vessels whose sum of beams is less than or equal to the width of the waterway can encounter in that section. In all the simulations carried out in this section, the objective is to minimize the total trip time of all vessels considered, and hence, the weights αand βare both set to 1. In addition, we consider a minimum time between crossings of ∆0= 1 h/10. 1All data employed to generate the different scenarios are provided by the local authoritiesg with slight modifications for confidential matters. 2.5. Simulation results 47 2.5.2 Scenario generation In order to analyse the performance of the proposed approach, it has been applied to a number of different randomly generated scheduling scenarios. Each scenario is defined by the following parameters: •N: number of vessels considered, half of them sailing upstream and the other half sailing downstream. •tinit: Initial time of the scenario. •λ: Characteristic parameter of a Poisson distribution used to define the time interval between two consecutive arrivals of vessels to the same end of the waterway. •DL: Maximum period of time a vessel is allowed to be sailing before reaching its final destination. Each scenario generated using these parameters is defined by the sequence of times in which vessels arrive to the waterway. The sequence at each end of the waterway is obtained following a Poisson distribution with characteristic parameter λ, starting both sequences at time tinit. The width of each vessel is determined randomly following an uniform distribution. We assume that all vessels have a draught equal to 7.5 meters, which approximately corresponds to the draught of the largest vessel currently operating in the Port of Seville, to account for the worst case scenario. 2.5.3 Simulation results In this subsection, we show the simulations carried out to test the proposed approach and analyze the obtained results. We show the main properties of the proposed approach in terms of computational complexity, optimality, and feasibility, and how this approach outperforms a first-arrived first-served policy which optimizes vessels as they arrive to the waterway without modifying the trips of other vessels already sailing through it. Due to the discretization of the map of depth, units [h/10] and [km/10] are employed in all the simulation. The complexity of the optimization problem depends mainly on the number of vessels N, the number of sections Zand the number of safe tubes for each vessel. In what follows we illustrate how the number of constraints and binary variables grow with the number of vessels N, the number of sections Z, and the number of tubes. We also analyze the impact of these variables on the computational time. The MILP problem is NP-hard and the computation time grows exponentially with the number of binary variables. 48 Chapter 2. Optimal scheduling in inland waterways Figure 2.9: Number of binary variables, constraints and safe tubes as a function of N. Figures 2.9 and 2.10 show the effect of the number of vessels considered, N, on the complexity of the problem, the different costs, and the computing time. The results shown are the average values of 50 different scenarios for increasing values of Nand fixed values of λand DL. The initial time of each scenario is chosen randomly in the first 24 hours of the week. In this set of scenarios, vessels arrive both at the port of Seville and the river estuary with a mean frequency of λ= 3 hours and have a maximum of DL= 18 hours to reach their destination. In these simulations, the width of the different vessels has been randomly generated. Figure 2.9 shows the number of binary variables, constraints and safe tubes. This figure shows that the number of binary variables and constraints grow polynomially with N, while the number of safe tubes is almost linear. Figure 2.10 shows the computation time needed to solve the problem using Gurobi, and the waiting and navigation costs. This figure shows that the computation time grows exponentially as expected while the costs grow almost linearly. We notice that, even for a large number of vessels, the optimization problem is solved within a reasonable time. Note that, because the set of safe tubes can be computed in advance knowing the prediction of the time, this time has not been considered. Figure 2.11 shows the effect of the maximum trip time DLon the complexity of the problem in terms of the number of safe tubes for a total of 12 vessels, i.e., N= 12 and a fixed value of λ= 3 hours. As it can be seen, the number of safe tubes grows with DL. In Table 2.2 we show the time it takes to compute these 2.5. Simulation results 49 Figure 2.10: Optimization time; waiting and navigation costs. Table 2.2: Safe tube computing time as a function of DL DL[h/10] 100 120 140 160 180 200 Comp. time [s] 1.48 1.78 2.14 2.57 3.25 4.22 sets of safe tubes applying the procedure detailed by the flow diagram depicted in Figure 2.5 as a function of DL. As it can be appreciated, computing time grow exponentially with the value of DL. It is also interesting to see how, given the periodic nature of the tide, the number of tubes generated strongly depends on tready i. This is shown in Figures 2.12 and 2.13 for vessels sailing upstream and downstream, respectively. As it can be seen, both grow exponentially with DL, but the number of tubes generated when sailing downstream is greater than the number of tubes generated when sailing upstream. This is because in the case of vessels sailing upstream, the only option is to surf the wave generated by the tide, while when sailing downstream the vessel may have to wait for the next tide to overcome some points of the waterway, and often this can be done in different times of the trip, leading to multiple options to arrive before the time limit tready i+DL. Regarding waiting and navigation costs, it is important to see that these can be affected by the values of the waiting parameters αand β, for the navigation and waiting costs, respectively. To see the effect of these parameters on the costs included in the performance index, simulations have been carried out varying the value of αfor a fixed value of β. In these simulations, the value of DLhas been fixed to 200 h/10, the number of vessels considered is N= 6, and the arrival frequency parameter has been fixed to λ= 3 hours. The results obtained are the mean values of a series of 100 randomly generated scenarios. These are shown in 50 Chapter 2. Optimal scheduling in inland waterways Figure 2.11: Number of safe tubes with respect of DLfor a fixed value of tready i. Table 2.3: Effect of the weighting parameters on waiting and navigation costs. α β CWCN 0.5 1 21.13 686.87 1 1 76.36 631.5 1.5 1 319.24 388.62 2 1 533.26 275.61 2.5 1 637.25 223.61 Table 2.3. Choosing an appropriate value for DLis important because if it is chosen too small, it may not be possible to reach the destination during that period, yielding and infeasible problem. To demonstrate this issue, we present a simulation in which 50 random scenarios are generated fixing N= 12 and λ= 3 hours for decreasing values of DL. The results are shown in Table IV. For each value of DL, the percentage of scenarios starting in an initial random time on the first 24 hours which are not feasible (% UF) are obtained. As expected, if DLis too small, the vessels cannot reach their destination because no feasible tube can be found. It is important to remark that those vessels that need longer trip times are those travelling against the tide from the estuary of the river to the Port of Seville. These vessels need over 16 hours to ensure that a feasible tube will exist. Remember that the worst case scenario is considered, i.e, vessels of a draught equal to 7.5 meters. We present next some experiments that demonstrate that using the proposed 2.5. Simulation results 51 Figure 2.12: Number for tubes generated for vessels sailing upstream as a function of DL and tready i. Table 2.4: Effect of DLon the feasibility of the problem. DL[h/1] 150 160 170 180 190 200 210 220 % UF 100 86 50 6 0 0 0 0 planning approach can improve the performance of the port. To this end, the proposed approach is compared to the baseline solution in which in each scenario, vessels are scheduled individually as they arrive to the waterway. This is a firstarrived first-served (FA/FS) approach in which an operator schedules each vessel optimally considering the speed, depth, and width constraints while fixing the plan of the previous vessels. This first-arrived first-served approach does not profit from the possibility of planning all vessels simultaneously, leading to a worse performance as demonstrated in the results. The planning in the first-arrived first served approach is solved by fixing the values of the previously planned trips for vessels getting earlier to the waterway. The first simulation demonstrates that, for an increasing frequency of vessel arrivals (λ), feasibility issues may arise if vessels are scheduled individually, which in real operation means that vessels inside the waterway may have to modify their previously decided plans. The results are shown in Table V, where the percentage of unfeasible scenarios using both the baseline and the proposed approach are shown (UF Baseline and UF Proposed, respectively). In these scenarios, N= 8, DL= 18 hours and tinit = 0. We consider two different cases. In the first one, to account for the worst-case scenario, all vessels are large, i.e., bi= 4. In the 58 Chapter 3. Safe optimal rescheduling in inland waterways Figure 3.2: Decision tree for classifying vessel incidents. In this classification tree, zi(tcurrent) refers to the expected location of vessel iat current time tcurrent according to the optimal plan. z† i(tcurrent) refers to the location of vessel iprovided by the AIS signal also at current time tcurrent.viis the average speed of vessel iestimated using a certain number of past location data from the AIS signal. vbreak is the threshold for determining breakdown incidents. equipment. When a vessel experiences a mechanical failure, it may become immobile, lose control, or drift into restricted areas, thereby escalating the risk of accidents. Additionally, unforeseen maintenance issues may arise within inland waterways, necessitating immediate attention and potentially causing disruptions to vessel operations. The nature of these maintenance issues can vary in severity, ranging from minor repairs to more extensive tasks requiring extended periods of vessel downtime. Unanticipated maintenance problems not only contribute to delays but can also exacerbate congestion or operational disruptions, thereby increasing the risk of accidents. In this study, our focus centers on three specific types of incidents: •Arrival Delay: This occurs when a vessel arrives at the waterway later than originally anticipated in the initial scheduling ([59]). •Breakdown: This incident occurs when a vessel experiences a mechanical breakdown, necessitating a halt in its sailing. 3.3. Anomalies detection and identification 59 •Speed Reduction: In this scenario, a vessel is required to reduce its speed, often as a precaution to prevent engine overheating. Moreover, various factors, including weather conditions, water currents, and vessel size, can also influence the vessel’s speed ([60]). These three categories of incidents are commonly observed in the Guadalquivir River and necessitate individual attention from port authorities. In general, this task is time-consuming and can occur at any time during the day. By comprehending the root causes, potential repercussions, and implementing suitable mitigation measures for these incidents, our objective is to bolster vessel safety, optimize operational efficiency, and minimize the risks associated with inland waterway navigation ([61]). In this study, we introduce an anomaly detection and identification algorithm that relies on the AIS signal. In the preceding section, we presented a scheduling algorithm aimed at determining the optimal crossing times for vessels at each boundary within the waterway, denoted as ti,p. Assuming vessels maintain a constant speed within each section of the waterway, it becomes feasible to compute the expected location of each vessel, denoted as zi(t). To verify vessel compliance with their optimal trip plans, we employ a monitoring system. This system continually compares the expected vessel location, zi(t), with the actual location provided by the AIS, denoted as z† i(t). If a substantial deviation exists between the expected and actual locations, surpassing a predefined threshold value ϵz, an unexpected incident is flagged. The threshold value ϵzsignifies the maximum allowable deviation between the expected and actual vessel locations. Through continuous monitoring of vessels, this system can issue early warnings of potential incidents, affording authorities the opportunity to intervene before accidents occur. Let tcurrent be the current time. Let ¯vibe the average speed of vessel iconsidering the last Nwmeasures from the AIS signal. Let vbreak be the breakdown threshold established for determining a breakdown incident. We assume that no incidents occur until rescheduling is carried out after an active incident. In case an incident is detected, it is classified as arrival delay if the vessel is located at one of the extremes of the waterway. If the vessel is sailing through the waterway when the incident is detected, and the estimated average speed ¯viis below the breakdown threshold vbreak, the incident is classified as breakdown. Otherwise, the incident is classified as speed reduction. This classification algorithm is illustrated by the decision tree represented in Figure 3.2. 60 Chapter 3. Safe optimal rescheduling in inland waterways 3.4 Rescheduling strategy When unforeseen incidents, such as those previously described, occur in inland waterways, it may become necessary to reschedule vessel trips to ensure safe and optimal operations under the new circumstances. This entails analyzing the updated conditions and making adjustments to vessel schedules, taking into account factors such as the incident’s nature and severity, the existing traffic conditions, and any relevant regulations or guidelines. Suppose an unexpected incident is detected at time t×involving vessel i∗. At that moment, the location of each vessel ialready navigating in the waterway is denoted as z† i(t×), and the last boundary it crossed before the incident is identified as p× i. To derive the new optimal trip plan tfor all vessels, a fresh optimization problem must be solved, incorporating the current location of all vessels already underway in the waterway. In the event of a speed reduction incident, the rescheduling process involves modifying the maximum speed at which the affected vessel can sail, replacing it with ¯vi∗. This speed is estimated based on the last NAAIS signals received. In this scenario, rescheduling takes place immediately upon incident detection at time t×. For breakdown incidents, the rescheduling problem must be addressed after the affected vessel is prepared to resume its journey, denoted as trepair. In cases of arrival delay incidents, the rescheduling process is initiated after the vessel has arrived at the waterway, and the incident has been detected. The specific timing of rescheduling varies based on the type of incident. Figures 3.3-3.5 provide a visual representation of when vessels are rescheduled, depending on the incident type. When conducting rescheduling, two conflicting considerations come into play. The first revolves around ensuring that the new trip plan achieves both optimal performance and maximum safety for all participating vessels. The second issue entails assessing the number of vessels that will be affected by the rescheduling process, which encompasses vessels that may need to adjust their own trip plans or schedules in response to the incident. Minimizing the impact on the number of affected vessels is of paramount importance, as significant disruptions or delays can detrimentally affect the overall efficiency and competitiveness of the port. Notably, substantial delays or operational disruptions can tarnish the port’s reputation and dissuade future business engagements [62]. Striking a balance between these conflicting concerns necessitates a comprehensive understanding of the specific incident and its potential repercussions on vessel operations. This often entails close collaboration with vessel operators and other stakeholders to collect and analyze data on vessel movements, traffic patterns, and other pertinent factors. Recognizing the critical balance between optimizing performance and ensuring safety while safeguarding the reputation and competitiveness of the port, it 3.4. Rescheduling strategy 61 Figure 3.3: Detection and rescheduling time for arrival delay incidents. ∆delay is the time difference between the expected and real arrival times to the waterway. Figure 3.4: Detection and rescheduling time for speed reduction incidents. ∆taux i∗is the time needed to sail from the location of the vessel when rescheduling is carried out until the location of the next boundary sailing at maximum speed represented by µ. 62 Chapter 3. Safe optimal rescheduling in inland waterways Figure 3.5: Detection and rescheduling time for breakdown incidents. becomes imperative to explore various rescheduling approaches. In this study, we put forth three distinct rescheduling approaches: isolated rescheduling, global rescheduling, and multi-objective rescheduling. Subsequent subsections delve into each of these approaches, offering a comprehensive description and outlining general formulations. These rescheduling strategies are designed to address the challenges posed by arrival delays, speed reductions, and breakdown incidents in a systematic and effective manner. 3.4.1 Isolated rescheduling In the case of the isolated rescheduling strategy, the primary objective is to determine a new optimal and feasible plan exclusively for the affected vessel, while leaving the trip plans of the remaining vessels (and consequently their arrival times at their respective destinations) untouched. It’s important to note that when dealing with a breakdown incident, several specific considerations come into play during the rescheduling process. Firstly, it is assumed that, regardless of where the breakdown occurs, the affected vessel can be safely docked along the waterway’s bank. This assumption hinges on the channel’s width being sufficient at any given point to accommodate the vessel without impeding navigation or violating the crossing and head-on constraints laid out in the original plan. Secondly, it’s crucial to emphasize that the unaffected vessels within the fleet should continue sailing according to their original schedules until the new rescheduling process is executed. This proactive approach minimizes the risk of additional delays or complications arising from schedule modifications. Lastly, the rescheduling process must be executed in a timely manner to avert further disruptions and en- 3.4. Rescheduling strategy 63 sure the continued efficient operation of all vessels. To adhere to operational constraints, vessels affected by such incidents should only resume navigation once indicated by a new decision variable denoted as taux. The following optimization problem, derived from the scheduling problem detailed in Chapter 2, is put forward: min t,taux,c JS s.t. (2.2) −(2.12), vi∗= ¯vi∗if speed reduction ,(3.1) ti,p =t† i,p ∀i=i∗,∀p∈NZ 0,(3.2) ti∗,p =t† i∗,p,∀p<p× i∗,if i∗∈ Iu,(3.3) ti∗,p =t† i∗,p,∀p≥p× i∗,if i∗∈ Id,(3.4) ti∗,p×+1 ≥taux + ∆taux i∗if i∗∈ Iu,(3.5) ti∗,p×≥taux + ∆taux i∗if i∗∈ Id,(3.6) in (2.10) and (2.11) substitute ti∗,p×by taux,(3.7) taux =t×if delay or speed reduction,(3.8) taux ≥trepair if breakdown,(3.9) where JSis the total waiting and sailing time, taux represents the new decision variable introduced to determine the optimal time for the affected vessels to resume sailing. In the case of speed reduction or arrival delay incidents, this time must coincide with the moment when the incident is detected and the optimal trip plan is rescheduled, as indicated in constraint (3.8). For breakdown incidents, this time should be greater than the moment when the affected vessel is repaired, as specified in constraint (3.9). To prevent collision accidents, constraints (2.10) and (2.11) must be adjusted as specified in constraint (3.7). This issue is illustrated in Figure 3.6, where a vessel sailing upstream (depicted in red) is affected by a breakdown incident. To avoid a collision with the downstream vessel (depicted in blue), taux must be greater than tj,p. Constraint (3.1) is introduced to modify the maximum speed at which vessel ican sail in the case of a speed reduction incident. Constraint (3.2) ensures that the new trip plans of vessels unaffected by the incident remain consistent with their original plans, where t† i,p represents the time when vessel i crosses boundary paccording to the originally scheduled plan. Constraints (3.3) and (3.4) ensure that the crossing times of the boundaries already passed by vessel i∗are consistent with the original trip plans. Constraints (3.5) and (3.6) take into account the current position and the distance already covered by vessel i∗, where ∆taux i∗represents the time required to sail from the vessel’s location 64 Chapter 3. Safe optimal rescheduling in inland waterways Figure 3.6: Illustrative example of the problem associated with the crossing constraint following the repair of a vessel affected by a breakdown incident. at the time of rescheduling (or the location of the waterway where vessels are positioned when they are allowed to resume sailing in the event of a breakdown or an unknown position incident) to the location of the next boundary while sailing at the maximum speed. 3.4.2 Global rescheduling The isolated rescheduling approach focuses on modifying the trip plan of the affected vessel while keeping the plans of other vessels unchanged. While this strategy minimizes disruptions to the original plans, there are situations where it may result in an infeasible problem. In other words, it may not be possible to find a new trip plan for vessel i∗that adheres to speed and encountering constraints without altering the plans of other vessels. To illustrate this issue, consider Figure 3.7, which depicts the trajectories of several vessels in a hypothetical waterway based on their trip plans. Imagine a scenario where two vessels, one sailing upstream (represented by the red line) and the other downstream (represented by the blue line), can only encounter each other safely in the green-shaded section of the waterway to avoid a collision. Now, suppose that at the time-space point marked by a black star, the upstream vessel 3.4. Rescheduling strategy 65 Figure 3.7: Illustrative example of feasibility problems due to a speed reduction incident. experiences a speed reduction incident. The new trajectory for this vessel at its reduced maximum speed is shown as the red dotted line. In this case, any potential encounter between these two vessels could only occur in the region where the blue line intersects the red-shaded area, which is not a feasible solution. Therefore, it becomes evident that finding a feasible solution without modifying the trajectory of the downstream vessel (blue line) is impossible. One solution to mitigate the possibility of failing to find new feasible trip plans is to adjust the trip plans of all vessels when an incident occurs, a strategy known as global rescheduling. Similar to the previous section, this is accomplished by solving the following optimization problem, which is derived from the scheduling problem presented in Chapter 2 with appropriate modifications: min t,taux,c JS s.t. (2.2) −(2.11),(3.1),(3.5) −(3.9), ti,p =t† i,p,∀p<p× i,∀i∈ Iu,(3.10) ti,p =t† i,p,∀p≥p× i,∀i∈ Id,(3.11) ti,p×+1 ≥taux + ∆taux iif i∈ Iu\i∗,(3.12) ti,p×≥taux + ∆taux iif i∈ Id\i∗.(3.13) 66 Chapter 3. Safe optimal rescheduling in inland waterways Constraints (3.10) and (3.11) ensure that the crossing times of the boundaries already crossed by each vessel iremain consistent with their original trip plans. Meanwhile, constraints (3.12) and (3.13) consider vessels iunaffected by the incident, accounting for the distance already traveled following the original plan at the time of the incident detection. Here, ∆taux irepresents the time required for vessel ito sail from its location at the moment of rescheduling until it reaches the next boundary while maintaining maximum speed. In contrast to the isolated approach, the global rescheduling strategy involves modifying the trip plans of a larger number of vessels, as will be demonstrated in the experiments conducted in Section 4.4. However, this broader scope may help alleviate some of the feasibility issues encountered in the isolated approach, as the optimization problem gains more flexibility to find suitable solutions. 3.4.3 Multi-objective rescheduling When the goal is to find an optimal solution that prioritizes both feasibility and minimal disruption to vessel schedules, a multi-objective approach can be employed ([63]). In this context, we consider that a vessel’s trip plan is impacted when its arrival time at the final destination deviates from the one specified in its original trip plan. To mitigate this deviation, a new penalty term is introduced into the cost function of the global rescheduling problem. This penalty term is designed to penalize any differences between the arrival time predicted by the previous trip plan and the arrival time determined by solving the new rescheduling problem. This revised cost function is defined as follows: JR=X i∈Iu |ti,Z −t† i,Z|+X i∈Id |ti,0−t† i,0|.(3.14) In this case, it’s important to note that only deviations in terms of arrival times for each vessel are considered. Alternatively, the entire trajectory could have been taken into account. The multi-objective rescheduling problem is formulated using a weighted sum approach, where the cost function is a linear combination of JSand JR. This approach aims to strike a balance between optimizing sailing efficiency to reduce operational costs and enhancing the system’s adaptability and responsiveness to maintain safety and minimize disruptions. The multi-objective optimization problem can be expressed as follows: min t,taux,c JS+η·JR(3.15) s.t. (2.2) −(2.11),(3.1),(3.5) −(3.9). 3.5. Case Study 67 In this formulation, ηrepresents a single weighting parameter that allows for different solutions depending on which cost is prioritized. The values of sailing and rescheduling costs obtained for various values of ηconstitute Pareto optimal solutions for the multi-objective optimization problem, as documented in [63]. These solutions create a Pareto front, which comprises a set of non-dominated solutions where no solution can be improved without worsening at least one of the objectives. Consequently, a compromise needs to be established between both objectives to select the most suitable solution. The selection process entails assessing the trade-offs between the objectives and choosing the most desirable solution based on the preferences of the decision-maker. This approach shares the same constraints as the global rescheduling approach, implying that the trip plans of all vessels can be adjusted to meet the desired objectives. In the rescheduling cost, it is feasible to incorporate varying weights to prioritize specific vessels. This flexibility enables the decision-maker to assign greater significance to particular vessels, especially those critical for the seamless operation of the transportation system. For instance, vessels transporting essential goods or passengers may receive a higher weighting in the rescheduling cost to guarantee their timely arrival at their destinations. 3.5 Case Study In this section, we will carry out simulations to demonstrate the practical implementation of our proposed monitoring system and evaluate various rescheduling techniques applied to vessels navigating the Guadalquivir River. We employ the same configuration of the waterway as in Chapter 2. All optimization problems were solved using the Gurobi solver ([57]). The simulations were conducted on an AMD Ryzen 5 platform running at a clock speed of 3 GHz. To evaluate the proposed monitoring and rescheduling approach, a series of experiments were conducted using randomly generated scenarios. Each scenario is defined by the arrival times tready iof vessels ready to enter the waterway. The sequence of arrivals at each end of the waterway is generated using a Poisson distribution with a characteristic parameter of λ. Both sequences commence at the initial time tinit. Vessel beam sizes are categorized as small, medium, or large, quantified as 1, 2, and 4, respectively. Throughout all experiments conducted in this section, a uniform distribution was employed to determine the beam size for each vessel. To assess the proposed rescheduling strategies, experiments were designed to introduce arrival delays, speed reductions, and breakdown incidents for the vessels. For arrival delay incidents, each vessel may experience such an incident with a probability of pdelay. In such cases, a random arrival delay, following a uniform 74 Chapter 3. Safe optimal rescheduling in inland waterways Figure 3.14: Example of isolated rescheduling for a breakdown incident. Figure 3.15: Example of global rescheduling for an arrival delay incident. 3.5. Case Study 75 Figure 3.16: Example of global rescheduling for a speed reduction incident. Figure 3.17: Example of global rescheduling for a breakdown incident. 76 Chapter 3. Safe optimal rescheduling in inland waterways Table 3.1: Simulation results for arrival delay incidents. Rescheduling strategy JS(h/10) JR(h/10) A.V Global 41.12 5.72 6.51 M.O (η= 0.1) 41.44 5.69 6.28 M.O (η= 0.5) 42.28 3.12 3.56 M.O (η= 1) 44.19 0.79 2.89 M.O (η= 10) 44.36 0.61 2.23 M.O (η= 100) 44.75 0.61 1.21 Isolated 45.34 0.58 1 Table 3.2: Simulation results for speed reduction incidents. Rescheduling strategy JS(h/10) JR(h/10) A.V Global 43.09 2.98 5.12 M.O (η= 0.01) 43.80 3.07 4.39 M.O (η= 0.1) 44.05 2.67 3.87 M.O (η= 1) 44.86 2.25 2.56 M.O (η= 10) 45.03 2.11 1.34 M.O (η= 100) 45.49 2.04 1.28 Isolated 46.76 2.03 1 Table 3.3: Simulation results for breakdown incidents. Rescheduling strategy JS(h/10) JR(h/10) A.V Global 31.97 20.42 6.76 M.O (η= 0.1) 32.55 21.29 6.30 M.O (η= 0.5) 38.24 15.17 5.41 M.O (η= 1) 47.81 6.65 4.93 M.O (η= 10) 47.99 6.34 3.71 M.O (η= 100) 46.23 5.63 2.69 Isolated 46.89 4.65 1 specifically in minimizing the impact on the number of vessels affected during the replanning process while adhering to a predefined threshold. This ηserves as a weighting factor that influences the decision-making process during multi-objective replanning. Its careful calibration is essential for striking a delicate balance between various objectives. A higher value of ηmay prioritize minimizing the number of vessels affected, emphasizing the significance of preserving the existing schedule integrity. On the contrary, a lower value of ηmight place 3.6. Conclusions 77 more emphasis on achieving better waiting waiting and transit times, potentially resulting in a higher impact on all the vessels. In essence, the selection of ηserves as a nuanced lever, allowing planners to fine-tune the replanning strategy based on the specific objectives and constraints of the maritime scheduling system. Consequently, a thorough understanding and thoughtful adjustment of this parameter become instrumental in steering the replanning process toward outcomes that align closely with operational requirements, minimizing disruptions to the least possible extent. 3.6 Conclusions This chapter introduced a real-time monitoring system and a multi-objective rescheduling strategy designed to rearrange vessel schedules in natural inland waterways when incidents involving any of the vessels in the original plan occur. Experiments have been conducted, and comparisons made with three alternative rescheduling strategies: isolated rescheduling, global rescheduling and multi-objective reschduling. The results underscore the effectiveness of the multiobjective rescheduling strategy, demonstrating superior performance in terms of fewer vessels being affected by rescheduling and less delay in arrival times. This strategy allows for a flexible trade-off between the number of affected vessels and the delay incurred by the rescheduling strategy. The value of ηplays a crucial role, directly impacting the number of vessels influenced by rescheduling and the discrepancy in arrival times between the original and rescheduled trip plans. As ηincreases, the number of affected vessels decreases, and the difference in arrival times diminishes. This highlights the importance of carefully selecting the ηvalue to strike the right balance between minimizing disruptions and mitigating delays. In essence, the multi-objective rescheduling strategy offers a promising approach to enhance the safety and efficiency of vessel navigation in natural waterways, particularly in the face of unexpected incidents. 78 Chapter 3. Safe optimal rescheduling in inland waterways 79 Chapter 4 Risk-aware distributionally robust control in inland waterways 4.1 Introduction In this chapter, the vessel control problem is viewed as a trajectory-tracking problem, where the optimal reference trajectory is provided by the planner developed in Chapter 2. Due to the dynamic and uncertain nature of tide islands, it is crucial to design a motion controller that efficiently follows the reference trajectory while avoiding grounding accidents, especially when operating with a limited dataset of sensor readings, which is associated with increased uncertainty due to the modeling of the uncertain regions of depth constraint violation. Since the main source of uncertainty is the depth of the waterway at each point and time instance, we first propose a novel formulation to model tide islands as stochastic uni-dimensional polytopes in the time-space map where the constraint imposed by the depth of the waterway is violated. The only information available about these uncertainties is the limited set of data obtained from noisy measurements taken by depth sensors placed along the waterway. Using this dataset, an interpolated map of the time-space regions of depth constraint violation is obtained. Based on this information, a time-varying empirical distribution of the width of each tide island is derived. Then, we design a motion controller that assesses the risk of accidents via the conditional value-at-risk (CVaR), which measures the average worst-case loss. CVaR is a coherent risk measure in the sense of Artzner [64] (that is, provide invariance, subadditivity, positive homogeneity, and monotonicity) that can distinguish tail events and is considered an adequate risk measure for robotics applications [65]. However, in order to properly assess the risk of accidents, it is 80 Chapter 4. Risk-aware distributionally robust control in inland waterways required to have accurate information about the probability distribution of the underlying uncertainties. Given that we have only a limited dataset of sensor readings to maintain the validity of the used tide model, we may end up with undesired behaviors and a lack of safety. To address this issue, we utilize the distributionally robust risk-aware model predictive control (DR-MPC) method introduced in [66], which is robust against distributional inaccuracies within a specific set of distributions called the ambiguity set and can result in high-performance and safe control actions even with inaccurate information. To the best of our knowledge, this marks the pioneering application of distributionally robust optimization (DRO) and distributionally robust control (DRC) in the field of maritime transportation. In this work, the ambiguity set is designed as a statistical ball around the given nominal distribution, where the distance between distributions is measured via the Wasserstein distance. Unfortunately, the proposed DR-MPC problem is intractable as it constitutes an infinite-dimensional problem. To overcome this issue, a Kantorovich duality-based strategy [67] is employed to reformulate the original problem into a finite-dimensional nonconvex optimization problem that can be solved using a standard commercial solver. Finally, using depth sensor data collected in the Guadalquivir River, we empirically demonstrate the performance of our risk-aware Wasserstein DR-MPC approach that solves the motion control problem of vessels in the presence of inaccuracies in the empirical distribution. The findings indicate that the approach successfully controls the vessel along the waterway without any collisions, even with a limited dataset of only six observations, while the standard robust approach result in collision rates of at least 63%.1. 4.2 Preliminaries 4.2.1 System and obstacles modeling In this chapter, we treat each vessel as a water surface robot whose dynamics can be modeled by a discrete-time system x(t+ 1) = f(x(t), u(t)), y(t) = h(x(t), u(t)), where x(t)∈Rnxis the state of the system (e.g., location, velocity), and u(t)∈ Rnuis the control input (e.g., thrust, acceleration). The system output y(t)∈Rny 1We define a collision as a situation in which a vessel enters an unsafe region due to a specific uncertainty realization. This definition serves as a measure of the algorithm’s effectiveness in managing and ensuring that vessels remain within the unforeseen safe region, considering only a limited dataset of measurements 4.2. Preliminaries 81 Figure 4.1: Fictitious time-space map with random size-changing obstacles. represents the position of the vessel in a ny-dimensional space. The functions f:Rnx×Rnu→Rnxand h:Rnx×Rnu→Rnyare general nonlinear functions representing the system dynamics and the output mapping, respectively. Perfect knowledge of the state and noiseless output measuring is assumed. Moreover, the system state and the control input are constrained as x(t)∈ X, u(t)∈ U, where X ⊆ Rnxand U ⊆ Rnuare convex compact sets, designed based on the physical constraints. Vessels must safely sail through the waterway while avoiding obstacles, which are the regions in the time-space map where the depth constraint is violated. Due to the nonconvex nature of these regions, each of them is approximated by the ball of minimum radius containing all points in the region, as it is depicted in Fig. 4.1, where three fictitious tide islands have been represented2. Here, the dark blue areas represent the tide islands, while ωl,t,k represents the distance from the extreme of the ball to the center of each obstacle lat time t+k. Once the convex region containing each tide island is found, each of the obstacles to be avoided can be seen as a one-dimensional ball whose center is always located in the same position of the waterway but whose radii periodically change in time due to the effect of the tide. In a general formulation of the collision 2The approach proposed in this chapter is also applicable if the tide island is treated as the union of several convex polytopes. Instead, the approach of finding the minimum balls containing all points in the islands has been adopted for ease of explanation. Note that this approach results in a greater level of robustness. 82 Chapter 4. Risk-aware distributionally robust control in inland waterways avoidance problem, we consider a total of Lsize-changing obstacles (tide islands) to be avoided by vessels while sailing in the waterway. The region occupied by each obstacle l, with l= 1, ..., L, at time instance t, is denoted by Ol(t)⊂R. The region occupied by each obstacle lat time t+kcan be expressed as the following polytope: Ol(t+k) := {x∈R| |x− Oc l| ≤ ωl,t,k} ={x∈R|A(x− Oc l)≤ωl,t,k},(4.1) where Oc lis the center of the ball, ωl,t,k its radius at time t+k, while A= [1,−1]⊤∈R2. In this work, we consider ωl,t,k to be a random variable whose true probability distribution is unknown. The obstacles’ stochastic nature arises from various factors, including measurement noise from depth sensors, information loss during depth map interpolation, and the impact of unquantifiable natural phenomena on waterway depth (e.g., the effect of suspended sediments on the density of the river water and the tidal amplification effect [68]). The procedure of obtaining an empirical distribution for ωl,t,k is detailed in Section 4.2.2. Note that these obstacles are given by the intersection of the ball containing all points where the depth constraint is violated with a plane of constant value given by the time instance considered. This is shown in Fig. 4.1, where the red lines represent the obstacles to be avoided at some particular time t∗. Having the definition of each l-th obstacle, we define its safe region, Yl(t+k), as the complement of the region occupied by the obstacle, i.e., Yl(t+k) := R\ O◦ l(t+k), where O◦ l(t+k) represents the interior of Ol(t+k). For collision avoidance, vessels should always sail through the intersection of the safe regions associated with all obstacles, i.e., y(t+k)∈TL i=1 Yl(t+k), in order to guarantee safe navigation. 4.2.2 Empirical distribution generation In practice, the true distribution µl,t,k of the uncertain parameter ωl,t,k, representing the width of each obstacle lat time t+k, is unknown, and the only information available about its distribution is a limited set of historical data. In this work, we assume that the tidal wave is a perfect sine of constant period. Therefore, we assume that the depth at time instances separated by intervals given by the tide period are samples drawn from the same probability distribution. 4.2. Preliminaries 83 Figure 4.2: Obtaining the uncertainty data set for ωl,t,k at tfor different observations of the same obstacle l. Assumption 4.1. Let the depth at some location of the waterway be a periodic wave [69]. Let the period of this wave be given by a constant value, which is reasonable for the considered time period, given the small variation caused by the gravitational effect of the moon. Also, let Tbe the period of the tidal wave. Then the following expression holds: ωl,t,k := ωl,t,k+iT , i = 1, ..., N. Under Assumption 4.1, a series of sets of all possible values of the width of each obstacle lat each time instance thas been obtained using the map of depth as in 2. Each of these datasets is a collection of different observations of ωl,t,iT for all i= 1, ..., N, which is represented in Fig. 4.3. Then, these datasets are employed to obtain an empirical distribution of ωl,t,k for each obstacle and for each time instance. To obtain an estimation of the real probability distribution, the only information available is a limited set of Npossibly noisy data samples, Dl,t,k = {ˆω1 l,t,k, ..., ˆωN l,t,k}. A possible option would be to obtain an empirical distribution defined as νl,t,k =1 N N X i=1 δˆωi l,t,k , where δωis the Dirac delta function concentrated at ω. This way of obtaining an empirical distribution is, however, not capable of providing a reliable estimation of the safety risk, especially when the size of the sample data set Nis small. 90 Chapter 4. Risk-aware distributionally robust control in inland waterways where the inequalities follow from the feasibility of ρ′. By verifying all the remaining constraints, we conclude that the optimal solution (λ′, s′, ρ′) to the reformulated problem is feasible for the original one, i.e., J′=J∗. Thus, the two problems are equivalent. ■ It is important to note that although Proposition 4.6 is rooted in [66, Proposition 1], the key difference lies in the decoupling of disturbances and the obstacle’s position due to the way disturbances influence the system. This decoupling allows for constraint reduction when reformulating the DR-MPC problem. Specifically, the original DR-MPC problem (4.4) can be reformulated as inf u,x,y, z,λ,s,ρ ∥yK−τK∥2 P+ K−1 X k=0 ∥yk−τk∥2 Q+ K−1 X k=1 ∥∆uk∥2 R(4.9a) xk+1 =f(xk, uk) (4.9b) yk=h(xk, uk) (4.9c) x0=x(t) (4.9d) zl,k +1 1−αλl,kθ+1 N N X i=1 sl,k,i≤δl(4.9e) ˆω(i) l,t,k +ρ⊤ l,kA(Oc l−yk)≤sl,k,i +zl,k (4.9f) ρ⊤ l,ke2= 1 (4.9g) sl,k,i +zl,k ≥0 (4.9h) sl,k,i ≥0 (4.9i) λl,k ≥1 (4.9j) ρl,k ≥0 (4.9k) xk∈ X (4.9l) uk∈ U (4.9m) zl,k ∈R,(4.9n) where all constraints hold for k= 1, ..., K,l= 1, ..., L and i= 1, ..., N, except for constraints (4.9m) and (4.9l), which hold for k= 0, ..., K −1 and k= 0, ..., K, respectively. The reformulated above problem is a finite-dimensional problem. However, it is still nonconvex due to the bilinearity of constraint (4.9f). A locally optimal solution could be obtained by means of nonlinear programming algorithms such as interior point methods or sequential quadratic programming [85]. If the model of the system dynamics and output equations are affine, relaxation techniques can be employed to find a globally optimal solution [86]. A notable advantage of the Wasserstein DR-MPC approach (4.9) is that for a carefully designed radius θ, it assures a probabilistic finite-sample performance guarantee, meaning that the safety risk constraint is satisfied with a probability 4.4. Case study 91 no less than a certain threshold, even when evaluated under a set of new samples chosen independently of the training data [66]. Remark 4.7. The deviation of the vessel from its reference trajectory could be such that maneuvers among vessels may not occur in the expected section of the waterway according to the optimal trip plan. To solve this, a multi-agent control approach could be adopted. The proposed method can be used for centralized control of multiple vessels by considering a single (possibly large) MPC problem considering all vessels and their associated operational constraints. This scenario is out of the scope of this work, as we aim to propose a general formulation of the DR-MPC problem for a single vessel in natural waterways. 4.4 Case study In this section, we carry out a series of simulations in which the proposed control approach is applied to a real case scenario in the Guadalquivir River. We use the DR-MPC method as a tracking controller for the vessel of interest with its corresponding reference trajectory. For training purposes, it is assumed that only a set of N= 11 possibly noisy values of past records of ωl,t,k is available. A series of experiments are carried out to analyze the performance and robustness of the proposed approach, measuring the cost of the DR-MPC problem and the minimum distance between the location of the vessel y(t) and the contour of the safe region Y. In the first one, for a given value of δl, the risk tolerance level, we analyze the performance and robustness of the system as a function of θ, the radius of the Wasserstein ball defining the ambiguity set centered at the empirical distribution. Then, for a given value of θ, we analyze the performance and safety of the vessel as a function of the number of samples Nemployed to generate the empirical distribution. All the results are compared to two baselines: a standard chance-constrained MPC (CC-MPC) [87] and a risk-aware MPC (SAA-MPC) [88], where in both cases the obstacle avoidance constraint solely relies on the empirical distribution. We maintained the same probability level αas used in DR-MPC for the baselines. All the experiments have been solved in AMD RYZEN 4000 CPU @ 3GHz using Gurobi solver, which incorporates a spatial branch and bound algorithm for solving bilinear programs [89]. 4.4.1 Setup The Guadalquivir River is divided into a total of 24 sections, representing the number of boundaries. Each of these sections pis characterized by its length, minimum width, and the maximum speed at which vessels can sail through it. 92 Chapter 4. Risk-aware distributionally robust control in inland waterways Figure 4.4: Trajectories of the vessels controlled by the SAA-MPC, CC-MPC, and DRMPC for different values of θ. The dotted black lines around each tide island represent the maximum value of the uncertainty in the observation dataset. These parameter values can be found in [70]. The maximum time we allow each vessel to spend waiting and sailing through the waterway is set to 12. In the scheduling problem, a total of four vessels are considered. The maximum speed at which these vessels can sail is set to vi= 25 km/h, and the beam of each vessel is randomly selected. The draft of all vessels is set to 7 m. Thus, the depth map employed in Chapter 2 is employed for all vessels, which shows that L= 5 tide islands must be avoided by each vessel. The planning objective is then to minimize the time vessels spend sailing through the waterway and waiting to access it. We assume that the times when vessels arrive at the waterway are sampled from a Poisson distribution. 4.4.2 Vessel motion control Given the optimal reference, we now demonstrate the utility of the proposed DRC method. The objective is to drive a single vessel from one extreme of the waterway to the other (i.e., track the reference trajectory) while avoiding the obstacles representing the tide islands. Because the analysis of vessel maneuverability is not the objective of this work, the model of the vessel is given by the linear 4.4. Case study 93 Table 4.1: Average total cost, safety margin, and collision rate for the DR-MPC, SAAMPC, and CC-MPC approaches for different values of θwith δl= 0.02, α= 0.95, and N= 11 computed over 100 simulations. Method Total Cost (×105) Safety Margin (km) Collision Rate (%) DR-MPC θ= 0.002 3.495 ±0.068 7.026 ±0.078 0 θ= 0.00175 3.267 ±0.052 5.885 ±0.325 0 θ= 0.0015 3.079 ±0.064 2.393 ±0.794 0 θ= 0.00125 2.801 ±0.053 1.041 ±0.587 5 θ= 0.001 2.612 ±0.063 −1.783 ±4.983 52 SAA-MPC 2.620 ±0.054 −0.824 ±2.271 63 CC-MPC 1.739 ±0.062 −21.801 ±0.808 89 system xk+1 =xk+Tsuk, where xk∈Rand uk∈Rare the position and speed of the vessel at time instance k, respectively, and Tsis the sampling time, which in this case is set to 1 h/10 (6 minutes). Note that in this case, the measured state is the output of the system. We set the MPC prediction horizon to K= 10, while the weighting factors of the cost function are set to Q=P= 1 and R= 0.1. Effect of Wasserstein radius In the first experiment, we analyze the effect of the Wasserstein radius θon the control performance and safety of the DR-MPC method. A total of 100 simulations are performed for different values of θ. We generate the empirical distribution assuming that, at each time step, only the Nlast values of ωl,t,k for each time step tare available. These values are randomly selected from a validation data set of 1200 values of ωl,t,k. Examples of the different trajectories of the vessel controlled by the baselines and our DR-MPC with parameters δl= 0.02, α= 0.95, and N= 11 for a single uncertainty realization are shown in Fig. 4.4. Note that, in this case, only the first and last obstacles affect the navigation due to their distances to the reference trajectory. For all the scenarios generated, the average value of the total costs, the minimum distance between the vessel and any of the obstacles (safety margin), as well as the collision rates are reported in Table 4.1. Notably, larger values of θcorrespond to higher costs for DR-MPC and larger safety margins. 94 Chapter 4. Risk-aware distributionally robust control in inland waterways Table 4.2: Average total cost, safety margin, and collision rate for DR-MPC, SAA-MPC, and CC-MPC approaches for different values of Nwith δl= 0.02, α= 0.95, and θ= 0.0015 computed over 100 simulations. Method Sample Size Total Cost (×105) Safety Margin (km) Collision Rate (%) DR-MPC N= 11 3.079 ±0.064 2.393 ±0.794 0 N= 6 3.293 ±0.538 1.272 ±0.963 0 N= 3 2.917 ±0.634 −6.436 ±8.712 34 N= 1 1.636 ±0.683 −18.673 ±10.095 100 SAA-MPC N= 11 2.620 ±0.054 −0.824 ±2.271 63 N= 6 2.222 ±0.350 −7.899 ±4.488 75 N= 3 1.963 ±0.424 −16.729 ±8.605 100 N= 1 1.278 ±0.683 −23.615 ±8.308 100 CC-MPC N= 11 1.739 ±0.062 −21.801 ±0.808 89 N= 6 1.783 ±0.261 −20.843 ±4.478 96 N= 3 1.753 ±0.399 −18.964 ±9.099 100 N= 1 1.268 ±0.591 −22.805 ±9.060 100 In contrast, both SAA-MPC and CC-MPC prioritize cost over safety, leading to negative safety margins and collisions occurring in 63% and 89% of cases, respectively. Remarkably, all trajectories generated by DR-MPC with θ≥0.0015 are collision-free. Even for DR-MPC with θ= 0.001, the collision rate is lower than that for the baselines, underscoring the necessity of adopting the distributionally robust approach to ensure collision-free navigation. Moreover, our DR-MPC method achieves a positive average safety margin for θ≥0.00125, indicating no collisions with obstacles. In contrast, both SAA-MPC and CC-MPC consistently show negative safety margins, signifying vessel penetration of obstacles. Effect of sample size In the second experiment, we examine how, for some fixed value of the Wasserstein radius, the control performance and safety are affected by the amount of data samples. It is assumed that only the last Nsamples of ωl,t,k for each time step tare available. These values are randomly selected from a validation data set of 1200 values of ωl,t,k for each time step t. The results of adopting the DRMPC approach are compared to those obtained when the baselines are applied 4.5. Conclusions 95 for 100 randomly generated scenarios using the same configuration as in the first experiment. Assuming the best trade-off between cost and safety is achieved at θ= 0.0015, we present the average values of total cost, safety margin, and collision rate for DR-MPC, SAA-MPC, and CC-MPC in Table 4.2. These results were obtained for different values of N, with δl= 0.02 and α= 0.95. As anticipated, trajectories generated by SAA-MPC and CC-MPC consistently result in collisions, regardless of the number of data samples considered. Moreover, the collision rate for vessels controlled by both SAA-MPC and CC-MPC rises as the number of samples decreases while the safety margin remains negative. In contrast, our DRMPC method ensures collision-free navigation with a larger safety margin, even with a small dataset of N= 6 samples. 4.5 Conclusions A DRC approach for vessels in natural waterways affected by tides was presented in this chapter. A risk-aware DR-MPC method was proposed for sailing while avoiding stochastic grounding accidents. We modeled the regions of depth constraint violation as balls whose radii belong to an unknown probability distribution. We employ past measurements of the tide to build the empirical distribution of the modeled obstacles’ radii. To hedge against inaccuracies in the resulting distributional information, the DR-MPC method limits the safety risk by allowing perturbation within a Wasserstein ambiguity set. By doing so, the proposed approach resolves the issue related to the inexact empirical distribution obtained from the limited amount of available data. The results show that even with a very small sample size, the vessel driven by the Wasserstein DR-MPC successfully avoids the obstacles that randomly change in size over time. For different values of the Wasserstein radius and the number of data samples, the proposed DR-MPC approach outperforms SAA-MPC and CC-MPC approaches. 96 Chapter 4. Risk-aware distributionally robust control in inland waterways 97 Chapter 5 Wplanpy. A tool for scheduling vessels in inland waterway 5.1 Introduction Efficient navigation planning in natural waterways presents a distinctive set of challenges, necessitating adaptive solutions that account for the dynamic interplay of changing environmental conditions and operational constraints. Addressing these complexities is crucial, particularly in regions with specific requirements, such as the Guadalquivir River, an inland port situated in the southern reaches of Spain. Throughout the chapters of this doctoral thesis, the development of algorithms for the management of uncertainty induced by the tidal effect and the planning of navigation in natural inland waterways has been carried out. This concluding chapter delves into the implementation of a software tool meticulously crafted to meet the exacting demands outlined by the port authorities of the Guadalquivir River. It represents the culmination of the work developed in this doctoral thesis, aiming to provide a practical implementation of the algorithms developed in this thesis and tailored to the current needs of the Port of Seville. Our focus revolves around the optimization of cargo vessel journeys within inland waterways, a task demanding a nuanced approach that integrates seamlessly with the intricacies of real-time data and fluctuating environmental conditions. To this end, we implement the scheduling methodology proposed in Chapter 2. The implemented system, along with its integrated library of functions, stands as a testament to innovation in navigation planning. Specifically tailored to the unique constraints of the Guadalquivir River, this software tool empowers navigation planners with a comprehensive solution. At its core, the system concentrates on refining the planning of cargo vessel routes, where considerations extend beyond the standard navigational challenges to encompass factors such as varying depths and encounter situations. By em- 98 Chapter 5. Wplanpy. A tool for scheduling vessels in inland waterway bracing a forward-thinking approach, our software enables the calculation of safe crossing windows as proposed in Chapter 2, allowing vessels to navigate critical points along their journeys with minimized risk and heightened safety standards. This implementation marks a significant leap forward in the domain of inland navigation planning, ushering in a valuable resource poised to enhance logistics operations in inherently challenging environments. The main contribution of this final chapter lies in the practical implementation of a safe tube finding method and the scheduling algorithm for finding the optimal trip plans for a set of vessels in natural inland waterways, effectively minimizing the risk of accidents and ensuring secure navigation. To foster collaboration and further advancements in the field, we have taken a commendable step by distributing the codes encompassing diverse functionalities through an open-source repository. This not only encourages transparency but also invites the collective expertise of the community, thereby propelling the evolution of navigation planning tools and strategies. In essence, our work serves as a beacon of progress, illuminating the path toward safer and more efficient inland navigation. 5.2 Tool overview As presented in Chapter 2, the optimal navigation plan must ensure that each vessel reaches its destination within the specified time frame while also guaranteeing compliance with all operational constraints, including those imposed by the dynamic effect of tides. The idea is that the tool serves not as an autonomous guidance system but as a navigation aid tool. In accordance with current navigation regulations in most channels of this type, it is assumed that vessel control and maneuverability are the responsibility of the pilot, an expert navigator for the channel. The pilot is responsible for adjusting the vessel’s speed to adhere to the plan. This means that, for a given optimal plan tip, there is not a unique trajectory, but rather a set of possible paths to follow that adhere to the plan. The choice of following one trajectory over another will always depend on the navigation criteria adopted by the pilot, which will define the profile followed by the vessel. The overall framework of the proposed tool for the implementation of the desired functionalities is shown in Figure 5.1. This tool is always managed by the waterways manager. The objective, rather than finding the individualized optimal plan for each of the vessels, is to find the global optimum, always taking into account that the established contracts between port authorities and the various vessels regarding entry and stay times in the channel must be respected. Non- 5.2. Tool overview 99 Figure 5.1: General architecture of the proposed solution for scheduling vessels in inland waterways. compliance with these could not only affect the port’s reputation but also lead to contractual penalties. In this way, the planning tool receives from the waterway manager the priority of each of the vessels that have requested to navigate through the channel and are waiting in one of the parking areas at both ends of the channel for permission to access it, as well as the instructions for carrying out optimal navigation, always under the control of the expert pilot in river navigation. Taking into account the scheduling guidelines provided, the developed planning tool is responsible for calculating optimal plans for each of the vessels collectively. This is done in a two-layer structure. In the first layer, the tool calculates the set of safe tubes for each of the vessels based on the estuary characteristics, vessel data, and tidal predictions. These safe navigation tubes are defined as a collection of temporal windows, each associated with the various waypoints along the river, indicating the time intervals during which it is safe to cross each of them, ensuring that the depth restriction imposed by the river’s maximum depth at these locations, taking into account the bathymetric profile and tide predictions, is not violated. To this end, the following parameters are needed: •The depth map, which takes into account both the bathymetric profile of the river and the tide prediction for the considered time window. This map defines the time instances at which the tidal restriction is violated at each position along the waterway. 106 Chapter 5. Wplanpy. A tool for scheduling vessels in inland waterway Figure 5.4: Simulation results transitioning from one waypoint to another without violating speed or depth constraints. This is achieved by locating the minimum and maximum points within the input crossing window, such that a line with a constant slope equal to the inverse of the maximum allowable speed in the section connects with the output crossing window without violating the depth restriction at any of the intermediate points in the section. An example of safe tubes for a vessel sailing upstream is shown in figure, where the yellow lines represent the safe crossing windows at each waypoint of the waterway and the dotted blue line represents the time limit. An example of safe tubes calculated using the tool is represented in Figure 5.3. 5.3.3 Planning module The main module of the tool is named wplanpy.py. This module takes as input data read from the cloud-based database, which includes information about each of the vessels. It then returns, as output data stored back in the database, the optimal trip plan for each vessel. The behavior of this module is as follows. First, once the input data have been read form the cloud database, the tool calculates the set of safe tubes for each vessel. To do this, the function tubesfinding.py is called. This module receives as input data the information about the different vessels, the information describing the waterway, and the depth map, and it returns, as output data, the set of tubes to be used by the optimization problem. Using the set of safe tubes, and the information of each vessel, the module build the optimization problem proposed in Chapter 2 using MIP Python library. 5.4. Simulation results 107 Table 5.1: Vessel parameters Origin Beam Max. Speed (km/h) Draft (m) Time Arrival Vessels Downstream S 2 22 7.5 6:00 S 1 20 6.5 6:12 S 2 22 7 6:24 S 2 18 7.5 6:54 Vessels Upstream C 2 20 7.8 6:03 C 1 20 6 6:10 C 1 18 6 6:20 C 1 17 6.5 6:30 Once the optimal plans for all vessels have been calculated, the tool stores them in the database so that each of the vessels can read them directly. Additionally, a graphical representation of the path that each of the vessels should follow is provided, assuming that the vessels travel at a constant speed to reach each of the different waypoints at the time indicated by the optimal plan. Note that this trajectory may vary depending on the navigation criteria applied by the pilot of each vessel. 5.4 Simulation results In this section, we test the behavior of the developed tool through a case study applied to the Guadalquivir River. To do this, we create a scenario where, for confidentiality reasons, the values of each of the vessels as well as the bathymetry and tidal data have been randomly altered. The information relative to the depth map is an array of float stored in the document db.wplanpy.depth map taking the form of a 1398 (time steps) by 871 (space steps) array with a sampling time ∆t= 6 minutes and sampling space ∆d= 100 meters. This information is provided by a series of depth sensors located along the river. We consider a scenario in which a total of 8 vessels intend to access the channel during the same operating window, half of them sailing upstream and the other half sailing downstream. All of them have their origin at the Port of Seville (S) for the downstream-bound vessels and at the stuary of the Guadalquivir River in the town of Chipiona (C) for the upstream-bound vessels. The values that characterize each of the vessels are detailed in Table 5.1, which show the information extracted from the document db.wplanpy.waterway. Note that the beam value, instead of its actual measurement, receives a discrete value in the range 1 to 4, indicating the size as small, medium, large, or very large, following the common practice in this 108 Chapter 5. Wplanpy. A tool for scheduling vessels in inland waterway type of waterways. The values used for the description of the waterway are the same that those detailed in Chapter 2, which are extracted from the documents stored in the collection db.waplanpy.vessels. The optimal plan obtained using the proposed tool for this scenario are shown in Figure 5.4. This optimal trip plan is stored in the document db.wplanpy.location. For the calculation of the optimal plan, the same priority weight has been given to each of the vessels. Instead, different weights could have been used to prioritize the transit and waiting of certain vessels. All the functionalities detailed in chapter for the calculation of the safe navigation tubes and the resolution of the optimization problem for obtaining the optimal plans are available in the following open source repository under MIT license: https://github.com/JMNadales/WPLANPY 5.5 Conclusions In this chapter, we introduced an innovative tool for computing optimal navigation plans in natural inland waterways. Beyond addressing various operational constraints, our approach uniquely considers the dynamic impact of tides in the planning process to mitigate the risk of accidents. This tool represents a significant advancement in navigation planning methodologies for complex natural waterway environments, offering a more comprehensive and safety-oriented approach. The tool operates in two primary phases. Firstly, leveraging using the depth map for a specific time frame, it computes a set of safe navigation tubes. These tubes delineate temporal windows during which it is secure to traverse each section of the waterway, ensuring the existence of at least one viable trajectory for safe canal navigation. Secondly, building upon the established set of safe tubes and considering additional operational constraints, the tool calculates a set of secure navigation plans tailored to each individual vessel. The tool has been validated through practical implementation in a real-world case study centered on the Guadalquivir River, a natural inland waterway located in the south of Spain. 109 Conclusions The culmination of the individual studies within this thesis has yielded comprehensive insights and innovative solutions aimed at enhancing the planning and navigation of vessels in natural inland waterways, with a particular focus on the challenging environment of the Guadalquivir River. The application of the proposed methodologies, as demonstrated in each of the chapters of this work, would result not only in an improvement in the safety of navigation, but also in an increase in the productivity and efficiency of the process in economic and social terms. In the first study, a two-step optimization-based approach was proposed for scheduling and planning vessels, considering time-varying depths in the waterway. Extensive simulations in the Guadalquivir River demonstrated the applicability of the formulation in solving planning problems for varying scenarios. The proposed solution not only improved upon existing first-arrived first-served strategies but also showcased computational tractability, paving the way for its potential application as a management tool for the Port of Seville. The second study introduced a real-time monitoring system and a multiobjective rescheduling strategy, proving its effectiveness through experiments and comparisons with alternative strategies. The multi-objective strategy demonstrated superior performance in terms of minimizing the number of affected vessels and reducing transit and waiting times, offering a flexible trade-off that can be fine-tuned using the parameter η. This multi-objective rescheduling strategy stands as a promising approach to enhance safety and efficiency in vessel navigation, particularly when faced with unexpected incidents. The third study focused on a risk-aware distributionally robust model predictive control approach for vessels navigating in natural inland waterways, where the tide significantly impacts navigation. By incorporating a Wasserstein ambiguity set to handle uncertainties in obstacle sizes, the proposed DR-MPC method outperformed other approaches in avoiding stochastic grounding accidents. This study showcased the robustness of the DR-MPC approach, even with limited data, emphasizing its potential for improving safety in tide-affected waterways. 110 Appendix . Conclusions The fourth and final study presented a software tool for computing optimal navigation plans in natural inland waterways, addressing operational constraints and dynamically considering tides to mitigate the risk of accident. The tool, operating in two phases, calculates safe navigation tubes and secure navigation plans for individual vessels. The practical implementation on the Guadalquivir River validated the tool’s functionalities, and all code related to this work is available in an open-source repository. Collectively, these studies represent a contribution to the field of inland navigation planning, offering not only individual advancements but also the potential for a holistic and integrated approach to improve safety and efficiency in complex natural waterway environments. 111 Future work The findings and insights derived from this research work provide a foundational understanding of scheduling, rescheduling and optimal robust navigation in natural inland waterways. However, as the scope of problems in natural inland waterways continually presents challenges and opportunities, this work presents potential directions for further exploration and refinement, aiming to contribute to the ongoing evolution of knowledge in the field of scheduling and navigation within natural inland waterways. 1. Throughout this thesis, different algorithms have been developed for the scheduling and rescheduling of vessels in natural inland waterways. Moving forward, a primary avenue of future work lies in the implementation of these tools on real scenarios. The translation of these algorithms from theoretical constructs to operational solutions represents a critical step in bridging the gap between academic research and real-world maritime challenges. This transition towards practical implementation aligns with the overarching goal of enhancing the efficiency and effectiveness of vessel scheduling and navigation in natural inland waterways. As industry demands solutions that seamlessly integrate with existing frameworks, the forthcoming focus on implementation underscores the commitment to making tangible contributions to the field and addressing the pressing needs of maritime stakeholders. 2. In the field of business process models, a noteworthy future direction involves expanding existing models, mainly focused on discrete events, with dynamic elements. The envisioned research proposes the integration of dynamic scheduling models into business process simulations, specifically targeting port management in natural inland waterways. By incorporating dynamic factors like fluctuating water levels and real-time traffic, this extension aims at enhancing the fidelity of the simulations, offering a more realistic and accurate representation of the challenges faced in natural inland waterways and port operations. Such an approach has the potential to contribute significantly to optimizing decision-making processes and improving overall operational efficiency in the intricate domain of inland waterway logistics. 112 Appendix . Future work 3. In Chapter 4, a distributionally robust control scheme for navigation in natural inland waterways was proposed. The idea is to control vessels in such a way the their trajectories adhere to the optimal trejectory generated form the optimal trip planning from Chapter 2. However, vessel’s deviation from its reference trajectory may result in unexpected maneuvers among vessels. A potential solution to address this challenge involves adopting a multi-agent control approach. This approach entails using a centralized control method to govern multiple vessels, encompassing a single, possibly extensive, model predictive control problem that considers all vessels along with their respective operational constraints. 4. In a forthcoming contribution, we aim to explore the integration of distributed control strategies based on game theory principles for vessel navigation in natural inland waterways. This approach seeks to optimize system performance by considering the self-interests of individual participants, fostering a flexible and adaptive distributed control system. An integral aspect of this investigation involves analyzing the significance of contracts established among stakeholders. These contracts will serve as strategic instruments, shaping the behavior of vessels within the network and influencing their navigation strategies to align with overarching system objectives. The research aims to advance our understanding of collaborative decision-making dynamics in complex waterway environments, emphasizing the role of contractual agreements in the effectiveness of distributed control strategies. Ultimately, this holistic framework aims to enhance the efficiency, adaptability, and strategic alignment of vessels navigating natural inland waterways. 5. The effective integration of natural inland waterways channel planning with other critical operations, such as the Berth Allocation Problem and Quay Crane Scheduling Problem, is of paramount importance for optimizing the overall efficiency of port management. These operations are closely interconnected, with channel planning playing a central role in facilitating smooth vessel access to berths and terminals. Seamless coordination between channel planning and onshore tasks, such as berth allocation and crane scheduling, ensures proper synchronization, minimizing wait times, and optimizing resource utilization. This strategic integration not only enhances operational productivity but also contributes to cost reduction and maximizes port capacity, crucial elements for the overall success of logistics operations in inland waterway environments. Bibliography [1] S. Sirviente, J. S´anchez-Rodr´ıguez, J. J. Gomiz-Pascual, M. Bolado-Penagos, A. Sierra, T. Ortega, O. ´ Alvarez, J. Forja, and M. Bruno, “A numerical simulation study of the hydrodynamic effects caused by morphological changes in the Guadalquivir River Estuary,” Science of The Total Environment, vol. 902, p. 166084, 2023. [2] S. Costa, J. Guti´errez Mas, and J. Morales, “Establecimiento del r´egimen de flujo en el estuario del Guadalquivir, mediante el an´alisis de formas de fondo con sonda multihaz,” Revista de la Sociedad Geol´ogica de Espa˜na, vol. 22, no. 1-2, pp. 23–42, 2009. [3] N. Akbulaev and G. Bayramli, “Maritime transport and economic growth: interconnection and influence (an example of the countries in the Caspian sea coast; Azerbaijan, Turkmenistan, Kazakhstan and Iran),” Marine Policy, vol. 118, p. 104005, 2020. [4] S. C. Nita, A. Hrebenciuc, et al., “The importance of maritime transport for economic growth in the European Union: a panel data analysis,” Sustainability, vol. 13, no. 14, p. 7961, 2021. [5] L. Heilig, E. Lalla-Ruiz, and S. Voß, “Digital transformation in maritime ports: analysis and a game theoretic framework,” Netnomics: Economic research and electronic networking, vol. 18, no. 2, pp. 227–254, 2017. [6] Y. Jiang, J. Lu, Y. Cai, and Q. Zeng, “Analysis of the impacts of different modes of governance on inland waterway transport development on the Pearl river: The Yangtze river mode vs. the Pearl river mode,” Journal of Transport Geography, vol. 71, pp. 235–252, 2018. [7] L. Guo, J. Wang, and J. Zheng, “Berth allocation problem with uncertain vessel handling times considering weather conditions,” Computers & Industrial Engineering, vol. 158, p. 107417, 2021. [8] K. Buhrkal, S. Zuglian, S. Ropke, J. Larsen, and R. Lusby, “Models for the discrete berth allocation problem: a computational comparison,” Transportation Research Part E: Logistics and Transportation Review, vol. 47, no. 4, pp. 461–473, 2011. 113 114 Bibliography [9] M. A. Dulebenets, “Application of evolutionary computation for berth scheduling at marine container terminals: Parameter tuning versus parameter control,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 1, pp. 25–37, 2018. [10] X. Lyu, R. R. Negenborn, X. Shi, and F. Schulte, “A collaborative berth planning approach for disruption recovery,” IEEE Open Journal of Intelligent Transportation Systems, 2022. [11] S. Ma, H. Li, N. Zhu, and C. Fu, “Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty,” Journal of Scheduling, vol. 24, no. 2, pp. 137–174, 2021. [12] D. Sun, L. Tang, R. Baldacci, and A. Lim, “An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability,” European Journal of Operational Research, vol. 291, no. 1, pp. 271–283, 2021. [13] Y. Li, F. Chu, F. Zheng, and M. Liu, “A bi-objective optimization for integrated berth allocation and quay crane assignment with preventive maintenance activities,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–18, 2020. [14] R. T. Cahyono, S. P. Kenaka, and B. Jayawardhana, “Simultaneous allocation and scheduling of quay cranes, Cranes, and trucks in integrated container terminal operations,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–15, 2021. [15] Y. Zhang, B. Atasoy, and R. R. Negenborn, “Preference-based multi-objective optimization for synchromodal transport using adaptive large neighborhood search,” Transportation Research Record, p. 03611981211049148, 2021. [16] X. Zhang, J. Lin, Z. Guo, and T. Liu, “Vessel transportation scheduling optimization based on channel–berth coordination,” Ocean Engineering, vol. 112, pp. 145–152, 2016. [17] J. Zhang, T. A. Santos, C. Guedes Soares, and X. Yan, “Sequential ship traffic scheduling model for restricted two-way waterway transportation,” Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment, vol. 231, no. 1, pp. 86–97, 2017. [18] D. Liu, G. Shi, and Z. Kang, “Fuzzy scheduling problem of vessels in oneway waterway,” Journal of Marine Science and Engineering, vol. 9, no. 10, p. 1064, 2021. [19] S. Li and S. Jia, “The seaport traffic scheduling problem: formulations and a column-row generation algorithm,” Transportation Research Part B: Methodological, vol. 128, pp. 158–184, 2019. Bibliography 115 [20] S. Jia, C.-L. Li, and Z. Xu, “Managing navigation channel traffic and anchorage area utilization of a container port,” Transportation Science, vol. 53, no. 3, pp. 728–745, 2019. [21] S. Jia, L. Wu, and Q. Meng, “Joint scheduling of vessel traffic and pilots in seaport waters,” Transportation Science, vol. 54, no. 6, pp. 1495–1515, 2020. [22] L. Wu, S. Jia, and S. Wang, “Pilotage planning in seaports,” European Journal of Operational Research, vol. 287, no. 1, pp. 90–105, 2020. [23] S. Jia, S. Li, X. Lin, and X. Chen, “Scheduling tugboats in a seaport,” Transportation Science, vol. 55, no. 6, pp. 1370–1391, 2021. [24] S. Jia, Q. Meng, and H. Kuang, “Equitable vessel traffic scheduling in a seaport,” Transportation Science, vol. 56, no. 1, pp. 162–181, 2022. [25] E. L¨ubbecke, M. E. L¨ubbecke, and R. H. M¨ohring, “Ship traffic optimization for the Kiel Canal,” Operations Research, vol. 67, no. 3, pp. 791–812, 2019. [26] F. Meisel and K. Fagerholt, “Scheduling two-way ship traffic for the Kiel Canal: Model, extensions and a matheuristic,” Computers & Operations Research, vol. 106, pp. 119–132, 2019. [27] E. Lalla-Ruiz, X. Shi, and S. Voß, “The waterway ship scheduling problem,” Transportation Research Part D: Transport and Environment, vol. 60, pp. 191–209, 2018. [28] A. Hill, E. Lalla-Ruiz, S. Voß, and M. Goycoolea, “A multi-mode resourceconstrained project scheduling reformulation for the waterway ship scheduling problem,” Journal of scheduling, vol. 22, no. 2, pp. 173–182, 2019. [29] B. Zhang and Z. Zheng, “Model and algorithm for vessel scheduling through a one-way tidal channel,” Journal of Waterway, Port, Coastal, and Ocean Engineering, vol. 146, no. 1, p. 04019032, 2020. [30] B. Zhang, Z. Zheng, and D. Wang, “A model and algorithm for vessel scheduling through a two-way tidal channel,” Maritime Policy & Management, vol. 47, no. 2, pp. 188–202, 2020. [31] B. Zhang and Z. Zheng, “Model and algorithm for vessel scheduling optimisation through the compound channel with the consideration of tide height,” International Journal of Shipping and Transport Logistics, vol. 13, no. 3-4, pp. 445–461, 2021. [32] L. Nehrke and A. Schulz, “Scheduling of waterways with tide and passing box,” Naval Research Logistics (NRL), vol. 69, no. 4, pp. 609–621, 2022. 122 List of Figures 3.2 Decision tree for classifying vessel incidents. In this classification tree, zi(tcurrent) refers to the expected location of vessel iat current time tcurrent according to the optimal plan. z† i(tcurrent) refers to the location of vessel iprovided by the AIS signal also at current time tcurrent.viis the average speed of vessel iestimated using a certain number of past location data from the AIS signal. vbreak is the threshold for determining breakdown incidents. . . . . . . . . . 58 3.3 Detection and rescheduling time for arrival delay incidents. ∆delay is the time difference between the expected and real arrival times tothewaterway. ............................ 61 3.4 Detection and rescheduling time for speed reduction incidents. ∆taux i∗ is the time needed to sail from the location of the vessel when rescheduling is carried out until the location of the next boundary sailing at maximum speed represented by µ.............. 61 3.5 Detection and rescheduling time for breakdown incidents. . . . . . 62 3.6 Illustrative example of the problem associated with the crossing constraint following the repair of a vessel affected by a breakdown incident.................................. 64 3.7 Illustrative example of feasibility problems due to a speed reduction incident.................................. 65 3.8 Average number of accidents as a function of the probability of arrival delay incident. . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.9 Average number of accidents as a function of the probability of speed reduction incident. . . . . . . . . . . . . . . . . . . . . . . . . 70 3.10 Average number of accidents as a function of the probability of breakdownincident. .......................... 71 3.11 Incident detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.12 Example of isolated rescheduling for an arrival delay incident. . . . 73 3.13 Example of isolated rescheduling for a speed reduction incident. . . 73 3.14 Example of isolated rescheduling for a breakdown incident. . . . . 74 3.15 Example of global rescheduling for an arrival delay incident. . . . . 74 3.16 Example of global rescheduling for a speed reduction incident. . . . 75 3.17 Example of global rescheduling for a breakdown incident. . . . . . 75 4.1 Fictitious time-space map with random size-changing obstacles. . . 81 4.2 Obtaining the uncertainty data set for ωl,t,k at tfor different observations of the same obstacle l. ................... 83 4.3 Condition value at risk (CVaR). . . . . . . . . . . . . . . . . . . . . 85 4.4 Trajectories of the vessels controlled by the SAA-MPC, CC-MPC, and DR-MPC for different values of θ. The dotted black lines around each tide island represent the maximum value of the uncertainty in the observation dataset. . . . . . . . . . . . . . . . . . . . 92 List of Figures 123 5.1 General architecture of the proposed solution for scheduling vessels ininlandwaterways. .......................... 99 5.2 Dependency diagram of back-end codes. . . . . . . . . . . . . . . . 102 5.3 Example of safe crossing tubes for a 7.5 meter draft vessel. the safe crossing windows are represented in yellow. The dotted blue line represents the time limit. . . . . . . . . . . . . . . . . . . . . . . . 105 5.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 124 List of Figures List of Tables 2.1 Guadalquivir waterway parameters. . . . . . . . . . . . . . . . . . . 46 2.2 Safe tube computing time as a function of DL............ 49 2.3 Effect of the weighting parameters on waiting and navigation costs. 50 2.4 Effect of DLon the feasibility of the problem. . . . . . . . . . . . . 51 2.5 Effect of λon the feasibility of the problem. . . . . . . . . . . . . . 52 2.6 Effect of λon the cost of the problem comparing the costs of the proposed solution with those obtained when the first-arrived firstserved (FA/FS) approach is adopted. . . . . . . . . . . . . . . . . . 52 3.1 Simulation results for arrival delay incidents. . . . . . . . . . . . . 76 3.2 Simulation results for speed reduction incidents. . . . . . . . . . . . 76 3.3 Simulation results for breakdown incidents. . . . . . . . . . . . . . 76 4.1 Average total cost, safety margin, and collision rate for the DRMPC, SAA-MPC, and CC-MPC approaches for different values of θwith δl= 0.02, α= 0.95, and N= 11 computed over 100 simulations................................ 93 4.2 Average total cost, safety margin, and collision rate for DR-MPC, SAA-MPC, and CC-MPC approaches for different values of Nwith δl= 0.02, α= 0.95, and θ= 0.0015 computed over 100 simulations. 94 5.1 Vesselparameters............................ 107 125 126 List of Tables