A Mathematical Model for Container Loading Problem with Milkrun Transportation Side Constraints

Öz

Container Loading Problem is one of the common problems encountered in logistics under Cutting and Packing Problem category. Particularly, the versions with more side constraints are considered as Non-Deterministic Polynomial-Time (NP) Hard problem. In this research, an original Container Loading Problem, which finds a solution to the spare-part transportation problem of a company, is modeled and solved. Since the main problem has lots of variables and constraints, the solving time of the problem gets larger. Therefore, the main problem is divided into two parts and tried to be solved sequentially. Whereas the first problem is used for the allocation of the boxes into the containers and the tours of the trucks, the second problem is used for the stowage of the boxes into the used containers. When both problems are solved sequentially, the output of the first problem is provided as the input to the second problem. Finally, the results are benchmarked with the lower bound on the required number of containers. The medium size test problem, built with synthetic data, is solved with the two models sequentially and a feasible near-optimal solution is found in the reasonable time. Keywords: Vehicle Routing Problem, Rectangular Container Loading Problem, Cutting and Packing Problem, Knapsack Problem, Cutting Stock Problem, Milkrun System

Anahtar Kelimeler

• Vehicle Routing Problem
• Rectangular Container Loading Problem
• Cutting and Packing Problem
• Knapsack Problem
• Cutting Stock Problem
• Milkrun System

Döngüsel Taşıma Sistemi Yan Kısıtlarına Sahip Konteyner Yükleme Problemi için Bir Model Önerisi

Öz

Konteyner Yükleme Problemi, Kesme ve Paketleme Problemleri altında incelenen ve taşımacılıkta yaygın olarak kullanılan problemlerden biridir. Özellikle fazla sayıda yan kısıtlara sahip versiyonları NP-zor problemler kategorisindedir. Bu çalışmada, bir lojistik firmasının yedek parça taşıma problemini çözen özgün bir Konteyner Yükleme Problemi modellenerek, çözülmüştür. Ana problemin içermiş olduğu değişken ve kısıt sayısı fazla olduğu için çözüm süresi çok uzamaktadır. Bu nedenle ana problem ikiye bölünerek ardışık olarak çözülmeye çalışılmıştır. Birinci problem, konteynerler içerisine konulacak kutuların ayrımını ve kullanılacak tırların turlarını bulurken, ikinci problem, ayrılan kutuların konteynerlerin içerisine yerleşimini sağlamaktadır. İki problem ardışık olarak çözülürken, birinci problemin çıktısı, ikinci probleme girdi olarak verilmektedir. Daha sonra bulunan sonuç, bütün paketlerin yüklenmesi için gerekli olan konteyner sayısının alt sınırıyla karşılaştırılarak sonuçların performans değerlendirilmesi yapılmıştır. Sentetik olarak oluşturulan orta ölçekli test problemi, iki model ile ardışık olarak çözülmüş ve makul bir sürede çözülebilen, en iyi çözüme çok yakın uygun bir çözüm bulunmuştur. Anahtar Kelimeler: Araç Rotalama Problemi, Dikdörtgensel Konteyner Yükleme Problemi, Kesme ve Paketleme Problemi, Sırt Çantası Problemi, Stok Kesme Problemi, Döngüsel Taşıma Sistemi

Anahtar Kelimeler

• Araç Rotalama Problemi
• Dikdörtgensel Konteyner Yükleme Problemi
• Kesme ve Paketleme Problemi
• Sırt Çantası Problemi
• Stok Kesme Problemi
• Döngüsel Taşıma Sistemi

Kaynakça

1. Abdou, G., & Elmasry, M. (1999). 3D random stacking of weakly heterogeneous palletization problems. International Journal of Production Research, 37, 1505- 1524.
2. Alonso, M. T., Alvarez-Valdes, R., Iori, M., & Parreno, F. (2019). Mathematical models for multi-container loading problems with practical constraints. Computers & Industrial Engineering, 127, 722-733.
3. Amossen, R. R., & Pisinger, D. (2010). Multi-dimensional bin packing problems with guillotine constraints. Computers & Operations Research, 37, 1999-2006.
4. Bischoff, E., & Ratcliff, M. S. W. (1995). Issues in the development of approaches to container loading. Omega, 23, 377-390.
5. Bortfeldt, A., & Gehring, H. (1999). Two metaheuristics for strip packing problems. In D. K. Despotis & C. Zopounidis (Eds.), Proceedings of the 5th International Conference of the Decision Science Institute (pp. 1153- 1156).
6. Bortfeldt, A., & Wascher, G. (2012). Container loading problems – A state-of-the-art review (Working Paper Series No. 7/2012).
7. Carpenter, H., & Dowsland, W. B. (1985). Practical considerations of the pallet loading problem. Journal of the Operational Research Society, 36, 486-497.
8. Chan, F. T. S., Bhagwat, R., Kumar, N., Tiwari, M. K., & Lam, P. (2006). Development of a decision support system for air-cargo pallets loading problem. Expert Systems with Applications, 31, 472-485.

9. Chen, C., Lee, S., & Chen, Q. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80(1), 68-76.
10. Chien, C., & Deng, J. (2004). A container packing support system for determining and visualising container packing patterns. Decision Support Systems, 37, 23-34.
11. Davies, A., & Bischoff, E. E. (1999). Weight distribution considerations in container loading. European Journal of Operational Research, 114, 509-527.
12. Deplano, I., Lersteau, C., & Nguyen, T. T. (2021). A mixedinteger model for the multiple heterogeneous knapsack problem with realistic container loading constraints and bins’ priority. International Transactions in Operational Research, 28, 3244-3275.
13. Egeblad, J., Garavelli, C., Lisi, L., & Pisinger, D. (2010). Heuristics for container loading of furniture. European Journal of Operational Research, 200, 881-892.
14. Eley, M. (2003). A bottleneck assignment approach to the multiple container loading problem. OR Spectrum, 25, 45-60.
15. Fanslau, T., & Bortfeldt, A. (2010). A tree-search algorithm for solving the container loading problem. INFORMS Journal on Computing, 22, 222-235.
16. Fekete, S. P., Schepers, J., & van der Veen, J. C. (2007). An exact algorithm for higher-dimensional orthogonal packing. Operations Research, 55, 569-587.
17. Fuellerer, G., Doerner, K., Hartl, R. F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with threedimensional loading constraints. European Journal of Operational Research, 201, 751-759.
18. Gajda, M., Trivella, A., Mansini, R., & Pisinger, D. (2022). An optimization approach for a complex real-life container loading problem. Omega, 107, 102559. https://doi.org/10.1016/j.omega.2021.102559
19. Gehring, H., & Bortfeldt, A. (1997). A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 4, 401-418.
20. Gimenez-Palacios, I., Alonso, M. T., Alvarez-Valdes, R., & Parreno, F. (2023). Multicontainer loading problems with multidrop and split delivery conditions. Computers & Industrial Engineering, 175, 108844. https://doi.org/10.1016/j.cie.2022.108844
21. Girlich, E., & Tarnowski, A. G. (1994). Zur Effektivität von Gradientenverfahren für Zuschnittprobleme. OR Spectrum, 16, 211-221.
22. Goncalves, J. F., & Resende, M. G. C. (2012). A parallel multi-population biased random key genetic algorithm for a container loading problem. Computers & Operations Research, 39, 179-190.
23. He, K., & Huang, W. (2011). An efficient placement heuristic for three-dimensional rectangular packing. Computers & Operations Research, 38, 227-233.
24. Hemminki, J., Leipala, T., & Nevalainen, O. (1998). On-line packing with boxes of different size. International Journal of Production Research, 36, 2225-2245.
25. Hifi, M. (2004). Exact algorithms for unconstrained threedimensional cutting problems: A comparative study. Computers & Operations Research, 31, 657-674.
26. Hodgson, T. J. (1982). A combined approach to the pallet loading problem. IIE Transactions, 14, 175-182.
27. Junqueira, L., Morabito, R., & Yamashita, D. S. (2012). Three-dimensional container loading models with cargo stability and load bearing constraints. Computers & Operations Research, 39, 74-85.
28. Jiao, G., Huang, M., Song, Y., Li, H., & Wang, X. (2024). Container loading problem based on robotic loader system: An optimization approach. Expert Systems with Applications, 236, 121222. https://doi.org/10.1016/j.eswa.2023.121222
29. Liu, J., Yue, Y., Dong, Z., Maple, C., & Keech, M. (2011). A novel hybrid tabu search approach the container loading. Computers & Operations Research, 38, 797- 807.
30. Makarem, O. C., & Haraty, R. A. (2010). Smart container loading. Journal of Computational Methods in Science and Engineering, 10, 231-245.
31. Martello, S., Pisinger, D., & Vigo, D. (2000). The threedimensional bin packing problem. Operations Research, 48, 256-267.
32. Morabito, R., & Arenelas, M. (1994). An AND/OR-graph approach to the container loading problem. International Transactions in Operational Research, 1, 59-73.
33. Moura, A., & Oliveira, J. F. (2009). An integrated approach to the vehicle routing and container loading problems. OR Spectrum, 31, 775-800.
34. Nascimento, O. X., Queiroz, T. A., & Junqueira, L. (2021). Practical constraints in the container loading problem: Comprehensive formulations and exact algorithms. Computers & Operations Research, 128, 105-186.
35. Ngoi, B. K. A., Tay, M. L., & Chua, E. S. (1994). Applying spatial representation techniques to the container packing problem. International Journal of Production Research, 32, 111-123.
36. Padberg, M. (2000). Packing small boxes into a big box. Mathematical Methods of Operations Research, 52, 1- 21.
37. Parreno, F., Alvarez-Valdes, R., Tamarit, J. M., & Oliveira, J. F. (2008). A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 20, 412-422.
38. Pisinger, D. (2002). Heuristics for the container loading problem. European Journal of Operational Research, 141, 382-392.
39. Techanitisawad, A., & Tangwiwatwong, P. (2004). A GAbased heuristic for interrelated container selection loading problems. Industrial Engineering and Management Systems, 3, 22-37.
40. Terno, J., Scheithauer, G., Sommerweiss, U., & Riehme, J. (2000). An efficient approach for the multi-pallet loading problem. European Journal of Operational Research, 123, 372-381.
41. Tsai, D. M. (1987). Modelling and analysis of threedimensional robotic palletizing systems for mixed carton sizes [Doctoral dissertation]. Iowa State University.
42. Wascher, G., Hausner, H., & Schuman, H. (2007). An improved topology of cutting and packing problems. European Journal of Operational Research, 183, 1109- 1130.