Open-Loop Solutions for the Dynamic Routing Problem

摘要

This work deals with the problem of obtaining an open-loop solution to the minimum delay dynamic routing problem. The dynamic routing problem is stated using a dynamic model suggested in previous works. This work uses some previously known properties of the optimal solution and formulates the routing problem as a cubic optimization problem. In general such problems are very hard to solve; however, the specific problem at hand is finally formulated as a nonconvex quadratic program by using its special structure. Two different approaches, based on the latter representation of the problem, are proposed: (a) Utilization of existing methods for solving nonconvex quadratic programs, (b) development of a special purpose algorithm. The algorithm is developed for single destination networks with unity weightings in the cost functional, and it finds the optimal solution by solving a series of linear programs. The algorithm is based on a series of specially developed theorems. These theorems provide use with new insight into the behaviour of the dynamic routing in networks. The method is implemented by a computer program and several examples are run to test its applicability. (Author)