Innovative Applications of O.R.
Models and algorithms for an integrated vessel scheduling and tug assignment problem within a canal harbor

https://doi.org/10.1016/j.ejor.2021.10.037Get rights and content

Highlights

  • We introduce an integrated ship and tug scheduling problem within a canal harbor.

  • We design two mathematical programming models to formulate the problem.

  • We propose heuristic algorithms based on these models.

  • We assess the performance of these algorithms in a thorough experimental analysis.

Abstract

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. In this paper, we propose, compare and discuss models and algorithms for determining solutions for the PSAP. Specifically, we introduce two mathematical programming models and we derive from them four heuristics: two based on the time limited execution of a commercial solver, and two on a receding horizon principle. Finally, we present the results of a computational study aiming at assessing the performance of the considered algorithms on problem instances obtained from the Port of Venice, a medium size Italian port. The receding horizon based heuristics show good performances. They provide good quality solutions for the majority of the instances within a reasonable computational time.

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 G=(V,E). The vertex set V 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 P1 and P2: P1 is a time-indexed model, whereas P2 is a continuous time one. Model P2 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 Ω1 and Ω2: the former solves Model P1, the latter Model P2. 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 i77700HQ 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 E1 and E2. 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)

  • X. Wang et al.

    A two-phase heuristic for an in-port ship routing problem with tank allocation

    Computers & Operations Research

    (2018)
  • J. Wawrzyniak et al.

    Selecting algorithms for large berth allocation problems

    European Journal of Operational Research

    (2020)
  • X. Xu et al.

    Integrated train timetabling and locomotive assignment

    Transportation Research Part B: Methodological

    (2018)
  • X. Zhang et al.

    Vessel transportation scheduling optimization based on channel berth coordination

    Ocean Engineering

    (2016)
  • L. Zhen et al.

    Daily berth planning in a tidal port with channel flow control

    Transportation Research Part B: Methodological

    (2017)
  • J. Zheng et al.

    Canal effects on a liner hub location problem

    Transportation Research Part E: Logistics and Transportation Review

    (2019)
  • (a). Access from the sea. https://www.port.venice.it/en/access-from-the-sea.html....
  • (b). Ordinanze. https://www.guardiacostiera.gov.it/venezia/Pages/ordinanze.aspx....
  • Y. Adulyasak et al.

    Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems

    INFORMS Journal on Computing

    (2014)
  • Cited by (3)

    View full text