On the performance of triangulation-based multiple shooting method for 2D shortest path problems

Proceedings of International Workshop on Advanced Computing and Applications. LNCS Transactions on Large Scale Data and Knowledge Centered Systems, 8960 (2014), 45-56
http://dx.doi.org/10.1007/978-3-662-45947-8_4

In this paper we describe an algorithm based on the idea of the direct multiple shooting method for solving approximately 2D geometric shortest path problems (introduced by An et al. in Journal of Computational and Applied Mathematics, 244 (2103), pp. 67-76). The algorithm 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.