- -

A branch and bound approach for large pre-marshalling problems

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A branch and bound approach for large pre-marshalling problems

Show simple item record

Files in this item

dc.contributor.author Tanaka, Shunji es_ES
dc.contributor.author Tierney, Kevin es_ES
dc.contributor.author Parreño-Torres, Consuelo es_ES
dc.contributor.author Alvarez-Valdes, Ramón es_ES
dc.contributor.author Ruiz García, Rubén es_ES
dc.date.accessioned 2020-12-03T04:31:34Z
dc.date.available 2020-12-03T04:31:34Z
dc.date.issued 2019-10-01 es_ES
dc.identifier.issn 0377-2217 es_ES
dc.identifier.uri http://hdl.handle.net/10251/156318
dc.description.abstract [EN] The container pre-marshalling problem involves the sorting of containers in stacks so that there are no blocking containers and retrieval is carried out without additional movements. This sorting process should be carried out in as few container moves as possible. Despite recent advancements in solving real world sized problems to optimality, several classes of pre-marshalling problems remain difficult for exact approaches. We propose a branch and bound algorithm with new components for solving such difficult instances. We strengthen existing lower bounds and introduce two new lower bounds that use a relaxation of the pre-marshalling problem to provide tight bounds in specific situations. We introduce generalized dominance rules that help reduce the search space, and a memoization heuristic that finds feasible solutions quickly. We evaluate our approach on standard benchmarks of pre-marshalling instances, as well as on a new dataset to avoid overfitting to the available data. Overall, our approach optimally solves many more instances than previous work, and finds feasible solutions on nearly every problem it encounters in limited CPU times. es_ES
dc.description.sponsorship The authors thank the Paderborn Center for Parallel Computation (PC2) for the use of the Arminius cluster for the computational study in this work. This work has been partially supported by the Spanish Ministry of Science, Innovation, and Universities FPU Grant A-2015-12849 and by the Spanish Ministry of Economy and Competitiveness, under projects DPI2014-53665-P and DPI2015-65895-R, partially financed with FEDER funds. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation MINECO/DPI2014-53665-P es_ES
dc.relation MICINN/A-2015-12849 es_ES
dc.relation MINISTERIO DE ECONOMIA Y EMPRESA/DPI2015-65895-R es_ES
dc.relation AEI/RTI2018-094940-B-I00-AR es_ES
dc.relation.ispartof European Journal of Operational Research es_ES
dc.rights Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) es_ES
dc.subject Logistics es_ES
dc.subject Container pre-marshalling es_ES
dc.subject Maritime applications es_ES
dc.subject Terminal operations es_ES
dc.subject.classification ESTADISTICA E INVESTIGACION OPERATIVA es_ES
dc.title A branch and bound approach for large pre-marshalling problems es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/j.ejor.2019.04.005 es_ES
dc.rights.accessRights Embargado es_ES
dc.date.embargoEndDate 2021-10-01 es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat es_ES
dc.description.bibliographicCitation Tanaka, S.; Tierney, K.; Parreño-Torres, C.; Alvarez-Valdes, R.; Ruiz García, R. (2019). A branch and bound approach for large pre-marshalling problems. European Journal of Operational Research. 278(1):211-225. https://doi.org/10.1016/j.ejor.2019.04.005 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1016/j.ejor.2019.04.005 es_ES
dc.description.upvformatpinicio 211 es_ES
dc.description.upvformatpfin 225 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 278 es_ES
dc.description.issue 1 es_ES
dc.relation.pasarela S\405876 es_ES
dc.contributor.funder AGENCIA ESTATAL DE INVESTIGACION es_ES
dc.contributor.funder MINISTERIO DE ECONOMIA Y EMPRESA es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder Ministerio de Ciencia, Innovación y Universidades es_ES


This item appears in the following Collection(s)

Show simple item record