A branch and bound approach for large pre-marshalling problems

Tanaka S, Tierney K, Parreno-Torres C, Alvarez-Valdes R, Ruiz R (In Press)
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 278(1): 211-225.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Im Druck | Englisch
Autor
; ; ; ;
Abstract / Bemerkung
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. (C) 2019 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Band
278
Ausgabe
1
Seite(n)
211-225
ISSN
eISSN
PUB-ID

Zitieren

Tanaka S, Tierney K, Parreno-Torres C, Alvarez-Valdes R, Ruiz R. A branch and bound approach for large pre-marshalling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. In Press;278(1):211-225.
Tanaka, S., Tierney, K., Parreno-Torres, C., Alvarez-Valdes, R., & Ruiz, R. (In Press). A branch and bound approach for large pre-marshalling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 278(1), 211-225. doi:10.1016/j.ejor.2019.04.005
Tanaka, S., Tierney, K., Parreno-Torres, C., Alvarez-Valdes, R., and Ruiz, R. (In Press). A branch and bound approach for large pre-marshalling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 278, 211-225.
Tanaka, S., et al., In Press. A branch and bound approach for large pre-marshalling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 278(1), p 211-225.
S. Tanaka, et al., “A branch and bound approach for large pre-marshalling problems”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 278, In Press, pp. 211-225.
Tanaka, S., Tierney, K., Parreno-Torres, C., Alvarez-Valdes, R., Ruiz, R.: A branch and bound approach for large pre-marshalling problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. 278, 211-225 (In Press).
Tanaka, Shunji, Tierney, Kevin, Parreno-Torres, Consuelo, Alvarez-Valdes, Ramon, and Ruiz, Ruben. “A branch and bound approach for large pre-marshalling problems”. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 278.1 (In Press): 211-225.