Algorithm models for maritime routes (S5) – Project Description

by Adam Damiano and Chun Xie

Project Definition

The modeling of ancient shipping paths and itineraries can be approximated with the use of records from shipping ports and vessels. However, even with these records, it is still difficult to know which pathways were taken and unrecorded journeys are difficult to predict. The objective of this project is to create a program that, when given two ports, will find the quickest path between the ports while considering geography, currents, winds, and ship parameters including size and speed. Deliverables of the project will be the program with designed algorithm model to solve the problem of finding the quickest maritime routes when given relevant shipping parameters and its visualization.

Methodology

The algorithm to solve the quickest path will use input including geography, currents, winds and also ship parameters such as size and speed. The design flow in order to  compute the quickest path and visualize the maritime route on the map shown in Chart I.

Program Design Flow
Chart I

 

Algorithm Development

The first step of developing an algorithm that will solve the quickest path is to select the appropriate optimization algorithm. This task can be completed by many heuristic algorithms, like the Memetic algorithm, Differential evolution, Differential Search algorithm, Dynamic relaxation, Genetic algorithms, Hill climbing, Nelder-Mead simplicial heuristic, Particle swarm optimization, Artificial bee colony optimization, Simulated annealing, Tabu search, etc. Path-optimization algorithms will be the first family of algorithms of interest; however, the inclusion of current, wind, and ship parameters makes existing path finding algorithms insufficient. Once a proper algorithm, or algorithm modification, is selected, the algorithm will be implemented with the computing language MATLAB. Emphasis will be placed on selecting an algorithm that will converge to the global solution.

Software platform

For this project, MATLAB, developed by Mathworks, will be used as the platform to design the algorithm model, not only because of its powerful numerical computing function, but also due to its mapping capacities, which will be beneficial to convert data to visualization.

 Data Importation

As seen in the design flow chart, the importation of input data is an important step for the program to calculate a solution. In order that the algorithm could be capable of easily interpreting inputs, a portion of this project will be dedicated to converting geographical data to paths in Cartesian coordinates and current and wind data into vector information via a visual interface in MATLAB.

Another body of data used will be the shipping record data set from 1262-1453. A script will be written that will convert the city acronyms to longitudinal and latitudinal coordinates, dates to time of travel, and will also store the captain of each voyage if listed. Having the data in this format will make validation of the algorithm possible.

Validation

In order to ensure that the algorithm is producing realistic results, the results from the algorithm will be compared to the shipping records from ancient Venice. If the algorithm is correct, it is expected that the real travel times will be longer than, but similar to, the results produced by the algorithm.

This comparison will provide the opportunity to infer interesting trends from Venetian maritime travel during this time. For example, it will be interesting to note if over time, captains discovered quicker routes between ports or if certain captains had consistently quicker travel compared to their colleagues.

Visualization

As Chart I indicates, the output of the algorithm is to present the quickest path on the map. However, the algorithm model output might be a sequence of points. Therefore, it is necessary to be converted to a visualization on the map so that users could easily see the quickest route. The visualization will also allow for the ability to include the magnitude and direction of current and of the wind. This visualization will be completed with the MATLAB Mapping Toolbox and will also be presented alongside metadata for the solved route.

If consistent trends are observed among captains, it may be possible to rank captains based on their travel time compared to the quickest route possible. If this is the case and one of the “Facebook of ancient Venice” groups will be including captains, this data could be included on their fictitious profiles.

Presentation Preparation

The final portion of the project will consist of preparing the deliverables in a way that is clear and meaningful to those that may investigate our project in the future. This will include documentation on why the algorithm was selected and how it works. Also, example solutions of the quickest path will be added to the Venice Atlas blog using mapping plugins and WordPress.

Extra Tasks

There are several interesting ways in which the project can be expanded that may be limited on time available. As such, the following tasks are included as extra ideas that may be completed if enough time permits at the end of the semester.

Standalone Program

At minimum, all of the scripts developed will be combined into a single program that will be considered as one of the deliverables of the project. One goal, however, would be to compile the program into a standalone executable file that could be run without any knowledge about or need to have MATLAB.

Simple Land Route Planning

A further interesting extension of the project would be to consider major cities on land in ancient Europe and associate them with the shipping ports that they would have used for trade or travel. This would allow an itinerary to be developed if one wanted to go from any city to any other within ancient Europe.

Consideration of Shipping Trends

When the shipping records are analyzed in comparison to the quickest path result from the algorithm, there may be trends that develop. Some of these trends could be a gradual decrease in travel time over the years or possibly quicker sailing by certain captains. If these trends can be characterized, it may be possible to consider them as factors in extrapolations for shipping travel times for undocumented years and routes.

Gannt Chart