425 Library, MC-522
1408 West Gregory Dr.
Urbana, IL 61801
Oak St. Library Facility
OSLF, 2nd Floor
809 South Oak Street
Mail Code 527
Champaign, IL 61820
A greedy algorithm was developed in several stages. The first layer of the algorithm focuses only on traveling in an x-y plane and does not factor in the z direction (the height of the shelves). A 5 by 23 array (x defining the ladder or column, y defining the aisle) was created showing the number of high priority trays in each aisle and ladder based on the following criteria:
- Recovering locations where “red” items are present
- Recovering only trays that contain more than 6 special collections items
This ensures that full (or nearly full) trays will be collected at locations that contain more than 50 items. A second layer was added to the algorithm by specifying a third dimension, the height of the shelves. This allows the algorithm to go to specific locations within the shelves, rather than just an aisle and a column. When the algorithm is run, it outputs a list of high priority item locations, along with the number of trays to be collected at that location. The list starts with the first item to be collected, and ends with the last.
The path defined by the algorithm is as follows:
- A lift with variable capacity (currently set to 16 trays) enters the first aisle.
- It moves to the first column (ladder) in this aisle, and begins to move vertically upwards, picking up trays on both the left and right side of the aisle.
- When the lift has reached its capacity, it returns to a depository, where the operator unloads the trays.
- The lift returns to the previous vertical height in the first aisle, first ladder.
- When all “red” items have been removed from both sides of the first ladder, the lift moves forward one location, to the first aisle second ladder.
- The lift begins to pick up trays from the bottom location of the second ladder, and proceeds in the same manner.
- When the lift reaches the last ladder, it moves back down the aisle, and goes to the second aisle, first ladder.
- The lift continues in this fashion until the end of the fifth aisle, when it is finished.
Calculation of Recovery Time
Recovery time is calculated by summing the lift travel time between locations, time to remove trays, and the time to empty the lift at capacity (see while statements in the evalTime function attached in Appendix B). The assumptions made in the calculation of time are as follows:
- The lift moves vertically at 1.28 mph and horizontally at 2.73 mph. These numbers are based on calculations done during normal operation of the lift. Time and distance measurements were taken to determine these speeds.
- The lifts vertical travel time is calculated by multiplying the numbers of rows moved by the average height of these rows which is approximately 12 inches. This is then divided by the vertical velocity to get time.
- The lifts horizontal travel time is based on the numbers of ladders moved multiplied by the width of each shelf which is a uniform 53.25 inches. This number is then divided by the horizontal velocity.
- The lift, when capacity is reached, returns from its current location to the aisle to unload. This time is calculated using the current (i,j,k) location found and the location (1,1,1) to represent the aisles entrance using the vertical and horizontal travel times described before. There is also an average 3 minute unloading time attached to this calculation before returning to its previous location. If this location has no trays then it will be bypassed and move to the next location.
- Trays take ten seconds to remove and place on the lift. This time is added into every calculation.
Analysis of Different Methods
In addition to listing the locations of high priority items, the algorithm was used to evaluate the effectiveness of different retrieval methods (such as including “yellow” items) and to determine the lift’s optimal tray capacity. Figure 7.1 shows the lift capacity versus recovery time of three different collection methods. The lower blue curve shows the recovery time if red items were stored in recommended safe zones instead of being placed randomly throughout the module. The middle red curve displays the recovery time achieved when only red items are collected (random placement), and the upper orange curve shows recovery time when both red and yellow items are collected (random placement). The facility’s current lift capacity is 16 trays and by doubling the storage capacity the facility could reduce the recovery time of red items by 2.42 hours.
As seen by the upper curve in Figure 7.1, recovery time is nearly doubled when yellow items are added to the retrieval of critical items, this is due to the large increase in trays being recovered, and the frequent unloads that are necessary. To examine the efficiency between each method, the item value (material worth in dollars) being collected over time (seconds) was compared. When red items are retrieved without yellows, $121,533,000 is collected in 9.05 hours ($13,424,400 /hr). Red and yellow items combined are worth $167,348,000 and are recovered in 17.7 hours ($9,433,371/hr). The team recommends that only red items be recovered initially; if yellow items were to be included, an additional $45.8 million would be gathered, but recovery would take 1.96 times longer.
The lower curve in Figure 7.1 displays the lift capacity versus time if all items are to be stored together in safe zones. If the facility places future high priority trays in known safe zones, the recovery time can be reduced by a minimum of 1.0 hour. This time was found after running the algorithm using a new array which contained red items stored in safe zones. Unloading and loading times remained the same, along with the number of trays being collected, so the 1.0 hour reduction is a reduction in time spent traveling between locations. If every special collection item is located in a safe zone, the time saved will be further increased compared to the current random storage.
Although a list will be generated for the facility before a disaster listing the items to be picked up and their location, the algorithm is easily updateable. If there is a time constraint after a disaster, the lower limit of trays to be retrieved may be increased. The algorithm currently retrieves from any red location that has one or more trays and this limit can be changed so that only red locations with more than ‘x’ number of trays will be picked up. As the lower limit is increased, time for recovery decreases (Figure 7.2). The MatLab code for the recovery algorithm is shown in the Appendix Material: Code for Retrieval Algorithm.
Back to top