Algorithm Models for Maritime Routes (2014)

By Adam Damiano and Chun Xie

Motivation

Many programs exist for the optimization of maritime routes for ships with propeller locomotion. These programs consider geographic features, water currents, and the maximum speed of the ship. However, to properly model the paths of sailing ships, it is necessary to factor in the effects that the wind has upon the fastest path. For this project, a program was created that considers wind and ocean currents and the type of ship for the optimization of the fastest sailing route in the Mediterranean. The optimization program was built around an Ant Colony Optimization with edge costs being evaluated based upon sailing polars. The path was further optimized using a local search optimization to transform the gridded path to a continuous path.

Process

For this project, ocean current data was collected from the Argos database1, which is generated from the drift velocity and direction of buoys distributed around the Mediterranean Sea. The wind data was collected from the Quikscat database2, which offers global wind speed data based upon monthly mean averages over a range of 96 months evaluated from satellite images. The month of evaluation can be specified by the user when operating the program, which can be valuable for areas that experience great seasonal fluctuations or wind patterns. Wind and current data was interpolated across length dimensions to remove discontinuities that would result in path pinning. Geographical data was imported in the form of coast lines.

The difficulty of this project, and what sets this program apart from other path optimization programs, is the inclusion of the wind speed and direction in the analysis of the fastest route. To initialize the optimization, a connected grid is created with eight paths extending from each node. Along each edge, the travel time is evaluated with the use of sailing polars. A sailing polar is polar diagram that indicates the travel speed that a ship may travel in a particular direction for a given wind speed. Sailing polars were found for ships of a variety of sizes and a 3D interpolation was used to calculate the sailing polars for ships of any practical size and for wind speeds up to 60 kilometers per hour. For each edge, the wind speed is used to create a sailing polar, which is then rotated to align with the wind vector. The polar is then shifted according to the magnitude and direction of the water current, which results in a travel possibility polar that indicates how fast a boat can travel in any direction based upon the meteorological conditions at that node. The direction of the edge is then considered and the travel speed is evaluated. To calculate travel time the travel velocity is simply divided by the travel length between the two nodes. In the evaluation of the length between nodes, the sphericity of the Earth is considered by mapping the nodes to their respective point on the globe and by calculating the great arc between the two points.

Ant Colony Optimization (ACO) was selected as the optimization method for this project because it allows for bidirectional travel with asymmetric costs which is needed so that the program can evaluate the complexities that arise due to wind and ocean currents. ACO is a clever path optimization algorithm that was inspired based upon how ant colonies find food. The ants choose edges stochastically with probabilities established by considering the pheromone deposits and a heuristic incentive. The pheromones are deposited on edges throughout the optimization by ants who have found fast paths. The heuristic incentive is evaluated by giving preference to fast travel and to travel towards the destination. The heuristic varies edge selection probabilities only slightly because the fastest path may include both slow travel times for short distances or travel away from the destination to navigate land masses. After the ACO is complete, the result is an optimized path that is fixed to the edges and nodes of the connected graph. Since ships do not travel in a gridded manner, a second optimization is employed to further refine the path onto a continuous grid. The local search optimization is carried out by taking each node of the fastest path and, in turn, displacing them from their current location. This is completed at ten different locations from the point. For each of these displacements, the travel time is recalculated and fastest variation is then saved as the new fastest path. This is completed for every point on the path and a total of 16 passes are made on the path. Each pass alternates displacement of the point on the longitudinal or latitudinal axis with each displacement being smaller and smaller for each pass to ensure refinement. The result is a path that is further optimized and not bound to a grid.

The program was written to allow for the specification of the optimization that changes parameters such as node-to-node spacing, coast line details, ACO iterations, and number of local search passes.  Also, the program is built with robust error handling that informs users if there is a problem with data entry and will readjust starting points placed on land to the nearest coast. The program concludes with a report of the evaluation and a display of the fastest route along with the ability to display wind and ocean current data on top of the route.

Results

To validate the results, path times optimized by the program were compared to estimated Mediterranean sailing travel times and were found in be in agreement3. Next, the algorithm was used for its intended purpose, to model the sailing of ancient Venetian ships. By using a data set of merchant fleets leaving Venice from the years 11th through 13th century, the travel times of the ships was compared against the optimized route from the program. A limited amount of meaningful travel time data was able to be extracted from the dataset; however, using the data available, the optimization showed path times between 70-85% that of the recorded travel times. This is to be expected because ancient shipping fleets did not have the means to optimize their travel paths in real-time. This result suggests that the travel time of ships in ancient Venice for unrecorded routes may be estimated by first optimizing the path and travel time and then using a multiplication factor of 1.2 to 1.45 to approximate the real travel time.

The program will be on display during the DH101 Presentation Fair.


1http://www.argo.ucsd.edu/ 2http://manati.star.nesdis.noaa.gov/datasets/QuikSCATData.php 3http://www.sailtraininginternational.org/