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

K Fagerholt (), S I Heimdal and A Loktu
Additional contact information
K Fagerholt: Norwegian University of Science and Technology
S I Heimdal: Norwegian Marine Technology Research Institute
A Loktu: Norwegian Marine Technology Research Institute

Journal of the Operational Research Society, 2000, vol. 51, issue 6, 683-688

Abstract: 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.

Keywords: sea transport; scheduling; logistics; networks and graphs (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2600950 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:51:y:2000:i:6:d:10.1057_palgrave.jors.2600950

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2600950

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().