IDEAS home Printed from https://ideas.repec.org/p/pur/prukra/1167.html
   My bibliography  Save this paper

Investing in the Links of a Stochastic Network to Minimize Expected Shortest Path. Length

Author

Listed:
  • Viswanath, Kannan
  • Peeta, Srinivas
  • Salman, Sibel F.

Abstract

We consider a network whose links are subject to independent, random failures due to a disruptive event. The survival probability of a link is increased, if it is strengthened by investment. A given budget is to be allocated among the links with the objective of optimizing the post-event performances of the network. Specifically, we seek to minimize the expected shortest path Length between a specified origin node and destination node in the network. This criterion is defined through the use of a fixed penalty cost for those network realizations in the expectation, that do not have a path connecting the origin node to the destination node. This problem type arises in the pre-disasters, by upgrading its weakest elements. We model the problem as a two-stage stochastic program in which the underlying probability distribution of the random variables is dependent on the first stage decision variables. Using a path-based approach we construct its equivalent deterministic program and derive structural results for the objective function. We then propose an approximate solution procedure based on a first order approximation the objective function. The procedure is tested by numerical experiments on a small-size network. The test results show that it yields very good performance on the instances solved.

Suggested Citation

  • Viswanath, Kannan & Peeta, Srinivas & Salman, Sibel F., 2004. "Investing in the Links of a Stochastic Network to Minimize Expected Shortest Path. Length," Purdue University Economics Working Papers 1167, Purdue University, Department of Economics.
    • Handle: RePEc:pur:prukra:1167
    as

    Download full text from publisher

    File URL: https://business.purdue.edu/research/Working-papers-series/Year-2004/1167.pdf
    Download Restriction: no
    ---><---

    Citations

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


    Cited by:

    1. Miloš Kopa & Tomáš Rusý, 2021. "A decision-dependent randomness stochastic program for asset–liability management model with a pricing decision," Annals of Operations Research, Springer, vol. 299(1), pages 241-271, April.
    2. Yueyue Fan & Changzheng Liu, 2010. "Solving Stochastic Transportation Network Protection Problems Using the Progressive Hedging-based Method," Networks and Spatial Economics, Springer, vol. 10(2), pages 193-208, June.
    3. Bora Tarhan & Ignacio Grossmann & Vikas Goel, 2013. "Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution," Annals of Operations Research, Springer, vol. 203(1), pages 141-166, March.
    4. Stefano Starita & M. Paola Scaparra & Jesse R. O’Hanley, 2017. "A dynamic model for road protection against flooding," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 74-88, January.
    5. Lars Hellemo & Paul I. Barton & Asgeir Tomasgard, 2018. "Decision-dependent probabilities in stochastic programs with recourse," Computational Management Science, Springer, vol. 15(3), pages 369-395, October.
    6. Qingxia Kong & Shan Li & Nan Liu & Chung-Piaw Teo & Zhenzhen Yan, 2020. "Appointment Scheduling Under Time-Dependent Patient No-Show Behavior," Management Science, INFORMS, vol. 66(8), pages 3480-3500, August.
    7. Kopa, Miloš & Rusý, Tomáš, 2023. "Robustness of stochastic programs with endogenous randomness via contamination," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1259-1272.
    8. Solak, Senay & Clarke, John-Paul B. & Johnson, Ellis L. & Barnes, Earl R., 2010. "Optimization of R&D project portfolios under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 207(1), pages 420-433, 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:pur:prukra:1167. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Business PHD (email available below). General contact details of provider: https://edirc.repec.org/data/kspurus.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.