IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v51y2000i6d10.1057_palgrave.jors.2600950.html
   My bibliography  Save this article

Shortest path in the presence of obstacles: An application to ocean shipping

Author

Listed:
  • K Fagerholt

    (Norwegian University of Science and Technology)

  • S I Heimdal

    (Norwegian Marine Technology Research Institute)

  • A Loktu

    (Norwegian Marine Technology Research Institute)

Abstract

This paper presents the problem of determining the estimated time of arrival (ETA) at the destination port for a ship located at sea. This problem is formulated as a shortest path problem with obstacles, where the obstacles are modelled by polygons representing the coastlines. An efficient solution algorithm is proposed to solve the problem. Instead of generating a complete visibility graph and solving the problem as an ordinary shortest path problem, the algorithm constructs arcs to the ship node during the solution process only when needed. This greatly enhances the algorithmic performance. Computational results based on test problems from an actual dry-bulk shipping operation are provided. The proposed algorithm is implemented in a decision support system for the planning of ship operations and it has successfully been applied on several real life problems.

Suggested Citation

  • K Fagerholt & S I Heimdal & A Loktu, 2000. "Shortest path in the presence of obstacles: An application to ocean shipping," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(6), pages 683-688, June.
    • Handle: RePEc:pal:jorsoc:v:51:y:2000:i:6:d:10.1057_palgrave.jors.2600950
    DOI: 10.1057/palgrave.jors.2600950
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2600950
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2600950?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    2. Ari, Ibrahim & Aksakalli, Vural & AydogĖ‡du, Volkan & Kum, Serdar, 2013. "Optimal ship navigation with safety distance and realistic turn constraints," European Journal of Operational Research, Elsevier, vol. 229(3), pages 707-717.
    3. Andrzej Bochniak & Monika Stoma, 2021. "Estimating the Optimal Location for the Storage of Pellet Surplus," Energies, MDPI, vol. 14(20), pages 1-16, October.
    4. Babel, Luitpold & Zimmermann, Thomas, 2015. "Planning safe navigation routes through mined waters," European Journal of Operational Research, Elsevier, vol. 241(1), pages 99-108.
    5. Alan Washburn & Gerald G. Brown, 2016. "An exact method for finding shortest routes on a sphere, avoiding obstacles," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(5), pages 374-385, August.
    6. Gerald G. Brown & Jeffrey E. Kline & Richard E. Rosenthal & Alan R. Washburn, 2007. "Steaming on Convex Hulls," Interfaces, INFORMS, vol. 37(4), pages 342-352, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:51:y:2000:i:6:d:10.1057_palgrave.jors.2600950. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.