Abstract
Bin packing problems make up an important topic of optimization problems. Their pioneering studies began in the seventies with a number of important works [1,2]. Fundamentally, their aim is to accommodate a set of items into a set of bins in order to optimize a given objective function while satisfying a number of constraints. Moreover, capacity constraints ensure that bin capacities are not exceeded. Nowadays, we are witnessing a particular trend concerning bin packing problems. While, at the beginning of the research, bin packing problems were mainly conceived as loading problems at an operational level, the evolution of problem formulations allows us to use bin packing problems in the field of Transportation and Logistics, both at an operational and tactical level, taking also into account economical and management aspects [3]. This evolution of the problem settings pushed researchers to address more sophisticated problems such as the Generalized Bin Packing Problem (GBPP) and the Generalized Bin Packing Problem with bin-dependent item profits (GBPPI) [4]. In this paper, we present the last advances of the GBPPI in the field of Transportation and Logistics. In particular, we present new methodologies and bounds, which allow us to better estimate gaps for large-size instances.
Authors: Baldi M.M., Gobbato L., Perboli G., Tadei R.
References
[1] M. R. Garey, R. L. Graham and J. D. Ullman. Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, STOC ’72 pp. 143-150, New York, NY, USA (1972).
[2] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3(4), pp. 299-325 (1974).
[3] V. Cacchiani, J.J. Salazar-Gonz´alez. Optimal solutions to a real-world integrated airline scheduling problem, Transportation Science, doi:10.1287/trsc.2015.0655.
[4] G. Perboli, L. Gobbato, and F. Perfetti. Packing problems in transportation and supply chain: new problems and trends, Procedia-Social and Behavioral Sciences, 111, pp. 672-681 (2014).
[5] M. M. Baldi, T. G. Crainic, G. Perboli and R. Tadei. The generalized bin packing problem, Transportation Research Part E: Logistics and Transportation Review, 48(6), pp. 1205-1220 (2012).
Conference AIRO 2016 – 46th Annual Conference of the Italian Operational Research Society – Emerging Advances in Logistics Systems Trieste, September 6-9, 2016
Year of publication 2016
