Maritime pattern extraction and route reconstruction from incomplete AIS data

The concept of synchromodality was introduced in the Netherlands in 2011 with the goal of allowing the usage of the most suitable mode of transport at all times during the fulfillment of an order, through cooperation within supply chains, transport chains and infrastructures [7]. According to [8] and [9], the core idea of the synchromodal concept is the real-time switching between the transport modes.

In 2013, the Synchromodal IT project was started, in an effort to provide a unified platform to integrate various stakeholders in the logistics domain and manage the process. The added value the Synchromodal IT platform brings is the ability to provide essential information for process optimization that LSPs either could not acquire on their own, or the expense of doing so would not justify the potential benefits [2].

As mentioned earlier, deep sea vessels are given priority over barges at port terminals, as they represent larger clients bringing higher volumes of cargo, and revenue. Consequently, the arrival of a deep sea vessel, makes the terminal unavailable for barges, which is referred to as terminal disturbance. If a barge is forced into idle mode due to this disturbance, or the cargo containers onboard cannot be loaded/unloaded, expenses for LSPs will increase. Considering the fact that most barges have to be booked in advance, these disruption events are posing constant challenges for the planers.

To solve the problem, the platform needs to predict the occurrence of these disruptions, and this is possible if we can predict the arrival time of deep sea vessels. The publicly available AIS data can be used to give current information about the position of any vessel, its heading, and speed. The literature review in [2] on using AIS data for predicting arrival times, shows that there are two distinctive approaches for estimating future position of a vessel depending on time frame.

The short-term prediction is used to identify anomalies in vessel behavior, indicating suspicious activities like smuggling, piracy, or illegal dumping. These kinds of predictions analyze motion patterns of individual vessels and are accurate for time frames of up to one hour in the future. On the contrary, the long-term prediction is not feasible through the analysis of individual patterns only. Therefore, it is required to extract route patterns, and use them for predicting potential vessel destinations—end points.

To extract maritime patterns from AIS data, it is required to have a good algorithm capable of identifying route waypoints. Pallotta et al. [4] define the TREAD methodology that uses incremental DBSCAN to isolate turning points, and connects them afterward to get shipping lanes. Lei et al. [10] developed the TMP algorithm that also uses DBSCAN to discover “hot regions” using them into a modified probabilistic suffix tree to obtain the probability distribution for discrete events occurring in a sequence, thus discovering moving behavior.

Giannotti et al. [11] introduce the T-pattern algorithm to extract frequent temporally annotated sequences of dense spatial regions from trajectories. Rinzivillo et al. [12] use progressive clustering to aggregate trajectories in their entirety based on their similarity in geographic, temporal or attribute space. However, the last two approaches are more suited for non-naval patterns, where initial trajectories do not have the tendency to considerably deviate from one to another due to external factors.

Handl and Knowles [13] show that unsupervised learning problems, such as data clustering, can be solved using an evolutionary approach. The paper also points out that the correct clustering solution often corresponds to the trade-off between two or more clustering objectives, such as minimization of overall deviation, and connectivity. Taking into account that the problem of discovering route patterns is based on clustering of positional data, we conclude that the evolutionary concepts can be used for waypoint identification.

Soares Junior et al. [14] use an unsupervised iterative procedure to segment trajectories. They identify representative points in the data, and use Minimum Description Length to compute similarities, and measure homogeneity needed by the GRASP-UTS algorithm to build new route segments through the modification of the representative points. Research done by Lee et al. [15] and Li et al. [16] use what authors refer to as the “partition-and-group framework” to cluster trajectories. In [15] a trajectory clustering algorithm TRACULUS is developed, which divides trajectories into line segments, and clusters each subset in order to discover common subtrajectories. This process generates a set of representative trajectories, that can be used to analyze special areas of interest. Since the trajectory data are received from the sensors incrementally, the approach is adopted in [16], introducing micro cluster maintenance, and macro cluster creation. This enables the processing of large amounts of data as it is being received, and allows for incremental trajectory clustering. We find this approach to be a good fit for our problem of route extraction as vessel positions coming from the AIS data are recorded sequentially, preventing the solution to be applied to an entire data set, and requiring a form of incremental pattern discovery. However, due to the fact that already extracted routes may not be valid if weather conditions change, and to the possibility of having incomplete and partially noisy data from the real case environment, we chose to base our solution on a genetic algorithm as it can adapt to trajectory changes, and it is showing robustness when handling imperfect input.

Dobrkovic et al. [3] investigate various algorithms for waypoint discovery in the area of the North sea, including DBSCAN, modified ant colony optimization, and a genetic algorithm. They explain that in a real case application algorithms have to cope with clustering maritime data points where density varies. This makes finding optimal parameters for all clustering algorithms challenging, as shown in Fig. 1 where DBSCAN either misclassifies an entire area of the Netherlands as one cluster, or the area in UK as noise.

The GA enhancement steps described in the solution design are made to enable the genetic algorithm to efficiently process large data volumes, which is typical for real life industrial applications. Therefore, we measure the time it takes for the improved algorithm to discover maritime waypoints and compare it with the execution time of the standard approach.

Since these two algorithms process data in a different manner, we design the test and set up algorithm parameters such that we can measure execution time of every epoch in similar conditions. For the time test, we set the area to the coordinates of South Holland province. The population size is set to 50, mutation is 1%, and both algorithms are capped at 100 epochs. The standard algorithm is tested with a chromosome length of 20. In the case of the improved algorithm, it is set to run 20 phases.

We run the standard genetic algorithm three times, using data sets containing 2150, 165,200, and 591,300 points. With each epoch, as the algorithm converges toward the solution, the number of intersection tests between WP, and points increases, slowing down the execution time. In direct relation to the formula (8), adding more points has a considerable negative effect on the performance as shown in Fig. 16. This reveals the limitation of the standard approach, as with the increase in points increases the requirement for additional WPs. In terms of the GA that means that the number of chromosomes also has to increase, resulting in exponential surge of the required time per epoch.

Next, we focus on the performance of the enhanced solution. In Fig. 17, we show by means of a scatter plot the execution time in seconds for all 20 phases, each running 100 epochs. Associated with each phase is the bar plotted value showing the number of points loaded. From the chart we can see that the time for each epoch stays within the interval 0.5–2.0 s. While the execution slows down throughout the epochs (which is typical for the GA), we notice that switching to the next phase enables the algorithm to omit the points used in the fitness check, and maintain a steady execution time. The chart highlights the main positive characteristic of the improved genetic algorithm, namely the ability to handle the increased amount of data without a significant impact on the overall performance.

The second essential test is the extraction quality of the algorithm, i.e., the extent to which it accurately represents maritime routes. To make that assessment in a real case environment, we can only rely on the visual comparison. Therefore, we choose to test the algorithm on the area corresponding to two Dutch provinces, while focusing on inland waterways. A good algorithm will generate the graph corresponding to the map of rivers and canals in these two provinces. If there is an edge across nonexistent waterway, that would be a clear indication of the poor extraction quality.

In Figs. 18, and 19, we show: the AIS positional data used for the experiment with the discovered waypoints, extracted graph after pruning, and the noise reduction, the same graph on top of positional data, and the actual waterways map for the region. The South Holland was chosen as the province with the heaviest inland traffic, and many intersections, while Overijssel was chosen as its opposite. In both cases we do not identify any inconsistencies such as routes going through the land areas, and the main routes from the map are also present in the graph. Therefore, we conclude that the algorithm produces an acceptable/correct route representation. However, we note the presence of noise in closely positioned waypoints, mostly attributed to the inaccuracies in input data, as shown in Fig. 10. In Test 1—Overijssel, there are some routes that the algorithm does not identify, but this not a defect of the algorithm: it is due to the fact that there are narrow canals, on which commercial vessels that are required to broadcast AIS signals, cannot sail (Fig. 18, blue dotted lines).

For the actual maps we used the online source from the “Waterrecreatie Nederland”[18].

The extraction quality test from the previous section gives an indication that the algorithm performs as expected, but it does not allow us to quantify its quality, and compare it with other approaches. Due to the fact that different algorithms use different AIS data sets that are not publicly available, we are not able to compare the performance of this solution with others under the same conditions. To lessen this drawback, and allow future comparisons we propose to use a set of simulated AIS data with enumerated routes.

We use the same test used in [3] containing four overlapping routes, two horizontal and two vertical (see Fig. 20). This configuration allows for the clear comparison of the extracted routes with the simulated ones. The routes are labeled a, b, c and d. For every route, the simulation generates new vessels at both ends. The simulation runs for a given number of intervals, and during each one, the vessel position is updated, and new vessels are generated at route ends. The vessel trajectory is given as a vector with direction toward the opposite end, and the magnitude of the vector is set according to the predefined lane specific parameter indicating the average speed. To prevent all vessels having the exact same path, another vector is added representing the deviation from the path. The movement delta per every interval is calculated as the sum of these two vectors. Since we want to test our algorithm on lanes that have different traffic density, the lane b is set to generate five times more vessels per interval than the lanes a, and d. The lane c represents a less travelled route generating one third of the traffic from the lanes a, and d. The average speed of the vessels is the same for lanes a, b, and c, while ships in lane d are set to move twice as fast. The intersections between the routes are labeled as capital red letters A, B, C, and D.

We run the simulation, setting it to generate 8000 ships over the interval of 200 time units. The position of every vessel is stored and used by the following experiments. Since the test presented in the Execution time section showed that the enhanced GA solution offers much higher execution speed with the same or better extraction quality, the standard GA was ignored, and all tests were performed on the enhanced GA. The algorithm was run ten times, using 100, 800 and 2000 epochs. For the same number of epochs the test was repeated three times. The first, and the second run had population, and elite size set to 50 and 2, respectively. The third one has those values doubled: 100 and 4. After these nine tests, we run one more test with significant increase on mutation size to 20%. To evaluate the algorithm we calculate the number of correctly extracted lanes in comparison with the total number of lanes, and do the same for the intersection points. The final score is the average of these two values. The results are given in Table 1

First we set our attention to the route accuracy. Based on the scores, we conclude that with sufficient number of epochs, the enhanced GA handles route extraction very well. The tests 1–3 were run with setting the limit to only 100 epochs. As this number of epochs is typically insufficient for the GA to converge to a good solution, we use it to compare how the accuracy increases with the increase in the epoch limit. Decreasing the number of epochs allows for fast execution, yet lowers the quality. However, due to preprocessing provided by the quad tree structure, the algorithm was able to quickly converge waypoints to the lanes, and correctly identify 2 or 3 out of 4, scoring between 50–75% for this part. Upon close inspection of the missed routes, we found the spread of waypoints to be correct in the large segment of the lane, yet the low number of epochs prevented the algorithm to accurately extract waypoints near the starts, and the ends, hence impacting the score. All tests (1–10) show that increasing the population size has negligible effect on the overall score, and this parameter is removed from further considerations. With tests 4–9, increasing the number of epochs to 800, and finally to 2000, allowed the algorithm to fit all the waypoints, and correctly identify all the lanes. From this we conclude that the further increase in the number of epochs would only decrease the execution speed without providing improved precision.

The intersection points proved to be more challenging for the GA. Although tests 4–9 had 75% score, not a single configuration managed to achieve 100% precision. This is due to the fact that the AIS point density within the intersection was not significantly greater than the density of the points in the neighborhood, hence in all of those tests the GA tended to be stuck in the local maximum, close to the optimal. Yet without a high mutation value, could not reach it. Test no. 5 illustrates this well, with the number of accurate intersection detections dropping to only one, due to the fact that the close neighboring waypoints were discovered first. The final test (no. 10) was performed to check the algorithm’s behavior with a large mutation value, and see if that would improve, or decrease the ability to detect the intersection points. As shown in Table 1, where the final score for the test 10 dropped to 37.5%, a large mutation value in the long run negatively impacts the solution contained within the elite chromosomes, eventually preventing the genes of the best entity to be preserved for future epochs. This causes accuracy to drop in both lane, and intersection detection. Balancing between the speed, and the extraction quality we find that the algorithm performs the best by using the parameters given in test 4. The graphical representation of the input data, waypoint extraction, graph creation, and the final result after filtering, and pruning for test 4 is given in Fig. 21, which scored 87.5% on our test. To explain the missing 12.5%, we zoom in on the intersection point B (the lover right one) in Fig. 21b, c. We can see how GA narrowly missed the intersection, and the impact it had on the final result Fig. 21d, even though the routes were accurately extracted.

The tests are repeated again with the same parameters, but instead of the complete data, we use the same simulation, and occlude two regions. We pick the regions in such a way that one occludes part of the lane a, and the other the intersection point C. Table 1 contains the parameters, and results for the tests 11–20. The simulation input data, after introducing the blank regions, are shown in Fig. 22a. As with the tests 1–3, small epoch limit of 100 in tests 11–13 prevents the algorithm to find a good solution, yet the preprocessing of quad tree still allows for a 75% accuracy of the route extraction. From 800 to 2000 epochs (tests 14–19) the solution performed with an incomplete data set in a similar fashion as in the case with the complete AIS data. There is a good extraction result for lanes, and intersections are either correctly identified, or there is a narrow miss attributed to the algorithm being stuck in the local maximum in the vicinity of those points. This time the genetic algorithm was more successful in identifying the intersection points, but this is attributed to the random choice of picking initial waypoints, and cannot be guaranteed. Test 20 with a high mutation again showed that increasing this parameter has considerable negative effect on the score.

The main point of tests 11–20 is to see how the GA handles missing data. Comparing Figs. 21 and 22 and the scores in Table 1, we can see that there is no performance drop caused by the blank region overlapping a part of the lane a. The variations in score are solely due to the stochastic nature of the GA. The waypoint C could not be detected as there was no input data in the vicinity, yet in this example it didn’t have a significant influence on the results. Figure 22 shows the input data set, waypoint discovery, and graph creation for the test 15. From the presented experiments, we may conclude that the enhanced GA provides a robust solution to extract maritime routes in a real case scenario using standard PC hardware.

The solution presented in this paper shows how to perform maritime route reconstruction using a genetic algorithm. Although related research such as [4, 12, 19] also deal with route extraction, and [20] can also provide up to 60 minute prediction in milliseconds, our decision to use an evolutionary approach is based on future needs of the Synchromodal IT platform.

The ideal Synchromodal IT platform should be able to handle data from large waterways areas, such as entire Atlantic ocean, and be able to estimate vessel arrival times 48 hours in the future. The current process of collecting, and storing AIS data, the available computational power, and the extant algorithms’ efficiency are limiting factors to achieve such an objective. However, working toward this scenario imposes that the following requirements and limitations must be taken into account:The current state of the art approaches treats input AIS data on an “as is” basis. The area under consideration is fully covered by AIS receivers, and the collected vessel data is deemed complete. There are no missing regions. On top of that, the patterns are extracted from the coastal areas where the route changes due to weather factors are not observed. In such conditions, the genetic algorithm can be outperformed both in terms of precision and speed. To the best of our knowledge, there is no solution that is addressing the problem of maritime route extraction between points including partially occluded areas. As demonstrated on waypoint extraction in [3], clustering solutions such as DBSCAN that contain no memory, are highly vulnerable, and intolerant to missing regions. The novelty of our approach lies in providing the means to discover maritime patterns when dealing with imperfect data, typical for a real case business environment.

Additionally, the requirements of the future Synchromodal IT platform suggest that the improved solution must not only be able to remember and adapt, but also to forget. To clarify, we consider the scenario when one sailing pattern changes due to external factors (weather, tide) [5]. If we consider a large waterway area, such as the Atlantic ocean, it is unfeasible to recalculate all patterns every time the change occurs. Storing the AIS data for such a large region, in contrast to handling real-time data streams would pose an additional challenge. Therefore, the solution must adapt in real time relying on the fragmented data currently available. Our GA approach has shown it is capable of evolving with the changes. It is our intention to explore what is the most suitable option to fade, and forget waypoints over time, if the traffic density decreases, thus endowing the solution with real-time adaption capabilities. To that end, the evolutionary approach seems to be a good candidate.

Ideally, the strong and weak points of this solution can best be illustrated by comparing them with other route extraction algorithms. Due to unavailability of AIS data used by the other approaches, we are unable to measure the differences in precision, and execution speed. As different environments can favor one solution over the other, in this section we present the current state of the art, and discuss the similarities with, and differences from our approach.

By short-term prediction, we assume estimating vessel points up to 60 minutes in the future [2]. For such a time interval the routes are not considered, instead the prediction is solely based on the data of the individual vessel, and its history. Perera and Soares [21] use Extended Kalman Filter to estimate the position, velocity, and acceleration of an vessel, and use these values to predict its position. Ristic et al. [22] focus on anomaly detection. With the assumption that the sailing patterns are extracted, they use Kernel density estimator to estimate the future position of a vessel, and compare it with known patterns to identify anomalous behavior.

Long-term predictions, and analysis of maritime patterns calls for a different approach. Rather than learning from each individual vessel, the data are grouped, and analyzed to discover route waypoints, lanes, and their characteristics. The common line for all approaches is the clustering algorithm, and typically it is based on DBSCAN or an improved version of it. Pallotta et al. [4] use incremental DBSCAN to identify waypoints as part of the THREAD algorithm to identify maritime routes. The challenge we faced when testing DBSCAN was that the fine tuning of parameters for good waypoint identification is not possible when dealing with areas with varying density. Due to the very high traffic density in the vicinity of Rotterdam, DBSCAN would give one of two options: a good waypoint spread within the Rotterdam harbor, and the rest treated as noise, or a good waypoint spread around the Rotterdam area, while the entire Rotterdam harbor area was classified as one huge cluster. Therefore, we conclude that this approach is possible as long as the region under consideration maintains a similar level of traffic density, but does not suffice for our needs.

The improvements of clustering have been addressed in [12] and [20]. Rinzivillo et al. [12] use OPTICS algorithm to achieve the progressive clustering and aggregate trajectories. Xiao et al. [20] use lattice-based DBSCAN, and with that approach significantly reduce the problem scale, allowing for fast route extraction, that the authors claim to be in milliseconds on standard PC computer. Containing DBSCAN within the lattice also solves the density problem. The genetic algorithm we use also successfully handles areas with varying density, although we have to report a slower execution time, which increases with the number of epochs. Rinzivillo et al. [12] and Xiao et al. [20] both use the complete data for the area of their consideration, and do not report any missing regions, or incorrect data. If the entire data set is available, both OPTICS, and lattice-based DBSCAN can effectively identify the waypoints. However, if AIS data come in streams which contain fragmented routes, DBSCAN (and its enhanced versions) is unable to cope, as it contains no memory. On the other hand, our genetic algorithm is proving to be more robust, clustering first the available points, and then converging to the higher density area, as additional AIS data become available. In section 2.3.3, we have showed that unless starting waypoints have been occluded, our solution is able to cope with missing regions.

Big data represent an additional dimension to the complexity of clustering moving entities, and trajectories, due to the fact that clustering algorithms used to group the objects according to their properties, do not scale effectively to the increasing volume. Extending the work of Rinzivillo et al. [12], Andrienko et al. [19] use a human analyst to combine clustering, and classification for large data sets. That approach implies that a human analyst will first select a subset of the objects, and experiment with various parameters, in order to build a suitable classifier. That classifier is then used to cluster data points, with the option that the analyst can further supervise the process, and alter the clusters when needed. The solution we propose in this paper is also able to scale with an increasing number of AIS data through incremental waypoint discovery, illustrated in section 0. Due to the quad tree preprocessing, and the removal of data in the vicinity of the extracted waypoints, the genetic algorithm is able to maintain the execution speed even with a continuous increase in input data (see Fig. 17). Although the requirements of the Synchromodal IT platform favor the option of fully autonomous solution, the potential benefits to improve the results through human–machine symbiosis are considerable, and will be investigated in the future.