•We address the Generalized Bin Packing Problem with bin-dependent item profits.•This problem arises in the last-mile urban parcel delivery service.•We provide a Mixed Integer Formulation of the ...problem and efficient heuristics.•A last-mile logistics case of an international courier is given.
In this paper, we present a new problem arising at a tactical level of setting a last-mile parcel delivery service in a city by considering different Transportation Companies (TC), which differ in cost and service quality. The courier must decide which TCs to select for the service in order to minimize the total cost and maximize the total service quality. We show that the problem can be modeled as a new packing problem, the Generalized Bin Packing Problem with bin-dependent item profits (GBPPI), where the items are the parcels to deliver and the bins are the TCs. The aim of the GBPPI is to select the appropriate fleet from TCs and determine the optimal assignment of parcels to vehicles such that the overall net cost is minimized. This cost takes into account both transportation costs and service quality. We provide a Mixed Integer Programming formulation of the problem, which is the starting point for the development of efficient heuristics that can address the GBPPI for instances involving up to 1000 items. Extensive computational tests show the accuracy of the proposed methods. Finally, we present a last-mile logistics case study of an international courier which addresses this problem.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The κ-exponential function, representing a generalization of the exponential function, has been firstly introduced in physics, and, then, it has been considered in a noteworthy number of fields ...because of its ability to take rare events into account. Among the possible applications of this function, one of particular interest is in economics in which rare events may consist in natural disasters, such as earthquakes that reduce the supply of capital, or epidemics or other external shocks influencing the supply of intermediate inputs, human or physical capital. Starting from the κ-exponential function, the κ-logistic function, which is a generalization of the sigmoidal function, can be obtained and used to describe production functions in a unique setting to take into account (1) several shapes usually considered in economics (i.e. concave and non-concave production functions), (2) economies at different development levels, and, (3) the possible occurrence of rare events. In this paper, we investigate the economic growth model as proposed by Böhm and Kaas (2000), wherein the production function utilizes the κ-logistic function. We provide theoretical results confirmed by extensive computational experiments and in line with economic literature showing that a poverty trap may emerge together with fluctuations, multistability and complex dynamics.
•The κ-logistic production function is a generalization of the sigmoidal production function.•Economic growth is considered across various levels of development.•Non-concave production functions can lead to the occurrence of multistability and complex dynamics.•The poverty trap can be exhibited.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this paper we introduce a new packing problem, the three-dimensional knapsack problem with balancing constraints (3BKP), the extension of the three-dimensional knapsack problem (3KP) where ...additional constraints related to the packing center of mass are given. The 3BKP consists in orthogonally packing a subset of three-dimensional weighted items into a knapsack in order to maximize the total profit of the loaded items. The items must not overlap and the packing center of mass must lie into a predefined boxed domain inside the knapsack. We assume that items can be rotated. We give a MIP model for the problem, upper bounds and an efficient heuristic to solve large size instances. The computational results show that the MIP model cannot find optimal solutions, except for small size instances, but it can be used to calculate upper and lower bounds. It is shown that our heuristic outperforms the solution quality both of the MIP model and the heuristics available in the literature explicitly designed to solve the 3KP.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
On the generalized bin packing problem Baldi, Mauro Maria; Bruglieri, Maurizio
International transactions in operational research,
20/May , Volume:
24, Issue:
3
Journal Article
Peer reviewed
Open access
The generalized bin packing problem (GBPP) is a novel packing problem arising in many transportation and logistic settings, characterized by multiple items and bins attributes and the presence of ...both compulsory and non‐compulsory items. In this paper, we study the computational complexity and the approximability of the GBPP. We prove that the GBPP cannot be approximated by any constant, unless P=NP. We also study the particular case of a single bin type and show that when an unlimited number of bins is available, the GBPP can be reduced to the bin packing with rejection (BPR) problem, which is approximable. We also prove that the GBPP satisfies Bellman's optimality principle and, exploiting this result, we develop a dynamic programming solution approach. Finally, we study the behavior of standard and widespread heuristics such as the first fit, best fit, first fit decreasing, and best fit decreasing. We show that while they successfully approximate previous versions of bin packing problems, they fail to approximate the GBPP.
Full text
Available for:
FZAB, GIS, IJS, IZUM, KILJ, NLZOH, NUK, OILJ, PILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
The generalized bin packing problem Baldi, Mauro Maria; Crainic, Teodor Gabriel; Perboli, Guido ...
Transportation research. Part E, Logistics and transportation review,
11/2012, Volume:
48, Issue:
6
Journal Article
Peer reviewed
Open access
► This problem arises in packing, transportation, and logistics. ► It considers both bin costs and item profits at the same time. ► It generalizes several bin packing and knapsack problems. ► ...Efficient lower and upper bounds are introduced. ► The proposed procedures solve a large set of instances.
In the Generalized Bin Packing Problem (GBPP), given two sets of compulsory and non-compulsory items characterized by volume and profit and a set of bins with given volume and cost, we want to select the subset of profitable non-compulsory items to be loaded together with the compulsory ones into the appropriate bins in order to minimize the total net cost. Lower and upper bounds to the GBPP are given. The results of extensive computational experiments show that the proposed procedures are efficient and the bounds are tight.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
In the Variable Cost and Size Bin Packing Problem with optional items, a set of items characterized by volume and profit and a set of bins of different types characterized by volume and cost are ...given. The goal consists in selecting those items and bins which optimize an objective function which combines the cost of the used bins and the profit of the selected items. We propose two methods to tackle the problem: branch-and-price as an exact method and beam search as a heuristics, derived from the branch-and-price. Our branch-and-price method is characterized by a two level branching strategy. At the first level the branching is performed on the number of available bins for each bin type. At the second level it consists on pairs of items which can or cannot be loaded together. Exploiting the branch-and-price skeleton, we then present a variegated beam search heuristics, characterized by different beam sizes. We finally present extensive computational results which show a high accuracy of the exact method and a very good efficiency of the proposed heuristics.
The regular pentagon had a symbolic meaning in the Pythagorean and Platonic philosophies and a subsequent important role in Western thought, appearing also in arts and architecture. A property of ...regular pentagons, which was probably discovered by the Pythagoreans, is that the ratio between the diagonal and the side of these pentagons is equal to the golden ratio. Here, we will study some relations existing between a regular pentagon and this ratio. First, we will focus on the group of fivefold rotational symmetry, to find the position in the complex plane of the vertices of this geometric figure. Then, we will propose an analytic method to solve the same problem based on the Cartesian coordinates, a method where we find the golden ratio without any specific geometric consideration. This study shows a comparison of the use of complex numbers, symmetries and analytic methods, applied to a subject which can be interesting for general education in mathematics. In fact, the proposed approach can convey and link several concepts, requiring only a general pre-college education, showing at the same time the richness that mathematics can offer in solving geometric problems.
Full text
Available for:
BFBNIB, GIS, IJS, KISLJ, NUK, PNG, UL, UM, UPUK
The problem consists in finding a transshipment facilities location that maximizes the total net utility when the handling utilities at the facilities are stochastic variables, under supply, demand, ...and lower and upper capacity constraints. The total net utility is given by the expected total shipping utility minus the total fixed cost of the located facilities. Shipping utilities are given by a deterministic utility for shipping freight from origins to destinations via transshipment facilities plus a stochastic handling utility at the facilities, whose probability distribution is unknown. After giving the stochastic model, by means of some results of the extreme values theory, the probability distribution of the maximum stochastic utilities is derived and the expected value of the optimum of the stochastic model is found. An efficient heuristics for solving real‐life instances is also given. Computational results show a very good performance of the proposed methods both in terms of accuracy and efficiency.
Full text
Available for:
FZAB, GIS, IJS, IZUM, KILJ, NLZOH, NUK, OILJ, PILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
We present a worst case analysis for the Generalized Bin Packing Problem, a novel packing problem arising in many Transportation and Logistics settings, characterized by multiple item and bin ...attributes and by the joint presence of both compulsory and non-compulsory items. The contribution of this paper is twofold: we conduct a worst case analysis applied to the much richer Generalized Bin Packing Problem of two outstanding bin packing algorithms (the First Fit Decreasing and the Best Fit Decreasing algorithms) arising in Transportation and Logistics, and we propose two semi-online algorithms also arising in the fields of Transportation and Logistics. We also show how knowing part of the instance or the whole instance is not enough for computing worst case ratio bounds.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
