Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories

Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-05
Main Authors: Luiz F O Moura Santos, Yoshizaki, Hugo T Y, Cunha, Claudio B
Format: Article
Language:English
Subjects:
Algorithms
Bins
Categories
Compatibility
Heuristic methods
Incompatibility
Integer programming
Operations research
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Luiz F O Moura Santos
Yoshizaki, Hugo T Y
Cunha, Claudio B
description Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2222823944</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2222823944</sourcerecordid><originalsourceid>FETCH-proquest_journals_22228239443</originalsourceid><addsrcrecordid>eNqNi8EKgkAURYcgSMp_eNBasBkt2yZFqxCKtjLa0xlTn82M9PsZ9AHdzVmcc2fM40JsgiTifMF8a5swDPl2x-NYeOx6l0bLokW4oK5VQUYRPeCK0pQKKjLgFMJB95DJ8qn7GjJDU97BWzsFKXWDdPr7T6XDmoxGu2LzSrYW_R-XbH063tJzMBh6jWhd3tBo-knlfFrCxT6KxH_VB_iuP6k</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2222823944</pqid></control><display><type>article</type><title>Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories</title><source>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</source><creator>Luiz F O Moura Santos ; Yoshizaki, Hugo T Y ; Cunha, Claudio B</creator><creatorcontrib>Luiz F O Moura Santos ; Yoshizaki, Hugo T Y ; Cunha, Claudio B</creatorcontrib><description>Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Algorithms ; Bins ; Categories ; Compatibility ; Heuristic methods ; Incompatibility ; Integer programming ; Operations research</subject><ispartof>arXiv.org, 2019-05</ispartof><rights>2019. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2222823944?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>776,780,25730,36988,44565</link.rule.ids></links><search><creatorcontrib>Luiz F O Moura Santos</creatorcontrib><creatorcontrib>Yoshizaki, Hugo T Y</creatorcontrib><creatorcontrib>Cunha, Claudio B</creatorcontrib><title>Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories</title><title>arXiv.org</title><description>Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.</description><subject>Algorithms</subject><subject>Bins</subject><subject>Categories</subject><subject>Compatibility</subject><subject>Heuristic methods</subject><subject>Incompatibility</subject><subject>Integer programming</subject><subject>Operations research</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2019</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqNi8EKgkAURYcgSMp_eNBasBkt2yZFqxCKtjLa0xlTn82M9PsZ9AHdzVmcc2fM40JsgiTifMF8a5swDPl2x-NYeOx6l0bLokW4oK5VQUYRPeCK0pQKKjLgFMJB95DJ8qn7GjJDU97BWzsFKXWDdPr7T6XDmoxGu2LzSrYW_R-XbH063tJzMBh6jWhd3tBo-knlfFrCxT6KxH_VB_iuP6k</recordid><startdate>20190509</startdate><enddate>20190509</enddate><creator>Luiz F O Moura Santos</creator><creator>Yoshizaki, Hugo T Y</creator><creator>Cunha, Claudio B</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PHGZM</scope><scope>PHGZT</scope><scope>PIMPY</scope><scope>PKEHL</scope><scope>PQEST</scope><scope>PQGLB</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20190509</creationdate><title>Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories</title><author>Luiz F O Moura Santos ; Yoshizaki, Hugo T Y ; Cunha, Claudio B</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_22228239443</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2019</creationdate><topic>Algorithms</topic><topic>Bins</topic><topic>Categories</topic><topic>Compatibility</topic><topic>Heuristic methods</topic><topic>Incompatibility</topic><topic>Integer programming</topic><topic>Operations research</topic><toplevel>online_resources</toplevel><creatorcontrib>Luiz F O Moura Santos</creatorcontrib><creatorcontrib>Yoshizaki, Hugo T Y</creatorcontrib><creatorcontrib>Cunha, Claudio B</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection (ProQuest)</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>ProQuest Central (New)</collection><collection>ProQuest One Academic (New)</collection><collection>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest One Academic Middle East (New)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Applied &amp; Life Sciences</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Luiz F O Moura Santos</au><au>Yoshizaki, Hugo T Y</au><au>Cunha, Claudio B</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories</atitle><jtitle>arXiv.org</jtitle><date>2019-05-09</date><risdate>2019</risdate><eissn>2331-8422</eissn><abstract>Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2019-05
issn 2331-8422
language eng
recordid cdi_proquest_journals_2222823944
source Publicly Available Content Database (Proquest) (PQ_SDU_P3)
subjects Algorithms
Bins
Categories
Compatibility
Heuristic methods
Incompatibility
Integer programming
Operations research
title Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-25T12%3A35%3A12IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=Variable%20Neighborhood%20Search%20for%20the%20Bin%20Packing%20Problem%20with%20Compatible%20Categories&rft.jtitle=arXiv.org&rft.au=Luiz%20F%20O%20Moura%20Santos&rft.date=2019-05-09&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E2222823944%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_22228239443%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2222823944&rft_id=info:pmid/&rfr_iscdi=true