Design of a Weather Dependent Re-routing Algorithm for SafeTrans Monte Carlo Simulations
MetadataShow full item record
SafeTrans is a software program used to simulate intended marine heavy lift transports with the purpose to obtain statistics on the shipping route, sailing speed and motion behavior. In SafeTrans a Monte Carlo simulation (MCS) can be performed in which a specific transport is simulated in multiple runs subjected to randomly selected historical weather forecast scenarios applicable to the sailing area. Some routes advised by the actual implemented Dijkstra re-route algorithm do not reflect realistic decisions. Experience with Safetrans re-routing has shown several problems and limitations of this algorithm design, such as land-crossings, route generation at fixed speed, optimization for sailing time only and lack of route decision memory. In this study Anya 3D is proposed, an improved re-route algorithm for SafeTrans MCS that aims at finding the optimal sailing route for a given weather forecast while meeting user-defined weather criteria and admissible ship engine settings. This route is based on a cost function that includes user-defined weights for fuel consumption, sailing time and late arrival penalty. The basis for this algorithm is Anya, a recently published sketch for an optimal any-angle pathfinding algorithm for 2D environments with grid-based obstacles. This sketched algorithm has been extended for path finding problems in a 3D space and time environment with sea grid cells either blocked or traversable in time depending on the weather conditions. In addition an algorithm is proposed to make a path taut in 3D based on the multi-objective cost function and economical speed. In simulations, the proposed algorithm is tested and compared to the actual re-route algorithm for route distance, sailing time, fuel consumption and runtime. In addition an implementation is made of the sample-based RRT* pathfinding algorithm in order to compare both Dijkstra and Anya 3D. Experiments have been performed for eight problem instants that contain severe weather conditions, distributed over four shipping routes. The experiments show better route generation with respect to the research objectives for Anya 3D in comparison to Dijkstra when the amount of obstacles is limited. In addition, runtimes of search queries with limited obstacles is shorter than the actual implemented algorithm. For more complex environments the performance of Anya 3D drops as the search space grows exponentially with the number of obstacles. Methods to prune branches of the search tree should be further investigated to avoid exponential growth.