by Andreas Komninos (Computer Technology Institute & Press “Diophantos”), Charalampos Kostopoulos (OptionsNet IT Services & Consulting) and John Garofalakis (Computer Technology Institute & Press “Diophantos”)
Yachting tourism has the potential to drive strong blue growth in hosting countries due to its multiplicative effects in other related service and goods economy sectors. The project “Intelligent ICT Applications for the Management of Marinas and Yachts” is using intelligent approaches to address the unique challenge of providing journey-planning tools to yachters.
Yachting is a major contributor to the high-quality, sustainable, blue growth economy in the Mediterranean. In Greece, yachting contributes approximately 4.4 jobs for every 100 docking spaces, and a further 100 jobs in related business sectors [L1], adding tremendous value to the local and national economy. Research and application of digital technology can enable further growth of this sector.
The project “Intelligent ICT Applications for the Management of Marinas and Yachts” (SaMMY+) [L2], is a partnership between industry and academia. The industry partner, OptionsNet, provides digital services to the marina booking and management sector, with its product platform SaMMY [L3]. The academic partner, the Computer Technology Institute and Press “Diophantos”, has expertise in algorithmic solutions for spatio-temporal data, and machine learning. Both partners are based in Patras, Greece. One of aims of the project is to improve the SaMMY platform, with a customer-facing multi-criterion journey planning service.
Route-finding in yachting is harder than for road travel because the connections between docking points (waypoints) in a journey are not fixed in space and time. A vessel can take any course between two waypoints, restricted only by geography and supplies (Figure 1). Variable weather conditions make it difficult to predict how long it might take to travel between two points, or even whether it is possible. Further, yacht travel planning involves queries about amenities at each destination (e.g. docking availability, fuel, nearby facilities), which typically do not pertain to land travel. A yachter aiming to plan a journey must thus: (i) identify candidate waypoints based on availability, on-site and/or nearby amenities, and (ii) calculate an optimal route between waypoints, with optimality depending on several criteria (e.g. maximising stay time at each point, or the number of visited points). This is a difficult cognitive task, requiring significant manual effort. Our aim is to develop algorithms to support the planning process.
Figure 1: Planning a yachting holiday route is a difficult challenge. A typical 7-day itinerary in the Ionian Sea can be almost any combination between the 35 ports and marinas shown here (Map data © OpenStreetMap, port and marina locations courtesy of http://mykosmos.gr, sample itinerary from http://charter-greece.com)
To identify candidate waypoints, we employ a semantic approach with docking points and other POIs modelled in an ontology (Figure 2). Compared to a traditional spatial database, an ontology offers much better support for reasoning to handle abstract queries likely to be posed by non-expert users during a search (e.g. “I have five days and want to visit Ithaca, Lefkas and Corfu and like to eat seafood”). It also offers better modelling flexibility (classes and relationships can easily be added or modified) and allows for fuzzy representations of relationships (e.g. “isNearBy” can be a relationship type between two POIs without concern for the actual distance).
Figure 2: An example ontology for marina candidate determination. Various POIs (including marinas) belong to cities. POIs can be related to various service types, and to marinas through the “isNearMarina” relationship.
Figure 3: The search space (number of possible simple paths) increases exponentially as more candidate docking points (vertices) are added to the graph.
To find an optimal route between waypoints, we model travel as a weighted, time-dependent graph, where vertices represent docking points, edge weights represent travel time and stay time can be included at various vertices [1, 2]. In contrast to land travel, where vertices are typically connected by a single edge, in sea travel every vertex is theoretically connected to all others (within reach of the vessel’s supply levels). This can translate to an exponentially large number of possible routes that can be investigated (the “search space”). For example, in a complete non-directional graph (all vertices connected to each other) with 10 vertices, selecting any two vertices as the start and end point, the search space includes 109,601 simple paths (Figure 3). Adding the user’s maximum available journey time to the problem can help limit the search space by using a backtracking algorithm, since this approach can quickly eliminate many of the possible paths that lead to a longer journey time [3].
Figure 4: Qualitative aspects of path search space. For our given graph model, it appears that the best compromise is short trips (three days) since on average these trips offer the lowest idle time and the search space is reasonably small. Longer maximum journey durations allow for more ports to be visited (up to five, on average), but most solutions in this search space lead to very large idle times.
Figure 5: Applying a restriction on the remaining idle time (here, 20%) significantly shortens the path search space, especially for trips with a longer maximum duration in our graph. Though for our given graph the best quality trips (less idle time) are three days, the search process can still return good results even for longer trips.
To demonstrate, we use a randomly generated full, non-directional graph with eight vertices and edge weights between 30 and 480 minutes and consider a fixed stay time at each vertex of 720 minutes (12 hours). A shorter maximum journey duration significantly limits the search space in this model (Figure 4, left). However, this creates another problem – we notice that for many of the possible solutions, there remains significant “spare time” (i.e. time after arrival at the end point, and the maximum user-specified journey time, see Figure 4). This means that many of these solutions are low quality, since to reduce this idle time, the yachter must stay longer in each (or one) port, which in turn may affect availability of spaces in subsequent destinations, and so on. Adding a threshold on the maximum allowable idle time (e.g. 20% of the maximum journey time) significantly improves the limitation of the search space (Figure 5). Furthermore, it allows for a better visitation experience, since the possible trips contain, on average, more points than using the maximum journey duration limit alone.
In the near future we aim to assess the performance of these algorithms using a realistic dataset. To populate the POI ontology, we have developed a scraping system to mine data from various sources (e.g. Foursquare, Facebook, Google Places). A problem that remains to be solved is the estimation of realistic travel times between docking points. For this, we aim to mine and analyse historical data from AIS records, according to vessel type and declared origin and destination.
Links:
[L1] https://nee.gr/downloads/184STUDY_ON_YACHTING.pdf
[L2] http://hermes.westgate.gr/sammy/
[L3] http://sammyacht.com
References:
[1] H. Wu et al.: “Path problems in temporal graphs”, Proc. VLDB Endow 7(9):721–732, 2014.
[2] G. V. Batz, P. Sanders: “Time-dependent route planning with generalized objective functions”, in: European symposium on algorithms, Springer, pp 169–180, 2012.
[3] A. Biere, M. Heule, H. van Maaren: “Handbook of Satisfiability”, IOS Press, ISBN 978-1-60750-376-7, 2009.
Please contact:
Andreas Komninos, Computer Technology Institute and Press “Diophantos”, Greece,
Charalampos Kostopoulos, OptionsNet IT Services & Consulting, Greece,
