Abstract
This research is grounded in the view that organizations are information processing systems. Organizations design their structure, processes, and information technologies for the purpose of processing, exchanging, and distributing the information required for their functions. The volume of information exchanged is not always the same. Thus in order to provide an efficient process of communication we propose an algorithm which determines the path that minimizes the expected value of an utility function over a dynamic probabilistic network with discrete or continuous real random variables (parameters) associated to each emerging arc. To obtain the optimal dynamic path from a source to sink node in the discrete case, we use a generalization of Bellman first-in-first-out labeling correcting algorithm used to determine the shortest path in directed networks with deterministic parameters associated to each arc. In the case where arc parameters are continuous random variables we propose algorithms involving multi-objective optimization. Additionally, some initialization techniques that improve the running times without jeopardizing memory are also considered. The topology of the networks is not known in advance, which means that we only have knowledge of the incoming (outgoing) arcs, and their parameters, of some specific node once we reach it. Thus the optimal path is determined in a dynamic way. We also present computational results for networks with 100 up to 10,000 nodes and densities 2, 5, and 10.
Key Terms in this Chapter
Utility Function: A function that measures the utility of each problem solution (or parts of it).
Dominance Relation: Let (N, A) be a network. Consider and, let p and q be two paths of Tij (tree of the paths from i to j in (N, A)). The dominance relation in , denoted by “”, is defined in the following form with at least one restrict inequality. In such case, we will say that pdominatesq or qis dominated by p. Note that we only can relate paths which have the same initial and terminal nodes.
Stochastic Optimal Path: A path that optimizes the expected value of an utility function over a dynamic probabilistic network with discrete or continuous real random variables (parameters) associated to each emerging arc.
Deterministic Shortest Path Problem: A path that optimizes the value of an utility function over network with deterministic parameters associated to each emerging arc.
Forward Star of Node i: The set formed by the terminal nodes of its outgoing arcs.
Strong Optimality Principle: Let i and j be two nodes of N. (P) verifies the strong optimality principle if any non dominated path (that is, optimal path) from i to j in (N, A) is formed by non dominated sub-paths.
Probabilistic Network: A network where to each arc is associated discrete or continuous real random variables.