An Optimal Path Model for the Risk-Averse Traveler

Leilei Zhang () and Tito Homem- de-Mello ()
Additional contact information
Leilei Zhang: Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011
Tito Homem- de-Mello: School of Business, Universidad Adolfo Ibáñez, 7820436 Santiago, Chile

Transportation Science, 2017, vol. 51, issue 2, 518-535

Abstract: In this paper we discuss stochastic optimal path problems where the goal is to find a path that has minimal expected cost and at the same time is less risky (in terms of travel time) than a given benchmark path. The model is suitable for a risk-averse traveler who prefers a path with a more guaranteed travel time to another path that could be faster but could also be slower. Such risk attitude is incorporated using the concept of second order stochastic dominance constraints. A recently developed theory for optimization problems with stochastic dominance constraints ensures that the resulting problem can be written as a large linear integer program with binary variables; for networks of realistic size, however, such a direct approach is not practical because of the size of the resulting optimization problem. Moreover, the solution returned by the model may contain cycles, which is clearly undesirable from a practical perspective. A number of strategies are explored to solve the problem. First, we prove that cycles can be prevented by a simple modification of the model if the arc travel times are mutually independent. We then propose a sample average approximation approach to the problem using samples from the distribution of travel times. Because of the randomness resulting from sampling, it is important that statistical guarantees for the solution returned by the algorithm be given, and we provide heuristic procedures to deal with stochastic constraints. We also incorporate a branch-and-cut approach that exploits the structure of the problem to deal with the integrality constraints more efficiently. We present some numerical experiments for a 1,522-arc system that corresponds to a large portion of the Chicago area network. The results show that our approach can solve the problem very effectively, producing solutions with statistical guarantees of optimality within a reasonable computational time.

Keywords: optimal path problem; stochastic dominance; sample average approximation; branch-and-cut (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0685 (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:51:y:2017:i:2:p:518-535

Access Statistics for this article

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