Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Solving Bin Packing Problems Using VRPSolver Models

  • Original Research
  • Published:
Operations Research Forum Aims and scope Submit manuscript

Abstract

We propose branch-cut-and-price algorithms for the classic bin packing problem and also for the following related problems: vector packing, variable sized bin packing, and variable sized bin packing with optional items. The algorithms are defined as models for VRPSolver, a generic solver for vehicle routing problems. In that way, a simple parameterization enables the use of several branch-cut-and-price advanced elements: automatic stabilization by smoothing, limited-memory rank-1 cuts, enumeration, hierarchical strong branching, and limited discrepancy search diving heuristics. As an original theoretical contribution, we prove that the branching over accumulated resource consumption (Gélinas et al, Ann Oper Res 61(1):91–109, 1995) that does not increase the difficulty of the pricing subproblem is sufficient for those bin packing models. Extensive computational results on instances from the literature show that the VRPSolver models have a performance that is very robust over all those problems, being often superior to the existing exact algorithms on the hardest instances. Several instances could be solved to optimality for the first time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Alves C, de Carvalho JMV (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput Oper Res 35(4):1315–1328

    Article  Google Scholar 

  2. Alvim ACF, Ribeiro CC, Glover F, Aloise DJ (2004) A hybrid improvement heuristic for the one-dimensional bin packing problem. J Heuristics 10 (2):205–229

    Article  Google Scholar 

  3. Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math Program 115:351–385

    Article  Google Scholar 

  4. Baldi MM, Crainic TG, Perboli G, Tadei R (2014) Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items. Ann Oper Res 222(1):125–141

    Article  Google Scholar 

  5. Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur J Oper Res 171(1):85–106

    Article  Google Scholar 

  6. Brandão F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Comput Oper Res 69:56–67

    Article  Google Scholar 

  7. Caprara A, Toth P (2001) Lower bounds and algorithms for the 2-dimensional vector packing problem. Discret Appl Math 111(3):231–262

    Article  Google Scholar 

  8. Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discret Optim 12:129–146

    Article  Google Scholar 

  9. Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transp Sci 53(4):946–985

    Article  Google Scholar 

  10. Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J Comput 32(1):101–119

    Article  Google Scholar 

  11. Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur J Oper Res 255(1):1–20

    Article  Google Scholar 

  12. Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev 59(2):295–320

    Article  Google Scholar 

  13. Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J Heuristics 2:5–30

    Article  Google Scholar 

  14. Fekete SP, Schepers J (2001) New classes of fast lower bounds for bin packing problems. Mathematical programming 91(1):11–31

    Article  Google Scholar 

  15. Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann Oper Res 61(1):91–109

    Article  Google Scholar 

  16. Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9(6):849–859

    Article  Google Scholar 

  17. Haouari M, Serairi M (2011) Relaxations and exact solution of the variable sized bin packing problem. Comput Optim Appl 48(2):345–368

    Article  Google Scholar 

  18. Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math Program Comput 4(4):363–381

    Article  Google Scholar 

  19. Hessler K, Gschwind T, Irnich S (2018) Stabilized branch-and-price algorithms for vector packing problems. Eur J Oper Res 271(2):401–419

    Article  Google Scholar 

  20. Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Column generation. Springer, pp 33–65

  21. Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper Res 56(2):497–511

    Article  Google Scholar 

  22. Kantorovich LV (1960) Mathematical methods of organizing and planning production. Manag Sci 6(4):366–422. Translation of a 1939 paper in Russian

    Article  Google Scholar 

  23. Monaci M (2002) Algorithms for packing and scheduling problems. PhD thesis, University of Bologna

  24. Pecin D, Pessoa A, Poggi M, Uchoa E (2014) branch-cut-and-price for capacitated vehicle routing, Springer

  25. Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J Comput 29(3):489–502

    Article  Google Scholar 

  26. Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math Program Comput 9(1):61–100

    Article  Google Scholar 

  27. Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017) Limited memory rank-1 cuts for vehicle routing problems. Oper Res Lett 45 (3):206–209

    Article  Google Scholar 

  28. Pessoa A, Sadykov R, Uchoa E (2018) Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur J Oper Res 270:530–543

    Article  Google Scholar 

  29. Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J Comput 30(2):339–360

    Article  Google Scholar 

  30. Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2019) A generic exact solver for vehicle routing and related problems. Technical Report L-2019-2, Cadernos do LOGIS-UFF, Niterói, Brazil

  31. Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2019) A generic exact solver for vehicle routing and related problems. In: International conference on integer programming and combinatorial optimization. Springer, pp 354–369

  32. Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin, p xx+ 546

    Book  Google Scholar 

  33. Pisinger D (1997) A minimal algorithm for the 0-1 knapsack problem. Oper Res 45(5):758–767

    Article  Google Scholar 

  34. Ryan DM, Foster BA (1981) Computer scheduling of public transport: urban passenger vehicle and crew scheduling. In: Wren A. (ed). North-Holland, pp 269–280

  35. Sadykov R, Uchoa E, Pessoa A (2020) A bucket graph based labeling algorithm with application to vehicle routing. Transp Sci, accepted

  36. Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch-and-price: the assets of diving methods. INFORMS J Comput 31(2):251–267

    Article  Google Scholar 

  37. Schoenfield JE (2002) Fast, exact solution of open bin packing problems without linear programming. Technical report, US Army Space and Missile Defense Command

  38. José M, de Carvalho V (2005) Using extra dual cuts to accelerate column generation. INFORMS J Comput 17(2):175–182

    Article  Google Scholar 

  39. Vance PH, Barnhart C, Johnson EL, Nemhauser GL (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput Optim Appl 3(2):111–130

    Article  Google Scholar 

  40. Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. In: 50 years of integer programming 1958-2008. Springer, pp 431–502

  41. Wäscher G, Gau T (1996) Heuristics for the integer one-dimensional cutting stock problem: A computational study. Operations-Research-Spektrum 18(3):131–144

    Article  Google Scholar 

  42. Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J Comput. Online First

  43. Wei L, Lai M, Lim A, Hu Q (2020) A branch-and-price algorithm for the two-dimensional vector packing problem. Eur J Oper Res 281(1):25–35

    Article  Google Scholar 

Download references

Acknowledgments

Experiments presented in this paper were carried out using the PlaFRIM (Federative Platform for Research in Computer Science and Mathematics), created under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI, and IMB and other entities: Conseil Régional d’Aquitaine, Université de Bordeaux, CNRS and ANR in accordance to the “Programme d’Investissements d’Avenir.”

Funding

The research was partially supported by the following grants: CNPq 313601/2018-6 and 306033/2019-4, Faperj E-26/202.887/2017, and CAPES PrInt UFF no 88881.

Author information

Authors and Affiliations

  1. Universidade Federal Fluminense - Engenharia de Produção, Rua Passo da Pátria 156, Niterói, RJ, 24210-240, Brasil

    Artur Pessoa & Ruslan Sadykov

  2. Inria Bordeaux – Sud-Ouest, 200 Avenue de la Vieille Tour, 33405, Talence, France

    Eduardo Uchoa

Authors
  1. Artur Pessoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ruslan Sadykov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eduardo Uchoa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Eduardo Uchoa.

Ethics declarations

Conflict of Interest

The authors declare that they have no conflict of interest.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pessoa, A., Sadykov, R. & Uchoa, E. Solving Bin Packing Problems Using VRPSolver Models. SN Oper. Res. Forum 2, 20 (2021). https://doi.org/10.1007/s43069-020-00047-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s43069-020-00047-8

Keywords

Search

Navigation