Route Planning for Military Ground Vehicles in Road Networks under Uncertain Battlefield Environment

Abstract EN

Route planning for military ground vehicles in the uncertain battlefield is a special kind of route planning problem, as the military vehicles face a great of uncertain and unpredicted attacks.

This paper models these uncertainties in the road network by a set of discrete scenarios.

A kth shortest-path method is introduced to find intact routes from the origin to the destination for each vehicle.

A binary integer programming is presented to formulate the problem.

As the combination of the uncertainties results in a huge number of scenarios, we employed the sample average approximation method to obtain a robust solution for the problem.

The solution approach is illustrated and tested through three road networks with different scales.

The computational results show that, for networks of small scale, our method can provide a good solution with a sample of small size, while, for the large network, with sample of small size, this method usually leads to a suboptimal solution, but a good solution can still be obtained as the sample size grows bigger.

In addition, variation trend of the deviation with different sample size indicates that a sample of larger size can bring more stability to the results.