On constrained optimal path problems and applications

Constrained Optimal Path (COP) problems seek optimal paths between a given source and destination pair in a domain. One or several real functions assign each path some values, called "metrics". A metric can be used either as a constraint, when it restricts the feasibility of paths by a threshold value, or as an objective function, when it is meant to be optimized. A COP problem computes the path with the best metrics.; We first describe the general concepts of COP problems---domain, path, metric, constraint, and objective function. Motivated by different research areas, we show that the problems of finding paths subject to the constraints and objective functions have similar structure.; The well studied instance of COP is the shortest path (SP) problem, in which the length of the path is the only metric. Though efficient algorithms exist to solve the SP problem precisely; most COP problems are difficult to solve.; We introduce the common approaches that address COP problems. These include integer programming methods, the Bellman approach, and heuristic methods. For the COP instances that are of interest, integer programming methods can find the optimal solution with exponential worst-case complexity. Most of the proposed algorithms in this thesis combine the Bellman approach and the k-shortest-path heuristic to search for sub-optimal paths in a practically efficient way.; We study some COP instances that have broad applications in QoS routing, optimal control, and mission planning, and develop polynomial algorithms towards them. The DCLC (Delay Constrained Least Cost) and MCOR (Multiple Constrained Optimal Routing) problems consider two or more additive metrics, and applies to flow-oriented routing with end-to-end QoS requirements. The ASWP (Ad-Hoc Shortest Widest Path) problem arises in bandwidth-guaranteed routing in wireless ad-hoc networks. The interference between neighboring links that share the medium and capacity is the critical issue here. The ASP (Anisotropic Shortest Path) problem seeks paths over continuous domains. We propose a novel method of searching for local optima, so that the global search can proceed over a simple, regular grid discretization.; These COP problems are hard because they violate the Bellman's Principle of Optimality. All the proposed algorithms take approximations and use heuristics so that they can search the path space efficiently and generate close-to-optimal solutions in polynomial time. We conduct numerical simulations to demonstrate the performance of these algorithms.