IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v39y2005i3p383-399.html
   My bibliography  Save this article

Multiobjective Path Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments

Author

Listed:
  • Tsung-Sheng Chang

    (Institute of Global Operations Strategy and Logistics Management, National Dong Hwa University, Hualien, Taiwan)

  • Linda K. Nozick

    (School of Civil and Environmental Engineering, Cornell University, Hollister Hall, Ithaca, New York 14853)

  • Mark A. Turnquist

    (School of Civil and Environmental Engineering, Cornell University, Hollister Hall, Ithaca, New York 14853)

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.

Suggested Citation

  • Tsung-Sheng Chang & Linda K. Nozick & Mark A. Turnquist, 2005. "Multiobjective Path Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments," Transportation Science, INFORMS, vol. 39(3), pages 383-399, August.
    • Handle: RePEc:inm:ortrsc:v:39:y:2005:i:3:p:383-399
    DOI: 10.1287/trsc.1040.0094
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1040.0094
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1040.0094?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
    ---><---

    References listed on IDEAS

    as
    1. Wijeratne, Ajith B. & Turnquist, Mark A. & Mirchandani, Pitu B., 1993. "Multiobjective routing of hazardous materials in stochastic networks," European Journal of Operational Research, Elsevier, vol. 65(1), pages 33-43, February.
    2. Randolph W. Hall, 1986. "The Fastest Path through a Network with Random Time-Dependent Travel Times," Transportation Science, INFORMS, vol. 20(3), pages 182-188, August.
    3. 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.
    4. Fu, Liping & Rilett, L. R., 1998. "Expected shortest paths in dynamic and stochastic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(7), pages 499-516, September.
    5. Erhan Erkut & Armann Ingolfsson, 2000. "Catastrophe Avoidance Models for Hazardous Materials Route Planning," Transportation Science, INFORMS, vol. 34(2), pages 165-179, May.
    6. Pretolani, Daniele, 2000. "A directed hypergraph model for random time dependent shortest paths," European Journal of Operational Research, Elsevier, vol. 123(2), pages 315-324, June.
    7. Hadar, Josef & Russell, William R, 1969. "Rules for Ordering Uncertain Prospects," American Economic Review, American Economic Association, vol. 59(1), pages 25-34, March.
    8. Current, John & Marsh, Michael, 1993. "Multiobjective transportation network design and routing problems: Taxonomy and annotation," European Journal of Operational Research, Elsevier, vol. 65(1), pages 4-19, February.
    9. Linda K. Nozick & George F. List & Mark A. Turnquist, 1997. "Integrated Routing and Scheduling in Hazardous Materials Transportation," Transportation Science, INFORMS, vol. 31(3), pages 200-215, August.
    10. Erhan Erkut & Vedat Verter, 1998. "Modeling of Transport Risk for Hazardous Materials," Operations Research, INFORMS, vol. 46(5), pages 625-642, October.
    11. 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.
    12. Raymond K. Cheung, 1998. "Iterative methods for dynamic stochastic shortest path problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(8), pages 769-789, December.
    13. George F. List & Pitu B. Mirchandani & Mark A. Turnquist & Konstantinos G. Zografos, 1991. "Modeling and Analysis for Hazardous Materials Transportation: Risk Analysis, Routing/Scheduling and Facility Location," Transportation Science, INFORMS, vol. 25(2), pages 100-114, May.
    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. Mohri, Seyed Sina & Asgari, Nasrin & Zanjirani Farahani, Reza & Bourlakis, Michael & Laker, Benjamin, 2020. "Fairness in hazmat routing-scheduling: A bi-objective Stackelberg game," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    2. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    3. Mohri, Seyed Sina & Mohammadi, Mehrdad & Gendreau, Michel & Pirayesh, Amir & Ghasemaghaei, Ali & Salehi, Vahid, 2022. "Hazardous material transportation problems: A comprehensive overview of models and solution approaches," European Journal of Operational Research, Elsevier, vol. 302(1), pages 1-38.
    4. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    5. Yang, Xuejing & Low, Joyce M.W. & Tang, Loon Ching, 2011. "Analysis of intermodal freight from China to Indian Ocean: A goal programming approach," Journal of Transport Geography, Elsevier, vol. 19(4), pages 515-527.
    6. Reilly, Allison & Nozick, Linda & Xu, Ningxiong & Jones, Dean, 2012. "Game theory-based identification of facility use restrictions for the movement of hazardous materials under terrorist threat," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 115-131.
    7. Nielsen, Lars Relund & Andersen, Kim Allan & Pretolani, Daniele, 2006. "Bicriterion a priori route choice in stochastic time-dependent networks," CORAL Working Papers L-2006-10, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    8. Zhang, Lukai & Feng, Xuesong & Chen, Dalin & Zhu, Nan & Liu, Yi, 2019. "Designing a hazardous materials transportation network by a bi-level programming based on toll policies," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    9. Shi, Ning & Zhou, Shaorui & Wang, Fan & Tao, Yi & Liu, Liming, 2017. "The multi-criteria constrained shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 13-29.
    10. 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.
    11. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    12. Nielsen, Lars Relund & Andersen, Kim Allan & Pretolani, Daniele, 2014. "Ranking paths in stochastic time-dependent networks," European Journal of Operational Research, Elsevier, vol. 236(3), pages 903-914.
    13. Prakash, A. Arun, 2018. "Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 127-147.
    14. Rahman, Ashrafur & Fiondella, Lance & Lownes, Nicholas E., 2014. "A Bi-Objective Approach to Evaluate Highway Routing and Regulatory Strategies for Hazardous Materials Transportation," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 53(1).
    15. Chen, Bi Yu & Li, Qingquan & Lam, William H.K., 2016. "Finding the k reliable shortest paths under travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 189-203.
    16. Wen, Liang & Çatay, Bülent & Eglese, Richard, 2014. "Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge," European Journal of Operational Research, Elsevier, vol. 236(3), pages 915-923.
    17. Szeto, W.Y. & Farahani, R.Z. & Sumalee, Agachai, 2017. "Link-based multi-class hazmat routing-scheduling problem: A multiple demon approach," European Journal of Operational Research, Elsevier, vol. 261(1), pages 337-354.
    18. Mohammadi, Mehrdad & Jula, Payman & Tavakkoli-Moghaddam, Reza, 2017. "Design of a reliable multi-modal multi-commodity model for hazardous materials transportation under uncertainty," European Journal of Operational Research, Elsevier, vol. 257(3), pages 792-809.
    19. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    20. Dadkar, Yashoda & Nozick, Linda & Jones, Dean, 2010. "Optimizing facility use restrictions for the movement of hazardous materials," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 267-281, February.
    21. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    22. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    23. Chang, Tsung-Sheng & Wan, Yat-wah & OOI, Wei Tsang, 2009. "A stochastic dynamic traveling salesman problem with hard time windows," European Journal of Operational Research, Elsevier, vol. 198(3), pages 748-759, November.

    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. Opasanon, Sathaporn & Miller-Hooks, Elise, 2006. "Multicriteria adaptive paths in stochastic, time-varying networks," European Journal of Operational Research, Elsevier, vol. 173(1), pages 72-91, August.
    2. Dell'Olmo, Paolo & Gentili, Monica & Scozzari, Andrea, 2005. "On finding dissimilar Pareto-optimal paths," European Journal of Operational Research, Elsevier, vol. 162(1), pages 70-82, April.
    3. Mohri, Seyed Sina & Mohammadi, Mehrdad & Gendreau, Michel & Pirayesh, Amir & Ghasemaghaei, Ali & Salehi, Vahid, 2022. "Hazardous material transportation problems: A comprehensive overview of models and solution approaches," European Journal of Operational Research, Elsevier, vol. 302(1), pages 1-38.
    4. 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.
    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. Levering, Nikki & Boon, Marko & Mandjes, Michel & Núñez-Queija, Rudesindo, 2022. "A framework for efficient dynamic routing under stochastically varying conditions," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 97-124.
    7. 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.
    8. Prakash, A. Arun, 2018. "Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 127-147.
    9. Wen, Liang & Çatay, Bülent & Eglese, Richard, 2014. "Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge," European Journal of Operational Research, Elsevier, vol. 236(3), pages 915-923.
    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. Gao, Song & Chabini, Ismail, 2006. "Optimal routing policy problems in stochastic time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 40(2), pages 93-122, February.
    12. Nielsen, Lars Relund & Andersen, Kim Allan & Pretolani, Daniele, 2014. "Ranking paths in stochastic time-dependent networks," European Journal of Operational Research, Elsevier, vol. 236(3), pages 903-914.
    13. Yang, Lixing & Zhou, Xuesong, 2014. "Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 22-44.
    14. Yang, Baiyu & Miller-Hooks, Elise, 2004. "Adaptive routing considering delays due to signal operations," Transportation Research Part B: Methodological, Elsevier, vol. 38(5), pages 385-413, June.
    15. Dadkar, Yashoda & Nozick, Linda & Jones, Dean, 2010. "Optimizing facility use restrictions for the movement of hazardous materials," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 267-281, February.
    16. Reilly, Allison & Nozick, Linda & Xu, Ningxiong & Jones, Dean, 2012. "Game theory-based identification of facility use restrictions for the movement of hazardous materials under terrorist threat," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 115-131.
    17. Yang, Xuejing & Low, Joyce M.W. & Tang, Loon Ching, 2011. "Analysis of intermodal freight from China to Indian Ocean: A goal programming approach," Journal of Transport Geography, Elsevier, vol. 19(4), pages 515-527.
    18. Yang, Lixing & Zhang, Yan & Li, Shukai & Gao, Yuan, 2016. "A two-stage stochastic optimization model for the transfer activity choice in metro networks," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 271-297.
    19. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    20. Nielsen, Lars Relund & Pretolani, Daniele & Andersen, Kim Allan, 2004. "K shortest paths in stochastic time-dependent networks," CORAL Working Papers L-2004-05, University of Aarhus, Aarhus School of Business, Department of Business Studies.

    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:inm:ortrsc:v:39:y:2005:i:3:p:383-399. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.