IDEAS home Printed from https://ideas.repec.org/a/taf/uiiexx/v50y2018i11p989-996.html
   My bibliography  Save this article

Optimal multiunit transfer over adversarial paths with increasing intercept probabilities

Author

Listed:
  • Christopher Garcia

Abstract

We consider a problem involving transporting a set of items over a set of hostile paths where an adversary seeks to intercept them, with the goal of maximizing the probability that all items successfully cross. Items leave a unique footprint as they cross a path, and the probability that an item is intercepted on a given path increases according to an intercept probability function as the cumulative footprint on that path increases. We provide a problem formulation and demonstrate several properties important for its solution. We then use these to develop four optimization algorithms: an exact algorithm (E), a greedy heuristic (G), a greedy heuristic with local search (LS), and a genetic algorithm (GA). These algorithms were evaluated via computational experiments on a large set of benchmark problems spanning different sizes and characteristics. LS provided the largest number of best solutions while outperforming GA in terms of solution time.

Suggested Citation

  • Christopher Garcia, 2018. "Optimal multiunit transfer over adversarial paths with increasing intercept probabilities," IISE Transactions, Taylor & Francis Journals, vol. 50(11), pages 989-996, November.
    • Handle: RePEc:taf:uiiexx:v:50:y:2018:i:11:p:989-996
    DOI: 10.1080/24725854.2018.1488306
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/24725854.2018.1488306
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/24725854.2018.1488306?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. Hausken, Kjell, 2008. "Strategic defense and attack for series and parallel reliability systems," European Journal of Operational Research, Elsevier, vol. 186(2), pages 856-881, April.
    2. Peter J. Kolesar, 1967. "Linear programming and the reliability of multicomponent systems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(3), pages 317-327.
    3. Cai, Zhiqiang & Si, Shubin & Sun, Shudong & Li, Caitao, 2016. "Optimization of linear consecutive-k-out-of-n system with a Birnbaum importance-based genetic algorithm," Reliability Engineering and System Safety, Elsevier, vol. 152(C), pages 248-258.
    4. Alikar, Najmeh & Mousavi, Seyed Mohsen & Raja Ghazilla, Raja Ariffin & Tavana, Madjid & Olugu, Ezutah Udoncy, 2017. "Application of the NSGA-II algorithm to a multi-period inventory-redundancy allocation problem in a series-parallel system," Reliability Engineering and System Safety, Elsevier, vol. 160(C), pages 1-10.
    5. Richard Bellman & Stuart Dreyfus, 1958. "Dynamic Programming and the Reliability of Multicomponent Devices," Operations Research, INFORMS, vol. 6(2), pages 200-206, April.
    6. Levitin, Gregory & Xing, Liudong & Dai, Yuanshun, 2013. "Cold-standby sequencing optimization considering mission cost," Reliability Engineering and System Safety, Elsevier, vol. 118(C), pages 28-34.
    7. F. A. Tillman & J. M. Liittschwager, 1967. "Integer Programming Formulation of Constrained Reliability Problems," Management Science, INFORMS, vol. 13(11), pages 887-899, July.
    8. Koichi Mizukami, 1968. "Optimum Redundancy for Maximum System Reliability by the Method of Convex and Integer Programming," Operations Research, INFORMS, vol. 16(2), pages 392-406, April.
    9. Hausken, Kjell, 2008. "Strategic defense and attack for reliability systems," Reliability Engineering and System Safety, Elsevier, vol. 93(11), pages 1740-1750.
    10. Fang, Yiping & Sansavini, Giovanni, 2017. "Optimizing power system investments and resilience against attacks," Reliability Engineering and System Safety, Elsevier, vol. 159(C), pages 161-173.
    11. John D. Kettelle, 1962. "Least-Cost Allocations of Reliability Investment," Operations Research, INFORMS, vol. 10(2), pages 249-265, April.
    12. Hausken, Kjell, 2010. "Defense and attack of complex and dependent systems," Reliability Engineering and System Safety, Elsevier, vol. 95(1), pages 29-42.
    13. Mo, Huadong & Xie, Min & Levitin, Gregory, 2015. "Optimal resource distribution between protection and redundancy considering the time and uncertainties of attacks," European Journal of Operational Research, Elsevier, vol. 243(1), pages 200-210.
    14. Peng, R. & Levitin, G. & Xie, M. & Ng, S.H., 2010. "Defending simple series and parallel systems with imperfect false targets," Reliability Engineering and System Safety, Elsevier, vol. 95(6), pages 679-688.
    Full references (including those not matched with items on IDEAS)

    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. Dan Kovenock & Brian Roberson, 2012. "Strategic Defense And Attack For Series And Parallel Reliability Systems: Comment," Defence and Peace Economics, Taylor & Francis Journals, vol. 23(5), pages 507-515, October.
    2. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    3. Gao, Kaiye & Yan, Xiangbin & Liu, Xiang-dong & Peng, Rui, 2019. "Object defence of a single object with preventive strike of random effect," Reliability Engineering and System Safety, Elsevier, vol. 186(C), pages 209-219.
    4. Mo, Huadong & Xie, Min & Levitin, Gregory, 2015. "Optimal resource distribution between protection and redundancy considering the time and uncertainties of attacks," European Journal of Operational Research, Elsevier, vol. 243(1), pages 200-210.
    5. Szidarovszky, Ferenc & Luo, Yi, 2014. "Incorporating risk seeking attitude into defense strategy," Reliability Engineering and System Safety, Elsevier, vol. 123(C), pages 104-109.
    6. Gallice, Andrea, 2017. "An approximate solution to rent-seeking contests with private information," European Journal of Operational Research, Elsevier, vol. 256(2), pages 673-684.
    7. Song, Cen & Zhuang, Jun, 2017. "N-stage security screening strategies in the face of strategic applicants," Reliability Engineering and System Safety, Elsevier, vol. 165(C), pages 292-301.
    8. Sushil Gupta & Martin K. Starr & Reza Zanjirani Farahani & Mahsa Mahboob Ghodsi, 2020. "Prevention of Terrorism–An Assessment of Prior POM Work and Future Potentials," Production and Operations Management, Production and Operations Management Society, vol. 29(7), pages 1789-1815, July.
    9. Hausken, Kjell, 2010. "Strategic Defense and Attack for Series and Parallel Reliability Systems: Reply on Comment," MPRA Paper 25497, University Library of Munich, Germany, revised 02 Oct 2010.
    10. Shan, Xiaojun & Zhuang, Jun, 2018. "Modeling cumulative defensive resource allocation against a strategic attacker in a multi-period multi-target sequential game," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 12-26.
    11. Ye, Zhi-Sheng & Peng, Rui & Wang, Wenbin, 2017. "Defense and attack of performance-sharing common bus systemsAuthor-Name: Zhai, Qingqing," European Journal of Operational Research, Elsevier, vol. 256(3), pages 962-975.
    12. Kjell Hausken, 2012. "Strategic defense and attack for series and parallel reliability systems: reply 1 to comment 1," Defence and Peace Economics, Taylor & Francis Journals, vol. 23(5), pages 525-531, October.
    13. Zhang, Jing & Zhuang, Jun & Jose, Victor Richmond R., 2018. "The role of risk preferences in a multi-target defender-attacker resource allocation game," Reliability Engineering and System Safety, Elsevier, vol. 169(C), pages 95-104.
    14. Hausken, Kjell, 2017. "Defense and attack for interdependent systems," European Journal of Operational Research, Elsevier, vol. 256(2), pages 582-591.
    15. Subhasish M. Chowdhury & Iryna Topolyan, 2013. "The Attack-and-Defence Group Contests," University of East Anglia Applied and Financial Economics Working Paper Series 049, School of Economics, University of East Anglia, Norwich, UK..
    16. Subhasish Chowdhury & Dan Kovenock & Roman Sheremeta, 2013. "An experimental investigation of Colonel Blotto games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 52(3), pages 833-861, April.
    17. Lin, Chen & Xiao, Hui & Kou, Gang & Peng, Rui, 2020. "Defending a series system with individual protection, overarching protection, and disinformation," Reliability Engineering and System Safety, Elsevier, vol. 204(C).
    18. Hausken, Kjell & Levitin, Gregory, 2009. "Minmax defense strategy for complex multi-state systems," Reliability Engineering and System Safety, Elsevier, vol. 94(2), pages 577-587.
    19. Levitin, Gregory & Hausken, Kjell, 2009. "Intelligence and impact contests in systems with redundancy, false targets, and partial protection," Reliability Engineering and System Safety, Elsevier, vol. 94(12), pages 1927-1941.
    20. Shan, Xiaojun & Zhuang, Jun, 2013. "Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game," European Journal of Operational Research, Elsevier, vol. 228(1), pages 262-272.

    More about this item

    Statistics

    Access and download statistics

    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:taf:uiiexx:v:50:y:2018:i:11:p:989-996. 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 Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/uiie .

    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.