On the Performance of Triangulation-Based Multiple Shooting Method for 2D Geometric Shortest Path Problems - Transactions on Large-Scale Data-and Knowledge-Centered Systems - page 46

solving shortest path problems in which the algorithms are constructed relying
on graph theory (see [ 3 , 6 ]). The main challenge of these methods is concentrated
in the size of the problem. Namely when the size of the problem is huge, the
required resource for computing is thus increased too much. This can be over-
come ideally by dividing the problem into sub-problems. The sub-problems are
solved. The obtained shortest paths of the sub-problems are then combined into
the shortest path of the original problem.
For solving ordinary differential equations (ODE), in particular with bound-
ary value problems, the multiple shooting method was introduced (see [ 13 ]). By
this method, the problem is first divided into several sub-problems. The values of
the solutions of sub-problems are computed simultaneously by iteration. To this
end, a continuity condition between the solutions of the sub-problems is required
at the solution of the problem. A variant of the multiple shooting method called
direct multiple shooting method was introduced by Bock and Plitt [ 4 ]togive
the solution of optimal control problems. Based on the idea of this method,
an approximate algorithm for solving 2D geometric shortest path problems has
been recently introduced by An et al. [ 1 ]. Given a simple polygon, the algorithm
first divides the polygon into sub-polygons then computes iteratively to obtain
an approximate shortest path between two vertices of the polygon. A so-called
collinear condition based on the idea of continuity and differentiability condi-
tions for combining the solutions in the sub-polygons, is constructed to obtain
an appropriate shortest path in the polygon (see Theorem 3.2-3.3 in [ 1 ]).
In this paper, we discuss in detail the algorithm introduced in [ 1 ]onthe
aspect of performance. It differs from [ 1 ] that we implement a triangulation-based
algorithm called the funnel algorithm (see [ 7 , 8 , 10 ]) for finding the geometric
shortest path in each sub-polygon instead of using the algorithm given in [ 2 ].
The funnel algorithm is based on triangulation of the polygon and graph theory.
The numerical tests show that the method is ecient and reliable.

2 Description of Multiple Shooting Method for Solving
the 2D Shortest Path Problems

2.1 Multiple Shooting Method for Solving ODE-Boundary
Value Problems

Consider the boundary value problem of seeking a differentiable function y =
f ( x ) of one variable x such that its derivative y ( x ) satisfies

y ( x )= f ( x, y ) , (1)

r y ( a ) ,y ( b ) =0 ,

(2)

where ( 2 ) specifies the boundary condition and a, b are two different numbers.
In a multiple shooting method (see [ 13 ]), the domain of solution of the prob-
lem is discretized into several intervals as follows,

a = x 1 <x 2 < ··· <x k = b.