The movement of forklifts or other unit-load equipment does not add value if the forklift is traveling with empty forks (dead-heading). For example, a forklift will deadhead to a storage location to get a pallet, but then travel productively to carry that pallet to shipping.
Movement in a unit-load warehouse is typically either to stow or retrieve pallets. In the simplest and most common protocol the forklift is devoted to unloading a trailer and stowing the pallets one-by-one or else retrieving pallets and loading them into a trailer. This protocol is known as single cycle. In a unit-load warehouse where all pallet movements are either stows or retrievals, a forklift operating under single-cycle protocol dead-heads at least half the time, because it must constantly return empty to receiving to unload another pallet or else travel empty to retrieve another pallet for shipping, as in Figure 6.6.
One way to reduce labor is to store product in convenient locations so that travel with the pallet is reduced — this is the subject of the next section. Another way is to reduce deadheading by careful interleaving of put-aways and retrievals, so that after a put-away, the forklift travels directly to pick up another pallet.
But how can the forklift driver know what retrievals are nearby? The identification of nearby tasks relies on some global view of the warehouse, such as that provided by a supervisor or the warehouse management system. In either case, the “controller” maintains a queue of waiting tasks, from which he or it assigns trips that are pairs of stows and retrievals. The pairs of stows and retrievals will be chosen to reduce deadheading as in Figure 6.7.
A human controller can build efficient trips in an ad hoc manner, but to be most effective, dual cycle requires additional IT support to coordinate tasks. With more IT ¨ support it is possible to construct the pairings that minimize dead-heading. Assume there is a task list consisting of stows i = 1, . . . , m and retrievals j = 1, . . . , n. Let the shortest distance between the location of stow i and the location of retrieval j be dij . (The shortest distances from each stowage location to all the retrieval locations must be computed, for example, by repeated use of the Shortest Path Algorithm described in
Figure 6.6: Under single-cycle protocol, half of all forklift travel is unproductive (red lines). In this example, both receiving and shipping are at the bottom (black disk). Trips to stow a pallet in an available location (gray squares) require that the forklift return with empty forks. Similarly, any trip to retrieve a pallet from a location (black squares) requires that the journey begin with empty forks.
Figure 6.7: Dual-cycles can reduce dead-heading by enabling travel directly from a stow to a retrieval. In this example, each of two stows (gray locations) have been paired with a retrieval (black locations). Dead-heading is shown in red.
Appendix C. While this is tedious to contemplate, it is trivial for a computational device that knows the layout of the warehouse and the addresses of the storage locations.) Then the problem of finding the pairings of stows and retrievals to minimize total deadheading may be expressed mathematically as where xij = 1 indicates that the forklift making stow i should then proceed in the most direct way possible to retrieval j.
The first constraint requires that every stow be paired with some retrieval, and the second constraint that every retrieval be paired with some stow. If there are fewer stows than retrievals, then we simply add enough “dummy” stows to make them equal,where each dummy stow represents travel from the shipping dock to a retrieval location. Similarly, if there are more stows than retrievals, we add dummy retrievals, each of which represents dead-heading to the receiving dock.
This is a special type of linear program called an Assignment Problem and can be solved quickly (for example, via the linear programming solver found in most spreadsheet programs).
To be most effective, dual-cycle operations should account for dynamically arriving tasks (stows or retrievals): When a forklift becomes available, re-solve the assignment problem to build a set of trips, and assign the trip with least deadheading to the waiting forklift. (We postpone any trip with lots of deadheading in hopes that a later-arriving task might be a better match and so further reduce deadheading.)
For a more general discussion of dynamic pickup and delivery problems, see [14].
If the warehouse requires more general moves than stows or retrievals, such as during a reorganization, then the problem becomes harder, a version of the Rural Postman Problem, which is to find the shortest route that visits each of a set of directed edges [20, 23].
When is dual cycle worth it?
Whether this is worth the effort depends on whether there is contemporaneous receiving and shipping. There might not be much opportunity to take advantage of dual cycles if, for example, product was shipped in the morning, and received in the afternoon.
The layout of the warehouse may make it harder to reduce dead-heading. In the layout of Figure 6.8, receiving, at the bottom, is separated from shipping, at the top, and so any dual cycle incurs unavoidable deadheading between them. In such a case, the dual-cycle protocol may yield no savings.
So: It is certain that the forklift must travel from receiving to a storage location and, later, from that location to shipping. There may be additional travel in the form of Figure 6.8: When receiving and shipping are separated, a dual-cycle trip must deadhead between them (dashed red line in the center).
dead-heading, but this may be reduced if there are many opportunities for dual-cycle trips.
