立體倉庫巷道式雙立柱堆垛機(jī)設(shè)計

喜歡這套資料就充值下載吧。資源目錄里展示的都可在線預(yù)覽哦。下載后都有，請放心下載，文件全都包含在內(nèi)，有疑問咨詢QQ:414951605 或 1304139763 Approaches for solving the container stacking problem with routedistance minimization and stack rearrangement considerationsNiraj Ramesh Dayamaa,b,d,n, Mohan Krishnamoorthya,d, Andreas Ernstc,Vishnu Narayananb, Narayan RangarajbaIITB-Monash Research Academy, IIT Bombay, Powai, Mumbai 400076, IndiabIndustrial Engineering and Operations Research, IIT Bombay, Powai, Mumbai 400076, IndiacCSIRO Mathematical and Information Sciences, Private Bag 10, Clayton South MDC, Victoria 3169, AustraliadDepartment of Mechanical and Aerospace Engineering, Monash University, Melbourne, Victoria 3168, Australiaa r t i c l e i n f oAvailable online 24 July 2014Keywords:Combinatorial optimizationCrane schedulingContainer stackingMixed integer programStacker crane problema b s t r a c tWe consider an optimization problem of sequencing the operations of cranes that are used for internalmovement of containers in maritime ports. Some features of this problem have been studied in theliterature as the stacker crane problem (SCP). However, the scope of most literature (including SCP) isrestricted to minimizing the route or distance traveled by cranes and the resulting movement-relatedcosts. In practice, cargo containers are generally stacked or piled up in multiple separate columns, heapsor stacks at ports. So, the cranes need to often rearrange or shuffle such container stacks, in order to pickup any required container. If substantial re-stacking is involved, cranes expend considerable effort incontainer stack rearrangement operations. The problem of minimizing the total efforts/time of the cranemust therefore account for both the stack rearrangement costs and also the movement-related (routedistance) costs. The consolidated problem differs from standard route distance minimization situations ifstack rearrangement activities are considered. We formally define the consolidated problem, identify itscharacteristic features and hence devise suitable models for it. We formulate several alternative MIPapproaches to solve the problem. We compare the performance of our MIP formulations and analyzetheir suitability for various possible situations.& 2014 Elsevier Ltd. All rights reserved.1. IntroductionThe assignment and scheduling of cranes for container move-ment operations have been well studied in the context of inter-modal freight container transportation at cargo container terminals(see 42). Optimization models have often been applied toimprove overall performance and efficiency in terms of turn-around time or throughput 8,45. Specifically, the stacker craneproblem (SCP) addresses the problem of minimizing the cost/time incurred when vehicles of unit load carrying capacity aredeployed to pickup and deliver containers between specifiedlocations 39.Major cargo terminals handle a large number of containers, sospace constraints often compel that containers be stacked up orpiled on top of each other in stacks, columns or heaps. Stackingoccurs at storage yards (where containers are stored, often for longperiods of time) or at the berth areas (the quay where cranes loador unload containers from ships). Stacking eventually leads toadditional, non-trivial costs whenever container stacks are subse-quently rearranged to fetch a container that was piled under othercontainers. However, discussions of crane scheduling and SCP inthe existing literature neglect the impact of stacking on opera-tional efficiency and schedules 23,30.Stack rearrangement efforts are distinct from the horizontalmovement activities performed by the cranes while physicallymoving the containers along pathways in the terminal. The totalcost incurred in container handling operations is the sum of the(vertical) stack rearrangement costs and the (horizontal) move-ment cost. We deal with the sequential ordering of containers, soas to minimize the overall handling costs with a focus on theunified vertical-horizontal cost minimization. The underlyingproblem can also be extended to more general cases (like indus-trial warehouses) and other examples in which stacks of objectsneed to be efficiently rearranged by forklifts. We do not addressside constraints like time window restrictions.The internal movement of containers within cargo terminalsinvolves a variety of operations that need to be executed. Weillustrate this using Fig. 1. This figure shows containers stacked atlocations (16) in a cargo terminal. The figure shows the initialContents lists available at ScienceDirectjournal homepage: & Operations Researchhttp:/dx.doi.org/10.1016/j.cor.2014.06.0180305-0548/& 2014 Elsevier Ltd. All rights reserved.nCorresponding author at: IITB-Monash Research Academy, IIT Bombay, Powai,Mumbai 400076, India.E-mail address: niraj.rameshiitb.ac.in (N.R. Dayama).Computers & Operations Research 52 (2014) 6883stack arrangement and the desired final arrangement of containersat these six locations. A single crane is allocated to execute all thehorizontal and vertical rearrangement tasks that are required.Consider container 1, which is placed in a stack under containers2,17 and 19 at location6. Container 1 needs to be moved to a newlocation5within the terminal. The crane deployed for thisactivity must do the following:1. The emptycrane must move from its current location to the pickuppoint6of container 1. We call this effort as no-load horizontalmotion effort (NLHM). NLHM involves a sequence-dependent costof horizontal movement because it depends on the immediateprecedence sequence of containers handled by this crane.2. The crane must now rearrange the stack at location1toremove the containers 19;17;2, which are stacked or piledabove the required container 1. We call this effort as the verticalstack rearrangement effort (VSR). VSR also depends on thesequence of containers handled by this crane. But it is radicallydifferent from NLHM, in the sense that, VSR for any container jdepends on the cumulative effect of all containers handledbefore this specific container j.3. The crane carries container 1 to its destination location5. Wecall this as full-load horizontal motion effort (FLHM). FLHMinvolves a fixed cost of horizontal movement.4. The crane must drop container 1 at the top of the stack atdestination location5. We neglect the cost and efforts of doingthis activity. The final stack position of 1 at5is not an issue forthe purpose of the current discussion.The total cost of container relocation is the summation of theimmediate-precedence dependent costs (NLHM), the cumulative-sequence dependent costs (VSR) and the fixed costs for all givencontainers (FLHM). We denote the problem of minimizing thissummation over all containers as the container stacking plusrouting problem (SpRP). For cargo terminals handling 100 con-tainers daily (see 31,33) and employing container stacks around810 high (see 32), substantial savings can be realized usingcrane operational schedule that do account for VSR in conjunctionwith NLHM. This is the motivation for our study of SpRP, in whichwe extend the SCP, that has been studied up until now, to alsoinclude the non-negligible VSR cost too.NLHM is modelled by transforming the problem (see 30,39)into an asymmetric traveling salesman problem as follows: wemodel the containers as nodes to be visited on a graph, withasymmetric arc costs between any pair of nodes i;jAN equal to thedistance (say Eij) between the corresponding locations of thosecontainers. The horizontal motion is modelled via a directedcomplete graph GhN;E. The n1 nodesNf0;1;2;ng of thisgraph denote the location 0 and all n containers in N. The edgesEinclude all directed edges needed to connect any pair i;j of nodesfromN. The cost of any directed edge i;j inE is the distance Eij.A Hamiltonian cycle overN construes a feasible operating sequencefor handling all containers. To minimize NLHM cost, we search forthe Hamiltonian path which minimizes the cost of all edgestraversed. For a given SpRP instance X, we define the graph GXhas its horizontal graph. Such a modeling of NLHM is a standardpractice in SCP literature (see 30,39).Fig. 1. Sketch showing required rearrangement of containers for a typical SpRP data instance.N.R. Dayama et al. / Computers & Operations Research 52 (2014) 688369To discuss VSR costs from Fig. 1, consider container 7. It needsto be moved from its pickup location3to delivery location5. Weneglect dead weight container 20 for our discussion. But container8 is stacked above 7 at3. Also, container 9 is supposed to bemoved into location3. Consider that the crane has alreadyhandled container 9 some time before handling 7, but container8 has not yet been handled. Now, if container 7 is fetched, thereexist containers 8 and 9 above container 7. These two containersneed to be temporarily removed from the stack of3beforefetching container 7. After container 7 is taken out of the stack,these containers must be placed back on location3in theiroriginal order. Thus, the additional stacking cost of two containersis incurred while fetching container 7 from3.On the contrary, consider that the crane handled container 8,then 7 and finally 9. In this case, neither 8 nor 9 appear above7 when 7 is to be fetched. So the VSR cost for 7 is zero (neglectingthe dead weight of container 20). So, the sequence of containerhandling for 8 and 9 decides the VSR cost for container 7.Generalizing this to other locations, the placement or removal ofsome container j impacts the VSR cost of other containers at alater time.1.1. Problem definitionConsider n unrelated identical containers to be moved (withoutpre-emption) within a known time horizon. These n containers arepiled up in columns or stacks. There may be some more containerspresent in the stacks (other than the n containers that need to bemoved). These additional containers act as dead weight in thestack handling. For any container i, which is one of the n contain-ers handled, the initial pickup location Piand the final destinationlocation Diare known. The physical distance between locations Piand Diis denoted as Ci. For a pair of containers i;j, the distancefrom delivery location Dito pickup location Pjis denoted as Eij. Theinitial number of containers in the stack at Piabove container i isdenoted as Hi. However, the actual number of containers above ichanges whenever more containers may be dropped onto or takenout from above i.A single crane is available to move the n containers. The craneis parked at a special location 0 (the depot) at the beginning of thetime horizon and must be returned to this depot location 0 by theend of the time horizon. This crane is the only resource capable ofexecuting all actions needed for SpRP. Any action involved inNLHM, FLHM or VSR expends an effort that translates into aproportional cost. We define these costs as follows:1. The cost incurred by crane to travel horizontal distance of oneunit ish(irrespective of NLHM or FLHM). If the crane hasplaced container i at location Di. Then it moves to pickuplocation Pjof container j. For this, it travels distance Eijas NLHMeffort and incurs costh? Eij. Then, the crane will carrycontainer j from location Pjto location Djtraversing distanceCjas FLHM. This incurs costh? Cj.2. The total cost incurred by the crane in removing and thenreplacing one container from a stack (while rearranging con-tainers) isv. Consider that container j currently has hjcontain-ers above it in the stack. If j is fetched, VSR cost ofv? hjmustbe incurred. This VSR cost is independent of the actual locationPjand any containers below j in the stack.Factorsh,vare fixed for the port/terminal and are assumed asinitial parameters for SpRP. Then, any SpRP data instance involvesthe following parameters:1. Pn ? 1 vector of those locations that are identified as theinitial source or pickup locations for the n containers.2. Dn ? 1 vector of those locations that are identified as thedelivery destination (or drop locations) for the n containers.3. Hn ? 1 vector of initial stack heights of containers piled upin the stack at pickup point Piabove container i (defined for allcontainers i among the original n containers). The actualnumber of containers stacked above i may change later on,whenever other containers are moved.4. Cn ? 1 vector of horizontal distances between pickuppoint Piand delivery point Difor any containers i.5. En ? n vector of horizontal distances between deliverypoint Diof ith container and pickup point Pjof jth containers,for all pairs of containers i;j among the original n containers. Eneed not be symmetric.We define term E0jas the vector of horizontal distances betweenlocation 0 and the pickup location Pjof jth container. Similarly, wedefine term Ei 0as the vector of horizontal distances between thedelivery location Diof ith container and the location 0. Finally, forconvenience of discussion, we define set N f1;2;ng as theunordered set of all n containers to be handled.1.2. AssumptionsWhile studying the SpRP, we make the following simplifyingassumptions:1. Time aspect: We neglect any time windows restrictions ordeadlines for container handling operations. We will use anaspect of time in several MIP formulations. We assume that thetime expended in executing a particular activity is numericallyequal to the cost incurred or effort invested in doing thatactivity. For example, if the VSR effort in handling container i isv? hi, we assert thatv? hiunits of time were needed by thecrane to fetch container i from its stack. So, minimization thetotal time needed in completing all activities for any SpRPinstance leads to minimization of total cost.2. Staging areas: There exist some small temporary staging areasnear the pickup locations where the containers might be placedduring stack rearrangement. Consider that a crane is taskedwith fetching container i from some location. But container jis stacked over i. So, the crane will first take out and place j intothe staging area. Then the crane will pick and place i next to j.Thereafter, it will replace j on the stack at location. Finally, itwill pick i and start moving towards Di. The staging area is to beused during the stack rearrangement activities only and mustbe vacated as soon as possible.3. Preparatory rearrangement for containers: No crane can do anyanticipatory or preparative rearrangement for any container orstack. Also, operations for a given container cannot be pre-empted or interrupted. For example, with reference to Fig. 1,suppose that a crane is scheduled to handle container 9 first,immediately followed by containers 7 and 8 will be handledmuch later. Then we assume that the crane will first delivercontainer 9 above the stack at location3above containers 7and 8. This completes the required actions for container 9.Thereafter, the crane will begin the operations for container 7.For fetching container 7, the crane will take off containers 9, 20and 8 temporarily, place them in staging area, then fetchcontainer 7, then replace containers 9, 20 and 8 on3andfinally move away with container 7. Specifically, the crane willnot interrupt the delivery of container 9 to facilitate the futureretrieval of container 7 from3.4. Final resulting stack height at delivery locations: Suppose thatcontainer i is being delivered to its drop location Di. During orafter this delivery operation, the stack height of containers at Diabove or below i has no impact on costs of i. The exact finalN.R. Dayama et al. / Computers & Operations Research 52 (2014) 688370considerations (or SECs). Such a route infeasibility or sub-tour isexpected in only a few cases because Eq. (29 (however weak)does enforce an interconnection between the two routes inducedby the two sets of variables. So, route feasibility restrictions arebest enforced by doing remedial or curative intervention only ifvariables do induce a meaningless route (violation of transitivity).This remedial intervention in terms of transitivity cuts keeps theunderlying formulation compact and easier to solve. Any additionalconstraints or variables (such as wijkor Yki) is superfluous and infact detrimental. Thus, the application of Theorems 1 and 2 has led toan novel cross-over of constraints between routing and stacking,resulting in an MIP formulation that performs best among all optionsexplored.4. Conclusions and future workIn this paper, we have introduced SpRP a new contribution tothe literature (to the best of our knowledge, SpRP has not beenstudied in the literature before.) We presented several traditionalMIP formulations that model and solve the SpRP. As a part of thecomputational analysis, we also showed the strength and applic-ability of specific formulations for different configurations.A vital contribution was the logical basis (Theorems 1 and 2) tocombine the key concepts from different MIP approaches. Thisused the inter-applicability of constraints to develop a strongerMIPformulation.Wedemonstratedthesuperiorityofthisapproach over many possible formulations/approaches for a widegamut of problem data instances with different configurations.Although these approaches are compelling and efficient andalthough the mathematical foundations in this work have enableda strengthening of the formulations that we developed, theapproaches still struggle to solve larger-sized problem instances.Further, some additional practical considerations and constraintsencountered in maritime ports also need to be addressed. Forexample, container ports may have specific time restrictions bywhich certain containers must reach a departing ship, train ortruck. We also need to consider dynamic/online instances in futurestudies. We believe that the best way to solve larger SpRP datainstances (with additional constraints) is through the develop-ment of efficient heuristic approaches.AcknowledgementsThe authors wish to acknowledge the insightful comments ofthe anonymous reviewers, whose comments have helped improvethis paper substantially.References1 Aslidis A. Combinatorial algorithms for stacking problems Ph.D. thesis.Massachusetts Institute of Technology; 1989.2 Baldacci R, Hadjiconstantinou E, Mingozzi A. An exact algorithm for thecapacitated vehicle routing problem based on a two-commodity networkflow formulation. Oper Res 2004;52:72338.3 Beasley JE, Krishnamoorthy M, Sharaiha YM, Abramson D. Scheduling aircraftlandingsthe static case. Transp Sci 2000;34:18097.4 Bianco L, DellOlmo P, Giordani S. Minimizing total completion time subject torelease dates and sequence dependent processing times. Ann Oper Res1999;86:393415.5 Bianco L, Ricciardelli S, Rinaldi G, Sassano A. Scheduling tasks with sequence-dependent processing times. Nav Res Logist 1988;35:17784.6 Bigeas L, Gamache M, Savard G. The time-dependent traveling salesmanproblem and single machine scheduling problems with sequence dependentsetup times. Discret Optim 2008;5:68599.7 Bish E, Chen F, Leong Y, Nelson B, Cheong Ng J, Simchi-Levi D. Dispatchingvehicles in a mega container terminal. In: Kim K, Gnther H-O, editors.Container terminals and cargo systems. Berlin, Heidelberg: Springer; 2007.p. 17994.8 Bohrer P. Crane Scheduling in container terminals Ph.D. thesis; 2005.9 Caserta M, Vo S, Sniedovich M. Applying the corridor method to a blocksrelocation problem. OR Spectr 2011;33:91529.10 de Castillo B, Daganzo CF. Handling strategies for import containers at marineterminals. Transp Res Part B: Methodol 1993;27:15166.11 Charbit P, Thomass S, Yeo A. The minimum feedback arc set problem is np-hard for tournaments. Comb Probab Comput 2007;16:14.12 Chen L, Langevin A, Riopel D. A tabu search algorithm for the relocationproblem in a warehousing system. Int J Prod Econ 2011;129:14756.13 Chen T. Yard operations in the container terminala study in the unproductivemoves. Marit Policy Manag 1999;26:2738.14 Christofides N, Colloff I. The rearrangement of items in a warehouse. Oper Res1973;21:57789.15 Claus A. A new formulation for the travelling salesman problem. SIAM J AlgebrDiscret Methods 1984;5:215.Fig. 8. Determining the overall best MIP variant.