IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v12y2012i4p561-587.html
   My bibliography  Save this article

Optimal Path Problems with Second-Order Stochastic Dominance Constraints

Author

Listed:
  • Yu Nie
  • Xing Wu
  • Tito Homem-de-Mello

Abstract

This paper studies optimal path problems integrated with the concept of second order stochastic dominance. These problems arise from applications where travelers are concerned with the trade off between the risks associated with random travel time and other travel costs. Risk-averse behavior is embedded by requiring the random travel times on the optimal paths to stochastically dominate that on a benchmark path in the second order. A general linear operating cost is introduced to combine link- and path-based costs. The latter, which is the focus of the paper, is employed to address schedule costs pertinent to late and early arrival. An equivalent integer program to the problem is constructed by transforming the stochastic dominance constraint into a finite number of linear constraints. The problem is solved using both off-the-shelf solvers and specialized algorithms based on dynamic programming (DP). Although neither approach ensures satisfactory performance for general large-scale problems, the numerical experiments indicate that the DP-based approach provides a computationally feasible option to solve medium-size instances (networks with several thousand links) when correlations among random link travel times can be ignored. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • Yu Nie & Xing Wu & Tito Homem-de-Mello, 2012. "Optimal Path Problems with Second-Order Stochastic Dominance Constraints," Networks and Spatial Economics, Springer, vol. 12(4), pages 561-587, December.
  • Handle: RePEc:kap:netspa:v:12:y:2012:i:4:p:561-587
    DOI: 10.1007/s11067-011-9167-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-011-9167-6
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s11067-011-9167-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
    2. Whitmore, G A, 1970. "Third-Degree Stochastic Dominance," American Economic Review, American Economic Association, vol. 60(3), pages 457-459, June.
    3. Carraway, Robert L. & Morin, Thomas L. & Moskowitz, Herbert, 1990. "Generalized dynamic programming for multicriteria optimization," European Journal of Operational Research, Elsevier, vol. 44(1), pages 95-104, January.
    4. Current, J. R. & Re Velle, C. S. & Cohon, J. L., 1985. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation," European Journal of Operational Research, Elsevier, vol. 21(2), pages 189-199, August.
    5. Hadar, Josef & Russell, William R., 1971. "Stochastic dominance and diversification," Journal of Economic Theory, Elsevier, vol. 3(3), pages 288-305, September.
    6. G. Hanoch & H. Levy, 1969. "The Efficiency Analysis of Choices Involving Risk," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 36(3), pages 335-346.
    7. Raj A. Sivakumar & Rajan Batta, 1994. "The Variance-Constrained Shortest Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 309-316, November.
    8. Paul A. Samuelson, 1970. "The Fundamental Approximation Theorem of Portfolio Analysis in terms of Means, Variances and Higher Moments," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 37(4), pages 537-542.
    9. Miller-Hooks, Elise & Mahmassani, Hani, 2003. "Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks," European Journal of Operational Research, Elsevier, vol. 146(1), pages 67-82, April.
    10. Naoki Ando & Eiichi Taniguchi, 2006. "Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows," Networks and Spatial Economics, Springer, vol. 6(3), pages 293-311, September.
    11. Suvrajeet Sen & Rekha Pillai & Shirish Joshi & Ajay K. Rathi, 2001. "A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems," Transportation Science, INFORMS, vol. 35(1), pages 37-49, February.
    12. Elise D. Miller-Hooks & Hani S. Mahmassani, 2000. "Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks," Transportation Science, INFORMS, vol. 34(2), pages 198-215, May.
    13. Harry Markowitz, 1952. "Portfolio Selection," Journal of Finance, American Finance Association, vol. 7(1), pages 77-91, March.
    14. Michael Masin & Yossi Bukchin, 2008. "Diversity Maximization Approach for Multiobjective Optimization," Operations Research, INFORMS, vol. 56(2), pages 411-424, April.
    15. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    16. Haim Levy, 1992. "Stochastic Dominance and Expected Utility: Survey and Analysis," Management Science, INFORMS, vol. 38(4), pages 555-593, April.
    17. Michael Bell, 2006. "Mixed Route Strategies for the Risk-Averse Shipment of Hazardous Materials," Networks and Spatial Economics, Springer, vol. 6(3), pages 253-265, September.
    18. Vickrey, William S, 1969. "Congestion Theory and Transport Investment," American Economic Review, American Economic Association, vol. 59(2), pages 251-260, May.
    19. H. Frank, 1969. "Shortest Paths in Probabilistic Graphs," Operations Research, INFORMS, vol. 17(4), pages 583-599, August.
    20. Bell, Michael G. H. & Cassir, Chris, 2002. "Risk-averse user equilibrium traffic assignment: an application of game theory," Transportation Research Part B: Methodological, Elsevier, vol. 36(8), pages 671-681, September.
    21. Rothschild, Michael & Stiglitz, Joseph E., 1970. "Increasing risk: I. A definition," Journal of Economic Theory, Elsevier, vol. 2(3), pages 225-243, September.
    22. Amir Eiger & Pitu B. Mirchandani & Hossein Soroush, 1985. "Path Preferences and Optimal Paths in Probabilistic Networks," Transportation Science, INFORMS, vol. 19(1), pages 75-84, February.
    23. Milton Friedman & L. J. Savage, 1948. "The Utility Analysis of Choices Involving Risk," Journal of Political Economy, University of Chicago Press, vol. 56(4), pages 279-279.
    24. Ishwar Murthy & Sumit Sarkar, 1996. "A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems," Transportation Science, INFORMS, vol. 30(3), pages 220-236, August.
    25. Yueyue Fan & Yu Nie, 2006. "Optimal Routing for Maximizing the Travel Time Reliability," Networks and Spatial Economics, Springer, vol. 6(3), pages 333-344, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zweers, Bernard G. & van der Mei, Rob D., 2022. "Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings," European Journal of Operational Research, Elsevier, vol. 300(1), pages 178-188.
    2. Malavasi, Matteo & Ortobelli Lozza, Sergio & Trück, Stefan, 2021. "Second order of stochastic dominance efficiency vs mean variance efficiency," European Journal of Operational Research, Elsevier, vol. 290(3), pages 1192-1206.
    3. Jin‐Zhu Yu & Hiba Baroud, 2019. "Quantifying Community Resilience Using Hierarchical Bayesian Kernel Methods: A Case Study on Recovery from Power Outages," Risk Analysis, John Wiley & Sons, vol. 39(9), pages 1930-1948, September.
    4. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    5. A. Arun Prakash & Karthik K. Srinivasan, 2017. "Finding the Most Reliable Strategy on Stochastic and Time-Dependent Transportation Networks: A Hypergraph Based Formulation," Networks and Spatial Economics, Springer, vol. 17(3), pages 809-840, September.
    6. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    7. Redmond, Michael & Campbell, Ann Melissa & Ehmke, Jan Fabian, 2022. "Reliability in public transit networks considering backup itineraries," European Journal of Operational Research, Elsevier, vol. 300(3), pages 852-864.
    8. Roberto Cominetti & Alfredo Torrico, 2016. "Additive Consistency of Risk Measures and Its Application to Risk-Averse Routing in Networks," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1510-1521, November.
    9. Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
    10. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    11. Nilay Noyan & Gábor Rudolf, 2013. "Optimization with Multivariate Conditional Value-at-Risk Constraints," Operations Research, INFORMS, vol. 61(4), pages 990-1013, August.
    12. William B. Haskell & Alejandro Toriello, 2018. "Modeling Stochastic Dominance as Infinite-Dimensional Constraint Systems via the Strassen Theorem," Journal of Optimization Theory and Applications, Springer, vol. 178(3), pages 726-742, September.
    13. ManWo Ng & Hong Lo, 2013. "Regional Air Quality Conformity in Transportation Networks with Stochastic Dependencies: A Theoretical Copula-Based Model," Networks and Spatial Economics, Springer, vol. 13(4), pages 373-397, December.
    14. Amita Sharma & Aparna Mehra, 2017. "Financial analysis based sectoral portfolio optimization under second order stochastic dominance," Annals of Operations Research, Springer, vol. 256(1), pages 171-197, September.
    15. Chen, Peng & Nie, Yu (Marco), 2013. "Bicriterion shortest path problem with a general nonadditive cost," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 419-435.
    16. Zhiwei Chen & Yucong Hu & Jutint Li & Xing Wu, 2020. "Optimal Deployment of Electric Bicycle Sharing Stations: Model Formulation and Solution Technique," Networks and Spatial Economics, Springer, vol. 20(1), pages 99-136, March.
    17. William Haskell & J. Shanthikumar & Z. Shen, 2013. "Optimization with a class of multivariate integral stochastic order constraints," Annals of Operations Research, Springer, vol. 206(1), pages 147-162, July.
    18. Xiangfeng Ji & Xuegang (Jeff) Ban & Mengtian Li & Jian Zhang & Bin Ran, 2017. "Non-expected Route Choice Model under Risk on Stochastic Traffic Networks," Networks and Spatial Economics, Springer, vol. 17(3), pages 777-807, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
    2. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    3. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    4. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    5. Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
    6. Leilei Zhang & Tito Homem-de-Mello, 2017. "An Optimal Path Model for the Risk-Averse Traveler," Transportation Science, INFORMS, vol. 51(2), pages 518-535, May.
    7. Wong, Wing-Keung, 2007. "Stochastic dominance and mean-variance measures of profit and loss for business planning and investment," European Journal of Operational Research, Elsevier, vol. 182(2), pages 829-843, October.
    8. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    9. Tan, Zhijia & Yang, Hai & Guo, Renyong, 2014. "Pareto efficiency of reliability-based traffic equilibria and risk-taking behavior of travelers," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 16-31.
    10. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    11. Raymond H. Chan & Ephraim Clark & Xu Guo & Wing-Keung Wong, 2020. "New development on the third-order stochastic dominance for risk-averse and risk-seeking investors with application in risk management," Risk Management, Palgrave Macmillan, vol. 22(2), pages 108-132, June.
    12. Moshe Levy & Haim Levy, 2013. "Prospect Theory: Much Ado About Nothing?," World Scientific Book Chapters, in: Leonard C MacLean & William T Ziemba (ed.), HANDBOOK OF THE FUNDAMENTALS OF FINANCIAL DECISION MAKING Part I, chapter 7, pages 129-144, World Scientific Publishing Co. Pte. Ltd..
    13. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    14. Fong, Wai Mun & Lean, Hooi Hooi & Wong, Wing Keung, 2008. "Stochastic dominance and behavior towards risk: The market for Internet stocks," Journal of Economic Behavior & Organization, Elsevier, vol. 68(1), pages 194-208, October.
    15. Nowak, Maciej, 2004. "Preference and veto thresholds in multicriteria analysis based on stochastic dominance," European Journal of Operational Research, Elsevier, vol. 158(2), pages 339-350, October.
    16. W. Wong & R. Chan, 2008. "Prospect and Markowitz stochastic dominance," Annals of Finance, Springer, vol. 4(1), pages 105-129, January.
    17. Bi Chen & William Lam & Agachai Sumalee & Qingquan Li & Hu Shao & Zhixiang Fang, 2013. "Finding Reliable Shortest Paths in Road Networks Under Uncertainty," Networks and Spatial Economics, Springer, vol. 13(2), pages 123-148, June.
    18. Yudhvir Seetharam, 2013. "Do Mutual Funds Attract the Right Investor? A Stochastic Dominance Approach," Journal of Economics and Behavioral Studies, AMH International, vol. 5(12), pages 905-914.
    19. Chan, Raymond H. & Clark, Ephraim & Wong, Wing-Keung, 2016. "On the Third Order Stochastic Dominance for Risk-Averse and Risk-Seeking Investors with Analysis of their Traditional and Internet Stocks," MPRA Paper 75002, University Library of Munich, Germany.
    20. Levy, Haim & Levy, Moshe, 2002. "Experimental test of the prospect theory value function: A stochastic dominance approach," Organizational Behavior and Human Decision Processes, Elsevier, vol. 89(2), pages 1058-1081, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:kap:netspa:v:12:y:2012:i:4:p:561-587. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.