|
Abstract:
|
Network Routing problems focus on exploiting the network -based struc -
ture of a mathematical optimization problem to establish e cient solutions that are tailored to the problem at hand . The topic of this dissertation relates to a speci c class of network routing problems , those in which the properties
of the nodes and /or links in the network can be represented as instances of a particular network -state realization , where the set possible network -state can
be represented by a discrete probability distribution . The main contribution of this research is to formalize the de nition of such families of network -states ,
a construct we de ne as Stochastic -State Networks (SSN ) , and show that certain properties of such networks can allow for the systematic development of exact and heuristic solution procedures for a speciric class of network routing problems . The class of network problems considered are those in which dynamic routing decisions are seeked , and where information about the network can only be gathered through direct observation of the instantiation of the stochastic elements of the network . Two speci c instances of routing problems are considered : a dynamic instance of a Traveling Salesman Problem , and a routing problem in the presence of stochastic link failures . Exact methods and heuristics are developed by exploiting the underlaying stochastic -state
network formulation and numerical results are presented . |