Sailing Path Optimization

Ancient History. For most of us, it is something we only access through books, paintings, and visits to crumbling historical sites. But what is we could virtually travel back in time? This is the lofty goal of Dr. Fredric Kaplan at EPFL who, along with graduate students like myself, is creating a Venice Time Machine. The aim of this Time Machine is to use technology to transport us back in time to the days of ancient Venice in ways never done before. You could ask questions such as: What was the price of fish in 910 AD? What would one see when looking out over the great canal from the Rialto bridge in 700 AD? If one wanted to take a boat from Venice to Cyprus, for example, how long would it take? This last question was my contribution to the Venice Time Machine and my first in-depth optimization project.

With today’s use of ship engines, finding the quickest maritime route is a trivial task as it simply reduces to finding the shortest path of travel. The introduction of sailing ships, however, requires a much more complex analysis. When considering a sailing ship, the optimization must consider water currents, wind speed and direction, and the type of boat. The final optimization program was broken down into two steps. The first step is an Ant Colony Optimization, which simulates the way in which ants will find the shortest path between their ant hill and a source of food. The second part of the optimization is a Local Search Optimization, which refines the path so that is resembles how ships actually sail.

Image of the Ant Colony Optimization in Progress

A snapshot of the ant colony optimization program in the process of finding the quickest maritime sailing path between Crete and Venice.

Image of the quickest sailing route found using a Local Search Optimization

The quickest sailing route found afterthe Local Search Optimization for a 65 foot boat travelling from Crete to Venice using wind data typical for late summer.

Using the results from the optimization and a handful of records from Ancient Venice, it was found that the Venetian ships generally travelled at 80% the optimal travel time. Therefore, for us Venetian Time Travels, one could pick two places, run the sailing path optimization program and then, by applying the inefficiency factor, one can now answer questions like “How long would it take to travel from Venice to Cyprus?”, even if no records of this travel exist today.