Shortest path in the presence of obstacles: An application to ocean shipping
- PDF / 163,773 Bytes
- 6 Pages / 595 x 842 pts (A4) Page_size
- 36 Downloads / 163 Views
#2000 Operational Research Society Ltd. All rights reserved. 0160-5682/00 $15.00 www.stockton-press.co.uk/jors
Shortest path in the presence of obstacles: An application to ocean shipping K Fagerholt1*, SI Heimdal2 and A Loktu2 1
Norwegian University of Science and Technology, and 2Norwegian Marine Technology Research Institute, Trondheim, Norway
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 ef®cient 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
Introduction Fast and accurate calculation of the estimated time of arrival (ETA) at a given destination port for a ship at sea is of high importance in several areas of the ocean shipping industry. For instance, in the routing and scheduling of ships on a day-to-day basis, it is crucial to know when a ship will arrive at its destination port and be available for new cargoes. ETAs may also be important in the planning of port operations. By receiving reliable ETAs for the ships arriving at the port, the planning of the port operations, such as allocation of labour, loading=discharging equipment and quays to the ships can be done more ef®ciently. The traditional way is to base the ETA on the shipmasters estimate. However, new technology satellite position reporting combined with electronic charts allow users on shore to verify the master's estimate or update ETA values at regular time intervals without disturbing the vessel crew at all hours. This paper presents an ef®cient algorithm for determining the ETA at a port for a ship located at sea. The algorithm is implemented in a decision support system for planning ship operations,1 which is installed and used by several shipowners. By calculating the sailing distance between the ship and its destination port, the ETA can be estimated by dividing the distance by the sailing speed. Calculating the distance between the ship and its destination port can be considered as determining the shortest path between two points in the presence of polygonal obstacles, *Correspondence: Dr K Fagerholt, Department of Marine Systems Design, Norwegian University of Science and Technology, Otto Nielsens vei 10, N-7034 Trondheim, Norway. E-mail: [email protected]
where one point corresponds to the ship
Data Loading...
