Constrained Shortest Path Problems in Threat Environments
by Assoc Prof Natashia Boland
Abstract: Reporting on joint work with Ranga Muhandiramge, Tim Robinson, Song Wang.
Military ships, submarines and aircraft are often faced with the problem
of planning a path through a threat environment, for example, through a
minefield. In situations where intelligence has been able to accurately
and reliably determine the location, and nature, of the threat(s),
planners seek a path that minimizes the risk of harm, while ensuring the
path satisfies operability constraints, for example, the length of the
path may not exceed some limit.
This problem can be approached by continuous techniques, or by
discretization, in which case a constrained shortest path problem in a
network (CSPP) must be solved. The CSPP has other applications in
transportation logistics, arising, for example, in its own right in road
transport models, or as a subproblem in column generation approaches to
air crew scheduling problems. We discuss these alternative approaches,
and present the results of our recent work on how to discretize the
continuous problem, and on how to better solve the CSPP.
For More Information: Mark Fackrell tel: 8344-8053 email: M.Fackrell@ms.unimelb.edu.au