EFFECTIVE COMPUTATIONAL MODELS FOR A CLASS OF CONSTRAINED PATH PROBLEMS
by
Louis Caccetta
Western Australian Centre of Excellence in Industrial Optimisation

The design of efficient routes for moving products, resources and information through a specified network or region which may be discrete or continuous arises in many applications. The objective may be expressed in terms of minimizing risk, cost or time or maximizing reliability. Usually the routes must satisfy a variety of constraints that may include : customer demand ; distance travelled; total transit time; delivery/pick up deadlines; need to visit or avoid specific nodes of the network; and a variety of resource restrictions that may include the vehicle capacity; number of customers serviced by a vehicle ; the available inventory; We consider a class of path problems where an object such as a robot or vehicle (air, naval, space or land) needs to traverse a specified region (discrete or continuous) between two points in a prescribed time or using a maximum amount of a resource such as fuel so as to avoid detection. The objective is to find a path for the object which satisfies the constraints and which minimizes the total risk of detection. of optimal control problems where the control functions are assumed piecewise constant and only take on values from a finite discrete set. The simplest form of the problem arises in discrete networks as a variation of the classical shortest path problem. The variation is a single constraint. This constrained shortest path problem is computationally hard (NP-hard). When the transit region is continuous as is the case in many applications the resulting optimisation problem is a discrete valued optimal control problem which is even more difficult solve. The aim in such a problem is to find a sequence of discrete control values and a corresponding set of exact switching times (i.e. times where control should switch between the discrete values) such that a given functional representing cost or risk is minimized. The objective is to find a path for the object which satisfies the constraints and which minimizes the total risk of detection. The risk function is not simple and depends on a range of factors such as the environment, the types of sensors, the speed, direction and position of the vehicle. In this paper we present a range of models and solution methods for both the discrete and continuous problems as well as discuss in a number of applications.

Date received: May 1, 2008