×

New insights on the block relocation problem. (English) Zbl 1391.90096

Summary: This article presents new methods for the block relocation problem (BRP). Although much of the existing work focuses on the restricted BRP, we tackle the unrestricted BRP, which yields more opportunities for optimisation. Our contributions include fast heuristics able to tackle very large instances within seconds, fast metaheuristics that provide very competitive performance on benchmark data sets, as well as a new lower bound that generalises existing ones. We embed it in a branch-and-bound algorithm, then assess the influence of various factors on the efficiency of branch-and-bound algorithms for the BRP.

MSC:

90B06 Transportation, logistics and supply chain management
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming

Software:

BRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aydin, C.; Ünlüyurt, T., Improved rehandling strategies for the container retrieval process, J. Adv. Transp., 46, 4, 378-393, (2012)
[2] Caserta, M.; Schwarze, S.; Voss, S., A mathematical formulation and complexity considerations for the blocks relocation problem, Eur. J. Oper. Res., 219, 1, 96-104, (2012) · Zbl 1244.90164
[3] Caserta, M.; Voss, S.; Sniedovich, M., Applying the corridor method to a blocks relocation problem, OR Spectr., 33, 4, 915-929, (2011) · Zbl 1229.90019
[4] Expósito-Izquierdo, C.; Melin-Batista, B.; Moreno-Vega, J., A domain-specific knowledge-based heuristic for the blocks relocation problem, Adv. Eng. Inf., 28, 4, 327-343, (2014)
[5] Expósito-Izquierdo, C.; Melin-Batista, B.; Moreno-Vega, J., An exact approach for the blocks relocation problem, Expert Syst. Appl., 42, 17-18, 6408-6422, (2015)
[6] Forster, F.; Bortfeldt, A., A tree search procedure for the container relocation problem, Comput. Oper. Res., 39, 2, 299-309, (2012) · Zbl 1251.90050
[7] Holm, S., A simple sequentially rejective multiple test procedure, Scand. J. Stat. Theory Appl., 6, 2, 65-70, (1979) · Zbl 0402.62058
[8] Jin, B.; Zhu, W.; Lim, A., Solving the container relocation problem by an improved greedy look-ahead heuristic, Eur. J. Oper. Res., 240, 3, 837-847, (2015) · Zbl 1338.90052
[9] Jovanovic, R.; Voss, S., A chain heuristic for the blocks relocation problem, Comput. Ind. Eng., 75, 79-86, (2014)
[10] Kim, K. H.; Hong, G.-P., A heuristic rule for relocating blocks, Comput. Oper. Res., 33, 4, 940-954, (2006) · Zbl 1079.90079
[11] Lee, Y.; Lee, Y.-J., A heuristic for retrieving containers from a yard, Comput. Oper. Res., 37, 6, 1139-1147, (2010) · Zbl 1178.90234
[12] Lehnfeld, J.; Knust, S., Loading, unloading and premarshalling of stacks in storage areas: survey and classification, Eur. J. Oper. Res., 239, 2, 297-312, (2014) · Zbl 1339.90006
[13] Petering, M.; Hussein, M., A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem, Eur. J. Oper. Res., 231, 1, 120-130, (2013) · Zbl 1317.90211
[14] Tanaka, S.; Mizuno, F., Dominance properties for the unrestricted block relocation problem and their application to a branch-and-bound algorithm, IEEE International Conference on Automation Science and Engineering, CASE 2015, Gothenburg, Sweden, August 24-28, 2015, 509-514, (2015)
[15] Tanaka, S.; Takii, K., A faster branch-and-bound algorithm for the block relocation problem, Automation Science and Engineering (CASE), 2014 IEEE International Conference on, 7-12, (2014)
[16] The World Bank, 2014. http://data.worldbank.org/indicator/is.shp.good.tu/.
[17] Voss, S.; Fink, A.; Duin, C., Looking ahead with the pilot method, Ann. Oper. Res., 136, 1, 285-302, (2005) · Zbl 1114.90064
[18] Wu, K. C.; Ting, C. J., A beam search algorithm for minimizing reshuffle operations at container yards, Proceedings of the 2010 International Conference on Logistics and Maritime Systems, (2010)
[19] Zehendner, E.; Caserta, M.; Feillet, M.; Schwarze, S.; Voss, S., An improved mathematical formulation for the blocks relocation problem, Eur. J. Oper. Res., 245, 2, 415-422, (2015) · Zbl 1347.90058
[20] Zhu, W.; Qin, H.; Lim, A.; Zhang, H., Iterative deepening a* algorithms for the container relocation problem, IEEE Trans. Autom. Sci. Eng., 9, 4, 710-722, (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.