Hybrid Algorithms for the Variable Sized Bin Packing Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Christian Blum , Vera Hemmelmayr , Hugo Hernández , Verena Schmid

ABSTRACT

This paper deals with the so-called variable sized bin packing problem, which is a generalization of the one-dimensional bin packing problem in which a set of items with given weights have to be packed into a minimum-cost set of bins of variable sizes and costs. First we propose a heuristic and a beam search approach. Both algorithms are strongly based on dynamic programming procedures and lower bounding techniques. Second, we propose a variable neighborhood search approach where some neighborhoods are also based on dynamic programming. The best results are obtained by using the solutions provided by the proposed heuristic as starting solutions for variable neighborhood search. The results show that this algorithm is very competitive with current state-of-the-art approaches. More... »

PAGES

16-30

References to SciGraph publications

  • 2003-03. Algorithms for packing and scheduling problems in 4OR
  • 2004. Knapsack Problems in NONE
  • 2011-03. Relaxations and exact solution of the variable sized bin packing problem in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • Book

    TITLE

    Hybrid Metaheuristics

    ISBN

    978-3-642-16053-0
    978-3-642-16054-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-16054-7_2

    DOI

    http://dx.doi.org/10.1007/978-3-642-16054-7_2

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1026356153


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Universitat Polit\u00e8cnica de Catalunya", 
              "id": "https://www.grid.ac/institutes/grid.6835.8", 
              "name": [
                "ALBCOM Research Group, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Blum", 
            "givenName": "Christian", 
            "id": "sg:person.011315326455.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011315326455.07"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Vienna", 
              "id": "https://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Department of Business Administration, Universit\u00e4t Wien, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hemmelmayr", 
            "givenName": "Vera", 
            "id": "sg:person.011404517117.33", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011404517117.33"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Universitat Polit\u00e8cnica de Catalunya", 
              "id": "https://www.grid.ac/institutes/grid.6835.8", 
              "name": [
                "ALBCOM Research Group, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hern\u00e1ndez", 
            "givenName": "Hugo", 
            "id": "sg:person.014423621445.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014423621445.79"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Vienna", 
              "id": "https://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Department of Business Administration, Universit\u00e4t Wien, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schmid", 
            "givenName": "Verena", 
            "id": "sg:person.012244127551.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012244127551.45"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10288-002-0011-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012978435", 
              "https://doi.org/10.1007/s10288-002-0011-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(02)00125-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013000650"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00207548808947840", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016292043"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1020901084", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24777-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020901084", 
              "https://doi.org/10.1007/978-3-540-24777-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24777-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020901084", 
              "https://doi.org/10.1007/978-3-540-24777-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24777-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020901084", 
              "https://doi.org/10.1007/978-3-540-24777-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2005.07.033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023085441"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10589-009-9276-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027624251", 
              "https://doi.org/10.1007/s10589-009-9276-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cor.2008.12.016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028136967"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(00)00100-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035285168"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(02)00247-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038427672"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0305-0548(97)00031-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042216299"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841878"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753979834669x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880288"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "This paper deals with the so-called variable sized bin packing problem, which is a generalization of the one-dimensional bin packing problem in which a set of items with given weights have to be packed into a minimum-cost set of bins of variable sizes and costs. First we propose a heuristic and a beam search approach. Both algorithms are strongly based on dynamic programming procedures and lower bounding techniques. Second, we propose a variable neighborhood search approach where some neighborhoods are also based on dynamic programming. The best results are obtained by using the solutions provided by the proposed heuristic as starting solutions for variable neighborhood search. The results show that this algorithm is very competitive with current state-of-the-art approaches.", 
        "editor": [
          {
            "familyName": "Blesa", 
            "givenName": "Mar\u00eda J.", 
            "type": "Person"
          }, 
          {
            "familyName": "Blum", 
            "givenName": "Christian", 
            "type": "Person"
          }, 
          {
            "familyName": "Raidl", 
            "givenName": "G\u00fcnther", 
            "type": "Person"
          }, 
          {
            "familyName": "Roli", 
            "givenName": "Andrea", 
            "type": "Person"
          }, 
          {
            "familyName": "Sampels", 
            "givenName": "Michael", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-16054-7_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-16053-0", 
            "978-3-642-16054-7"
          ], 
          "name": "Hybrid Metaheuristics", 
          "type": "Book"
        }, 
        "name": "Hybrid Algorithms for the Variable Sized Bin Packing Problem", 
        "pagination": "16-30", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1026356153"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-16054-7_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "7d8f5eff0e7760f8e074b8a503c3b795d6d368183b9035632361dfcf950ec877"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-16054-7_2", 
          "https://app.dimensions.ai/details/publication/pub.1026356153"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:26", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70056_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-16054-7_2"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16054-7_2'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16054-7_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16054-7_2'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16054-7_2'


     

    This table displays all metadata directly associated to this object as RDF triples.

    150 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-16054-7_2 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nf53ca35a1f7442f5a728b273115ba00f
    4 schema:citation sg:pub.10.1007/978-3-540-24777-7
    5 sg:pub.10.1007/s10288-002-0011-1
    6 sg:pub.10.1007/s10589-009-9276-z
    7 https://app.dimensions.ai/details/publication/pub.1020901084
    8 https://doi.org/10.1016/j.cor.2008.12.016
    9 https://doi.org/10.1016/j.ejor.2005.07.033
    10 https://doi.org/10.1016/s0305-0548(97)00031-2
    11 https://doi.org/10.1016/s0377-2217(00)00100-4
    12 https://doi.org/10.1016/s0377-2217(02)00125-x
    13 https://doi.org/10.1016/s0377-2217(02)00247-3
    14 https://doi.org/10.1080/00207548808947840
    15 https://doi.org/10.1137/0215016
    16 https://doi.org/10.1137/s009753979834669x
    17 schema:datePublished 2010
    18 schema:datePublishedReg 2010-01-01
    19 schema:description This paper deals with the so-called variable sized bin packing problem, which is a generalization of the one-dimensional bin packing problem in which a set of items with given weights have to be packed into a minimum-cost set of bins of variable sizes and costs. First we propose a heuristic and a beam search approach. Both algorithms are strongly based on dynamic programming procedures and lower bounding techniques. Second, we propose a variable neighborhood search approach where some neighborhoods are also based on dynamic programming. The best results are obtained by using the solutions provided by the proposed heuristic as starting solutions for variable neighborhood search. The results show that this algorithm is very competitive with current state-of-the-art approaches.
    20 schema:editor Nc16dabeb9cc04dfe92553a2d2d422517
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N6fc20abb4f1f4e489c22877513dd80fb
    25 schema:name Hybrid Algorithms for the Variable Sized Bin Packing Problem
    26 schema:pagination 16-30
    27 schema:productId N7e092b03fb0c4969879b8ba5d542ebda
    28 N9321f5fa01bb4d7e92308dfb65c66596
    29 Nd4c658fc120b4848a0c2e985f06973cf
    30 schema:publisher Ne685f1b1822946a5af9d2295b78d5e88
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026356153
    32 https://doi.org/10.1007/978-3-642-16054-7_2
    33 schema:sdDatePublished 2019-04-16T08:26
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nf30c13c721e0466aa00d64c00a84ffbb
    36 schema:url https://link.springer.com/10.1007%2F978-3-642-16054-7_2
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N35cb4c62aa38464b9b149aa3ab83af4f schema:familyName Blesa
    41 schema:givenName María J.
    42 rdf:type schema:Person
    43 N456063d0708944c18e6d95c0409ac3c1 schema:familyName Blum
    44 schema:givenName Christian
    45 rdf:type schema:Person
    46 N456ccc663072440a9d1bd4b4b2f1fcec rdf:first N456063d0708944c18e6d95c0409ac3c1
    47 rdf:rest N4db7bf6ed5aa48d5b69d7c03d0b95dca
    48 N4db7bf6ed5aa48d5b69d7c03d0b95dca rdf:first Nb02fb4aeeb344c7b9fb3968a25adf573
    49 rdf:rest N935e18db77b7451cace197724283526a
    50 N5483571a13034b1599683ca4e4e81fd2 schema:familyName Roli
    51 schema:givenName Andrea
    52 rdf:type schema:Person
    53 N5c3b97675dc4436ead21949f47c91451 schema:familyName Sampels
    54 schema:givenName Michael
    55 rdf:type schema:Person
    56 N6c9c208625a04f0890295970bd7307ff rdf:first sg:person.011404517117.33
    57 rdf:rest N9ecc0a6f65114c61a9739bce8d14b582
    58 N6fc20abb4f1f4e489c22877513dd80fb schema:isbn 978-3-642-16053-0
    59 978-3-642-16054-7
    60 schema:name Hybrid Metaheuristics
    61 rdf:type schema:Book
    62 N7e092b03fb0c4969879b8ba5d542ebda schema:name readcube_id
    63 schema:value 7d8f5eff0e7760f8e074b8a503c3b795d6d368183b9035632361dfcf950ec877
    64 rdf:type schema:PropertyValue
    65 N9321f5fa01bb4d7e92308dfb65c66596 schema:name dimensions_id
    66 schema:value pub.1026356153
    67 rdf:type schema:PropertyValue
    68 N935e18db77b7451cace197724283526a rdf:first N5483571a13034b1599683ca4e4e81fd2
    69 rdf:rest Nbf4933866e1d43b5aea6b0927747b19d
    70 N9ecc0a6f65114c61a9739bce8d14b582 rdf:first sg:person.014423621445.79
    71 rdf:rest Nd948c0e30d3541a3b81b9b9764bfe38b
    72 Nb02fb4aeeb344c7b9fb3968a25adf573 schema:familyName Raidl
    73 schema:givenName Günther
    74 rdf:type schema:Person
    75 Nbf4933866e1d43b5aea6b0927747b19d rdf:first N5c3b97675dc4436ead21949f47c91451
    76 rdf:rest rdf:nil
    77 Nc16dabeb9cc04dfe92553a2d2d422517 rdf:first N35cb4c62aa38464b9b149aa3ab83af4f
    78 rdf:rest N456ccc663072440a9d1bd4b4b2f1fcec
    79 Nd4c658fc120b4848a0c2e985f06973cf schema:name doi
    80 schema:value 10.1007/978-3-642-16054-7_2
    81 rdf:type schema:PropertyValue
    82 Nd948c0e30d3541a3b81b9b9764bfe38b rdf:first sg:person.012244127551.45
    83 rdf:rest rdf:nil
    84 Ne685f1b1822946a5af9d2295b78d5e88 schema:location Berlin, Heidelberg
    85 schema:name Springer Berlin Heidelberg
    86 rdf:type schema:Organisation
    87 Nf30c13c721e0466aa00d64c00a84ffbb schema:name Springer Nature - SN SciGraph project
    88 rdf:type schema:Organization
    89 Nf53ca35a1f7442f5a728b273115ba00f rdf:first sg:person.011315326455.07
    90 rdf:rest N6c9c208625a04f0890295970bd7307ff
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Artificial Intelligence and Image Processing
    96 rdf:type schema:DefinedTerm
    97 sg:person.011315326455.07 schema:affiliation https://www.grid.ac/institutes/grid.6835.8
    98 schema:familyName Blum
    99 schema:givenName Christian
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011315326455.07
    101 rdf:type schema:Person
    102 sg:person.011404517117.33 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
    103 schema:familyName Hemmelmayr
    104 schema:givenName Vera
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011404517117.33
    106 rdf:type schema:Person
    107 sg:person.012244127551.45 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
    108 schema:familyName Schmid
    109 schema:givenName Verena
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012244127551.45
    111 rdf:type schema:Person
    112 sg:person.014423621445.79 schema:affiliation https://www.grid.ac/institutes/grid.6835.8
    113 schema:familyName Hernández
    114 schema:givenName Hugo
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014423621445.79
    116 rdf:type schema:Person
    117 sg:pub.10.1007/978-3-540-24777-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020901084
    118 https://doi.org/10.1007/978-3-540-24777-7
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/s10288-002-0011-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012978435
    121 https://doi.org/10.1007/s10288-002-0011-1
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/s10589-009-9276-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027624251
    124 https://doi.org/10.1007/s10589-009-9276-z
    125 rdf:type schema:CreativeWork
    126 https://app.dimensions.ai/details/publication/pub.1020901084 schema:CreativeWork
    127 https://doi.org/10.1016/j.cor.2008.12.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028136967
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1016/j.ejor.2005.07.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023085441
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1016/s0305-0548(97)00031-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042216299
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1016/s0377-2217(00)00100-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035285168
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1016/s0377-2217(02)00125-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013000650
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1016/s0377-2217(02)00247-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038427672
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1080/00207548808947840 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016292043
    140 rdf:type schema:CreativeWork
    141 https://doi.org/10.1137/0215016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841878
    142 rdf:type schema:CreativeWork
    143 https://doi.org/10.1137/s009753979834669x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880288
    144 rdf:type schema:CreativeWork
    145 https://www.grid.ac/institutes/grid.10420.37 schema:alternateName University of Vienna
    146 schema:name Department of Business Administration, Universität Wien, Vienna, Austria
    147 rdf:type schema:Organization
    148 https://www.grid.ac/institutes/grid.6835.8 schema:alternateName Universitat Politècnica de Catalunya
    149 schema:name ALBCOM Research Group, Universitat Politècnica de Catalunya, Barcelona, Spain
    150 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...