مسئله به حداقل رساندن هزینه های متعدد بارگذاری کانتینر

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.

Our team was contracted by a buying agent for a large multi-national retailer to investigate better ways to formulate packing plans for the loading of goods into multiple containers. The agent’s procurement department is responsible for ordering products from manufacturers located in Asia, inspecting the products to ensure quality, and finally shipping the products to retail stores spread across Europe. As a result, one of the procurement department’s tasks is to arrange the products for shipping. Typically, the goods are loaded into containers of various standard sizes with different costs. The task is to select a set of containers that can contain all items while minimizing the total shipping cost. This problem is a variant of a class of problems known as the multiple container loading problem (MCLP), also called the multiple container packing problem. The MCLP describes the scenario where, given a set of 3-D rectangular boxes of different types and a set of 3-D rectangular containers of different types, the objective is to store the boxes into the containers as efficiently as possible. There are many variants to the MCLP; the particular variant our paper addresses is referred to as the multiple container loading cost minimization problem (MCLCMP). The MCLCMP is defined as follows. We are given a number of rectangular containers of M types, represented by C1, C2, … , CM, that differ in terms of dimensions and cost. The cost for each type is given by c1, c2, … , cM, and there are an unlimited number of each container available. We are also given a number of rectangular boxes of N types with different dimensions, represented by B1, B2, … , BN; there are nj, 1 ⩽ j ⩽ N available boxes of type j. The objective of the MCLCMP is to produce a set of packing plans such that all boxes are orthogonally packed into the containers and the total cost of containers used is minimized. Our technique can also handle a limited number of containers (i.e., there are mt, 1 ⩽ t ⩽ M available containers of type t) with minor modifications (as detailed in Section 8). We do not consider supporting area constraints, although our approach can be modified to do so. Our approach is an extension of the integer linear programming formulation proposed by Eley (2003) for the MCLP. We add a new parameter to this formulation that controls the percentage of boxes to be packed, and perform a binary search on this variable. In addition, we devise three different strategies to quickly generate packing patterns for single containers along with a subroutine that augments the set of packing patterns while searching for solutions for the IP-problem. We tested this technique using the standard set of 47 bin-packing test instances proposed by Ivancic et al. (1989), and found that it produced superior results in comparison with other existing approaches. However, the optimal solutions for these test instances are unknown, and so we cannot evaluate the objective performance of our approach based on this test set. Hence, we also devise a technique for generating test instances for the MCLCMP with verifiably optimal known solutions. The remainder of this paper is organized as follows. We first provide an overview of the existing literature related to our study in Section 2. Our new parameterized linear integer programming formulation is presented in Section 3; we perform binary search on the parameter based on a number of generated packing patterns. Section 4 describes our three strategies for generating packing patterns, which are used by the binary search algorithm given in Section 5. In order to obtain a more objective evaluation of the strength of our approach, we describe a new technique in Section 6 for generating test instances for this problem with known optimal solutions. We test our approach on both the bin-packing instances used in current research and on our new instances, and present the results in Section 7. Our paper concludes in Section 8, where we suggest ways to further extend our technique to handle other variants of the MCLP.

This paper studies the multiple container loading cost minimization problem, which has the practical application of modeling the process whereby the buying agent for a multi-national retailer redistributes products after inspection. We added a loading factor parameter to the set cover formulation by Eley (2003) to exploit the excess capacity of the chosen containers inherent in the formulation. Combined with three new strategies to find efficient packing patterns, a binary search on the loading factor produces a solution that is superior to the original model. Our SCBS approach is designed to handle multiple containers, and makes use of SCLP algorithms to do so. As new and better SCLP approaches are developed, they can be incorporated into the SCBS approach in order to find good packing patterns. The type of constraints that can be added to the basic MCLCMP is dependent on the constraints that the SCLP sub-components can handle. For example, although the S-GRASP and C-GRASP strategy can handle the supporting area constraint, the G4BP strategy is unable to do so. If we replace the G4BP strategy with a technique that can handle the supporting area constraint (or remove it entirely), then SCBS will be able to handle this constraint for the MCLCMP. Our approach can also handle the case where there are mt containers of type t. Let C(i) be the container filled using packing plan i. We simply add the following equation to the linear integer program SC (a): equation(20) View the MathML source∑C(i)=txi⩽mt,∀t. Turn MathJax on This modification also allows us to handle the case where the price offered by different carriers is different for containers of the same size: containers with the same dimensions but with different prices are considered to be of different types. Note that when there are a limited number of containers, then feasibility could become an issue should the total capacity of all containers be close to the total volume of all items. However, we have found that this scenario does not occur in the practical problem instances faced by our client, and in fact our assumption of unlimited containers is a reasonable approximation of the real situation. We also proposed a technique to generate instances of MCLCMP with known optimal solutions, and used this technique to generate a 350-instance test suite with 3–9 box types using three standard shipping container sizes. The box dimensions are based on the dimensions of common household appliances. The existence of a known optimal solution for these sets of test data allows a more accurate measure of the performance of various approaches than using a theoretical lower bound. This technique can also be used to generate test data for other variants of container loading problems.