article

Local search for a multi-drop multi-container loading problem

Authors:

Sara Ceschia,

Andrea SchaerfAuthors Info & Claims

Journal of Heuristics, Volume 19, Issue 2

Pages 275 - 294

https://doi.org/10.1007/s10732-011-9162-6

Published: 01 April 2013 Publication History

Abstract

We consider a complex variant of the Container Loading Problem arising from a real-world industrial application. It includes several features such as multiple containers, box rotation, and bearable weight, which are of importance in many practical situations. In addition, it also considers the situation in which boxes have to be delivered to different destinations (multi-drop).

Our solution technique is based on local search metaheuristics. Local search works on the space of sequences of boxes to be loaded, while the actual load is obtained by invoking, at each iteration, a specialized procedure called loader. The loader inserts the boxes in the container using a deterministic heuristic which produces a load that is feasible according to the constraints.

We test our solver on real-world instances provided by our industrial partner, showing a clear improvement on the previous heuristic solution. In addition, we compare our solver on benchmarks from the literature on the basic container loading problems. The outcome is that the results are in some cases in-line with the best ones in the literature and for other cases they also improve upon the best known ones. All instances and solutions are made available on the web for future comparisons.

References

[1]

Aarts, E.H., Korst, J., van Laarhoven, P.J.: Simulated annealing. In: Aarts, E.H., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. Wiley, Chichester (1997).

Google Scholar

[2]

Bischoff, E.: Three-dimensional packing of items with limited load bearing strength. J. Oper. Res. 168(3), 952-966 (2006).

Crossref

Google Scholar

[3]

Bischoff, E.E., Ratcliff, M.S.W.: Issues in the development of approaches to container loading. Omega 23(4), 377-390 (1995).

Crossref

Google Scholar

[4]

Bischoff, E.E., Janetz, F., Ratcliff, M.S.W.: Loading pallets with non-identical items. Eur. J. Oper. Res. 84(3), 681-692 (1995).

Crossref

Google Scholar

[5]

Bortfeldt, A.: A heuristic for multiple container loading problems. OR Spektrum 22, 239-261 (2000). In German.

Crossref

Google Scholar

[6]

Bortfeldt, A., Gehring, H.: A tabu search algorithm weakly heterogeneous container loading problem. OR Spektrum 20, 237-250 (1998). In German.

Google Scholar

[7]

Bortfeldt, A., Gehring, H.: A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131(1), 143-161 (2001).

Crossref

Google Scholar

[8]

Bortfeldt, A., Homberger, J.: Packing first, routing second--a heuristic for the vehicle routing and loading problem. In: Bortfeldt, A., Homberger, J., Kopfer, H., Pankratz, G., Strangmeier, R. (eds.) Intelligent Decision Support--Current Challenges and Approaches, Intelligente Entscheidungsunterstützung--Aktuelle Herausforderungen und LösungsansätzeIntelligent Decision Support, pp. 91-113. Deutscher Universitäts-Verlag, Wiesbaden (2008). In German.

Google Scholar

[9]

Bortfeldt, A., Gehring, H., Mack, D.: A parallel tabu search algorithm for solving the container loading problem. Parallel Comput. 29(5), 641-662 (2003).

Digital Library

Google Scholar

[10]

Davies, A.: Approaches to the container loading problem. PhD thesis, University of Wales, Swansea (2000).

Google Scholar

[11]

Davies, A.P., Bischoff, E.E.: Weight distribution considerations in container loading. Eur. J. Oper. Res. 114(3), 509-527 (1999).

Crossref

Google Scholar

[12]

Eglese, R.: Simulated annealing: a tool for operations research. Eur. J. Oper. Res. 46, 271-281 (1990).

Crossref

Google Scholar

[13]

Eley, M.: Solving container loading problems by block arrangement. Eur. J. Oper. Res. 141(2), 393-409 (2002).

Crossref

Google Scholar

[14]

Eley, M.: A bottleneck assignment approach to the multiple container loading problem. OR Spektrum 25(1), 45-60 (2003).

Crossref

Google Scholar

[15]

Fanslau, T., Bortfeldt, A.: A tree search algorithm for solving the container loading problem. INFORMS J. Comput. 22(2), 222-235 (2010).

Digital Library

Google Scholar

[16]

Fuellerer, G., Doerner, K.F., Hartl, R.F., Iori, M.: Metaheuristics for vehicle routing problems with three-dimensional loading constraints. Eur. J. Oper. Res. 201(3), 751-759 (2010).

Crossref

Google Scholar

[17]

Gehring, H., Bortfeldt, A.: A parallel genetic algorithm for solving the container loading problem. Int. Trans. Oper. Res. 9(4), 497-511 (2002).

Crossref

Google Scholar

[18]

Gendreau, M., Iori, M., Laporte, G., Martello, S.: A tabu search algorithm for a routing and container loading problem. Transp. Sci. 40(3), 342-350 (2006).

Digital Library

Google Scholar

[19]

George, J.A., Robinson, D.F.: A heuristic for packing boxes into a container. Comput. Oper. Res. 7(3), 147-156 (1980).

Crossref

Google Scholar

[20]

Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1997).

Crossref

Google Scholar

[21]

Hoos, H.H., Stützle, T.: Stochastic Local Search--Foundations and Applications. Morgan Kaufmann, San Francisco (2005).

Crossref

Google Scholar

[22]

Ivancic, N., Mathur, K., Mohanty, B.: An integer programming based heuristic approach to the three-dimensional packing problem. J. Manuf. Oper. Manag. 2(4), 268-298 (1989).

Google Scholar

[23]

Kirkpatrick, S., Gelatt, C.D. Jr., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671-680 (1983).

Crossref

Google Scholar

[24]

Mack, D., Bortfeldt, A., Gehring, H.: A parallel hybrid local search algorithm for the container loading problem. Int. Trans. Oper. Res. 11(5), 511-533 (2004).

Crossref

Google Scholar

[25]

Moura, A., Oliveira, J.F.: A grasp approach to the container-loading problem. IEEE Intell. Syst. 20, 50-57 (2005).

Digital Library

Google Scholar

[26]

Moura, A., Oliveira, J.F.: An integrated approach to the vehicle routing and container loading problems. OR Spektrum 31(4), 775-800 (2009).

Crossref

Google Scholar

[27]

Parreño, F., Alvarez-Valdes, R., Oliveira, J., Tamarit, J.: A maximal-space algorithm for the container loading problem. INFORMS J. Comput. 20(3), 412-422 (2008).

Digital Library

Google Scholar

[28]

Parreño, F., Alvarez-Valdes, R., Oliveira, J., Tamarit, J.: Neighborhood structures for the container loading problem: a VNS implementation. J. Heuristics 16(1), 1-22 (2010).

Digital Library

Google Scholar

[29]

Pisinger, D.: A tree search heuristic for the container loading problem. Ric. Oper. 28, 31-48 (1998).

Google Scholar

[30]

Pisinger, D.: Heuristics for the container loading problem. Eur. J. Oper. Res. 141, 382-392 (2002).

Crossref

Google Scholar

[31]

Raidl, G.R.: The multiple container packing problem: a genetic algorithm approach with weighted codings. ACM SIGAPP Appl. Comput. Rev. 7(2), 22-31 (1999).

Digital Library

Google Scholar

[32]

Raidl, G.R., Kodydek, G.: Genetic algorithms for the multiple container packing problem. In: PPSN V: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 875-884. Springer, London (1998).

Digital Library

Google Scholar

[33]

Ratcliff, M., Bischoff, E.: Allowing for weight considerations in container loading. OR Spektrum 20, 65-71 (1998).

Crossref

Google Scholar

[34]

Sang-Moon, S., Lee, S.-W., Yeo, G.-T., Jeon, M.-G.: An effective evolutionary algorithm for the multiple container packing problem. Prog. Nat. Sci. 18(3), 337-344 (2008).

Crossref

Google Scholar

[35]

Tarantilis, C., Zachariadis, E.E., Kiranoudis, C.T.: A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Trans. Intell. Trasp. Syst. 10(2), 1524-9050 (2009).

Crossref

Google Scholar

[36]

Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2002).

Crossref

Google Scholar

[37]

Venables, W.N., Ripley, B.D.: Modern Applied Statistics with S, 4th edn. Statistics and Computing. Springer, Berlin (2002).

Crossref

Google Scholar

[38]

Wang, L., Guo, S., Chen, S., Zhu, W., Lim, A.: Two natural heuristics for 3D packing with practical loading constraints. In: PRICAI 2010: Trends in Artificial, pp. 256-267 (2010).

Crossref

Google Scholar

[39]

Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3), 1109-1130 (2007).

Crossref

Google Scholar

Cited By

View all

Ceschia SDa Ros FDi Gaspero LSchaerf ALi XHandl J(2024)EasyLocal++ a 25-year Perspective on Local Search FrameworksProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664140(1658-1667)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664140
Zhang HLi QYao XLi XHandl J(2024)An Adaptive Interactive Routing-Packing Strategy for Split Delivery Vehicle Routing Problem with 3D Loading ConstraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3653991(249-257)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3653991
Jiao GHuang MSong YLi HWang X(2024)Container loading problem based on robotic loader systemExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121222236:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121222
Show More Cited By

Index Terms

Local search for a multi-drop multi-container loading problem

Recommendations

Neighborhood structures for the container loading problem: a VNS implementation

This paper presents a Variable Neighborhood Search (VNS) algorithm for the container loading problem. The algorithm combines a constructive procedure based on the concept of maximal-space, with five new movements defined directly on the physical layout ...
A hybrid simulated annealing algorithm for container loading problem
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation

This paper presents a hybrid simulated annealing algorithm for container loading problem with boxes of different sizes and single container for loading. A basic heuristic algorithm is introduced to generate feasible solution from a special structure ...
A tabu search algorithm for the quadratic assignment problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...

Reviews

Reviewer: Chaim M Scheff

Container loading problems (CLP) are interesting and easy to appreciate, and span from real-world to abstract mathematical variants. However, CLP is an NP-complete problem, so something as simple as comparing approaches, heuristics, and partial solutions arouses an instant migraine. This paper gives a wonderful lucid introduction to parameters, variations, and realistic applications for CLP. The volume of active hyperlinks in the paper may entice readers into spontaneous academic surfing of such great interest that one may lose track of the scope of the project and even begin thinking about CLP solution space tradeoffs. This paper magnificently presents complex CLP variants arising from practical industrial applications, such as multiple containers, box rotation, and bearable weight. Further heuristic intrigue comes from situations involving boxes being delivered to different destinations (multi-drop). The authors consider a CLP solution technique involving local search meta-heuristics, and conclude with a true sportsman-like comparison with others who have contributed to this fascinating field. So, much in the spirit of Lebesgue's original first chapter introducing measure theory to elementary education, CLP is a perfect problem for introducing the joys of applied mathematics into primary school. This paper should serve that community well, and it will just as well provide the university student with a forum for exploring and expressing mathematical thinking. Simply put, I recommend this must-read paper, even if it overlaps with many others, if only because the ideational development is presented clearly and the topic is easy to grasp and relevant. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Heuristics Volume 19, Issue 2

April 2013

321 pages

ISSN:1381-1231

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ceschia SDa Ros FDi Gaspero LSchaerf ALi XHandl J(2024)EasyLocal++ a 25-year Perspective on Local Search FrameworksProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664140(1658-1667)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664140
Zhang HLi QYao XLi XHandl J(2024)An Adaptive Interactive Routing-Packing Strategy for Split Delivery Vehicle Routing Problem with 3D Loading ConstraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3653991(249-257)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3653991
Jiao GHuang MSong YLi HWang X(2024)Container loading problem based on robotic loader systemExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121222236:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121222
Krebs CEhmke J(2021)Vertical Stability Constraints in Combined Vehicle Routing and 3D Container Loading ProblemsComputational Logistics10.1007/978-3-030-87672-2_29(442-455)Online publication date: 26-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-87672-2_29
Correcher JAlonso MParreo FAlvarez-Valdes R(2017)Solving a large multicontainer loading problem in the car manufacturing industryComputers and Operations Research10.1016/j.cor.2017.01.01282:C(139-152)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.cor.2017.01.012
Ahire SMalhotra MJensen J(2015)Carton-Mix Optimization for Walmart.com Distribution CentersInterfaces10.1287/inte.2015.079745:4(341-357)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1287/inte.2015.0797
Junqueira LMorabito R(2015)Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrierComputers and Industrial Engineering10.1016/j.cie.2015.06.00588:C(110-130)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.cie.2015.06.005
Ren ZJiang HZhang SZhang JLuo Z(2014)Boosting local search with Lagrangian relaxationJournal of Heuristics10.1007/s10732-014-9255-020:5(589-615)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s10732-014-9255-0
Nebel PRichter GWeicker KMoore J(2012)Multi-container loading with non-convex 3D shapes using a GA/TS hybridProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330321(1143-1150)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330321

Abstract

References

Cited By

Index Terms

Recommendations

Neighborhood structures for the container loading problem: a VNS implementation

A hybrid simulated annealing algorithm for container loading problem

A tabu search algorithm for the quadratic assignment problem

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations