A Heuristic Search Approach for a Nonstationary Stochastic Shortest Path Problem with Terminal Cost

James L. Bander and Chelsea C. White
Additional contact information
James L. Bander: Industrial Engineering and Operations Research, Norfolk Southern Corporation, 600 West Peachtree Street NW, Suite 900, Atlanta, Georgia 30308
Chelsea C. White: Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Transportation Science, 2002, vol. 36, issue 2, 218-230

Abstract: We present a best-first heuristic search approach for determining an optimal policy for a stochastic shortest path problem. A vehicle is to travel from an origin, starting at time t 0 , to a destination, where once the destination is reached a terminal cost is accrued. The terminal cost depends on the time of arrival. Travel time along each arc in the network is modeled as a random variable with a distribution dependent on the time that travel along the arc is begun. The objective is to determine a routing policy that minimizes expected total cost. A routing policy is a rule that assigns the next arc to traverse, given the current node and time.The heuristic search algorithm that we specialize to this stochastic problem is AO * . We demonstrate the significant computational advantages of AO * , relative to dynamic programming, on the basis of run time and storage, using a 131-intersection network of the major roads in Cleveland, Ohio. Further computational experience is based on grid networks that were randomly generated to have characteristics similar to transportation networks, and on randomly generated unstructured networks.

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.36.2.218.562 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:36:y:2002:i:2:p:218-230

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().