TY - JOUR

T1 - Optimal paths in probabilistic networks

T2 - A case with temporary preferences

AU - Mirchandani, Pitu B.

AU - Soroush, Hossein

N1 - Funding Information:
tThis work has been supported by UMTA (U.S.D.O.T.) Grant NY-06-0081 and NSF Grant ECS-If 17876. $Pitu B. Mirchandani is an Associate Professor of Electrical, Computer, and Systems Engineering, and the Chairman of the Operations Research and Statistics Program at Rensselaer Polytechnic Institute. WC holds the B.S. (Highest Honours) and MS. degrees in Engineering from the University of California at Los Angeles, the SM. degree in Aeronautics and Astronautice and Sc.D. degree in Operations Research from the Massachusetts institute of Technology. Professor Mirc~~n~s research interests include modeling and optimi~tion of networks and stochastic processes, and the applications of operations research and computers in trans~~ation, distri~tion, communication, and manufacturing. fHossein Soroush is an Assistant Professor of Management Science at the Michigan Technologioli University, Houghton. He holds the B.S. degree in Economic Management from the Karaj School of Mathematics and Economic Management. Iran, MS. degree in Operations Research from George Washington University, and the Ph.D. degree in Operations Research and Statistics from Rensselaer Polytechnic Institute. Professor Soroush’s interests are modeling and optimization of stochastic processesa nd applied operations research.

PY - 1985

Y1 - 1985

N2 - The classical shortest route problem in networks assumes deterministic arc weights and a utility (or cost) function that is linear over path weights for route evaluation. When the environment is stochastic and the "traveler's" utility function for travel attributes is nonlinear, we define "optimal paths" that maximize the expected utility. We review the concepts of temporary and permanent preferences for comparing a traveler's preference for available subpaths. It has been shown before that when the utility function is linear or exponential, permanent preferences prevail and an efficient Dijkstra-type algorithm [3] is available that determines the optimal path. In this paper an exact procedure is developed for determining an optimal path when the utility function is quadratic-a case where permanent preferences do not always prevail. The algorithm uses subpath comparison rules to establish permanent preferences, when possible, among subpaths of the given network. Although in the worst case the algorithm implicitly enumerates all paths (the number of operations increasing exponentially with the size of the network), we find, from the computational experience reported, that the number of potentially optimal paths to evaluate is generally manageable.

AB - The classical shortest route problem in networks assumes deterministic arc weights and a utility (or cost) function that is linear over path weights for route evaluation. When the environment is stochastic and the "traveler's" utility function for travel attributes is nonlinear, we define "optimal paths" that maximize the expected utility. We review the concepts of temporary and permanent preferences for comparing a traveler's preference for available subpaths. It has been shown before that when the utility function is linear or exponential, permanent preferences prevail and an efficient Dijkstra-type algorithm [3] is available that determines the optimal path. In this paper an exact procedure is developed for determining an optimal path when the utility function is quadratic-a case where permanent preferences do not always prevail. The algorithm uses subpath comparison rules to establish permanent preferences, when possible, among subpaths of the given network. Although in the worst case the algorithm implicitly enumerates all paths (the number of operations increasing exponentially with the size of the network), we find, from the computational experience reported, that the number of potentially optimal paths to evaluate is generally manageable.

UR - http://www.scopus.com/inward/record.url?scp=0021855448&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021855448&partnerID=8YFLogxK

U2 - 10.1016/0305-0548(85)90034-6

DO - 10.1016/0305-0548(85)90034-6

M3 - Article

AN - SCOPUS:0021855448

SN - 0305-0548

VL - 12

SP - 365

EP - 381

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 4

ER -