Division of Research July 1979 Graduate School of Business Administration The University of Michigan SOLVING A BOXCAR LOADING PROBLEM Working Paper No. 183 Robert W. Haessler The University of Michgian FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the express permission of the Division of Research.

ABSTRACT This paper describes a procedure for determining whether or not a customer order for rolls of material will fit into a boxcar of known dimensions. The procedure is designed to run at order entry time so that the order can be adjusted before production scheduling to obtain maximum boxcar utilization and, therefore, minimum transportation costs.

INTRODUCTION Many products that are shipped in railroad cars or truck trailers have weight/volume relationships such that volume is the critical factor in determining the amount of product that can be shipped in a single unit. Assuming that the dimensions of the product being shipped are fixed, a relatively complex packing problem may have to be solved to determine the maximum amount of the product that can be shipped as a single unit. The essence of the packing problem is to minimize the amount of space that cannot be utilized because it is too little to accomodate the smallest product being shipped. These packing or space utilization problems are identical with the material cutting problems studied extensively by Gilmore and Gomory [2,3,4]. In both cases the essential constraint needed to define what can be done simply states that only integer numbers of pieces can be cut from a stock size or packed in a space and the quantity of material or space used must be less than or equal to what is available. Although a number of one and two-dimensional cutting stock problems are being routinely solved by producers of materials such as paper, steel, and glass [5,6,7,8], the general space utilization problems are largely unsolved. The only exceptions are those problems which can be reduced to a single dimension such as stacking racks of varying heights. A primary difficulty in solving space utilization problems is the lack of the guillotine cut requirement that occurs in most material cutting situations. (The guillotine restriction is that once a cut is begun it must proceed in a straight line to the other side of the material.) This type of constraint simplifies the generation of feasible cutting patterns by eliminating more complex types that the cutting hardware is unable to deal with anyway. Because there generally are no such restrictions in space utilization or packing problems, the pattern generation process is far more complex.

-2 - Even with the guillotine cut restriction, there are some formidable problems in solving cutting stock or space utilization problems in higher dimensions. For example, the multi-stage pattern generation approach developed by Gilmore and Gomory [3] for the two-dimensional problem does not permit any limit to be placed on the number of times a size can appear in a pattern. This can cause serious problems in obtaining the required integer values for the number of times a pattern is to be used. Recent research by Christophides and Whitlock [1] has led to a procedure for generating two-dimensional cutting patterns for rectangular shapes with upper bounds on the number of times a size can appear in a pattern. Their algorithm is extremely complex and of questionable practicality for use as a pattern generation routine to solve two-dimensional cutting stock problems because of the computer time required. Even though the outlook for general purpose algorithms.to solve higher-dimensional cutting stock and space utilization problems is gloomy, it is still important and worthwhile to work on these problems. The primary consideration is that these are real problems that are being solved daily on some ad hoc basis. As such, the real issue is not to find optimizing algorithms to solve the problems in a mathematical sense, but to find systematic procedures that will obtain better results on the average than the methods currently being used. This can be done by focusing on a specific problem situation and exploiting the restrictions and structure of that situation to develop efficient and effective solution procedures. The objective of this paper is to describe one such space utilization problem that occurs in the paper industry. The next two sections describe the problem environment and present a mathematical formulation of the problem. These are followed by a discussion of the procedure developed to solve the problem and an example problem with the output obtained.

-3 - THE CARLOADING PROBLEM Large rolls of linerboard of varying width, but constant diameter, are to be shipped from the producing mill to the box plants that convert them into corrugated shipping containers. Carload freight is paid by the paper mills. Because it is virtually all repeat business, the mills are concerned that the orders they receive are for full carload quantities in the sense of maximum utilization of the rail car. The orders are filled from production runs on a make-to-order basis. Therefore any adjustments to the order to obtain better carload utilization must be made at order entry time before the production run is scheduled. If an order is less than a full carload, then the freight cost per ton will be higher than necessary. The economic incentive is provided by a decreasing incremental cost once some critical weight limit is surpassed. If more than a full carload is ordered, then some portion of the order will have to be stored until some future time when it can be shipped with another order for the same customer. The mill's requirement is for an automated carloading procedure to screen the large volume of incoming orders to identify those orders whose roll quantities should be adjusted to increase the weight in the car or to avoid producing rolls that will not fit in the car. The basic information needed is: 1. Dimensions of the boxcar 2. Ordered sizes and quantities 3. Rules governing the ways rolls can be loaded. Because many of the rolls weigh more than two tons, material handling limitations severely restrict the way in which rolls can be placed in the car. These ground- rules- are listed below:

-4 - 1. Rolls on the floor must be upright 2. One roll can be stacked on top of another provided there is 1" of clearance with the top of the car everwere.,but the four floor positions in the doorway,where there must be a 12" clearance. 3. Two rolls can be laid across the top of four rolls in either end of the car, provided there is a 4" width clearance at the top of the car. The four rolls forming the platform for the rollbacks must all be of the same height. A maximum of seven rollbacks can be placed in a fifty-foot car and nine in a sixty-foot car. A single roll cananot be.laid: across a base of two rolls because of stability problems. A bottom view of a boxcar is given in Figure 1. The capacity question in this plane is simply how many circles of the same diameter will fit into a rectangle of known dimensions. The diameters are such in this type of problem that the boxcar 'width is less than three times the roll diameter. The second level loading options can be seen in the side view given in Figure 2. The roll marked A is a wide roll and has nothing above it. Roll B is narrow and has room for Roll C to be stacked on top of it. Rolls D, including two not shown, form a platform for rolls E and F. These two rolls are strapped together to prevent them from rolling around. In almost all cases, maximizing the number of rolls in the car is equivalent to maximizing the weight assuming that when there is a choice the heaviest possible roll is used. It follows, therefore, that stacking such as B and C is the most desirable configuration because each floor space holds two rolls. The rollback configuration with rolls D, E, and F is next with 6 rolls in in four floor spaces. Single rolls such as A represent the lowest utilization of the floor space in terms of number of rolls.

BOTTOM VIEW L W O I;)... _ - _ I_. i FIGURE 1 SIDE VIEW L E 0 H A B D D.~~ ~ ~~~ I I I. I I Ir... I FIGURE 2

-5 - MATHEMATICAL MODEL A mathematical formulation to maximize the number of rolls in a single boxcar is given below. Assume that the original order calls for R. rolls of width W. for i - 1, -— m, where all the rolls are for diameter,D. Let BCH, BCW, BCL be the inner boxcar height,, width and length' dimensions, respectively. Max: 2Z.XS. + 2Z.XD. + 3Z.XR. + 1Z.X. i 3 3 3 3 3 33 subject to Z.AS.XS. +Z.AD.XD. + Z.AR.XR. + Z.A.Xj. R 33 3 3 3 3 3 3 3 333, Z.XS. + 2Z.XR. 4 FC - 4 3 3 3 3 Z.XD. < 4 3 ) Z.XR. < RC 3 3 Z.XS. + Z.XD. + 2EXR. + EX. = FC 33 3 3 3 3 XS., XD., XR., X., > 0, Integer 3 3 3, XS. 3 XD. 3 XR. X. AS. J - number of stacks of rolls in locations other than the doorway using stacking pattern j. - number of stacks of rolls in the doorway using doorway stacking pattern j. - number of rolls laid across the top of two rolls using rollback pattern j. -number of rolls with nothing on top of them - is a vector of elements AS.. defining a stacking pattern such 13 that Z.AS. W. < BCH - 1 1 13 i AS.. > 0, integer. 13

-6 - AD. - is a vector of elements AD.. defining a stacking pattern for the doorway such that Z.AD..W. < BCH-12 i 1i 1 AD.. > 0, integer 1J AR. - is a vector of elements AR.. defining a rollback pat.tern suchbthat 3 13 Z.AR.. = 3 1 1) Z.6(AR..) = 2 1 13 AR.i Wi/2 < BCH - (4 + D) for all i AR..0, integer 1J 0 for a = 0 where 6(a) = a 1 for a > 0 for all i A. - is a vector of elements A.. such that 3 13 1 for i = j A, 0 otherwise R - is a vector of order requirements, R. FC is the number of rolls that can be placed on end on the floor of the car. RC is the maximum number of rollbacks that can be put in the car. The only additional complication is that XR. cannot take on the value 1. The model can be extended to handle orders for more than one carload by simply increasing the values of FC and RCassuming that the cars are all of the same size. In addition, care must be taken to be sure that the rollbacks can be allocated over the cars. For example if two 50' cars are used, there can be a

-7 - maximum of 14 rollbacks. Seven rollback patterns each having a usage value of 2 would not be feasible. There would be no way to meet the restriction that the three rollbacks in one end of each car must have base rolls of the same height. SOLUTION PROCEDURE The structure of the problem to be solved is such that a relatively simple enumerative scheme can be used to solve the problem without having to resort to a general purpose integer programming algorithm. The procedure is based upon an investigation of what can happen on the second level. All the possibilities for stacking and rollbacks are identified and then pieced together to obtain a maximum loading of the car. The procedure is outlined below. 1. Determine the floor capacity of the car, FC. In most cases this could be simply input because there are a limited number of boxcar sizes and roll diameters used. The calculation is included here because it is fairly simple due to the fact that for all cases of interest here BCW < 3 * roll diameter and in many cases BCW < 2 * roll diameter. In the latter case there will be either an even or an odd number of rolls with centers lying on 2 lines parallel to the sides of the boxcar. In the former case, the centers will lie on either 2 -or 3 or 4 lines - parallel to the sides of the car. Each possibility can be checked and the floor plan containing the largest number used. 2. Identify the possibilities for rolls on the second level. The ordered sizes are analyzed and placed into one of four categories. This classification represents increasing levels of flexibility. Assume for

-8 -this discussion that the roll diameter, D, is less that 1/2 of the boxcar height, BCH. a. Wide rolls W. > BCH - (4 + D) These rolls are too wide to permit anything on top of them. They can be used as rollbacks if W. < BCW. b. Rollback base rolls. W. < BCH - (4 + D) I W. > (BCH - 1)/2 1 These rolls are too wide to be stacked alone but can be used as a base for rollbacks. They can be stacked only with narrower rolls if they are available. c. Regular stacking rolls W. -< (BCH - 1)/2 W. > (BCH - 12)/2 1 These rolls are too wide to stack in.the doorway but can be stacked elsewhere. d. Doorway stacking rolls. W. i (BCH - 12)/2 These rolls can be stacked in the doorway. If all the rolls are wide rolls, then FC is the maximum number in the car and there is nothing else to do. If all the rolls are in classifications a and b,go to 5.

-9 -3. Generate stacking possibilities without regard to the doorway restriction. Stacks are initially formed by taking the narrowest roll available and stacking it with the widest possible roll that can be stacked with it. This will maximize the number of stacks generated. A check is then made to determine if any of the stacks will fit in the doorway. If none of the rolls are in category d or if 4 stacks fit in the doorway, go to 5. 4. Enumerate the possible number of stacks that car be placed in the doorway. For example, if the initial solution had two stacks that would fit in the doorway, check to see if solutions can be found that have 3 and 4 stacks in the doorway. This can be done by first generating stacks for the doorway, and then when the desired number is found, go on to consider general stacks. Save each unique solution found here with varying numbers of total stacks. 5. Check each stacking solution found to see if rollbacks can also be used. To do this there must be floor space and category b rolls not yet used in stacks. 6. Check to see if stacks can be adjusted to increase the number of roll backs. In general a stack is preferred to a rollback because of space utilization and material handling considerations; however, it may be possible to increase the rollbacks by 2 by taking apart one stack. This possibility must be checked. 7. Determine the maximum number of rolls that can be put in the car based on the total rolls on the second level and floor capacity. Note if there are any restrictions on the rolls to be added or deleted. For example, it may be possible to add another roll so long as its width does not exceed some critical value. Adjust the order quantities in such a way as to maximize the weight in the car. If a roll must be - - I 1 1 1 I.. I,, I 11, tI ". I I - I I I I 1I ~. 1.. II I. L l, I.

-10 - added, increase the heaviest roll that will fit. If a roll must be deleted take out the lightest roll that can be deleted. EXAMPLE PROBLEM The following actual example represents a fairly aggressive usage of a computerized version of the procedure described in the previous section. The usable boxcar dimensions are width - 114" length - 730 height - 137" This is a hi-cube car that has a maximum weight capacity of 190,000 pounds. The original customer order is for the following 58" diameter rolls. 10.82" 6 78" 8 74" 6 70" The floor capacity of the car is for 24 rolls in two columns of 12 slightly offset because the roll diameter is more than 1/2 the width of the boxcar. There are no stacking possibiliites because the rolls are too wider however rollbacks can be placed on top of both the 74 and 70 inch rolls, Based on the original order quantities, 4 wide rolls can be laid on top of the 8 74" rolls and 3 wide rolls can be laid on top of the 6 70" rolls. This would be a total of 31 rolls (24 + 7), one more than ordered. However, there is room for two more rollbacks in the 60 foot car. If two 74" rolls are added, the capacity is increased to 32 and the necessary two rolls can be added. In addition, in this case the lower bound on the order quantity was 90% of the original order. This means that if one 82" roll is dropped from the order, two more 70" rolls can be added increasing the number in the car to 33 by adding one more rollback. The

-11 -net effect of all this juggling was to increase the weight of the shipment from 138,000 pounds to 150,000. The output from the program is shown in Figure 3. The same information can be transmitted to the mill to alert them as to what has happened to the order and how it should be loaded.

FIGURE 3 BOXCAR LOADING ROUTINE BOXCAR DATA QTY WIDTH LENGTH HEIGHT MAX TONS CAR # 1 114.0 730.0 137.0 95.0 1 ORDER DATA DIA= 58. QTY 10 6 8 6 S ZE 82.0000 78.0000 74.0000 70.0000 ROLL WT 4920.0 4680.0 4440.0 4200.0 30 ROLLS WEIGHING 69.0 TONS FLOOR PLAN BXCR QTY PATTERN 1 24 2 LOADING INSTRUCTIONS FOR BOXCAR 1 REMAINING ANALYSIS ASSUMES 1 BOXCARS IN USE FLOOR CAP= 24 TOTAL CAP= 33 ORDERED= 30 BOXCAR LIMIT IN TONS 95. ORDERED TONS 69. TAKE OUT 1 82.000 TO PERMIT MORE ROLLBACKS INCREASE 74.000 BY 2 TO ALLOW 1 MORE ROLLBACKS INCREASE 70.000 BY 2 TO ALLOW 1 MORE ROLLBACKS LOAD 5 ROLLS ON TOP OF 74.000 LOAD 4 ROLLS ON TOP OF 70.000 INCREASE ORDER BY 3 ROLLS OR 52000. POUNDS THERE ARE 0 FLOOR POSITIONS OPEN THERE ARE 0 UNRESTRICTED ROLLS TO BE ADDED PROGRAM ENDS NORMALLY

-12 - CONCLUSION Although carloading problems in general appear to be quite complex and intractable, it is possible in certain cases to exploit the special structure of a specific problem to develop systematic procedures for solving them. This paper has described a procedure for determining how large cylinders can be loaded into boxcars to maximize the weight shipped. The carloading procedure was designed for a paper producer to be run at order entry time to determine if the incoming orders represented full carload quantities. Those orders that are for full carload amounts are accepted as entered. Those orders that are less than full carloads are increased to make better utilization of the car and reduce the freight cost per ton shipped. Those orders that are far more than a full carload are reduced to avoid having to store finished goods in this make-to-order business. Research is currently under way to see if the scheduling system can be modified so that stacking rolls and rolls to be used as a base for rollbacks can be produced early in the run to permit the maximum boxcar utilization to be obtained in a efficient manner from a material handling viewpoint.

REFERENCES 1. N. Christofides and C. Whitlock, "An Algorithm for Two-dimensional Cutting Problem," Operations Research 13, 30-44 (1977). 2. P. C. Gilmore and R. E. Gomory, "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, 9, 849-859, (1961). 3. P. C. Gilmore and R. E. Gomory, "A Linear Programming Approach to the Cutting-Stock Problem - Part II," Operations Research, 11, 863-888 (1963). 4. P. C. Gilmore and R. E. Gomory, "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, 13, 94-120, (1965). 5. R. W. Haessler, "A Heuristic Programming Solution to a Nonlinear Cutting Stock Problem," Management Science, 17, B793-B802 (1971). 6. R. W. Haessler, "Single-Maching Roll Trim Problems and Solution Procedures," TAPPI, 59, 145-149 (Feb. 1976). 7. R. W. Haessler, "A Procedure for Solving the Master Slab Ripping Problem in the Steel Industry," forthcoming in AIIE Transactions. 8. U. Saxena and K. G. Ahluwalla, "Development of an Optimal Core Steel Slitting and Inventory Policy," AIIE Transactions, 10, 394-408 (1978)