A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations
Submitted to EJOR June 2017
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/109978 |
| _version_ | 1826195241060794368 |
|---|---|
| author | Galle, Virgile Barnhart, Cynthia Jaillet, Patrick |
| author_facet | Galle, Virgile Barnhart, Cynthia Jaillet, Patrick |
| author_sort | Galle, Virgile |
| collection | MIT |
| description | Submitted to EJOR June 2017 |
| first_indexed | 2024-09-23T10:09:37Z |
| format | Article |
| id | mit-1721.1/109978 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:09:37Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | mit-1721.1/1099782019-04-12T17:23:52Z A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations Galle, Virgile Barnhart, Cynthia Jaillet, Patrick OR in maritime industry Integer Programming Container Relocation Problem Block Relocation Problem Binary Encoding Submitted to EJOR June 2017 The Container Relocation Problem (CRP), also called Block Relocation Problem (BRP), is concerned with finding a sequence of moves of containers that minimizes the number of relocations needed to retrieve all containers, while respecting a given order of retrieval. The restricted CRP enforces that only containers blocking the target container can be relocated. We improve upon and enhance an existing binary encoding and using it, formulate the restricted CRP as a binary integer programming problem in which we exploit structural properties of the optimal solution. This integer programming formulation reduces significantly the number of variables and constraints compared to existing formulations. Its efficiency is shown through computational results on small and medium sized instances taken from the literature. 2017-06-16T19:28:10Z 2017-06-16T19:28:10Z 2017-06-16 2017-09-30 Article http://hdl.handle.net/1721.1/109978 en_US MIT Sloan School Working Paper;5199-17 Attribution-NonCommercial-NoDerivs 3.0 United States http://creativecommons.org/licenses/by-nc-nd/3.0/us/ application/pdf |
| spellingShingle | OR in maritime industry Integer Programming Container Relocation Problem Block Relocation Problem Binary Encoding Galle, Virgile Barnhart, Cynthia Jaillet, Patrick A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title | A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title_full | A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title_fullStr | A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title_full_unstemmed | A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title_short | A new 0-1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| title_sort | new 0 1 formulation of the restricted container relocation problem based on a binary encoding of congurations |
| topic | OR in maritime industry Integer Programming Container Relocation Problem Block Relocation Problem Binary Encoding |
| url | http://hdl.handle.net/1721.1/109978 |
| work_keys_str_mv | AT gallevirgile anew01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations AT barnhartcynthia anew01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations AT jailletpatrick anew01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations AT gallevirgile new01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations AT barnhartcynthia new01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations AT jailletpatrick new01formulationoftherestrictedcontainerrelocationproblembasedonabinaryencodingofcongurations |