School Seminars and Colloquia

Constrained Shortest Path Problems in Threat Environments

ORSUM Seminar

by Assoc Prof Natashia Boland


Institution: University of Melbourne
Date: Fri 13th May 2005
Time: 1:05 PM
Location: Room 213, Richard Berry Building, University of Melbourne

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