Skip to main content
SpringerLink
Log in

Scheduling ships movements within a canal harbor

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

In this paper we propose a model for the in-port ship scheduling problem that consists in scheduling the movement of ships inside a canal harbor. Our model, which we name RECIP-MILP, is inspired by a model for scheduling trains, to exploit the analogies between a canal harbor and a single track railway network. Moreover, we show how to translate spatial safety constraints into time ones. We apply our model to instances representing ship movements in the Port of Venice. We test the performance of both the exact RECIP-MILP model and a heuristic solution algorithm based on it. We show that we can exactly solve most instances in few minutes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  • Bierwirth C, Meisel F (2015) A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 244(3):675–689

    Article  MathSciNet  MATH  Google Scholar 

  • Bugarski V, Backalic T, Kuzmanov U (2013) Fuzzy decision support system for ship lock control. Expert Syst Appl 40:3953–3960

    Article  Google Scholar 

  • Cacchiani V, Huisman D, Kidd M, Kroon L, Toth P, Veelenturf L, Wagenaar J (2014) An overview of recovery models and algorithms for real-time railway rescheduling. Transp Res Part B Methodol 63:15–37

    Article  Google Scholar 

  • Canestrelli E, Corazza M, De Nadai G, Pesenti R (2017) Managing the ship movements in the port of venice. Netw Spat Econ 17(3):861–887

    Article  MathSciNet  MATH  Google Scholar 

  • Carlo HJ, Vis IFA, Roodbergen KJ (2015) Seaside operations in container terminals: literature overview, trends, and research directions. Flex Serv Manuf J 27(2):224–262 ISSN 1936-6590

    Article  MATH  Google Scholar 

  • Casagrande M (2015) The progressive regulation of the passage of large cruise ships in Venice: the decision-making. In: Proceedings between law and stakeholder pressure. Springer, Cham, pp 185–195. ISBN 978-3-319-11385-2

  • Chang YT, Song Y, Roh Y (2013) Assessing greenhouse gas emissions from port vessel operations at the Port of Incheon. Transp Res Part D Transp Environ 25:1–4

    Article  Google Scholar 

  • Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228:467–483

    Article  MathSciNet  MATH  Google Scholar 

  • Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University

  • Du Y, Chen Q, Lam JSL, Xu Y, Cao JX (2015) Modeling the impacts of tides and the virtual arrival policy in berth allocation. Transp Sci 49:939–956

    Article  Google Scholar 

  • Franzese LAG, Abdenur LO, Botter RC, Starks D, Cano AR (2011) Simulating the panama canal: present and future. In: Proceedings of the 2004 winter simulation conference, vol 2, pp 1835–1838

  • Gharehgozli AH, Roy D, de Koster R (2016) Sea container terminals: new technologies and OR models. Marit Econ Logist 18(2):103–140

    Article  Google Scholar 

  • Golias M, Portal I, Konur D, Kaisar E, Kolomvos G (2014) Robust berth scheduling at marine container terminals via hierarchical optimization. Comput Oper Res 41:412–422

    Article  MathSciNet  MATH  Google Scholar 

  • Gregoris E, Barbaro E, Morabito E, Toscano G, Donateo A, Cesari D, Contini D, Gambaro A (2016) Impact of maritime traffic on polycyclic aromatic hydrocarbons, metals and particulate matter in venice air. Environ Sci Pollut Res 23(7):6951–6959

    Article  Google Scholar 

  • Kontovas C, Psaraftis H (2011) Reduction of emissions along the maritime intermodal container chain: operational models and policies. Marit Policy Manag 38(4):451469

    Article  Google Scholar 

  • Lalla-Ruiz E, Shi X, Voß S (2018) The waterway ship scheduling problem. Transp Res Part D Transp Environ 60:191–209

    Article  Google Scholar 

  • Lübbecke E (2016) On- and offline scheduling of bidirectional traffic. In: Fink A et al (ed) Operations research proceedings

  • Lusby RM, Larsen J, Ehrgott M, Ryan D (2011) Railway track allocation: models and methods. OR Spectr 33(4):843–883

    Article  MathSciNet  MATH  Google Scholar 

  • Mavrakis D, Kontinakis N (2008) A queueing model of maritime traffic in Bosporus Straits. Simul Model Pract Theory 16:315–328

    Article  Google Scholar 

  • Nauss RM (2008) Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock. Eur J Oper Res 187:1268–1281

    Article  MATH  Google Scholar 

  • Nogueira TH, de Carvalho CRV, Santos GPA, de Camargo LC (2015) Mathematical model applied to single-track line scheduling problem in Brazilian railways. 4OR 13(4):403–441

    Article  MathSciNet  MATH  Google Scholar 

  • Parnell KE, Soomere T, Zaggia L, Rodin A, Lorenzetti G, Rapaglia J, Scarpa GM (2015) Ship-induced solitary Riemann waves of depression in Venice lagoon. Phys Lett A 379(6):555–559

    Article  Google Scholar 

  • Passchyn W, Coene S, Briskorn D, Hurink JL, Spieksma FCR, Vanden Berghe G (2016) The lockmaster’s problem. Eur J Oper Res 251(2):432–441

    Article  MathSciNet  MATH  Google Scholar 

  • Pellegrini P, Marliere G, Pesenti R, Rodriguez J (2015) RECIFE-MILP: an effective MILP-based heuristic for the real-time railway traffic management problem. IEEE Trans Intell Transp Syst 16(5):2609–2619

    Article  Google Scholar 

  • Petersen ER, Taylor AJ (1988) An optimal scheduling system for the Welland Canal. Transp Sci 22:173–185

    Article  MATH  Google Scholar 

  • Quaglietta E, Pellegrini P, Goverde RMP, Albrecht T, Jaekel B, Marlière G, Rodriguez J, Dollevoet T, Ambrogio B, Carcasole D, Giaroli M, Nicholson G (2016) The ON-TIME real-time railway traffic management framework: a proof-of-concept using a scalable standardised data communication architecture. Transp Res Part C Emerg Technol 63:23–50

    Article  Google Scholar 

  • Styhre L, Winnes H, Black J, Lee J, Le-Griffin H (2017) Greenhouse gas emissions from ships in ports: case studies in four continents. Transp Res Part D Transp Environ 54:212–224

    Article  Google Scholar 

  • Ulusçu ÖS, Altıok T (2009) Waiting time approximation in single-class queueing systems with multiple types of interruptions: modeling congestion at waterways entrances. Ann Oper Res 172:291–313

    Article  MATH  Google Scholar 

  • Ulusçu ÖS, Öbaş B, Altıok T, Or I, Yılmaz T (2009) Transit vessel scheduling in the Strait of Istanbul. J Navig 62:59–77

    Article  Google Scholar 

  • Verstichel J, De Causmaecker P, Spieksma F, Berghe GV (2014) The generalized lock scheduling problem: an exact approach. Transp Res Part E Log Transp Rev 65:16–34

    Article  Google Scholar 

  • Verstichel J, De Causmaecker P, Spieksma FCR, Vanden Berghe G (2014) Exact and heuristic methods for placing ships in locks. Eur J Oper Res 235:387–398

    Article  MathSciNet  MATH  Google Scholar 

  • Wang X, Arnesen MJ, Fagerholt K, Gjestvang M, Thun K (2018) A two-phase heuristic for an in-port ship routing problem with tank allocation. Comput Oper Res 91:37–47

    Article  MathSciNet  MATH  Google Scholar 

  • Yang Z, Shi H, Chen K, Bao H (2014) Optimization of container liner network on the Yangtze River. Marit Policy Manag 41(1):79–96

    Article  Google Scholar 

  • Zhang X, Lin J, Guo Z, Liu T (2016) Vessel transportation scheduling optimization based on channel–berth coordination. Ocean Eng 112:145–152

  • Zhen L, Liang Z, Zhuge D, Lee LH, Chew EP (2017) Daily berth planning in a tidal port with channel flow control. Transp Res Part B Methodol 106:193–217

    Article  Google Scholar 

Download references

Acknowledgements

The authors want to thanks the North Adriatic Sea Port Authority for its support and suggestion. In particular, Eng. P. Menegazzo and Capt. A. Revedin. This study was partially funded by the “Smart PORt Terminals - SPORT” MIUR-PRIN project (Grant No. 2015XAPRKF) financed by the Italian state and by the “CPER ELSAT2020” project co-financed by the European Union with the European Regional Development Fund, the French state and the Hauts-de-France Region Council. The study was partially developed within the Centro Studi su Economia e Management della Portualità of Università Ca’ Foscari, Venezia.

Author information

Authors and Affiliations

  1. Univ. Lille Nord de France, IFSTTAR, COSYS, LEOST, 20, rue Elisee Reclus, BP 70317, 59666, Villeneuve d’Ascq, France

    Paola Pellegrini

  2. Department of Management, Ca’ Foscari University of Venice, Cannaregio 873, 30121, Venice, Italy

    Giacomo di Tollo & Raffaele Pesenti

Authors
  1. Paola Pellegrini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giacomo di Tollo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raffaele Pesenti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raffaele Pesenti.

Ethics declarations

Conflict of interest

Author R. Pesenti has received research funds from the North Adriatic Sea Port Authority and declares that the Centro Studi su Economia e Management della Portualità is partially funded by the North Adriatic Sea Port Authority. G. di Tollo and P. Pellegrini declare that they have no conflict of interest.

Human and animal participants

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Communicated by P. Beraldi, M. Boccia, C. Sterle.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pellegrini, P., di Tollo, G. & Pesenti, R. Scheduling ships movements within a canal harbor. Soft Comput 23, 2923–2936 (2019). https://doi.org/10.1007/s00500-018-3469-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-018-3469-2

Keywords

Search

Navigation