IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v210y2013i1p165-19010.1007-s10479-011-1050-9.html
   My bibliography  Save this article

An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions

Author

Listed:
  • Lixin Tang
  • Wei Jiang
  • Georgios Saharidis

Abstract

We investigate a logistics facility location problem to determine whether the existing facilities remain open or not, what the expansion size of the open facilities should be and which potential facilities should be selected. The problem is formulated as a mixed integer linear programming model (MILP) with the objective to minimize the sum of the savings from closing the existing facilities, the expansion costs, the fixed setup costs, the facility operating costs and the transportation costs. The structure of the model motivates us to solve the problem using Benders decomposition algorithm. Three groups of valid inequalities are derived to improve the lower bounds obtained by the Benders master problem. By separating the primal Benders subproblem, different types of disaggregated cuts of the primal Benders cut are constructed in each iteration. A high density Pareto cut generation method is proposed to accelerate the convergence by lifting Pareto-optimal cuts. Computational experiments show that the combination of all the valid inequalities can improve the lower bounds significantly. By alternately applying the high density Pareto cut generation method based on the best disaggregated cuts, the improved Benders decomposition algorithm is advantageous in decreasing the total number of iterations and CPU time when compared to the standard Benders algorithm and optimization solver CPLEX, especially for large-scale instances. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • Lixin Tang & Wei Jiang & Georgios Saharidis, 2013. "An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions," Annals of Operations Research, Springer, vol. 210(1), pages 165-190, November.
  • Handle: RePEc:spr:annopr:v:210:y:2013:i:1:p:165-190:10.1007/s10479-011-1050-9
    DOI: 10.1007/s10479-011-1050-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-1050-9
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10479-011-1050-9?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. Gendreau, Michel & Potvin, Jean-Yves & Smires, Ali & Soriano, Patrick, 2006. "Multi-period capacity expansion for a local access telecommunications network," European Journal of Operational Research, Elsevier, vol. 172(3), pages 1051-1066, August.
    2. Poojari, C.A. & Beasley, J.E., 2009. "Improving benders decomposition using a genetic algorithm," European Journal of Operational Research, Elsevier, vol. 199(1), pages 89-97, November.
    3. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2009. "Facility location and supply chain management - A review," European Journal of Operational Research, Elsevier, vol. 196(2), pages 401-412, July.
    4. Cote, Gilles & Laughton, Michael A., 1984. "Large-scale mixed integer programming: Benders-type heuristics," European Journal of Operational Research, Elsevier, vol. 16(3), pages 327-333, June.
    5. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    6. Michel Minoux, 2001. "Discrete Cost Multicommodity Network Optimization Problems and Exact Solution Methods," Annals of Operations Research, Springer, vol. 106(1), pages 19-46, September.
    7. Walter Rei & Jean-François Cordeau & Michel Gendreau & Patrick Soriano, 2009. "Accelerating Benders Decomposition by Local Branching," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 333-345, May.
    8. C. O. Fong & V. Srinivasan, 1986. "The Multiregion Dynamic Capacity Expansion Problem: An Improved Heuristic," Management Science, INFORMS, vol. 32(9), pages 1140-1152, September.
    9. Dale McDaniel & Mike Devine, 1977. "A Modified Benders' Partitioning Algorithm for Mixed Integer Programming," Management Science, INFORMS, vol. 24(3), pages 312-319, November.
    10. Jean-François Cordeau & Federico Pasin & Marius Solomon, 2006. "An integrated model for logistics network design," Annals of Operations Research, Springer, vol. 144(1), pages 59-82, April.
    11. Klose, Andreas, 2000. "A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 126(2), pages 408-421, October.
    12. Erenguc, S. Selcuk & Simpson, N. C. & Vakharia, Asoo J., 1999. "Integrated production/distribution planning in supply chains: An invited review," European Journal of Operational Research, Elsevier, vol. 115(2), pages 219-236, June.
    13. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    14. Halit Üster & Gopalakrishnan Easwaran & Elif Akçali & Sila Çetinkaya, 2007. "Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 890-907, December.
    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. Faria, Victor. A.D. & de Queiroz, Anderson Rodrigo & Lima, Luana M.M. & Lima, José W.M., 2018. "Cooperative game theory and last addition method in the allocation of firm energy rights," Applied Energy, Elsevier, vol. 226(C), pages 905-915.
    2. Jian Zhou & Wenying Xia & Ke Wang & Hui Li & Qianyu Zhang, 2020. "Fuzzy Bi-Objective Closed-Loop Supply Chain Network Design Problem with Multiple Recovery Options," Sustainability, MDPI, vol. 12(17), pages 1-26, August.
    3. Nader Azad & Elkafi Hassini, 2019. "A Benders Decomposition Method for Designing Reliable Supply Chain Networks Accounting for Multimitigation Strategies and Demand Losses," Transportation Science, INFORMS, vol. 53(5), pages 1287-1312, September.
    4. M. Fattahi & M. Mahootchi & S. M. Moattar Husseini, 2016. "Integrated strategic and tactical supply chain planning with price-sensitive demands," Annals of Operations Research, Springer, vol. 242(2), pages 423-456, July.
    5. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    6. Jalali, Sajjad & Seifbarghy, Mehdi & Niaki, Seyed Taghi Akhavan, 2018. "A risk-averse location-protection problem under intentional facility disruptions: A modified hybrid decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 196-219.
    7. Attari, Mahdi Yousefi Nejad & Torkayesh, Ali Ebadi, 2018. "Developing benders decomposition algorithm for a green supply chain network of mine industry: Case of Iranian mine industry," Operations Research Perspectives, Elsevier, vol. 5(C), pages 371-382.
    8. Amirhossein Baghestani & Mohammadhossein Abbasi & Saeed Rastegar & Amir Reza Mamdoohi & Atoosa Afaghpoor & Mahmoud Saffarzadeh, 2023. "Logistics Village Location with Capacity Planning Problem, an MILP Model Approach," Sustainability, MDPI, vol. 15(5), pages 1-14, March.
    9. Ashkan Fakhri & Antonios Fragkogios & Georgios K. D. Saharidis, 2021. "An Accelerated Benders Decomposition Algorithm for Solving a Double-Type Double-Standard Maximal Covering Location Problem," SN Operations Research Forum, Springer, vol. 2(1), pages 1-24, March.
    10. Max Biggs & Rim Hariss & Georgia Perakis, 2023. "Constrained optimization of objective functions determined from random forests," Production and Operations Management, Production and Operations Management Society, vol. 32(2), pages 397-415, February.
    11. Simon Emde & Shohre Zehtabian & Yann Disser, 2023. "Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition," Annals of Operations Research, Springer, vol. 322(1), pages 467-496, March.
    12. Azad, Nader & Hassini, Elkafi, 2019. "Recovery strategies from major supply disruptions in single and multiple sourcing networks," European Journal of Operational Research, Elsevier, vol. 275(2), pages 481-501.
    13. Nader Ghaffarinasab & Bahar Y. Kara, 2019. "Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem," Networks and Spatial Economics, Springer, vol. 19(1), pages 83-108, March.
    14. Keyvanshokooh, Esmaeil & Ryan, Sarah M. & Kabir, Elnaz, 2016. "Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decomposition," European Journal of Operational Research, Elsevier, vol. 249(1), pages 76-92.
    15. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    16. Placido dos Santos, Felipe Silva & Oliveira, Fabricio, 2019. "An enhanced L-Shaped method for optimizing periodic-review inventory control problems modeled via two-stage stochastic programming," European Journal of Operational Research, Elsevier, vol. 275(2), pages 677-693.
    17. Reddy, K. Nageswara & Kumar, Akhilesh & Choudhary, Alok & Cheng, T. C. Edwin, 2022. "Multi-period green reverse logistics network design: An improved Benders-decomposition-based heuristic approach," European Journal of Operational Research, Elsevier, vol. 303(2), pages 735-752.
    18. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    19. Diego Ruiz-Hernández & David Delgado-Gómez, 2016. "The stochastic capacitated branch restructuring problem," Annals of Operations Research, Springer, vol. 246(1), pages 77-100, November.
    20. Mariel, Katharina & Minner, Stefan, 2017. "Benders decomposition for a strategic network design problem under NAFTA local content requirements," Omega, Elsevier, vol. 68(C), pages 62-75.
    21. Kumar, Pramesh & Khani, Alireza, 2022. "Planning of integrated mobility-on-demand and urban transit networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 166(C), pages 499-521.
    22. M. Jenabi & S. Fatemi Ghomi & S. Torabi & S. Hosseinian, 2015. "Acceleration strategies of Benders decomposition for the security constraints power system expansion planning," Annals of Operations Research, Springer, vol. 235(1), pages 337-369, December.
    23. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    24. Pearce, Robin H. & Forbes, Michael, 2018. "Disaggregated Benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 78-88.
    25. N. Beheshti Asl & S. A. MirHassani, 2019. "Accelerating benders decomposition: multiple cuts via multiple solutions," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 806-826, April.

    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. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    2. de Sá, Elisangela Martins & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2013. "An improved Benders decomposition algorithm for the tree of hubs location problem," European Journal of Operational Research, Elsevier, vol. 226(2), pages 185-202.
    3. M. Jenabi & S. Fatemi Ghomi & S. Torabi & S. Hosseinian, 2015. "Acceleration strategies of Benders decomposition for the security constraints power system expansion planning," Annals of Operations Research, Springer, vol. 235(1), pages 337-369, December.
    4. Hanif Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture," Annals of Operations Research, Springer, vol. 210(1), pages 213-244, November.
    5. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    6. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    7. Joe Naoum-Sawaya & Samir Elhedhli, 2013. "An interior-point Benders based branch-and-cut algorithm for mixed integer programs," Annals of Operations Research, Springer, vol. 210(1), pages 33-55, November.
    8. M. Jenabi & S. M. T. Fatemi Ghomi & S. A. Torabi & Moeen Sammak Jalali, 2022. "An accelerated Benders decomposition algorithm for stochastic power system expansion planning using sample average approximation," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1304-1336, December.
    9. Azad, Nader & Hassini, Elkafi, 2019. "Recovery strategies from major supply disruptions in single and multiple sourcing networks," European Journal of Operational Research, Elsevier, vol. 275(2), pages 481-501.
    10. Georgios Saharidis & Marianthi Ierapetritou, 2013. "Speed-up Benders decomposition using maximum density cut (MDC) generation," Annals of Operations Research, Springer, vol. 210(1), pages 101-123, November.
    11. Kuthambalayan, Thyagaraj S. & Mehta, Peeyush & Shanker, Kripa, 2014. "Integrating operations and marketing decisions using delayed differentiation of products and guaranteed delivery time under stochastic demand," European Journal of Operational Research, Elsevier, vol. 237(2), pages 617-627.
    12. Hanif Sherali & Brian Lunday, 2013. "On generating maximal nondominated Benders cuts," Annals of Operations Research, Springer, vol. 210(1), pages 57-72, November.
    13. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    14. Brech, Claus-Henning & Ernst, Andreas & Kolisch, Rainer, 2019. "Scheduling medical residents’ training at university hospitals," European Journal of Operational Research, Elsevier, vol. 274(1), pages 253-266.
    15. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    16. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    17. Jeihoonian, Mohammad & Kazemi Zanjani, Masoumeh & Gendreau, Michel, 2016. "Accelerating Benders decomposition for closed-loop supply chain network design: Case of used durable products with different quality levels," European Journal of Operational Research, Elsevier, vol. 251(3), pages 830-845.
    18. Nader Azad & Georgios Saharidis & Hamid Davoudpour & Hooman Malekly & Seyed Yektamaram, 2013. "Strategies for protecting supply chain networks against facility and transportation disruptions: an improved Benders decomposition approach," Annals of Operations Research, Springer, vol. 210(1), pages 125-163, November.
    19. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric, 2022. "Meta partial benders decomposition for the logistics service network design problem," European Journal of Operational Research, Elsevier, vol. 300(2), pages 473-489.
    20. Walter Rei & Jean-François Cordeau & Michel Gendreau & Patrick Soriano, 2009. "Accelerating Benders Decomposition by Local Branching," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 333-345, May.

    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:spr:annopr:v:210:y:2013:i:1:p:165-190:10.1007/s10479-011-1050-9. 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.