Multiobjective Path Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments
Authors:
- 1 August 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 39 (3) , 383-399
Abstract
We describe a method for finding nondominated paths for multiple routing objectives in networks where the routing attributes are uncertain, and the probability distributions that describe those attributes vary by time of day. This problem is particularly important in routing and scheduling of shipments of very hazardous materials. Our method extends and integrates the work of several previous authors, resulting in a new algorithm that propagates means and variances of the uncertain attributes along paths and compares partial paths that arrive at a given node within a user-specified time window. The comparison uses an approximate stochastic dominance criterion. We illustrate the effects of changing primary parameters of the algorithm using a small test network, and we show how the nondominated solution set achieved is larger than the set that would be identified if the uncertainty in routing attributes were ignored. We then demonstrate how the algorithm creates an effective solution set in a case study using a large network.Keywords
This publication has 27 references indexed in Scilit:
- Catastrophe Avoidance Models for Hazardous Materials Route PlanningTransportation Science, 2000
- Iterative methods for dynamic stochastic shortest path problemsNaval Research Logistics (NRL), 1998
- Modeling of Transport Risk for Hazardous MaterialsOperations Research, 1998
- Expected shortest paths in dynamic and stochastic traffic networksTransportation Research Part B: Methodological, 1998
- Real-Time Multiple-Objective Path Search for In-Vehicle Route Guidance SystemsTransportation Research Record: Journal of the Transportation Research Board, 1997
- Hazardous Materials Logistics1995
- Multiobjective transportation network design and routing problems: Taxonomy and annotationEuropean Journal of Operational Research, 1993
- Dynamic network models and driver information systemsTransportation Research Part A: General, 1991
- Route guidance systems for improving urban travel and location choicesTransportation Research Part A: General, 1988
- On a routing problemQuarterly of Applied Mathematics, 1958