Innovative Applications of O.R.Models and algorithms for an integrated vessel scheduling and tug assignment problem within a canal harbor
Introduction
The in-Port vessel Scheduling and tug Assignment Problem (PSAP) aims at determining the schedule for a given set of vessel movements and their escorting tugs within a port. Optimizing the schedule of vessel movements, specifically, vessel arrivals, departures, and berth to berth connections, is critical for the efficient management of a port, as many stakeholders have to coordinate their in-port activities accordingly. In this paper, we deal with the PSAP for ports consisting of canal harbors, where vessels have to keep a safety distance and cannot cross or pass each other. In this kind of ports, vessels are also subject to more stringent requirements than those of seaports as regard the usage of tugs, which have to help to navigate through narrow water canals.
The PSAP can be framed within the in-port or canal vessel scheduling and routing problem literature (Christiansen, Fagerholt, Nygreen, & Ronen, 2013). The literature on in-port scheduling problems considers vessels (typically container-ships) that have to be assigned to berths. Then quayside, yard and landside operations are scheduled accordingly. The berth allocation and quay crane scheduling problems (Bierwirth, Meisel, 2010, Carlo, Vis, Roodbergen, 2015, Gharehgozli, Roy, de Koster, 2016, Nishi, Okura, Lalla-Ruiz, Voß, 2020, Wawrzyniak, Drozdowski, ric Sanlaville, 2020) fall within this kind of literature. In recent years, the literature has also considered other topics, such as the problem of routing tankers that have to move between berths (Wang, Arnesen, Fagerholt, Gjestvang, & Thun, 2018). Other recent works focus on the problem of scheduling the access of port resources such as channels and berths (Du, Chen, Lam, Xu, Cao, 2015, Zhang, Lin, Guo, Liu, 2016, Zhen, Liang, Zhuge, Lee, Chew, 2017). In Lalla-Ruiz, Shi, & Voß (2018) and Hill, Lalla-Ruiz, Voss, & Goycoolea (2019), the problem of scheduling incoming and outgoing vessels through different waterways for accessing or leaving the port is dealt with. A framework that combines decision theory and stochastic optimization techniques to address tide routing is considered in Carrer, Ferson, & Green (2020). Problems arising in managing traffic in navigation channels that join the terminal basin or different terminals are dealt with in Corry & Bierwirth (2019); Jia, Li, & Xu (2019). Canal scheduling literature considers vessels navigating waterways and/or locks (Ji, Yuan, Yuan, Lei, Fernando, Iu, 2019, Passchyn, Coene, Briskorn, Hurink, Spieksma, Berghe, 2016, Verstichel, Causmaecker, Spieksma, Berghe, 2014), such as the Panama Canal (Franzese, Abdenur, Botter, Starks, Cano, 2004, Jackman, de Castillo, Olafsson, 2011, Zheng, Zhang, Qi, Wang, 2019), the Kiel Canal (Lübbecke, Lübbecke, Möhring, 2019, Meisel, Fagerholt, 2019), the Istanbul Strait (Mavrakis, Kontinakis, 2008, Ulusçu, Özbaş, Altıok, Or, Yılmaz, 2009), the Yangtze River (Li, Yang, Wang, & Weng, 2019).
In this work, we apply the PSAP to canal harbors such as the Port of Venice in Italy. The Port of Venice is a medium Italian port of the north Adriatic Sea. It is situated within the shallow water of the Venetian Lagoon. Here, vessels can access or leave the port only navigating along narrow canals. For this problem, we propose a formal definition, two mathematical models and four algorithms based on these models.
A first work in this context is (Pellegrini, di Tollo, & Pesenti, 2019), which introduces the problem of scheduling vessel movements within a canal harbor (PSP), without taking tugs into consideration. The authors propose a mixed integer linear programming (MILP) model inspired by RECIFE-MILP (Pellegrini, Marlire, Pesenti, & Rodriguez, 2015), an algorithm for the railway traffic management problem. This choice is motivated by the observation that the navigation of vessels along narrow canals presents some similarities with the movement of trains along single track railway lines. One of the models that we consider in this work extends the one in Pellegrini et al. (2019) in order to include the assignment of tugs.
The problem of assigning tugs to a set of vessel movements shows similarities with another railway management problem, the Locomotive Scheduling Problem (LSP) (Vaidyanathan, Ahuja, Liu, & Shughart, 2008). In the LSP, locomotives have to be assigned to trains with the objective of minimizing the deviation of the trains’ actual schedule from the planned one. We refer the interested reader to survey (Piu & Speranza, 2014) on the different variants of LSP. However, PSAP and LSP present some main differences. Locomotives can move from a train to another only along free track, where there are no other trains. Trains typically need a single locomotive and can stop along their route. Differently, tugs may navigate also through canals that are occupied by vessels. Vessels often need more than one tug and cannot stop along their route.
The PSAP assumes that the schedule of vessels and the assignment of tugs is decided with an integrated approach. In recent years, integrated approaches have attracted increasing interest as the sequential ones have intuitive drawbacks, as pointed out in Bussieck, Winter, & Zimmermann (1997) in the context of railway management. An example of an integrated approach in railways can be found in Xu, Li, & Xu (2018), where train timetable and locomotive assignment is defined at once, possibly canceling trains that cannot be served. A minimum cost multi-commodity network flow model is proposed to this aim.
In this paper, we first define and formalize the PSAP. Then, we introduce two mathematical programming models for it: one based on time-indexed variables, the other on continuous time variables. We exploit each model to develop two heuristic algorithms. Specifically, in one algorithm we execute a commercial solver on the considered model within a time limit; in the other one, we embed the considered model in a receding horizon framework. Finally, we assess the applicability and the performance of our algorithms by means of an extensive experimental analysis conducted on real and realistic randomly generated instances representing traffic at the Port of Venice, in Italy.
The remainder of this paper is organized as follows. In Section 2, we formally define the problem we deal with. In Section 3, we present the models for the PSAP that we propose in this paper. In Section 4, we detail the solution algorithms exploiting these models. In Section 5, we discuss our case study and the performance of the proposed algorithms. Finally, we draw conclusions in Section 6 and we discuss the applicability of some strengthening cuts for the models in the Appendix.
Section snippets
Problem statement
In this section, we provide the formal statement of the PSAP. We start by introducing the assumptions we make and the necessary notation. We then define the problem.
We model a port as a network of waterways . The vertex set includes the navigation points, i.e., the points in the canals that have some interest for navigation:
- •
berths and inlets;
- •
connection points between two waterways or between a berth and a waterway;
- •
other relevant points such as turning basins, initial/final points of
PSAP models
In this section, we introduce and discuss two mathematical programming models of PSAP denoted respectively by and : is a time-indexed model, whereas is a continuous time one. Model can be considered as the extension of the RECIP-MILP model presented in Pellegrini et al. (2019). In the appendix, we propose possible strengthening cuts for the two models.
Solution algorithms
In this paper, we propose four algorithms to tackle the PSAP. The first pair of them consist in solving the models proposed in Section 3 using a commercial solver within a predefined time limit. They are denoted and : the former solves Model , the latter Model . The second pair of algorithms still exploit the models but are characterized by an overlaying receding horizon heuristic, which we introduce in this section. As in Section 2, we denote by a feasible solution for a PSAP
Computational experiments
In this section, we present the results obtained by applying the proposed algorithms on two clusters of instances for the Port of Venice, our case study. We start with the presentation of the case study, and we continue with the results.
All the tests we present in this section are run on a laptop PC Dell XPS 15 9560, with an Intel Core iHQ at 2.80GHz and 16.0GB of installed RAM and with the solver XPRESS v8.5.6 64 bit. The following parameter setting is used for Algorithms and . The
Conclusions
In this paper, we defined and formulated the in-Port vessel Scheduling and tug Assignment Problem, and we proposed four algorithms for tackling it. In this problem, vessel movements and tugs must be scheduled to optimize the access to a port infrastructure. In particular, we focused on the case of canal harbors. We formally showed that instances in which vessels require the use of multiple tugs can be mapped into equivalent instances in which a one-to-one relation holds. The four proposed
Acknowledgments
This study was partially funded by the “Smart PORt Terminals - SPORT” MIUR-PRIN project (grant number: 2015XAPRKF) financed by the Italian Government.
References (39)
- et al.
A survey of berth allocation and quay crane scheduling problems in container terminals
European Journal of Operational Research
(2010) - et al.
Ship routing and scheduling in the new millennium
European Journal of Operational Research
(2013) - et al.
Exact and heuristic methods for optimizing lock-quay system in inland waterway
European Journal of Operational Research
(2019) - et al.
The waterway ship scheduling problem
Transportation Research Part D: Transport and Environment
(2018) - et al.
Ship routing and scheduling problem for steel plants cluster alongside the yangtze river
Transportation Research Part E: Logistics and Transportation Review
(2019) - et al.
A queueing model of maritime traffic in bosporus straits
Simulation Modelling Practice and Theory
(2008) - et al.
Scheduling two-way ship traffic for the kiel canal: Model, extensions and a matheuristic
Computers & Operations Research
(2019) - et al.
The lockmasters problem
European Journal of Operational Research
(2016) - et al.
Real-life locomotive planning: New formulations and computational results
Transportation Research Part B: Methodological
(2008) - et al.
The generalized lock scheduling problem: An exact approach
Transportation Research Part E: Logistics and Transportation Review
(2014)
A two-phase heuristic for an in-port ship routing problem with tank allocation
Computers & Operations Research
Selecting algorithms for large berth allocation problems
European Journal of Operational Research
Integrated train timetabling and locomotive assignment
Transportation Research Part B: Methodological
Vessel transportation scheduling optimization based on channel berth coordination
Ocean Engineering
Daily berth planning in a tidal port with channel flow control
Transportation Research Part B: Methodological
Canal effects on a liner hub location problem
Transportation Research Part E: Logistics and Transportation Review
Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems
INFORMS Journal on Computing
Cited by (3)
Tugboat Scheduling with Multiple Berthing Bases under Uncertainty
2023, Journal of Marine Science and EngineeringJoint Scheduling Optimization of Vessel and Tug Based on Improved NSGA-II Algorithm
2023, Proceedings of the IEEE International Conference on Software Engineering and Service Sciences, ICSESS