Abstract
In this paper, an exact method is designed to solve the multi-objective 2-dimensional vector packing problem. The algorithm is an adapted version of an efficient \(\epsilon \)-constraint method which proves its efficiency in solving a large variety of multi-objective optimization problems. This method is based on a clever decomposition of the initial problem into sub-problems which are iteratively solved through mathematical programming. To accelerate the search process, we propose a new integer programming model for solving the multi-objective 2-dimensional vector packing problem based on the compact model for the bin packing problem with fragile objects. Instead of scanning all possible solutions, we consider the solutions while solving a Subset-Sum Problem. Hence, non-useful subproblems are avoided and thus the search space is reduced. An experimental study is performed based instances from the literature. A comparison between the exact method and a grounded metaheuristic which provides good results in solving the multi-objective 2-dimensional vector packing problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Caprara, A., Toth, P.: Lower bounds and algorithms for the 2-dimensional vector packing problem. Discret. Appl. Math. 111(3), 231–262 (2001)
Clautiaux, F., Dell’Amico, M., Iori, M., Khanafer, A.: Lower and upper bounds for the bin packing problem with fragile objects. Discret. Appl. Math. 163(1), 73–86 (2014)
Dahmani, N., Clautiaux, F., Krichen, S., Talbi, E.G.: Iterative approaches for solving a multi-objective 2-dimensional vector packing problem. Comput. Ind. Eng. 66(1), 158–170 (2013)
Dahmani, N., Clautiaux, F., Krichen, S., Talbi, E.G.: Self-adaptive metaheuristics for solving a multi-objective 2-dimensional vector packing problem. Appl. Soft Comput. 16, 124–136 (2014)
Ehrgott, M.: A discussion of scalarization techniques for multiple objective integer programming. Ann. Oper. Res. 147, 343–360 (2006)
Ehrgott, M., Tenfelde-Podehl, D.: Computation of ideal and Nadir values and implications for their use in MCDM methods. Eur. J. Oper. Res. 151, 119–139 (2003)
Ehrgott, M., Gandibleux, X., Przybylski, A.: International series in operations research and management science. In: Exact methods for Multi-objective Combinatorial Optimisation, pp. 817–850. Springer (2016)
Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (Series of Books in the Mathematical Sciences). Freeman, W. H (1979)
Haimes, Y., Lasdon, L., Wismer, D.: On a bicriterion formulation of the problems of integrated system identification and system optimization. 1(3), 296–297 (1971)
Levin, M.S.: Bin packing problems (promising models and examples). J. Commun. Technol. Electron. 63(6), 655–666 (2018)
Liefooghe, A., Basseur, M., Jourdan, L., Talbi, E.G.: ParadisEO-MOEO: a framework for evolutionary multi-objective optimization. In: Obayashi, S., Poloni, C., Deb, K. (eds.) Evolutionary Multi-Criterion Optimization, Fourth International Conference (EMO 2007), vol. 4403 of LNCS., Matsushima, Japan, pp. 386–400. Springer (2007)
Mavrotas, G., Florios, K.: An improved version of the augmented \(\epsilon \)-constraint method (augmecon2) for finding the exact pareto set in multi-objective integer programming problems. Appl. Math. Comput. 219(18), 9652–9669 (2013)
Naderi, B., Yazdani, M.: A real multi-objective bin packing problem: a case study of an engine assembly line. Arab. J. Sci. Eng. 39(6), 5271–5277 (2014)
Turgut, O., Dalkiran, E., Murat, A.E.: An exact parallel objective space decomposition algorithm for solving multi-objective integer programming problems. J. Global Optim. 75, 35–62 (2019)
Reeves, G.R., Reid, R.C.: Minimum values over the efficient set in multiple objective decision making. Eur. J. Oper. Res. 36(3), 334–338 (1988)
Spencer, K.Y., Tsvetkov, P.V., Jarrell, J.J.: A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects. J. Heuristics 25(1), 1–45 (2019)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. Evol. Comput. 7, 117–132 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dahmani, N., Krichen, S., Talbi, EG., Kaddoura, S. (2021). Solving the Multi-objective 2-Dimensional Vector Packing Problem Using \(\epsilon \)-constraint Method. In: Rocha, Á., Adeli, H., Dzemyda, G., Moreira, F., Ramalho Correia, A.M. (eds) Trends and Applications in Information Systems and Technologies. WorldCIST 2021. Advances in Intelligent Systems and Computing, vol 1368. Springer, Cham. https://doi.org/10.1007/978-3-030-72654-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-72654-6_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72653-9
Online ISBN: 978-3-030-72654-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)