Transcription
WAREHOUSE LAYOUT DESIGN:MINIMIZING TRAVEL TIME WITH A GENETIC ANDSIMULATIVE APPROACH - METHODOLOGY AND CASE STUDYFilippo QueiroloFlavio TonelliDIPUniversity of GenoaVia all’Opera Pia 15I-16145 Genoa - ItalyE-mail: tonelli@itim.unige.itMaurizio SchenoneDSPEAPolytechnic of TurinCorso Duca degli Abruzzi 24I-10129 Turin - ItalyE-mail: schenone@athena.polito.itKEYWORDSGenetic algorithms, simulation, warehouse, layout design.ABSTRACTThis paper deals with the warehouse layout optimizationproblem with respect to the distance reduction and thetravel time minimization. The authors also searched for aflexible tool in order to optimize layout functionally to thefluctuations in demand and inventory level. The addressedoptimization problem is a constrained optimization problemon an integer domain and it is shown to be NP-hard. Thewide applicability of evolutionary computation and its goodperformances on a variety of different optimizationproblems have led to a strong interest in this type ofalgorithm. A heuristic genetic algorithm have beendeveloped and a system for the effective assignment of thestorage area to the different class of items is presented. Thesystem is based on the association of a genetic algorithmand a deterministic simulation model.Computational experiments are conducted to verify theeffectiveness of the algorithm. They were made by applyingthe proposed tool to a real industrial case concerning anItalian soft drinks company.As a result, the authors intend to provide a tool forwarehouse layout and operations optimization that could beattractive for operation management researchers andrealistically applicable by practitioners.INTRODUCTIONWarehousing can be defined by three functions: i)receiving goods from a source; ii) storing goods until theyare needed by a customer (internal or external); iii)retrieving the goods when requested.Storing material for an internal customer implies the needfor work-in-process storage, whereas storing goods for anexternal customer may imply the need for finished productsstorage. However, the functions of warehousing remain thesame and successful warehouse layouts must accomplishthe following objectives, regardless of material beingstored: maximize the use of space, maximize the use ofequipment, maximize the use of labor, maximizeaccessibility to all items, maximize protection of all items.Although the objectives of warehouse layout and operationProceedings 14th European Simulation SymposiumA. Verbraeck, W. Krug, eds. (c) SCS Europe BVBA, 2002Paolo NanIvan ZuninoSACS SavonaVia Cadorna 2I-17100 Savona - ItalyE-mail: sacs savona@yahoo.itare easily recognized, warehouse layout problems are oftencomplicated by a large varieties of products needingstorage, varying areas of required storage space and drasticfluctuations in product demand.Optimal approaches to warehouse layout problems oftenconsider a single objective (e.g. maximize floor spaceutilization) and/or provide a solution to a static problem.Warehouse design problems are further complicated byalternative storage methods and equipment.CA.RE. PROJECTFrequently large companies, characterized by advancedproduction planning and control methodologies and an hightechnological level, are supported by small-mediumenterprises (SMEs) which, in many cases, when notintegrated in efficient industrial districts or linked to aconsolidated network, can show remarkable structurallimitations and low competitiveness. In this scenario,research activities devoted to improve ICT systems ofSMEs are useful. This work has been developed within theCA.RE. project and it is just related to the whole reorganization of a SME, working in the large consumegoods market, producing and selling soft drinks for theItalian and the French markets.Importance of Finished Goods Warehouse ManagementIn several cases inventory management has a strong impacton the economics of a large-consume good company. Evenif inventory management is primary related to demandforecasting and master scheduling, material handling is acritical issue of this process since the total lead time dependon it. Moreover it’s a not value-added time-consumingactivity. For this reason finished goods allocation within thestorage areas is here addressed as a critical activity and it’sdeeply analyzed in order to reach an effective allocation ofthe finished goods. The reduction of the global storage costthrough the minimization of the total travel time is the maingoal of the proposed system, named Z-Sim.
THE INDUSTRIAL CASEThe studied company bottles mineral water and soft drinksin 8 different sizes and commercializes 15 types of softdrinks, producing 9 item classes. The structure of thewarehouse is based on 11 blocks with a total number ofstorage cells equal to 4408; these cells have to be dividedover the 9 commercialized items. Unit travel costs are itemdependent and different items cannot be mixed in a cell.Physical constraintsTwo different pallet formats are used inside the plant. Thetotal length of each block binds the pallet number that canbe inserted functionally to the specific assignment done.This last aspect plays a crucial role in the definition of aneffective problem code and functionally to the constraintswhich make very difficult the research of an optimalsolution: the constrained optimization problems areconsidered GA-hard [Chambers 1995].item typologies. Starting from the demand forecasting andfrom the MPS (i.e. master production schedule, themovements foresee inside an annual planning horizon), ZSim has to determine a finished goods spatial allocation forwhich the travel time is minimum. The proposed approachadopts a genetic algorithm to explore the wide researchspace and to evaluate the fitness by using a deterministicsimulator. The simulation plays a basic role inside the GAsresearch process. In fact the evolutionary computationrequires the definition of a fitness function which, in manyreal cases, in not possible to explicit analytically. Thereforethe simulation represents a suitable tool for candidatesolutions’ fitness straints related to the system performanceThe execution time of the research algorithm is mainly usedto evaluate the fitness of each member of the population.Thus it is necessary to optimize the computation avoidingthis calculation whenever the configuration is characterizedby an item place number less than the maximum allowedstock quantity. This approach introduces several typicallimitations of constrained optimization problems (COPs).Constrained Optimization ProblemsA COP is defined on a free research space D1 x x Dn,through a function F, which has to be optimized, and fromseveral constraints [c11, , ckk] which have to be satisfied.The constraints, characterizing the proposed industrial case,have a strong impact on the choice of the genetic operators:by increasing the number of constraints the probability todetermine not-feasible configurations increases and theresearch process efficiency decreases. A critical aspect ofthis type of approach is to guarantee that the geneticoperators maintain the constraints not considered in thefitness function.In order to reach this target it is possible to apply threedifferent approaches:1. filtering: not acceptable descendants are eliminated;2. repairing: not acceptable descendants are modifiedthrough a member post-processing operation;3. preserving: starting from acceptable parents by usingspecific genetic operators the acceptable descendantscreation is promoted.Z-Sim implements specific genetic operators (preserving)supported by a repairing routine.Z-SIM ARCHITECTUREThe development of the optimization process has beenrealized in order to achieve a rational and efficientassignment of pallet places with respect to the differentG.A.Figure 1: Main Units of Z-SIM ArchitectureDESIGN OF A GENETIC ALGORITHM FOR COPsAdopting a genetic approach, an import issue concerns thedata structures able to code the problem. The adoptedrepresentation uses a chromosome matrix; the alphabet iscomposed by ten symbols: nine of those are referred to theexisting items while a special char identifies not assignedplaces. Genetic search is generally based on three maingenetic operators. They are selection, crossover andmutation [Mitchell 1998]. The adopted operators arepartially derived from already applied heuristic approaches[Chambers 1995], modified and integrated whenever notsatisfactory; moreover some new operators have beendesigned in order to improve the performances and theresearch process.Crossover OperatorScanning gene is the operator that are most frequently usedto combine different members, reducing the generation ofunfeasible (i.e. outside the research space) solutions. Theidea on which the scanning is based proposes to position amarker on parents consecutive positions and then to chooseone of the marked position values in order to derive the newdescendant value. In the uniform scanning case the choiceover marked genes is made through a casual mechanismaccording to a uniform distribution; in the occurrencebased scanning case the most occurring value is selectedchoosing among the marked ones. Two solutions have beenadopted for the markers advance during the crossoverprocess: the first one implies that all the markers related tothe descendant’s chosen value have to be updated (i.e. rightshifted); the second one provides the updating of all themarkers independently from the marked value.Besides the two described solutions (uniform and
occurrence scanning) a two-points standard crossovermechanism and a new operator, named Holland schemespreserver, have been implemented. This latter procedureimplies the use of markers, like in the case of occurrencescanning, with the assignment of the most frequent value tothe descendant only in the case in which that value occursat least three times; if this is not true the value is chosen,from the adopted symbols dataset, in a random way. a path, parallel to the block section, needed to arrive fromthe first pallet of the block to the place in which the palletis picked-up (C).EndStorage Area #3Route BParent 1Parent 2Parent 3Parent 4Child322127533218247578665134468785416Parent 1Parent 2Parent 3Parent 4Child3221275333218247578665134468785416Parent 1Parent 2Parent 3Parent 4Child32212753332182747578665134468785416Parent 1Parent 2Parent 3Parent 4Child322127533321827475748665134468785416Parent 1Parent 2Parent 3Parent 4Child3221275333218274757486658134468785416Parent 1Parent 2Parent 3Parent 4Child32212753332182747574866581344168785416Parent 1Parent 2Parent 3Parent t 1Parent 2Parent 3Parent re 2: Basic Gene Scanning Operator in the Case ofSequences without Symbol ReplicationsRoute ARoute CFixed RouteProduction line/Storage UnitStartProd. LineFigure 3: Description of the Path followed by a Trolleystoring Finished GoodsDuring the research space exploration process 11 physicalconstraints and 9 constraints related to the systemperformance have been considered.Mutation OperatorsBy considering the mutation operators five new heuristics,especially studied with respect to the investigated problem,have been introduced; these heuristics are completelyextendible to other COPs and are suitable to preserve thepromising features of individuals. By realizing specificoperators it needs to pay attention to two fundamentalrequirements:1. it is necessary that the operator preserves promisingsolutions and in particular it is necessary to performpermutations of chromosome portions;2. it is important to bound significantly the randomsubstitution of the genes, that is typical of mutationoperator. This type of mechanism, common for a largerpart of free optimization GA applications, is fatal in theCOP case.Store item planned for the first day of the planning horizonCANDIDATE SOLUTIONSelect next planning dayWSelect materialMPS(daily resolution)resolution)Select a free cellAExecute storingREDistance (y) travel distanceHSelect materialDisaggregatedDemandForecastSelect a not-empty cellOExecute pick-upUSDistance (y) distance (y) pick up distanceEDistance (tot) distance (tot) distance (y)NEnd of theplanning horizonYOutput dist(tot)Figure 4: Block Diagram of the Fitness Evaluation ModuleSIMULATION FOR FITNESS EVALUATIONBONUS/ MALUS FITNESS COMPONENTBy looking at the minimization of the total travel time, theAuthors decided to use a fitness function defined as thetotal time that trolley consume. The calculation of thefitness value of a specific warehouse configuration (i.e. theassignment of each storage cell to a specific item) isperformed through a deterministic simulator.The distance made by a trolley during a movement from aproduction line to a storage cell and from the storage cell tothe distribution vehicle is identified by three paths: a constant path, which is equal to the distance betweenplants and block; a path perpendicular to the block section composed oftwo different routes:the route to reach the border of the storage block;the average route needed to pick a pallet inside thepile (B);The described finished goods warehouse is managed in anon-automatic way. Therefore a pallet place assignmentprocedure, even if optimal from a performance viewpoint,implies management difficulties (i.e. the assignment ofitem-place is hard to memorize). It would imply theabandoning of the solution found by the GA in favor of abetter usability. For this reason, in Z-SIM the fitnessfunction is integrated by a component related to abonus/malus function. This component is calculated as ameasure of the real possibility to use the correspondinglayout. This component is introduced at the termination ofthe traditional convergence process: at first an optimalsolution is searched basing only on the total travel time;subsequently a local optimization is performed byaddressing the research toward more realistic solutions.
onManualWareManSatisfactorySolutionFigure 5: Integration of the Z-SIM Architecturewith MANUALWAREMANUAL FINE TUNING AND ACCREDITATIONSuch a system allows to improve significantly the resultfrom an applicability viewpoint. Nevertheless both referringto the GAs features themselves (oriented to determine suboptimal solutions) and to facilitate the results sharing to thecompany management and production manager, a manualmodification module has been developed in order to changethe configuration determined by using the GA. Thismodule, called MANUALWARE, represents a directsimulator interface. Thus, in this way, it is possible to makechanges and to improve the obtained solution; moreover itis possible to perform solution robustness analysis andwhat-if inquires in order to evaluate the impact of variationsdirectly depending from the products disposition inside thewarehouse.PERFORMANCE EVALUATIONThe following figure shows the results obtained by theexecution of a complete Z-Sim research process. It can bedivided into two macro-phases: research with zero bonusand research with meaningful bonus values. Furthermoreduring the search process different crossover operators hasbeen used in order to exploit the best features of each ofthem.900850Best chromosomePopulation Average Fitness800Fitness Function750700650Introduction ofbonus/ GenerationFigure 6: Z-SIM Evolution: Transient, Stabilization, LocalSearch and Determination of a Satisfactory ConfigurationThe authors approached a real industrial case concerningwarehousing. The industrial problem has been modeled bya hybrid (genetic and simulative) approach. The GAshowed good performance, efficiently determining aneffective warehouse layout. Approaching COPs by usingGAs, specific genetic operators should be designed and asort of repairing procedure should be introduced, even if itreduces the performance of the whole system. By theintroduction of MANUALWARE, the accreditation of theproposed approach has been reached and a critical issue ofevolutionary computation (related to not optimal solutionfinding) has been successfully faced. MoreoverMANUALWARE allows practitioners to consider all thequalitative constraints of the optimization problem; in factits use led to the adoption of the suggested layout. Theintegration between GA and simulation greatly led to theanalysis and results dissemination. In this way it waspossible to analyze multiple scenarios and to share theobtained results with the production manager. Possiblefuture work are related to the application of proposedtechniques to a multi level warehouse optimizationproblem.ACKNOWLEDGEMENTSThe authors wish to thank the referees for suggestions thathave proved very useful in revising the submitted version ofthis paper.REFERENCESBeyer, D., Sethi, S. P., Sridhar, R. Stochastic MultiproductInventory Models with Limited Storage. Journal ofOptimization Theory and Applications, 111. 2001. 553-588.Chambers, L. Practical Handbook of Genetic Algorithm,CRC Press, New York, 1995Cormier, G., Kersey, D. F. Conceptual Design of a Warehousefor Just-In-Time Operations in a Bakery. Computers &Industrial Engineering, 29. 1995. 361-365.Degraeve, Z., Gochet, W., Jans, R. Alternative formulations for alayout problem in the fashion industry. European Journal ofOperational Research. In Press, Available online 28November 2001.Drury, J. Towards more efficient orderpicking, in IMM.Monographs 1. Cranfield, UK: Institute of MaterialsManagement, 1988.De Koster, R., Van Der Poort, E. Routing orderpickers in awarehouse: a comparison between optimal and heuristicsolutions. IIE Transactions, 30. 1998. 469-480.Kohlmorgen, U., Schmeck, H., Haase, K. Experiences with finegrained parallel genetic algorithms. Annals of OperationsResearch, 90. 1999. 203-219.Lai, K. K., Xue, J., Zhang, G. Layout design for a paper reelwarehouse: a two-stage heuristic approach. InternationalJournal of Production Economics, 75. 2002. 231-243.Larson, T. N., March, H., Kusiak, A. A heuristic approach towarehouse layout with class-based storage. IIE Transactions,29. 1997. 337-348.Mitchell., M. 1998. An Introduction to Genetic Algorithms.First MIT Press paperback edition, Massachusetts.Pierreval, H., Tautou, L. Using evolutionary algorithms and
simulation for the optimization of manufacturing systems. IIETransactions, 29. 1997. 181-189.Tersine, R. J. Principles of inventory and materials management.Fourth Edition. New Jersey: Prentice-Hall InternationalEditions, 1994.Tompkins, J. A. The challenge of warehousing. The WarehouseManagement Handbook. New York: McGraw-Hill, 1988. 114.Van Den Berg, J. P. A literature survey on planning and controlof warehousing systems. IIE Transactions, 31. 1999. 751762.AUTHOR BIOGRAPHIESPAOLO NAN is a graduating student of ManagementEngineering at University of Genoa. He had experiences instudent projects related to genetic algorithms andscheduling. He is an ordinary member of SACS.FILIPPO QUEIROLO is a member of DIP ResearchGroup at University of Genoa. He’s research interestinclude Artificial Computation, Operation Management,Simulation, and Signal Processing. He is a member of SCS,vice-president of SACS and Liophant Simulation Club.MAURIZIO SCHENONE is associate professor ofPolytechnic of Turin. He is also involved in researchactivity and teaching at University of Genoa. He hasworked in the operation management. His research interestsespecially focus on planning production and control andlogistics systems. He is a member of ANIMP.FLAVIO TONELLI is a complex systems managementresearcher in the Department of Production Engineering atUniversity of Genoa. He earned a PhD in Productionsystems and industrial plant management from Universityof Parma and degrees from Genoa University. His researchinterests include planning production and control andlogistics systems, simulation modeling, object orientedsoftware design and prototyping,. He is a member ofANIMP, Liophant Simulation Club and Society forComputer Simulation.IVAN ZUNINO is a master degree student of ManagementEngineering at University of Genoa. He had experience in astudent project related to Inventory Management methods.Recently he has been involved in a project for global reorganization of a mineral water company of Savona Area.He is ordinary member of SACS.
Genetic algorithms, simulation, warehouse, layout design. ABSTRACT This paper deals with the warehouse layout optimization problem with respect to the distance reduction and the travel time minimization. The authors also searched for a flexible tool in order to optimize layout functionally to the fluctuations in demand and inventory level. The .
