An optimal control approach to dynamic routing in networks

Abstract

This paper explores the application of optimal control theory to the problem of dynamic routing in networks. The approach derives from a continuous state space model for dynamic routing and an associated linear optimal control problem with linear state and control variable inequality constraints. The conceptual form of an algorithm is presented for finding a feedback solution to the optimal control problem when the inputs are assumed to be constant in time. The algorithm employs a combination of necessary conditions, dynamic programming, and linear programming to construct a set of convex polyhedral cones which cover the admissible state space with optimal controls. An implementable form of the algorithm, along with a simple example, is presented for a special class of single destination networks.