Paper 4

On the Performance of Triangulation-Based Multiple Shooting Method for 2D Geometric Shortest Path Problems

Authors: Phan Thanh An, Nguyen Ngoc Hai, Tran Van Hoai, and Le Hong Trang

Volume 16 (2014)

Abstract

In this paper we describe an algorithm based on the idea of the direct multiple shooting method for solving approximately 2D ge- ometric shortest path problems (introduced by An et al. in Journal of Computational and AppliedMathematics, 244 (2103), pp. 67-76). The al- gorithm divides the problem into suitable sub-problems, and then solves iteratively sub-problems. A so-called collinear condition for combining the sub-problems was constructed to obtain an approximate solution of the original problem. We discuss here the performance of the algorithm. In order to solve the sub-problems, a triangulation-based algorithm is used. The algorithms are implemented by C++ code. Numerical tests for An et al.’s algorithm are given to show that it runs significantly in terms of run time and memory usage.