INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL ISSN 1841-9836, 12(1):41-52, February 2017. Lagrangian Formulation for Energy-efficient Warehouse Design I. Derpich, J. Sepulveda Ivan Derpich*, Juan Sepulveda Departamento de Ingeniería Industrial Universidad de Santiago de Chile, USACH Ave. Ecuador 3769, Estacion Central, Santiago, Chile (ivan.derpich,juan.sepulveda)@usach.cl *Corresponding author:ivan.derpich@usach.cl Abstract: Energy consumption in modern warehouses is today an important issue which has not received much attention in the scientific community. In this paper it is addressed the problem of warehouse design considering the energy costs incurred by vehicles and equipment in a fully or partially automated facility. Closed-form solutions are obtained by a formulating the Lagrangian of an operational cost function with equality constraints. The contribution of the paper is to develop formulas for reduced energy consumption and pollution, both relevant aspects in sustainable engineering systems. An example applied to a distributor of MRO items is presented. In this version the energy cost is integrated into the formula, modifying the method presented in [1].a Keywords: Energy optimization, integrated facility design, green supply chains. aReprinted and extended, with permission based on License Number 3954930120977 ©[2016] IEEE, from "Computers Communications and Control (ICCCC), 2016 6th Inter- national Conference on" 1 Introduction This paper is an extension of [1], which considers separately the cost of travel in the plane and the cost of energy for moving the items along the vertical axis. In this present paper both costs are integrated and formulas are obtained for designing facilities in an automated facility. The design of a warehouse or a distribution center (DC) has become a fundamental decision for the optimization of a supply chain. Even though there exist several articles in the academic literature in which efficient layout models have been studied, it has not been formulated a simple mathematical model in order to obtain the basic variables for the construction of a DC in three dimensions (3D). In warehousing facilities the movement of goods is performed by various types of equipment such as AGV (Automated Guided Vehicle), fork lifters, stackers, vertical reach trucks, conveyors or by automated robotics equipment of Cartesian movement adjacent to the storage racks, as in AS/R (Automated Storage/Retrieval) systems. In the literature there exist works with formulas to design shelves in two and three dimensions buy they do not adequately consider the problem of movement in the Z-axis, thereby giving inefficient results with very high shelves that ignore energy consumption and sub-optimize costs. This occurs because the known approaches consider the movement only on the X-Y plane, and such horizontal movement as expensive as in height, which in general does not hold in actual facilities. The problem is exacerbated for heavy materials due to greater energy waste. In this paper the above problem is solved by a cost model which considers in addition the cost of movement in height. With the model and derived formulas, more efficient shelves design with less energy consumption is generated. The formulas developed are optimal with respect to travel distances and they are obtained from solving a nonlinear optimization problem with linear constraints through a Lagrange transformation. Copyright © 2006-2017 by CCC Publications 42 I. Derpich, J. Sepulveda The formulas found in the literature mainly address the problem in two dimensions; for instance, Bassan et al. (1980) [2], consider a rectangular warehouse and racks which are parallel or perpendicular to the wall. They discuss also the optimal location of the warehouse door, and the optimal design when the storage area is divided into different zones. All of their work is developed on the horizontal plane; they fix a priori a given number of vertical racks and that value is used as a parameter. Some formulas for three dimensions that have been developed, consider implicit equations whose resolution must be made with an iterative method, this makes it difficult to use, as for example in Onut et al. (2008) [3]. In this paper it is considered that supplies are received from several suppliers and dispatched to many customers; consequently the study is complemented with the design of a multi -level warehouse (according to product flow) by using an ABC method- ology. Baker and Canessa (2009) [4] state that a structured approach for the design of a storage system in the company is not currently available and they make a compilation of different ap- proaches to finalize with the proposition of a new design methodology. Another classic work is Gu et al. (2010) [5] in which a detailed revision of the warehouse design research is presented by considering practical case studies and computational support tools. In addition, they present a framework for a systematic classification. Gu et al. (2010) [5] also conclude that even though there are a large number of papers focusing on details of the different systems, there are few addressing the decision making concerning storage systems. The work by Rouwenhorst el al. (2000) [6] presents a framework of references and classifica- tion of problems regarding design and control of storage facilities. To the review of the literature on storage systems is added the need for studies on isolated design rather than sub-problems. A central idea in [6] is dividing the functions of planning and design of warehouses at three levels: strategic, tactical and operational. At the strategic level, the number of warehouses, size and location of each, the equipment for handling materials, the functional areas, the process flow and warehouse layout, are determined. At the tactical level, manpower needed to operate the warehouse, the location of the products in the functional areas, replacement and order picking policies, are determined. At the operational level, the concern relates to the routing of the products, batch determi- nation, daily and weekly staff allocation and control tasks. In this framework of analysis it can be seen that the design of the warehouse, and in particular the number of shelves, is a strategic decision. Moreover, the determination of the sizes of product areas according to categories A, B and C is a tactical decision strongly involved with the decisions of the operational level. Thus the determination of the optimal design of a warehouse or distribution center is essential to minimize the transfer of products and therefore to minimize energy expenditure. In a relatively recent work, Heragu et al. (2005) [7] propose a mathematical model of mixed integer linear pro- gramming to decide which section to assign each product (dispatch, reservation or cross-docking), and also decide what process flow to associate, in addition to other decisions of operational and tactical level . A recent article by Zhou et al. in 2016 [8], addresses the question of how to design facilities, in a finite horizon taking into account various requirements of demand with respect to size, price, location, security, among others. They study the impact of re-design and methods to modify the design of the facility and present a mixed integer programming model and solve it by column-generation and branch and bound algorithms. Roodbergen et al. 2006 [9], they published a work on picking area layout in a warehouse, so that the average travel distance is minimized. They provide formulas that can be used to calculate the average length that an order runs under different routing policies. The optimal layout is determined using a model of nonlinear programming. The optimal number of aisles depends on the discipline of picking and the size of the picking list. Lagrangian Formulation for Energy-efficient Warehouse Design 43 Another approach that is used is dynamic storage allocation (DSAP or dynamic storage assignment problem). In the paper by Li et al. [10] is presented an integrated mechanism for the purpose of optimization which is based on the ABC classification and the mutual affinity of the products. The mechanism is developed by using a data mining technique and the authors show that the DSAP is a NP-hard problem. The results show that it is an advantageous approach to the classic ABC method, but requires the formulation of a complex problem and its resolution through a simulation of a metaheuristic method, which is not easy. In the paper already cited, Zhou et al. [8] present a new approach called self-managed warehouses is shown, whose use has rapidly grown in the world and are a universal trend. The problem in such a warehouse is the need for re-doing the layout frequently, so it is necessary to have direct ways to reconfigure the space continuously. In this work, the developed mathematical formulas are explicit and easy to use for the design of a warehouse or DC; it is assumed that a rectangular space is available, with a single main entrance gate in front in the center of the longest wall and an exit door located similarly at the rear wall. The formulas give the number of double racks to be used, the number of pallet spaces in each frame and its height also measured in pallets. The objective function is to optimize the total cost of movement of goods in the DC. In the first chapter a review of the literature on the use of mathematical methods in the design of distribution centers is presented. We conclude that not available explicit formulas for the design , so there are models applied to special cases .In the second chapter the formulas proposed in the paper has been much development, a rectangular supposed cellar with a single door in the center and a cost function nonlinear type is used with linear constraints , which are solved using Lagrange system to obtain the sought formulas. In the third chapter an experiment with a test case taken from the literature, one of the few papers found with similar studies is presented . The results are comparable , obtaining wineries lower height, which also reduces the total cost of transportation of the articles.Finally in chapter four conclusions and future work are presented . This is related to the development of formulas that can be used where space is restricted. 2 Distribution center configuration In the literature different configurations for the layout of a distribution center reportedl. Francis (1967) [11] studied architecture design theoretically and proved that the best configura- tion is an area that both measurements are the same , that is a perfect square. However in most cases, a rectangular area , is assumed. in this paper we will assume the same, however eventually develop formulas to tell whether the area is square or rectangular. 2.1 Assumptions Some assumptions to be made in developing the layout of the distribution center are: • Goods are stored in double racks, except for the rack adjacent the wall, which has only one side. • The shape of the store is rectangular (see Figure 1). • There should be wide aisles between the racks, and along the walls the width of these aisles should be the same. • Goods enter through a door located at one of the walls of the store and leave through the same door. 44 I. Derpich, J. Sepulveda The first study of Bassan et al. (1980) [2] conducted on the design of a distribution center provided two possible distributions of the shelves. In this paper, only the distribution shown in Figure 1 is analyzed, where the shelves are located in the sense of the narrower direction (v). Figure 1: Rectangular distribution center The notation used in this study is as follows: • N = total storage capacity in storage spaces (slots). • a = width of an aisle, where it is assumed that all the aisles have the same width. • w = width of double shelf. • W= average weight of a unit storage in a container. • L = length of a storage unit in the shelf. • m = total number of storage spaces along a shelf. • h = number of vertical storage spaces. • n = number of double shelves. • u = length of the store. • v = width of the warehouse. • d = annual movement (demand) of the warehouse, in storage units. It is assumed that a unit of stored article occupies a unit of space (in items / year). • Ch =material handling cost of moving a unit of article per unit of length in the x-y surface (in US$/m). • Ce = energy cost (in US$/unit of energy). • Tv = average travel distance on the v-direction in meter. Lagrangian Formulation for Energy-efficient Warehouse Design 45 • Tu = average travel distance on the u-direction in meter. • Th = average travel distance in height in meter. • ve = velocity of moving a unit of weight W in a distance in height (mt/sec) 2.2 Cost function This paper considers only the cost of moving and handling of goods inside the warehouse. For this, we use Figure 1 as a reference and hence the measures considered. First the length and width of the distribution center will be determined, which are determined by: Width u = n(w + a) (1) Length v = 2a + mL (2) Then the area of the distribution center is as follows: uv = n(w + a)(2a + mL) (3) In order to calculate the cost of moving goods, the average travel distance of each stored unit is required. It will be assumed that the doors are located at the centers of the walls and that all goods are equally likely to be used. To determine the cost function of the DC, we must first set the probabilities of carrying a good in the horizontal plane and in height. In the horizontal plane, two axes of movement are defined: one for lateral movement (u direction) and one towards the bottom of the warehouse (v direction), as shown in Figure 1. Thus, let Tv , Tu and Th be the distances in each direction. As the probability of taking a good to the left or right from the door of the CD store is the same, the average travel distance on the horizontal axis is (4): Tu = u 4 = n(w + a) 4 (4) For the distance on direction v, the length of an average trip depends on the category of the item, that is, A, B or C. Let PA ,PB and PC be the probability that the item to be moved belongs to category A, B and C, respectively. In addition, let mA, mB and mC be the corresponding number of reserved spaces in the direction v for products in categories A, B, C, respectively. With this formulation the average length of a trip in direction v is given by: Tv = a + Pa mAL 2 + PB(mAL + mBL 2 ) + PC(mAL + mBL + mCL 2 ) (5) By property of probabilities, the following holds: PA + PB + PC = 1 (6) 46 I. Derpich, J. Sepulveda By factorizing in function of L and arranging in (5) the equation (7) is obtained Tv = a + L[Pa mA 2 + PB(mA + mB 2 ) + PC(mA + mB + mC 2 )] (7) The term PA mA 2 corresponds to the average number of slots to be traveled for storing a product of type A; the term PB(mA + mB 2 ) corresponds to the average number of slots to be traveled for storing a product of type B, while the term PC(mA + mB + mC 2 ) corresponds to the average number of slots to be traveled for storing a product of type C. The total capacity of category A, B and C within the DC to store goods can be expressed as follows: NA = 2mAnh (8) NB = 2mBnh (9) NC = 2mCnh (10) Now, let’s get the cost of consumption of energy expended in the movement of goods in height h. Considering an AGV to move the articles in height, we have the following expression for power consumption. Th = WHt (11) Where: • W is the average mass of conveyed articles. • t is the average time spent on moving the load a unit distance h.t es el tiempo medio gastado en mover la carga una unidad de distancia h. By common expression of the average speed v = Lh t then t = Lh ve . Let E be the consumption of energy: E = CeW hLh ve (12) In (12) Ce is the cost of energy expended in moving a load of W kilos in height at a constant speed ve, taking a time Lh. If other equipment is used to move materials in height, as it could be drones or an automated robot, expression (12) will change. For an AGV equipment, the cost equation for a DC with the ABC method is (13): C = 4dCh[a+L(PA mA 2 +Pb(mA+ mB 2 )+PC(mA+mB + mC 2 ))+ n(w + a) 4 ]+2dCe[ WLh2 ve ] (13) The model can be expressed as in (14): Lagrangian Formulation for Energy-efficient Warehouse Design 47 C = 4dCh[a+L(PA mA 2 +Pb(mA + mB 2 ) +PC(mA +mB + mC 2 ) + n(w + a) 4 ] + 2dCe[ WLh2 ve ] (14) subject to NA = 2mAnh (15) NB = 2mBnh (16) NC = 2mCnh (17) By transforming the system by converting to the Lagrangian function see the reference Lu- enberger (1989) [12] , we have: C = 4dCh[a + L(PA mA 2 + Pb(mA + mB 2 ) + PC(mA + mB + mC 2 ) + n(w + a) 4 ] + 2dCe[ WLh2 ve ] + (18) λA[NA − 2mAnh] + λB[NB − 2mBnh] + λC[NC − 2mCnh](19) By partial differentiation on mA , mB , mC , n, h, λA , λB y λC we obtain. δLg δmA = 4ChdL( PA 2 + PB + PC) − 2λAnh = 0 (20) δLg δmB = 4ChdL( PB 2 + PC) − 2λBnh = 0 (21) δLg δmC = 4ChdL( PC 2 ) − 2λCnh = 0 (22) δLg δn = 4Chd (w + a) 4 − 2λAmAh− 2λBmBh− 2λCmCh = 0 (23) δLg δh = 4dCeWLh ve − 2λAmAn− 2λBmBn− 2λCmCn = 0 (24) δLg λA = NA − 2mAnh = 0 (25) δLg λB = NB − 2mBnh = 0 (26) δLg λC = NC − 2mCnh = 0 (27) lete K1 and K2 be respectivelly: K1 = PA 2 + PB + PC (28) K2 = PB 2 + PC (29) 48 I. Derpich, J. Sepulveda As λA, λB and λC represent the shadow price of the corresponding resource, that is , for A, B or C, respectively, values of λA, λB and λC are obtained as shown in (25), (26), (27): λA = 2ChdLK1 nh (30) λB = 2ChdLK2 nh (31) λC = ChdLPC nh (32) Finally we obtain: n = 5 √ 16ChL 3Exp21CeW (w + a)3Chve (33) h = 5 √ (w + a)C2hExp1v 2 e 8LC2eW 2 (34) mA = NA 2 5 √ (w + a)2CeW 2L2Exp31Chve (35) mB = NB 2 5 √ (w + a)2CeW 2L2Exp31Chve (36) mC = NC 5 √ (w + a)2CeW 2L2Exp31Chve (37) where : Exp1 = K1NA + K2NB + PCNC 2 (38) Theorem 1. For the values of the Lagrangian multipliers, it holds that: λA > λB > λC (39) Proof: The only different term between the expressions of λA and λB is K1 and K2. Let us recall the corresponding expressions: K1 = PA 2 + PB + PC (40) K2 = PB 2 + PC (41) therefore if PA > 0 and PB > 0 then K1 > K2 and λA > λB. (42) Lagrangian Formulation for Energy-efficient Warehouse Design 49 On the other hand, it can be seen that if PB > 0 then λB > λC. (43) 2 This theorem has the following implication, it shows that the shadow price of the space resource intended for items type A are greater than those of items type B and in turn both are greater than than type C’s. The shadow price of a resource is a measure of its value or scarcity, in this case it represents how much it is saved when an extra slot unit is allocated to each of the types of dedicated storage areas A, B or C. 3 Experimenting with a test case In order to validate the developed formulas, various calculations of warehouse distribution were performed using the data of (Onut et al, 2008) [2] for MRO (maintenance, repair, and operational) items showing ABC categories. Note that this is the only reference found in the literature with formulas for the case in three dimensions. In that document, the developed formulas are implicit and the problem was solved by the method of particle swarm optimization (PSO). The store used was programmed to handlefive families of products, including personal cleaning, home cleaning, chemical raw materials, electrical spare parts, and ceramics objects including 10, 14, 62, 11 and 7 types of articles, respectively. Before applying the formulas developed in this paper, a procedure is applied for determining which group according to the ABC method is assigned to a given product. Therefore, the goods in Class A are closer to the door, while class B at a distance of midrange and class C at a greater distance. After completing this process, 14 elements in class A, 24 class B elements and 12 elements of the class C were found. The probabilities of membership in each class were taken as 0.6, 0.3 and 0.1 respectively. The total flow of the warehouse is 120,000 pallets of products per year and the capacity of the warehouse is 6,000 pallets. The capacity of the warehouse is divided into size classes 3,000 (NA), 2000 (NB) and 1000 (NC). With respect to the dimensions of the warehouse, there are available racks with loading by both sides of a total width (w) of 2.2 mt., a length of 0.9 mt. wide and 1 mt. height. The width of the aisles is 2 mt. and the width of doors 4 mt. The cost factors considered are two. First we considered the cost of use the AGV moving in the horizontal plane Ch, it is obtained per meter transported. Second we considered the energy cost generated by the movement in 3D of the AGV (Ce, it is obtained per meter transported per kilo and per the spended time in seconds. With this information, the summary data are: • L=0.9 meters (length of storage unit or slot) • N=6000 (total storage capacity in slots) • a=2.0 meters (aisle width) • d=120,000 (anual demand for pallets) • Ch=US$ 1.13*10-3 (material handling cost in US$/mt) • Ce= US$ 7.91*10-6 (energy cost US$/mt-Kg-seg) • NA=3,000 (number of pallets in category A) • NB=2,000 (number of palletes in category B) 50 I. Derpich, J. Sepulveda Table 1: Results obtained using the developed formulas Values n h mA mB mC m Obtained 15.06 5.01 19.89 13.26 6.63 39.77 Rounded 15 5 20 13 7 40 Table 2: Shadow prices for each type of space A,B, C. λA λB λC 7.18 2.56 0.51 • NC=1,000 (number of pallets in category C) • PA=0.6 (probability of product is category A) • PB=0.3 (probability of product is category B) • PC=0.1 (probability of product is category C) • W=20 (mass,Kg) • w=2.2 (meters) • ve=0.2 (meters/second) With these values the dimensions that give the formulas for the number of shelves (n), number of containers in height (h), number of shelves type A (mA), number of shelves type B (mB) and number shelves type C (mC) are shown in Table 1 below: It is noted that the number of double shelves is 15 which gives 30 racks in total, with a number 40 slots, which added to the space occupied by the aisles gives an area of 2,520 square meters. The shadow price values are shown in Table 2 below It is appreciated that the space dedicated items type A is more expensive than type B, and type C; and that the space dedicated to type B items is more expensive than the articles dedicated to type C. Thus each space unit type A contributes a value of 7.18 US$/slot-year to the cost of moving materials in a year, while each unit type B space contributes 2.56 US$/slot-year while the C type contributes 0.51 US$/slot-year. Thus, if there was additional space for warehousing this should go to space for items type A first and then items type B and C. The total average cost of warehousing separated by movement in the horizontal plane on the one hand and vertical movement for another, it is shown in Table 3. Table 3: Average annual costs in US$ Cost of movement in the horizontal plane 21,971 Cost of movement in the vertical axis 5,222 Total Cost 27,192 Lagrangian Formulation for Energy-efficient Warehouse Design 51 This is the total cost corresponding to the storage and picking operations for the total annual demand, this gives an average cost of 4.53 US$/slot and it is consistent with the shadow prices obtained. Conclusions and future works In this paper new approach to the design of distribution centers was presented; particularly for a rectangular design with the heightwise movement. Explicit formulas to calculate the number of pallets, the number of double shelves, the number of unit spaces for each shelf and number of unit spaces in height were developed. The formulas obtained are easy to use. These have been obtained by a Lagrangian function obtained from a quadratic minimization problem with equality constraints. In the literature there are no explicit formulas in three dimensions by which this work is a valuable contribution to the design of distribution centers in three dimensions. Future works developing closed-form solutions as to those found in this paper should be continued, but conforming to a given area, since this is a typical situation in the company, in which the available surface poses constraints to the warehouse design problem. Acknowledgment The authors are very grateful to DICYT (Scientific and Technological Research Office), Project Number 061317DC and the Industrial Engineering (IE) Department, both of the Uni- versity of Santiago of Chile for their support in this work. Also to IE graduates Ren’e Ibacache and Nicole Muńoz who helped in the model implementation. Bibliography [1] I. Derpich and J. Sepulveda (2016), A Model for Storage Facility Design with Energy Costs, Computers Communications and Control (ICCCC), 2016 6th International Conference on, IEEE Xplore, e-ISSN 978-1-5090-1735-5, DOI: 10.1109/ICCCC.2016.7496753, 147 - 150. [2] Y. Bassan, Y. Roll and M.J. Rosenblatt (1980), Internal Layout Design of a Warehouse, IIE Transactions, 12(4): 317-322. [3] S. Onut, U.R.Tuzkaya, D. Bilgehan (2008), A particle swarm optimization algorithm for the multiple level warehouse layout design problem, Computers & Industrial Engineering, 54: 783-799. [4] P. Baker and M. Canessa (2009), Warehouse design: A structured approach , European Journal of Operational Research, 193: 425-436. [5] J. Gu, M.Goetschalckx and L.F. McGinnis (2010), Research on warehouse design and per- formance evaluation: A comprehensive review, European Journal of Operational Research, 203:539-549. [6] B. Rouwenhorst, B. , B. Reuterb, V. Stockrahmb, G.J. van Houtumc, R.J. Mantela and W.H.M. Zijmc (2000), Warehouse design and control: Framework and literature review, European Journal of Operational Research , 122(3): 515-533. [7] S.S. Heragu, L. DU, R.J. Mantel and P.C. Schuur (2005), Mathematical model for warehouse design and product allocation International Journal of Production Research, 43(2):327-338. 52 I. Derpich, J. Sepulveda [8] S. Zhou, Y. Gong and R. De Koster(2016), Designing self-storage warehouses with customer choice, International Journal of Production Research, 54(10): 3080-3104. [9] K.J. Roodbergen and F.A. Vis (2006), A model for warehouse layout, IIE Transactions, 38:799-811. [10] J. Li, M. Moghaddam and S.Y. Nof (2016), Dynamic storage assignment with product affinity and ABC classification - a case study, Int J Adv Manuf Technol, 84:2179-2194. [11] R.L. Francis (1967), On some problems of rectangular warehouse design and layout, Journal of Industrial Engineering, 18: 595-604. [12] D. G. Luenberger (1989), Linear and non linear programming, Chapter 10, Addison Wesley Iberoamericana, 299-305.