nach oben

OR Spectrum

Erschienen in:

07.01.2020 | Regular Article

Enhancing Benders decomposition algorithm to solve a combat logistics problem

verfasst von: Mohammad Marufuzzaman, Farjana Nur, Amy E. Bednar, Mark Cowan

Erschienen in: OR Spectrum | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper proposes a multi-time period, two-stage stochastic programming model for the design and management of a typical combat logistics problem. The design shall minimize the total path setup cost, commodity preposition and processing costs, and expected transportation, storage, and shortage costs across all possible path failure scenarios. Due to the complexity associated with solving the model, we propose an accelerated Benders decomposition algorithm to solve the model in a realistic-size network problem within a reasonable amount of time. The Benders decomposition algorithm incorporates several algorithmic improvements such as pareto-optimal cuts, multi-cuts, knapsack inequalities, integer cuts, input ordering, mean-value cuts, and the rolling horizon heuristic. Computational experiments are performed to assess the efficiency of different enhancement techniques within the Benders decomposition algorithm.

Vorheriger Artikel A matheuristic for the swap body vehicle routing problem

Nächster Artikel One-way and two-way cost allocation in hub network problems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

This is primarily due to the fact that over time the attacker will realize the adopted strategies undertaken by the combat logistics network. Therefore, it is mandatory for the combat logistic network planner to account for this factor while designing for the overall combat operations.

This can be achieved via dropping the capacity of the susceptible paths \(u_{ijp}\) by multiplying them with a \(\beta _{ijp}\) value less than 1.0, i.e., \(\beta _{ijp} < 1\) in \(u_{ijp}\beta _{ijp}\). See constraint (7) for details.

Three different path failure probability scenarios have been constructed for this case; however, the decision maker can construct additional groups by further classifying the failure scenarios (e.g., low-medium/high-medium path failure scenario grouping and the like).

https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/.

Ahner DK, Parson CR (2015) Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming. Optimization Letters 9(8):1689–1701. https://doi.org/10.1007/s11590-014-0823-x CrossRef

Akgün I, Tansel BÇ (2007) Optimization of transportation requirements in the deployment of military units. Computers and Operations Research 34(4):1158–1176. https://doi.org/10.1016/j.cor.2005.06.016 CrossRef

Andersen J, Crainic TG, Christiansen M (2009) Service network design with asset management: Formulations and comparative analyses. Transportation Research Part C 17(2):197–207. https://doi.org/10.1016/j.trc.2008.10.005 CrossRef

Balasubramanian J, Grossmann I (2004) Approximation to multistage stochastic optimization in multiperiod batch plant scheduling under demand uncertainty. Industrial and Engineering Chemistry Research 43(14):3695–3713. https://doi.org/10.1021/ie030308+ CrossRef

Barahona F, Chowdhary P, Ettl M, Huang P, Kimbrel T, Ladanyi L, Lee YM, Schieber B, Sourirajan K, Sviridenko M, Swirszcz GM (2007) Inventory allocation and transportation scheduling for logistics of network-centric military operations. IBM Journal of Research and Development 51(3/4):391–407. https://doi.org/10.1147/rd.513.0391 CrossRef

Batun S, Denton BT, Huschka TR, Schaefer AJ (2011) Operating room pooling and parallel surgery processing under uncertainty. INFORMS Journal on Computing 23(2):220–237. https://doi.org/10.1287/ijoc.1100.0396 CrossRef

Benders JF (1962) Partitioning procedures for solving mixedvariables programming problems. Numerische Mathematik 4:237–252. https://doi.org/10.1007/BF01386316 CrossRef

Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. European Journal of Operational Research 34(3):384–392. https://doi.org/10.1016/0377-2217(88)90159-2 CrossRef

Brown GG, Carlyle WM (2008) Optimizing the US Navy’s combat logistics force. Naval Research Logistics (NRL) 55(8):800–810. https://doi.org/10.1002/nav.20318 CrossRef

CPLEX. (2016). Benders algorithm in CPLEX V12.7.0. Retrieved from: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/ReleaseNotes/topics/releasenotes127/newBenders.html

Crainic TG, Rousseau JM (1986) Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem. Transportation Research Part B 20(3):225–242. https://doi.org/10.1016/0191-2615(86)90019-6 CrossRef

Errico F, Crainic TG, Malucelli F, Nonato M (2016) A Benders decomposition approach for the symmetric TSP with generalized latency arising in the design of semiflexible transit systems. Transportation Science 51(2):706–722. https://doi.org/10.1287/trsc.2015.0636 CrossRef

Faied, M., & Girard, A. (2010). Modeling and optimizing military air operations. In Proceedings of the 48th IEEE conference on decision and control (pp. 6274–6279). https://doi.org/10.1109/CDC.2009.5399926

Fischetti M, Lodi A (2003) Local branching. Mathematical Programming 98:23–47. https://doi.org/10.1007/s10107-003-0395-5 CrossRef

Fulton LV, Lasdon LS, McDaniel RR Jr, Coppola MN (2010) Two-stage stochastic optimization for the allocation of medical assets in steady-state combat operations. The Journal of Defense Modeling and Simulation 7(2):89–102. https://doi.org/10.1177/1548512910364390 CrossRef

Gendron B, Crainic TG, Frangioni A (1999) Multicommodity capacitated network design. Springer, Berlin, pp 1–19. https://doi.org/10.1007/978-1-4615-5087-7_1 CrossRef

General Algebraic Modeling System. (GAMS). (2013). Retrieved from: http://www.gams.com/

Georgiadis MC, Tsiakis P, Longinidis P, Sofioglou MK (2011) Optimal design of supply chain networks under uncertain transient demand variations. Omega 39(3):254–272. https://doi.org/10.1016/j.omega.2010.07.002 CrossRef

Gue KR (2003) A dynamic distribution model for combat logistics. Computers and Operations Research 30(3):367–381. https://doi.org/10.1016/S0305-0548(01)00104-6 CrossRef

Jans R, Desrosiers J (2013) Efficient symmetry breaking formulations for the job grouping problem. Computers and Operations Research 40(4):1132–1142. https://doi.org/10.1016/j.cor.2012.11.017 CrossRef

Kleywegt AJ, Shapiro A, Homem-De-Mello T (2001) The sample average approximation method for stochastic discrete optimization. SIAM Journal of Optimization 12:479–502. https://doi.org/10.1137/S1052623499363220 CrossRef

Kostina AM, Guillen-Gosalbeza G, Meleb FD, Bagajewiczc MJ, Jimeneza L (2011) A novel rolling horizon strategy for the strategic planning of supply chains. Application to the sugar cane industry of Argentina. Computers and Chemical Engineering 35:2540–2563. https://doi.org/10.1016/j.compchemeng.2011.04.006 CrossRef

Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research 29:464–484. https://doi.org/10.1287/opre.29.3.464 CrossRef

Magnanti TL, Wong RT (1984) Network design and transportation planning: Models and algorithms. Transportation Science 18(1):1–55. https://doi.org/10.1287/trsc.18.1.1 CrossRef

Mak WK, Morton DP, Wood RK (1999) Monte Carlo bounding techniques for determining solution quality in stochastic programs. Operations Research Letters 24:47–56. https://doi.org/10.1016/S0167-6377(98)00054-6 CrossRef

Marufuzzaman M, Eksioglu SD (2017) Designing a reliable and dynamic multi-modal transportation network for biofuel supply chain. Transportation Science 51(2):494–517. https://doi.org/10.1287/trsc.2015.0632 CrossRef

NATO. (2012). Logistics handbook. Retrieved from: https://www.nato.int/nato_static_fl2014/assets/pdf/pdf_2016_03/20160303_2012-logistics_hndbk-en.pdf

National Priorities Project. (2018a). Military spending in the United States. Retrieved from: https://www.nationalpriorities.org/campaigns/military-spending-united-states/

National Priorities Project. (2018b). Overseas contingency operations: The Pentagon slush fund. Retrieved from https://www.nationalpriorities.org/campaigns/overseas-contingency-operations/

Norkin VI, Ermoliev YM, Ruszczynski A (1998) On optimal allocation of indivisibles under uncertainty. Operations Research 46:381–395. https://doi.org/10.1287/opre.46.3.381 CrossRef

Norkin VI, Pflug GC, Ruszczynski A (1998) A branch and bound method for stochastic global optimization. Mathematical Programming 83(3):425–450. https://doi.org/10.1007/BF02680569 CrossRef

Office of Management and Budget. (2017). America first: A budget blueprint to make America great again. Retrieved from https://www.gpo.gov/fdsys/pkg/BUDGET-2018-BLUEPRINT/pdf/BUDGET-2018-BLUEPRINT.pdf

Overholts DL II, Bell JE, Arostegui MA (2009) A location analysis approach for military maintenance scheduling with geographically dispersed service areas. Omega 37(4):838–852. https://doi.org/10.1016/j.omega.2008.05.003 CrossRef

Papadakos N (2008) Practical enhancements to the magnanti-wong method. Operations Research Letters 36:444–449. https://doi.org/10.1016/j.orl.2008.01.005 CrossRef

Ren, J., Zheng, X. L., & Tan, Y. J. (2013). Multi-product supply planning for combat units in battlefield environment. In The 19th international conference on industrial engineering and engineering management (pp. 445–453). https://doi.org/10.1007/978-3-642-37270-4_43 CrossRef

Rettke AJ, Robbins MJ, Lunday BJ (2016) Approximate dynamic programming for the dispatch of military medical evacuation assets. European Journal of Operational Research 254(3):824–839. https://doi.org/10.1016/j.ejor.2016.04.017 CrossRef

Santoso T, Ahmed S, Goetschalckx M, Shapiro A (2005) A stochastic programming approach for supply chain network design under uncertainty. European Journal of Operational Research 167:96–115. https://doi.org/10.1016/j.ejor.2004.01.046 CrossRef

Schutz P, Tomasgard A, Ahmed S (2009) Supply chain design under uncertainty using sample average approximation and dual decomposition. European Journal of Operational Research 199:409–419. https://doi.org/10.1016/j.ejor.2008.11.040 CrossRef

Sebbah S, Ghanmi A, Boukhtouta A (2013) A column-and-cut generation algorithm for planning of Canadian armed forces tactical logistics distribution. Computers and Operations Research 40(12):3069–3079. https://doi.org/10.1016/j.cor.2013.07.002 CrossRef

Toyoglu H, Karasan OE, Kara BY (2011) Distribution network design on the battlefield. Naval Research Logistics (NRL) 58(3):188–209. https://doi.org/10.1002/nav.20402 CrossRef

Tsadikovich D, Levner E, Tell H, Werner F (2016) Integrated demand-responsive scheduling of maintenance and transportation operations in military supply chains. International Journal of Production Research 54(19):5798–5810. https://doi.org/10.1080/00207543.2016.1178864 CrossRef

Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Computational Optimization and Applications 24:289–333. https://doi.org/10.1023/A:1021814225969 CrossRef

Titel: Enhancing Benders decomposition algorithm to solve a combat logistics problem
verfasst von: Mohammad Marufuzzaman
Farjana Nur
Amy E. Bednar
Mark Cowan
Publikationsdatum: 07.01.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: OR Spectrum / Ausgabe 1/2020
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-019-00571-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2020

A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

Acknowledgement to Reviewers

Mathematical models to improve the current practice in a Home Healthcare Unit

A long-term unit commitment problem with hydrothermal coordination for economic and emission control in large-scale electricity systems

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

Balance in resource allocation problems: a changing reference approach