GEOMETRIC APPROACHES TO SOLVE THE CHEBYSHEV TRAVELING SALESMAN PROBLEM Yavuz A. Bozer Department of Industrial ard Operations Engineering University of Michigan 1205 Beal Avenue Ann Arbor,MI 48109-2117 Ellen C. Schorn IBM Corporation, Information Products Division Department 17E/002-2 1001 W. T. Harris Blvd. Charlotte, NC 28257 Gunter P. Sharp Material Handling Research Center School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332 Technical Report 87-29 December 1987

ABSTRACT Several heuristic procedures based on geometric concepts have been developed for the Chebyshev Traveling Salesman Problem (CTSP) which has numerous applications in materials handling and information storage-retrieval. The following study is concerned with evaluating the performance of geometric approaches as a function of the shape of the service region and the number of points to be sequenced. A new approach, namely, the band insertion heuristic is also introduced and compared with existing procedures. Trade-offs in tour quality and runtime is the primary focus of the study which is empirical in nature; however, the results generally apply to a wide range of configurations.

GEOMETRIC APPROACHES TO SOLVE THE CHEBYSHEV TRAVELING SALESMAN PROBLEM I. INTRODUCTION A significant number of heuristic procedures have been developed for solving the planar Traveling Salesman Problem and its variations. The following study is concerned with a subset which can be best described as "geometric approaches." Such approaches capitalize on the geometric properties of the optimum tour or the "cities." As opposed to using a cost matrix to obtain a solution, they are driven by the location of the "cities." They are also recognized as relatively fast procedures that are conceptually simple and easy to implement. In the Chebyshev Traveling Salesman Problem (CTSP), the distance between two points is measured by the Chebyshev metric (also known as the 1, - norm). As far as the planar TSP literature is concerned, the Euclidean metric or a given distance matrix that meets the triangular inequality appear to be the two types of problems studied most often in the past. The Chebyshev TSP and the rectilinear TSP have received little attention in comparison. Furthermore, a number of results have been reported on the worst-case and average performance of various "matrix driven" TSP heuristics. On the other hand, only a limited number of results are available for geometric approaches. The studies reported for such approaches tend to represent isolated cases where a newly developed heuristic procedure is compared against a previous one or the optimum solution. Hence, aside from evaluating a new geometric approach, the following study represents a comprehensive study where major published geometric approaches are compared and empirically evaluated. 1

In evaluating the above heuristic procedures, the main goal is to empirically study certain "runtime" and "solution quality" trade-offs typically encountered in comparing approximate algorithms. It is also important to identify those procedures that consistently yield relatively inferior results under certain conditions. Conceptual simplicity, ease of implementation and similar concerns are also addressed. Lastly, as a reference point, the heuristic which yields the best results with respect to tour length is compared with the exact procedure. II. THE CHEBYSHEV TRAVELING SALESMAN PROBLEM The principal incentive for studying the CTSP stems from numerous applications where the only appropriate metric is the Chebyshev metric. For example, powered by two separate motors, storage/retrieval (S/R) machines used in materials handling travel simultaneously in the horizontal and vertical directions. Hence, travel time between two points is equal to the maximum of the horizontal and vertical travel times. Such machines are used quite extensively in warehousing and manufacturing. Examples include raw materials and finished goods handling with Unit Load Automated StorageRetrieval Systems (AS/RS); small parts and work-in-process handling with Miniload AS/RS; and order picking with Person-on-Board AS/RS. Also, component accumulation prior to assembly (that is, kitting) can be performed by Miniload AS/RS, Person-on-Board AS/RS or Carousel conveyors (where the vertical travel of a stationary extract-insert device is overlapped with the rotation of a horizontal carousel). With the introduction of Microload AS/RS, S/R machines are also being used to directly support material flow in Flexible Manufacturing and Flexible Assembly systems as well. The Chebyshev metric is also encountered in certain information storage-retrieval systems known as two-dimensional mass storage systems. Powered by two separate drives in the x and y axes, in some systems the read/write (R/W) head follows the Chebyshev metric (see Wong[25] among others). Hence, in those cases where the requests are batched, minimizing the total head movement in going through all the records requested in a single 2

batch leads to the CTSP. Naturally, other factors such as record placement and batch construction rules will affect the throughput capacity of the system. The above application areas are also characterized by certain practical limitations. First, only a limited amount of solution time is available. Order picking systems and information systems typically have a high transaction rate and they, more or less, operate on a continuous basis. Secondly, the number of requests to be served on one trip (or batch) is quite limited. For example, in order picking, the maximum number of picks made on a single trip typically varies between 12 and 20. Furthermore, the number of picks is constrained by the capacity of the S/R machine which is usually defined by the total weight and/or volume handled on a single trip. As shown by Karp [15] and Papadimitriou [20], the Traveling Salesman Problem is NPcomplete. Thus, even for the relatively small problem sizes encountered in the above areas, it is unlikely that an exact procedure will meet the solution time requirements. (A further discussion on the difficulty of obtaining an exact solution to the CTSP will be presented later). More importantly, if "fast and effective" heuristic procedures are developed, there will be little or no incentive to use an exact procedure. III. LITERATURE REVIEW The TSP literature has progressed in several directions. This section will be limited to studies based on heuristic procedures, particularly those concerned with performance evaluation. A review and evaluation of several TSP heuristics is presented by Golden et al. [13]. As tour construction heuristics, the authors study the following procedures: nearest neighbor, Clark and Wright savings, insertion procedures (nearest insertion, minimum cost insertion, arbitrary insertion, farthest insertion), Christofides' heuristic [9] and Stinson's heuristic [23]. As part of the above study, they also evaluate the convex hull heuristic. For tour improvement, they study the 2-way and 3-way exchange procedures developed by Lin [16]. The above procedures are tested on two types of 3

matrices: those that satisfy the triangle inequality and those that are randomly generated. According to Golden et al., composite heuristics (a tour construction heuristic followed by 2-way and 3-way exchanges) yield excellent results. Extensive computational tests are performed to compare resulting tour lengths. However, no runtimes are reported since the codes used were "reasonably inefficient." The convex hull heuristic coupled with various insertion strategies was also studied by Norback and Love [18] for the Euclidean metric, by Allison and Noga [1] for the Rectilinear metric, and by Goetschalckx [11] for the Chebyshev metric. Goetschalckx compared the performance of the hull heuristic with the band heuristic as a function of the rack shape and the number of points. Based on his results, the composite band heuristic yields tour lengths comparable to those obtained from the hull heuristic without improvement. However, the hull heuristic runs nearly twice as fast on the average. Both heuristics will be described shortly. The band heuristic was used by Gudehus [14] and Barrett [4] who studied order picking systems based on Person-on-Board AS/RS. However, the above authors did not evaluate the band heuristic against other procedures. The throughput capacity of Personon-Board AS/R systems was also studied by Bachers et al. [2] who compared the nearest neighbor, minimum cost insertion and band heuristics. They also considered sorting the x-coordinate of each point as well as sequencing the orders on a FCFS basis. The authors studied the performance of the above procedures relative to eachother and the exact solution. They varied the rack dimensions as well as the speed of the S/R machine and the maximum number of points visited on a single trip. Based on their results (displayed only in graphical mode), it appears that the minimum cost insertion heuristic generally yields better tour lengths. However, according to Bachers et al., the performance of each method depends on the above parameters and therefore an "evaluation of the methods can only be given generally and in rough outlines." For each heuristic considered in this study, additional references are provided 4

along with their description. Lastly, it may be noted that the reader may refer to a survey paper by Parker and Rardin [21] for reviewing results associated with various exact and "matrix driven" heuristic procedures. IV. DEFINITIONS AND ASSUMPTIONS For ease of reference, the study will be presented within the framework of order picking based on Person-on-Board AS/RS. Note that, in information systems, the S/R machine is replaced by the R/W head and the storage rack is represented as an array of cartridges housed in compartments. It is assumed that each trip originates and terminates at an Input/Output (I/O) point located at the lower left-hand corner of a rectangular storage rack. After visiting each opening once, the picker returns to the I/O point which is generally used for discharging the containers of the current order and obtaining the pick list and empty containers for the next order. (With Unitload AS/RS or Miniload AS/RS, the I/O point serves a slightly different purpose. However, when the motion of the empty S/R machine is traced, a tour similar to the one described above for Person-on-Board AS/RS is obtained; see Bozer [7]). In mass storage systems, an I/O point does not necessarily exist. Within a single batch of records, starting from its last location, the R/W head travels directly from one record to the next. That is, the R/W head must follow a Hamiltonian path rather than a circuit. However, one can first determine a sequence to visit all the record locations (including the I/O point). Once a tour is obtained, it can be transformed to a path by removing the two edges connecting the "unused" I/O point. Needless to say, additional error is introduced when the above approach is used. However, its impact is anticipated to diminish as the batch size is increased. Consider next the parameters used for the study. Suppose the S/R machine travels at x fpm and y fpm in the horizontal and vertical directions, respectively. Further suppose that the storage rack is L (>0) feet long and H (>0) feet high. Ignoring the 5

acceleration and deceleration of the S/R machine, let TX=L/x and TY=H/y. Following the approach presented by Bozer and White [8], the scaling factor, T and the shape factor, b can be computed as follows: T = max(TX,TY) and b=min(TX/T,TY/T) (1) Note that 0 < b < 1, by definition. If TX=TY, then b=l and the rack is "square-in-time." That is, the time to reach the most distant row is equal to the time to reach the most distant column. If TX>TY or TX<TY, then b<l. Suppose TX>TY. If the rack size and the S/R machine travel velocities remain constant, then, as H is decreased, b approaches to zero and the rack becomes "flatter" or "narrower." The heuristic procedures described in the following section apply to any rack and S/R machine combination. Since they are based on geometric concepts, their relative performance is likely to vary with the shape of the rack. The size of the rack, however, is not relevant as long as a reasonably large number of openings exist. Hence, results derived for a particular size rack by varying its shape factor will apply to other racks with similar shape factors. The principal assumptions for the study can be summarized as follows: 1. Each trip originates and terminates at the I/O point located at the lower lefthand corner of a rectangular storage rack. The Chebyshev distance from the I/O point to the closest opening is one distance unit. 2. The S/R machine follows the Chebyshev metric with unit travel speed in either direction. The travel speed is constant; that is, acceleration and deceleration are not considered. 3. A pre-determined number of randomly distributed openings are visited on each trip. The S/R machine stops at the center of each opening. 4. The rack is a discrete rack with 2500 openings. Each opening is represented as a unit distance square. As the shape factor is varied, approximately 2500 openings are retained. 6

V. TOUR CONSTRUCTION PROCEDURES Each heuristic is briefly described in the following paragraphs. For further details, appropriate references are presented along with each heuristic. (Note: for convenience, all the points in the following Figures are connected by straight lines which does not necessarily correspond to the path followed by the S/R machine). The Convex Hull Heuristic (H) The convex hull heuristic was first proposed independently by Stewart [22] and Or [19]. Subsequently, it was altered by Goetschalckx [11] (for the Chebyshev metric) and Allison and Noga [1] (for the rectilinear metric). A detailed description of the version used in this study is given by [11]. Parallel to the results derived for the Euclidean metric by Barachet [3], Goetschalckx [11] has shown for the Chebyshev metric that the order in which the points appear on the boundary of the convex hull is identical to the order in which they appear in the optimum tour. Hence, if point i precedes point k on the hull boundary, it will still precede point k in the optimum tour. In reference to Figure 1, the procedure consists of two phases. In the first phase, the convex hull of all the points is determined. In doing so, the maximum number of points are placed on the boundary by using the "free point" insertion scheme (see [11]). For example, as shown in Figure 1, due to the nature of the Chebyshev norm, point 8 may be inserted between points 5 and 6 with no increase in travel time. In fact, any point that falls within the parallelogram shown in dashed line can be considered to be a "free point." In general, traveling from point p to point s, if the travel time in the horizontal direction is not equal to the travel time in the vertical, then another point, say, point q can be visited with no increase in travel time as long as it falls within a certain parallelogram. If the above two travel times are equal, then the parallelogram becomes a straight line. (A similar case exists for the rectilinear metric where the parallelogram is replaced by a rectangle). 7

/ N N / 1 (I/O) 1 (I/O) Figure 1. The Convex Hull Heuristic 8

Note that, considered individually, there could be multiple "free points" in traveling from p to s. Suppose two such points are labeled q and r. Depending on the locations of q and r, if the picker follows the sequence p-q-r-s, then point r may no longer be a "free point" in traveling from q to s. However, it may be possible to follow the sequence p-r-q-s without increasing the travel time between p and s. Naturally, many possibilities exist for two or more "free points." For such cases, Goetschalckx [11] formulated and solved a sub-problem to maximize the number of "free points" inserted between two adjacent vertices of the convex hull. At the end of phase one, if all the points have been visited, then the tour obtained is optimum. Otherwise, the second phase consists of an insertion procedure where the remaining points are added to the current partial tour one at-a-time. The procedure used by Goetschalckx is the minimum cost insertion scheme where a given point is inserted between adjacent points on the partial tour such that incremental travel time is minimized. For example, in Figure 1, inserting point 9 between points 1 and 2 would cause the minimum increase in travel time. The Band Heuristic (B) The band heuristic appears to have been first proposed by Gudehus [14]. Perhaps due to its simplicity, the band heuristic is widely used in industry. It is based on dividing the rack into two equal width horizontal bands. In the lower band, the points are sorted in the increasing x-coordinate direction, while in the upper band they are sorted in the opposite direction. An example is shown in Figure 2. Note that any even number of bands can be used. However, Bozer [7] has shown that, approximately up to 25 points, using two bands minimizes the expected tour length obtained from the band heuristic. Since 25 points is considered a practical upper limit for nearly all the applications described earlier, the band heuristic considered in this study is limited to two bands. 9

The Band Insertion Heuristic (B9 and B2) The band insertion heuristic is a new geometric approach developed as a result of this study. It was derived by comparing the strengths and weaknesses of the previous two approaches. From this standpoint, it may not appear to be a novel approach. However, as shown later in the study, the band insertion heuristic performs quite well and its simplicity makes it attractive. The convex hull heuristic generally yields a reasonably good partial tour (obtained at the end of the first phase). However, coupled with the procedure to maximize the number of "free point" insertions, the first phase of the convex hull procedure is quite complicated in comparison to the band heuristic. The band heuristic, on the other hand, is simple yet it may cause some unnecessary "vertical travel" especially in sequencing those points close to the center of the rack. It is instructive to note that, the "best" way to sequence such points seems to be the least obvious. As a point is moved closer towards the center of the rack, not only will the travel time to reach that point increase, but the plausible ways it can be reached from other points will increase as well. The band insertion heuristic proceeds as follows: a certain portion of the rack is initially blocked out. All the points in the unblocked portion are sequenced according to the band heuristic to obtain a partial tour. Subsequently, the remaining points in the blocked region are inserted using the minimum cost insertion scheme described earlier. Two alternative approaches are shown in Figure 3 where the blocked region is crosshatched. Note that both approaches generate partial tours "similar" to those obtained from the convex hull heuristic. As shown in Figure 3, one may block either the center one-ninth of the rack or the center one-half strip. Naturally, other choices of size and shape exist. However, such refinements (which are likely to yield relatively minor improvements) will not be considered in this study. 10

0~~~~ 9~~~~~~~~~ 0~~~~ 1 (I/O) Figure 2. The Band Heuristic A (I/O) (I/O) - Point in outer region of rack A- Interior point to be inserted using minimum cost point Insertion scheme Figure 3. Alternative Insertion Regions for the Band Insertion Heuristic 11

The Sweep Heuristic (CS) The sweep heuristic was originally proposed by Gillett and Miller [10] for constructing delivery routes in vehicle routing problems. Although the sweep heuristic has performed reasonably well in the past, it has not been evaluated under the Chebyshev metric. In reference to Figure 4, the procedure can be summarized as follows: each point is connected to the I/O point with a straight line. Subsequently, all the points are sorted according to the angle they make with the x-axis. Note that the procedure is based on "sweeping" a straight line (pivoted at the I/O point) through the rack. Hence, it will be termed the "corner sweep" heuristic. Using the I/O point as the pivot point may cause "zigzagging" when certain points located towards the opposite ends of the rack have similar angles (see points 3 and 4 in Figure 4). An alternate location is the centroid of the rack where the magnitude and occurence of "zigzagging" is likely to decrease. In fact, based on a preliminary experiment, it was empirically shown that using the centroid as the pivot point (that is, the "center sweep" heuristic) outperforms the corner sweep heuristic by a fairly wide margin which increases with the number of points. As shown in Figure 5, with the center sweep heuristic, the I/O point is treated like another pick point. Note that the picker does not visit the centroid of the rack which is only used as a pivot point. The Spacefilling Curve (SF) Spacefilling curves have been studied by mathematicians for a long period of time. However, it was recently proposed by Bartholdi and Platzman [6] as a sequencing heuristic. As shown in Figure 6, a spacefilling curve connects all the openings in the rack based on their proximity. Although alternative curves exist, the one shown in Figure 6 was recommended by Bartholdi [5]. Generating the initial spacefilling curve is a fairly time consuming operation; however, it is only performed once for a given rack. After the spacefilling curve is constructed, each opening is assigned a sequence number based on its relative position on 12

(/) (I/O) (I/O) Figure 4. The (Corner) Sweep Heuristic M %1.0,go (I/O) Figure 5. The (Center) Sweep Heuristic 13

the curve. Thus, a given set of openings are sequenced simply by sorting the corresponding set of sequence numbers. An example is shown in Figure 6. VI. TOUR IMPROVEMENT PROCEDURES The heuristic procedures described above are considered to be "construction" routines. That is, given a set of points, each procedure is terminated as soon as a tour is obtained. Before designating the above tour as a final solution, however, one may attempt to improve it by varying the sequence in which certain points are visited. Composite procedures, that is, heuristic procedures that consist of a construction phase followed by an improvement phase have been shown to be quite effective; see, for example, Golden et al. [13]. A well-known improvement procedure due to Lin [16] is based on systematically replacing two or three edges in the current tour with alternative edges. For example, in Figure 7, a two-way exchange is accomplished by temporarily replacing the two edges (3-4) and (1-6) by (3-6) and (1-4). If the resulting tour is shorter, then the change is made permanent and the procedure is restarted. The number of all possible 2-way and 3-way exchanges grow rapidly with the number of points. Also, there are more possible 3-way exchanges than there are two, and compared to the speed of the construction phase, the computational effort required to evaluate all possible 3-way exchanges could quickly become unreasonable. Hence, the following restrictions are placed on 3-way exchanges. First, 3-way exchanges are considered only after all possible 2-way exchanges have been considered. This implies that generally, the 3-way exchange procedure will be restarted less often. Secondly, only those triplets in which two of the links are adjacent will be considered. The above approach has the effect of removing a point from its current position in the tour and inserting it between two other points. It was used by Goetschalckx [11] for the convex hull heuristic where non-optimum tours can occur only due to incorrect "free point" or minimum cost insertions. 14

(I/O) ( I/O) Figure 6. Sample Tour Based on a Spacefilling Curve 3 3 2 6 4 1 4 1 3 7% 2 5 Figure 7. The Two-Way Exchange Procedure 15

In an attempt to further explore the potential for reducing the runtime associated with the improvement phase, a specialized 2-way exchange routine similar to the one reported by Norback and Love [18] was developed. It considers only those cases where the two links are one removed from each other. For example, in a tour given by 1-2-3-4-5-1, it first considers the tour 1-3-2-4-5-1. If no improvement is obtained it next considers the tour 2-4-3-5-1-2 followed by 3-5-4-1-2-3, 4-1-5-2-3-4 and 5-2-1-3-4-5. At any point, if an improvement is obtained, the change is made permanent and the procedure continues from the next point in the new tour. For example, starting with 1-23-4-5-1, if the tour 1-3-2-4-5-1 is shorter, then the change is made and the next tour to be considered is 3-4-2-5-1-3 since point 3 now follows point 1. On the other hand, starting with 1-2-3-4-5-1 again, if the first improvement was obtained with 2-4-3-5-1-2, then the next tour to be considered would be 4-5-3-1-2-4 and so on. The procedure is not terminated until n consecutive exchanges yield no improvement (where n is the total number of points, including the I/O point). VII. THE MONTE CARLO EXPERIMENT A Monte Carlo experiment was conducted to compare the construction and improvement procedures described earlier. The basis of comparison is the tour length and runtime (or solution time). Six construction heuristics are considered: the convex hull (H), the band (B), the 1/9 band insertion (B9), the 1/2 band insertion (B2), the center sweep (CS) and the spacefilling curve (SF). Each heuristic is considered with each one of four improvement options: no improvement, specialized 2-way exchanges, (all possible) 2-way exchanges, and 2&3-way exchanges (that is, all possible 2-way exchanges followed by restricted 3-way exchanges). Thus 24 construction-improvement combinations were studied. Four rack shapes (b=1.00, 0.75, 0.50, 0.25).and five pick levels (5, 10, 15, 20 and 25 points) were used in the study. Each pick level was used with each rack shape, resulting in 20 rack-pick combinations. Fifty problems were randomly generated and assigned to each rack-pick combination. Thus, each problem set was solved with 24 construction-improvement combinations for a total of 24x20x50, or 24,000 problem 16

solutions. All the routines were coded in Pascal by the same individual. To the greatest extent possible, the same program modules and programming techniques were used in all programs (including a module used for sorting). The only exception is a code for the first phase of the hull heuristic which was obtained from Goetschalckx. Hence, no claim is made regarding the absolute efficiency of the programs. However, care was exercised to maintain comparable efficiency throughout the study. VIII. COMPARISON OF CONSTRUCTION PROCEDURES The above experiment is a factorial design in which rack shape and pick level are factors nested within problem sets, and the problem sets are completely crosssed with the construction heuristic and improvement factors. However, interactions between problem sets and the heuristic and improvement factors were not significant. The nested factor could thus be removed, and the experiment analyzed as having a completely crossed factorial design with four factors (heuristic, improvement, rack shape, pick level) and 50 replicates. An analysis of variance was applied to the tour lengths obtained through the experiment. The ANOVA indicates that all factors and almost all interactions have a significant effect on tour length. Consequently, a factor's main effect is determined by observing changes in tour length as that particular factor is varied while the other three are held constant. The first set of investigations is aimed at examining the mean tour length obtained from the above procedures for each rack-pick combination. Given a set of results for a particular combination, pairs of sample means were compared using Duncan's multiple range test. The results are shown in Table 1 where percent differences are given relative to the shortest tour length. Also, if the absolute difference between two means is less than a critical value (determined at a significance level of 1%), then they are underscored to 17

Table 1. Effect of Heuristics on Mean Tour Length - Duncan's Test Results and Percent Differences (No Improvement) b/Pick Mean Tour Lengths Ranked from Best to Worst H 82 CS SF B9 8 1.00/5 121.94 122.60 124.16 125.72 127.68 130.84 _- O _ 0.5X 1.8% 3.1% 4.7% 7.3X H 82 CS SF 89 B 1.00/10 148.24 152.24 154.54 155.78 170.16 174.52 4.0% 4.2% 5.1Z 14.8% 17.7% H 82 CS SF B9 B 1.00/15 174.34 178.86 187.06 189.60 206.18 214.40 - _2.6% 7.3. 8.8Z 18.3% 23.0% H 82 SF CS 89 B 1.00/20 193.32 203.60 213.00 215.70 236.72 251.36 ___- _ 5.3% 10.2% 11.6% 22.4Z 30.0% H B2 SF CS 89 B 1.00/25 211.94 224.72 236.38 246.72 274.46 298.12 - _ 6.0% 11.5X 16.4% 29.5% 40.7% H 82 CS SF 89 8 0.75/5 123.16 124.20 125.58 127.56 127.64 128.30 0.8% 2.0% 3.6% 3.6% 4.2% H 82 CS B9 SF B 0.75/10 154.74 156.80 162.90 168.48 169.56 170.46 - -- 1.32 5.3% 8.9X 9.6% 10.2% H B2 CS B9 SF B 0.75/15 174.96 179.26 194.08 195.24 200.10 200.84 _- _ 2.5Z 10.9X 11.6X 14.4% 14.8% H 82 CS SF 89 B 0.75/20 195.66 200.98 223.58 227.26 227.88 234.72 __- 2.7% 14.3Z 16.2% 16.5% 20.0% H 82 SF CS 89 8 0.75/25 216.60 225.04 253.42 259.40 263.50 274.50 - _3.9% 17.0% 19.8X 21.7% 26.7% I III C Sweep H-Hu 11 B-Band 89-1/9 Band 82-1/2 Band Insertion Insertion CS-Center Sweep SF-Spacef 1ling significantly different Curve at 1%) (Underscored means were not found to be 18

Table 1. (Cont'd) Effect of Heuristics on Mean Tour Length - Duncan's Test Results and Percent Differences (No Improvement) b/Pick Mean Tour Lengths Ranked from Best to Worst H 82 B CS SF 0.50/5 138.02 138.40 140.54 141.14 142.80 143.62 - O0.3% 1.8% 2.3% 3.5% 4.1% H 82 B9 B SF CS 0.50/10 160.84 162.70 168.80 170.20 177.54 179.88 -_ 1.2X 4.9% 5.8% 10.4Z 11.8% H 82 B9 B SF CS 0.50/15 179,54 182.90 192.12 195.32 205.02 213.02 -_1,.9% 7.0% 8.8Z 14.2Z 18.6% H 82 89 B SF CS 0.50/20 195.68 199.50 214.18 221.82 227.64 250.96 _- _ _ 2.0X 9.5Z 13.4% 16.3X 28.37 H 82 89 B SF CS 0.50/25 211.56 215.64 234.38 244.42 250.26 287.16 - _1.9% 10.8% 15.5% 18.3% 35.7% H B2 89 B SF CS 0.25/5 175.76 175.78 176.66 176.88 181.52 184.54 _- <~0.1% 0.5% 0.6% 3.3% 5.0% H 82'89 B SF CS 0.25/10 196.26 196.62 200.00 200.62 223.08 230.58 - O, 0.2% 1.9% 2.2Z 13.7% 17.5% 82 H B9 B SF CS 0.25/15 211.02 211.14 216.94 218.18 252.28 280.30 _- O0.1% 2.8% 3.4Z 19.6% 32.8% 82 H B9 B SF CS 0.25/20 220.80 222.04 230.04 233.76 278.34 329.48 _- O0.6Z 4.2% 5.9% 26.1% 49.2% 82 H 89 B SF CS 0.25/25 233.08 234.10 244.78 249.06 302.80 377.34 0.4X 5.0Z 6.9% 29.9% 61.9% I _ I II I I I IIII I I II I I IIICSCeteISee H-Hul1 B-Band 89-1/9 Band 82-1/2 Band Insertion Insertion CS-Center Sweep SF=Spacefilling significantly different Curve at 1%) (Underscored means were not found to be 19

indicate that the difference in question is not statistically significant. If a pair or set is not underscored, it indicates that the right element is significantly greater than the left element. From Table 1 it can be readily observed that, regardless of the shape factor, none of the mean tour lengths are significantly different at 5 picks. However, at 25 picks, all the differences observed are significant for b=1.OO and certain groupings occur as the shape factor is decreased. For 10 or more picks, heuristics H and B2 yield the shortest tour lengths for the entire range of b values considered for the study. Heuristic H appears to perform better for larger b values while the opposite is true for heuristic B2. The results shown in Table 1 are graphically illustrated in Figure 8 and Figure 9 for b=1.00 and b=0.25, respectively. Note that the worst performing heuristics at b=l.00 (that is, B and B9 in Figure 8), exchange positions with heuristic CS when b is decreased to 0.25 (see Figure 9). The above is mainly due to the fact that as the rack becomes "flatter," the impact of unnecessary vertical travel typically found in B and B9 diminishes while increased "zigzagging" (described earlier) is observed for CS. Figure 10 is a graphical representation of mean tour lengths as a function of b, averaged over all pick levels as well as over 50 replicates. Except for heuristics B and B9, all the heuristics yield shorter tour lengths when the rack is square-in-time; that is, b=1.00. The ideal rack shape for B and B9, however, appears to be b=0.50. (Recall that the total number of openings is kept fixed approximately at 2500 as the shape factor is varied). IX. EFFECT OF IMPROVEMENT PROCEDURES Recall that four options are considered in the improvement phase. Suppose TL(.) designates the final tour length obtained from the corresponding option. Then, us:-g the same initial tour obtained at the end of the construction phase, TL(2&3-way) < TL(2-way) < TL(NONE) (2) and TL(spec.2-way) I TL(NONE) (3) 20

300 - 290 - Hull (H) 280- A — 1/2 Band Insertion (B2) 270 - Spacefilling Curve (SF) 260 - 260 X- Center Sweep (CS) 250 250- 0-1/9 Band Insertion (B9) 240 240 - -Band (B) * 230 220 o 210 - 200 190 - 170 160 150 140 - 130 120 5 IS Numbe of Ptcks Figure 8. Mean Tour Length Without Improvement (b=1.00) 25 21

380 370- / 350 C 03-Hull (H) 330 340Q A-1/2 Band Insertion (82) 330- 0-1/9 Band Insertion (B9) 320- +-Band (B) 310 V-Spacefilling Curve (SF) 300 X-Center Sweep (CS) - 290'i 270* 260 8 250 240 230 220 - 210 200 - 190 180 170 - 5 15 25 Number of Picks Figure 9. Mean Tour Length Without Improvement (b=0.25) 22

290 280- \ - Hull (H) 270~~~~\ -A - 1/2 Band Inserti< ~270- \ V- Spacefilling Cur\ 260- \ X- Center Sweep (CS' - 1/9 Band Insertic c? ~~250~'- \ \Band (B) s 240 o 230 CS Ic 220- SF I 0 20: 90- 180 170 0.25 0.50 0.75 Rack Shope Figure 10. Mean Tour Length Without Improvement Averaged Over All Pick Levels 23

by definition. Hence, no statistical tests will be applied. Also, the number of exchanges considered by the specialized 2-way routine is only a subset of those considered by the 2-way routine. Hence, one would generally expect the 2-way routine to outperform its specialized version (except for certain "pathological" cases where the specialized 2-way exchange yields a shorter tour due to the particular order in which the exchanges are considered and executed). The results of the experiment are shown in Table 2 where percent differences are given relative to 2&3-way improvement. It can be clearly observed that, for all rack shapes and pick levels considered, the marginal reduction obtained in tour length by using the 2&3-way routine instead of the 2-way routine is almost negligible. Furthermore, for heuristic H, little or no reduction in tour length is obtained with any one of the improvement routines. As shown later, heuristic H generally yields nearoptimum tours. Hence, it is difficult to improve the initial tour. Likewise, improvement routines yield relatively small reductions under heuristic B2 where they become somewhat effective only as the pick level and the shape factor are increased. The performance of all the remaining heuristics (B, B9, CS and SF) considerably improve when the specialized 2-way exchange routine is used. However, further improvement is obtained when (all possible) 2-way exchanges are considered. The improvement is noticeably smaller for heuristics B and B9 when b=0.25. For heuristics CS and SF, it is relatively small if b=1.00. Referring back to Figure 8 and Figure 9, it is clear that improvement routines become more effective as the quality of the initial tour deteriorates. (A result that was anticipated). However, as seen in the next section, they also start consuming more computer time. Observing the columns of Table 2 across the heuristics reveals another result: for all the pick levels and b values considered, applying the 2-way exchange routine to B, B9, CS and SF yields final tour lengths that are comparable to those obtained from H and B2 without improvement. 24

Table 2. Effect of Improvement on Mean Tour Length Mde Toow L.on" (,Acdr n O, r) 2&3 Way 2.WV Non 100^ 134 12114T " 0.0% 121 9 00% 24 0.0% 1 0010 14. 41 0.0% 14t16 0.0% 14.24 <0.1% r0lS 1 173 0 173.40 0.1% 173 0.4% 174.34 0.6% 1010 191 9 19.4 0.3% 192. 0.5% 193.32 0.7% 10 S 0 20.t70 10.t 0.5% 211.4 08% 2114 I 1% 0.71 123.16 12.16 0.0% 121.16 0.0% 123.16 0.0% O.t71 114.3 154.40 <0.1% 14.52 0.1% 1S4.74 0.2% 0.715 174.32 174.7 0.2% 174.9 0.3% 1749 0.4% 0.7t/20 19. 1940 0.5% 1f.00 0.7% 19fi. 1.1% 0.725 213.33 214.70 0.7% 315.36 1.0% 21.60 1.S% 0.50 130.02% aO 0. 13.U 0.0% 13.02 0.0% O 1." 10. 1014 0.0% 10." 0.0% 1 O.U 0.0% 0.5011 179.0 179.12 0.1% 179.46 0.2% 179.54 0.3% 0.51 194.60 194.7t O.1% 195.42 0.4% 0.6% 0. 5 0.M 210.7 0.4% 211.14 0.6% 211. o0.6% 0.2m 17n.n 171.76 0.0%o,7 0.0% 1757 0.0% 0.21/10 1.16 11L0.1i 4.0% 19. 0.1% 19.2 0.1% 0.2S/1 1210. 0.14 0.0% 211.14 0.% 211.14 O.S% 0.21/30 213 20.4 0.1% 221. 0.7% 222.04 06% 0.22M 23.2 332.3<3 1% 334.0 0.0% 23410 00% _ _ k 2.213 Wp I2-Way tdNo" 1 00 0 19.76 191 1.7% 220.3 14.% 2X7 22.0% 1.110.7 21S.16 1 0% 2471 1.0% 274.46 29.0% 0.7/ 12.16 123.33 0.1% 12." 0.6% 127T64 3.6% 0.71/10 154l 154.10 0.1% 1S. 3.4% 16.46 9.1% 0.71 17.26 17014 0.5% 17.26 0.9% 19.24 114% 0.7 /2 194.4 19600 1.3% 212.46 9.3% 2270 t17.2% 0.7 25 214. 217.60 1.4% 244 12.3% 263.30 22.0% 0.50 13 0.02 13.0 0.0% 136. 0.3% 146.14 1% 0.510 O160." 16. 0.1% 1.46 16% 16.0 4 9% O.50IS 179.12 179.4 0.3% 1.06 3.3% 192.12 73% 050130 1.13 116 0.9% 20.0 4.6% 214.16 9.% 0.5 25 210JO 212.4 1.0% 221.72.5% 214.3 11.5% 0.2 175.76 17.76 0.0% 171. 0.1% 170." 0.5% 0.2S1/ 1906 1.I1 <0.1% 1 4 0.0% 206.00 2.0% 0.2/1S 207 I 210 0.2% 214 2.1% 21.94 3.4% 0.2J/26 2 221.4 0.% 0. 134 2.% 230.0 4.4% 0.21/31 1 233.43 0.7% 239.70 3.4% 24.76 5.6% Ack> Id2&0 Wft 24ft omNone %WWOC Pick 213Way wa 23S-Way C _ 1 35s 121. 12.10 0.1% 122.3 0.4% 124.16 1i% 100110 14612 14 0.3% 14.74 1.1% 114. 4 43% 10015 172.3 174.0 0.9% 177. 2.5% 170T 79% 100120 192.7 1".0 12% 200. 4.1% 215.70 119% 1 0025 210.92 21.1 1.1% 224. 6.7% 24.73 70% 0.7 12.16 123.34 0.1% 12.0 0.4% 125.0 2.0% 0.7/10 114. S1S.4 0.5% 157. 2.2% 16.0 S.4% 0.7/1S 174.54 175.0 0.7% 162 4.4% 14.0 11 2% 0.7S20 19".36 f22 10% 204. 46.0% 22.50 15.6% 0.7/2S 213.9 2103 2.1% 23S1. 10.1% 25940 21.2% 0.S1 13.03 13I.2 0.1% 139.0 0.7% 14260 3.5% 0.510 160.0 11.76 0.6% 161.30 2.% 179 119% 0.501S 1,79.36 11.12 10% 112.0 74% 21302 16.0% 0. 122 1976 1 4% 219.70 12.6% Z509 2.6% 0.5S25 211.63 21.i 1.0% 24S.3 15S.9 267 1 35.7% O.2/1 171.70 171.7 0.0% 176.60 0.5% 164.S4 50% 0.2s/10l 1.0 13..4 0.2%.3 1 3.7% 230.5 176% 02- 20. 7 210.7tl 0.4% 23.10 14.0% a20) 33.6% 0.21 32I. 222.12 0.0% 374.06 24.4% 321.4 49 % 0.2121 21.0 2 1 1%. 30. 13.4% 37734 G6.7% 25 Mean tow rurtU (Aft<C ing Order) 4& 100 12194 122.04 0 1' 23. 1 7% 130 64 I3 1.00110 14.24 14960 1.0% I8. 72% 1745 2 17 7% 1.00115 17.7 l 176.22 14% 1920 11 2 214 20 23 3% 1.0020 192.0 195.42 1 4% 22.06 16.3% 251 34 30 4 10025S 21171 216.4 2.2% 25.76 19.6% 26. 12 406% 0. t75 12. 16 123.3 0.1% 1240 0.7% 12. 30 4 2% 0.75/10 114.3 15S.04 0.4% 160.0 40% 170 4 1t 4% 0.7111 171.12 176.76 0.9% 19.00 6% 2 14 7% 0.75 /20 190 17 22 1.6% 21s54 11 1% 234 2 20 9 0.7/2S 213.26 2112 2.3% 24.24 15.S% 274 0 28 7% O.50 130.02 13.06 <0.1% 13.92 0.7% 141 14 2 3% O.5010 140.0 11.5 0.4% 164.0 2.2% 170 20 S 7% 0.t5S 179.30 100." 0.6% 16.00 4 % 19S 32 8 9% 0.50 14.04 140 1.8% 20.N4 7 2% 221 82 13 8% 0.501 20.00 212.4 1.3% 227.31 8.4% 24442 16 S% 0. 17.76 17.76 0.0% 176.12 0.2% 1764 0 6% 0.21/10 1". 1 0.10 40.1% 11.12 1 1% 20062 2 3 0.2r1 t.72 210.2 0.2% 215. 2.8% 21.18 4 0% 0.2/3 234 2211.S 0.6% 229.1S 4.2% 23 76 S6 % 0.1 231.1 1233.76 0.% 243.0. 4% 2490 4%.......~M Tow Len (A_ icng 9 Odef 3_1 3Wt& 33. y... 1/ 1.001 121.14 122.03 0.1% 22.0 j 5 1.010 14.33 146.0 0.2% 1S0.20 1 3% 152 24 2 6% 1.0011 173.3 17. 0.4% 176.04 1 5% 176 3 2% 1 00120 193.0 1.6 10. 19t i 3 3% 203 60 54% 1.501 212.0 214.6 0.9% 220.10 3.7% 224 72 S 9 0.7 1 123.14 123.42 0.2% 123.5 0 3% 24 20 a I% 0.75/10 114.0 114.74 0.1% 15.3 0.7%'1560' 4% 0.7/15 174.16 17.4 0.3% 177 1 S% 179 26 2 5% 0.70 194.24 19".0 0.7% 197 74 1 8% 200 3 5% 0.7S25 214." 215.30 0.6% 20.34 2 6% 22S 04 4 3% 0.51 130.03 1310 0.1% 131.10 0.1% 1340 3 3% 0.5010 1E0.6 161.02 0.1% 162.10 08% 162 70 1 S2 0.515 179.1 179.70 0.3% 11t 1 4% 182 90 2 % 0.502 14.3 11.6 0.5% 197 6 1 4% 199 So 2 4% 0.5S0 210.0 211.7 0.6% 213.14 1 4% 215 64 2 4% 0.25 17.7 17.76 0.0% 17S.7 <0.1% 75 78 <0 % 0.2S/10 11i.04 110.0 0.0% 11.46 0.2% 19 62 3% 0.21/1 200.72 210.0 0.% 210.3 0.S% 211 02 6% 0.21 2 2.14 202 <0.1% 320. 0.2% 22060o 3 1 0.211 231.5 231. 0.2% 232.50 04% 233 06 6S mdeM Tow Lo1 (Acamdtnq Orwt P1u M& 3201 Way 2-W S""',,, 2-Wa -S1nu 10 M 1214 " 12164 00% 122.4 04%, 2S2,2 100110 140.12 14.16 0.7% 150.20 14%'5 57:% 100 S 173.9 176.24 1.3% 10.) 3.7% 1690 i s 10010 192.36 1.1 6 1.9% 203 0 6.0% 213 00 o o s 1.0012 212.02 21022 2.0% 224.9 46.1% 2363 i 0.7/ 121.16 123.24 0.1% 124.5S 11% 1275 i s 0.7/10 1 4.2 115.22 0.5% 1616" 46% 10 54 *S 0.7111s 174. 170.34 0.0% 16.7 6.% 200 10 4 O.75/ 194.72 190.60 2.0% 2110 6.4% 227 26' 0.71S 214.24 210.2 1.0% 210 10.2% 253 42 6* s 0.S01 13.0 130.4 0.2% 1i 06 1 3% 43 U 0.5010 1460.9 11.94 0.6% 171 6.8% 177 4 o 0.50S1 179.14 ll1. 1.1% 10U 106% 20S 02. 0.501 103 190.96 15% 219 3 116% 227 G4 t.50 1 211.93 21 U 2.3% 240.46 13.5% 250 2 0.21/10 I.1 14 14 0.1% 2110 71% 223, 0.20/1 l 31 0. 0. 240. 14.5% 252 21 0.a2 32.3 2I1. 0o.7% I l. 20 7% 27 0.219.54 2M.3 24 6% 302 6 L

X. EFFECT OF RUNTIME ON PERFORMANCE EVALUATION Runtimes for each heuristic, averaged over the four rack shapes, five pick levels and 50 replicates, are given in Table 3. Considering the results given earlier in Table 2, it is clear that the additional time required by the 2&3-way exchange routine is not justified. Also note that, with no improvement, heuristics B and SF are the fastest while heuristic H is the slowest by a wide margin. However, when the improvement routines are executed, heuristics H and B2 display the smallest increase in runtime since they generate better initial tours. Excluding heuristic H, the runtime required by the 2-way exchange routine is approximately 1.5 to 3 times longer than the specialized version. As far as construction routines are concerned, heuristic H yields the shortest tour lengths while it has the longest average runtime. Hence, in the remainder of the study, other procedures will be compared against heuristic H. The results are summarized in Table 4 where each heuristic, coupled with an improvement-routine obtained from Table 2, is compared with heuristic H. The 2-way exchange routine was applied to each heuristic since it generates tour lengths comparable to those obtained from heuristic H. Note that, at 5 picks, no improvement routines are considered necessary. Furthermore, for 10 or more picks, heuristic B2 is evaluated in three forms: B2, B2+spec and B2+2-way where "spec" refers to the specialized 2-way exchange routine. Suppose AL(.) represents the AVERAGE tour LENGTH obtained from the corresponding heuristic procedure for a given number of picks and shape factor. For 5 picks, AL(B2) is always within 1% of AL(H) and it runs 2.71 times faster. Heuristic SF, on the other hand, runs 12.18 times faster than heuristic H with a maximum mean difference of only 4.1%. The following observations can be made for 10 or more picks: 1. AL(B+2-way) is always within 2.1% of AL(H). Up to 15 picks, it is 1.54 to 2.09 times faster. However, beyond 20 picks, its runtime is comparable to heuristic H. 26

Table 3. Average Runtime per Problem in Milliseconds (CDC Cyber 6400) Improvement Heuristic None Special 2-way 2&3-way Hull 14.403 14.783 17.054 24.883 Band 0.919 4.297 12.391 22.106 1/9 Bins 4.638 5.223 11.982 21.415 1/2 Bins 5.490 5.937 9.341 17.787 Csweep 1.687 5.176 13.913 23.246 Sfcurve 0.792 4.159 12.350 22.950 27

Table 4. Mean Runtime and Tour Length Compairson with Hull P Heuristic Avg RT for P FTimer % Diff from Avg Hull TL P Heuristic Faster.......... Picks Picks |than Hull 1.00 0.75 0.50 0.25 5 H 2.68 - 0 0 0 0 B 0.31 8.65 7.3% 4.2% 2.3% 0.6% B9 0.91 2.95 4.7% 3.6% 1.8% 0.5% B2 0.99 2.71 0.5% 0.8% 0.3% <0.1% CS 0.62 4.32 1.8% 2.0% 3.5% 5.0% SF 0.22 12.18 3.1% 3.6% 4.1% 3.3% 10 H 7.04 - 0 0 0 0 B+2-way 3.37 2.09 1.0% 0.2% 0.4% -0.1% 89+2-way 3.79 1.86 0.6% -0.2% <0.1% -0.1% 82 2.53 2.78 2.7% 1.3% 1.2% 0.2% 82 + spec 2.81 2.51 1.3% 0.7% 0.8% 0.1% 2 + 2 -way 3.65 1.93 0.2% <0.1% 0.1% -0.1% CS+2-way 3.76 1.87 0.2% 0.4% 0.6% 0.1% SF +2-way 3.24 2.17 0.6% 0.3% 0.7% <0.1% 15 H 12.83 - 0 0 0 0 8+2-way 8.32 1.54 1.7% 1.0% 0.5% -0.4% 89 + 2 - way 8.62 1.49 0.8% 0.7% 0.1% -0.4% 82 4.66 2.75 3.2% 2.5% 1.9% -0.1% 82+ spec 5.10 2.52 1.6% 1.5% 1.2% -0.2% 82+2-way 7.31 1.76 0.4% 0.3% <0.1% -0.5% CS + 2 - way 8.93 1.44 0.9% 0.5% 0.9% -0.2% SF + 2 - way 8.60 1.49 1.7% 0.8% 1.1% -0.2% 20 H 20.33 - 0 0 0 0 + 2-way 17.21 1.18 1.1% 0.8% 1.4% -0.2% 89 + 2 - way 16.82 1.21 1.4% 0.6% 0.6% -0.3% 82 7.68 2.65 5.3% 2.7% 2.0% -0.6% 82+ spec 8.24 2.47 3.1% 1.1% 1.0% -0.6% 82 +2-way 12.82 1.59 0.9% <0.1% 0.1% -0.8% CS+2-way 18.57 1.09 0.9% -0.2% 1.1% <0.1% SF+2-way 17.79 1.14 1.4% 1.5% 1.7% -0.1% 25 H 29.15 - 0 0 0 0 B+2-way 32.01 0.91 2.1% 0.7% 0.4% -0.1% 89+2-way 29.43 0.99 1.7% 0.5% 0.4% -0.3% 82 11.61 2.51 6.0% 3.9% 1.9% -0.4% 82+ spec 12.42 2.35 3.9% 1.7% 0.9% -0.6% 82+ 2- way 21.69 1.34 1.1% -0.3% 0.1% -0.9% CS + 2 - way 36.92 0.79 0.6% 0.8% 1.0% -0.1% SF + 2 - way 31.15 0.94 2.0% 0.7% 2.5% 0.2% H-Hull B9-1/9 Band Insertion B-Band B2-1/2 Band Insertion CS-Center Sweep SF-Spacefilling Curve 28

2. AL(B9+2-way) is always within 1.7% of AL(H). Up to 15 picks, it is 1.49 to 1.86 times faster. However, beyond 20 picks, its runtime is comparable to heuristic H. 3. The maximum mean deviation observed for B2 is 6%. However, it runs 2.51 to 2.78 times faster and up to 15 picks, AL(B2) is approximately within 3% of AL(H). 4. The maximum mean deviation observed for B2+spec is 3.9%. It runs 2.35 to 2.52 times faster and up to 20 picks, AL(B2+spec) is approximately within 3% of AL(H). 5. AL(B2+2-way) is always approximately within 1% of AL(H). It also runs 1.34 to 1.93 times faster. 6. AL(CS+2-way) is always approximately within 1% of AL(H). Up to 15 picks it runs 1.44 to 1.87 times faster. However, for 25 picks, its runtime is 1.27 times longer than that of heuristic H. 7. AL(SF+2-way) is always within 2.5% of AL(H). Up to 15 picks, it is 1.49 to 2.17 times faster. However, beyond 20 picks, its runtime is comparable to heuristic H. Hence, heuristics B+2-way, B9+2-way and SF+2-way are similar in performance. However, from an implementation standpoint (that is, programming, debugging, documenting, etc.), B+2-way and SF+2-way are more attractive. As far as tour quality is concerned, heuristic B2+spec can also be included in the above group. However, it runs approximately 1.25 times faster than the above three procedures. Heuristic B2+2-way is clearly a strong alternative to heuristic H. Compared to heuristic H, it runs 1.34 to 1.93 times faster and it is easier to implement especially if a pre-coded 2-way exchange routine is available. Furthermore, heuristic B is widely used in industry and converting it to heuristic B2 is a relatively straightforward task. XI. THE EXACT PROCEDURE As a reference point, heuristic H will be compared with the exact solution. However, it must be noted that using a branch-and-bound approach to solve the CTSP 7eads to considerably long execution times due to "free points" discussed earlier. As tre rack becomes flatter and/or the number of picks increase, the number of "free points" located 29

towards the center portion of the rack increase as well. In most cases, such points lead to alternative optimum solutions since they can be visited in a number of ways without increasing travel time. In fact, consider a hypothetical rack where b=0.00 and n is the total number of points (including the I/O point). Then, there are 2n-2 alternative optimum solutions which consist of traveling to the farthest point and back. Using a branch-and-bound approach will obviously require a considerable amount of computer time since the algorithm will not terminate until all optimum solutions have been identified. Using dynamic programming instead and/or perturbing some of the points may be helpful. However, such concerns are beyond the scope of this study. Consequently, only a subset of the problems were solved using the branch-and-bound code presented by Syslo et al. [24] (which is based on the algorithm developed by Little et al. [17]). The results are shown in Table 5. Due to excessively long execution times, it was not possible to study small b values for 20 and 25 picks. For the remaining rack-pick combinations, the performance of heuristic H is quite remarkable. Up to 10 picks, it almost always obtained the optimum solution. For 15 picks, the maximum mean deviation from the optimum tour length is 1.11%. For 20 or more picks, the above figure increases to 3.49%. Hence, within the range studied, heuristic H (on the average) generates optimum or near-optimum solutions. The same conclusion can be extended to heuristic B2+2-way since it was observed to be always within 1% of AL(H). The results shown in Table 5 can be extended to other heuristics. For example, consider the case where b=1.00 with 15 picks. From Table 5, AL(H) is 1.11% above optimum and (from Table 4) AL(B2+2-way) is 0.40% above AL(H). Hence, for b=1.00 and 15 picks, AL(B2+2-way) is 1.51444% above optimum. In evaluating the performance of each heuristic, one must also consider the:roblem environment. For example, in order picking, the system throughput is a function of total trip time which is defined as the sum of travel time, total picking time at selected openings and time spent at the I/O point. In many instances, the time associated ~ith 30

Table 5. Comparison of the Hull Tour Length and the Optimum Solution Shape Picks Factor 5 10 15 20 25 0.00% 0.15% 1.11% 1.34% 1.01% 1.00 1.00 0.98 0.75 0.67 0.80 50 50 24 12 5 50 47 13 5 2 0.00% 0.25% 0.54% 1.51% 3.49% 0.75 1.00 0.96 0.92 0.72 0.57 50 50 25 18 7 50 45 17 7 3 0.00% 0.01% 0.55% 1.20% 0.50 1.00 1.00 0.92 0.81 50 50 24 16 50 49 17 10 0.00% 0.13% 0.55% 0.25 1.00 1.00 0.87 50 50 15 50 47 10 Cell Entries: Line 1 - Average percent above optimum solution Line 2 - Proportion of observations which are within 2% of the optimum solution Line 3 - Number of observations Line 4 - Number of exact solutions obtained by heuristic 31

the latter two activities is independent of the sequence in which the openings are visited. Hence, as far as sequencing is concerned, they represent "fixed costs." Due to "fixed costs," a sizable reduction in travel time may represent only a marginal reduction in total trip time. The final outcome depends on the rack size and shape, the velocity of the S/R machine (in both directions), the pick level (that is, the number of picks/trip), the picking time and the time spent at the I/O point. XII. CONCLUSIONS Six tour construction heuristics, along with three improvement routines, were compared with one another. The heuristics were tested on problems ranging from 5 to 25 picks in four different rack shapes. Given a fixed rack size, the mean tour length obtained from the band and the 1/9 band insertion heuristics appears to be minimized approximately at b=0.50. For the hull, 1/2 band insertion, center sweep and spacefilling heuristics, the mean tour length decreases as b goes to 1.00. The hull heuristic, which is relatively the most complex and time consuming heuristic among those studied, has the best overall performance in tour length. The only construction heuristic comparable to the hull in tour quality is the newly developed 1/2 band insertion. Coupled with the 2-way exchange routine, its average tour length is within 1% of the average hull tour length and it runs 1.34 to 1.93 times faster. With no improvement, the above difference is within 6% and it runs 2.5 to 2.8 times faster. The 1/2 band insertion heuristic is also conceptually simpler and easier to implement. Improvement routines are not effective with the hull heuristic which already generates optimum or near-optimum solutions. They are also quite ineffective with the 1/2 band insertion routine. However, with the remaining heuristics (band, 1/9 band insertion, center sweep and spacefilling curve), the improvement in tour length can be substantial depending on the shape factor and the number of picks. The above four heuristics yield tour lengths comparable to those obtained from the 32

hull and 1/2 band insertion when 2-way and specialized 2-way exchange routines are applied. The corresponding increase in runtime, however, is proportional to the improvement in tour length. Little or no further improvement is observed when the 2&3way exchange routine is applied. Since the completion of this experiment, in an independent study, Goetschalckx [12] improved the hull heuristic by using a more efficient approach to determine the convex hull. He also evaluated the impact of deleting the "free point" insertion scheme by using the minimum cost insertion technique for such points. Subsequently, the author compared the hull heuristic with the band and 1/2 band insertion heuristics. Contrary to the results he reported in [11], Goetschalckx concluded that "differences in efficiency and effectiveness between the (above) heuristics are not considered very significant for practical purposes." For further details the reader is referred to [12]. 33

BIBLIOGRAPHY [1 ] Allison D. C. S. and Noga M. T., "The Rectilinear Traveling Salesman Problem," Information Processing Letters, Vol. 18, No. 4, 1984, pp. 195-199. [2 ] Bachers R., Dangelmaier W. and Warnecke H. J., "Selection and Use of Order Picking Strategies in a High-Bay Warehouse," Proceedings of Material Handling Focus'85, Material Handling Research Center and Georgia Institute of Technology, Atlanta, GA, September 1820, 1985. [3 ] Barachet L. L., "Graphic Solution of the Traveling Salesman Problem," Operations Research, Vol. 5, 1957, pp. 841-845. [4 ] Barrett B. G., "A Further Digression on the Over-Automated Warehouse: Some Evidence," Interfaces, Vol. 8, No. 1, 1977, pp. 46-49. [5 ] Bartholdi III J. J., Personal Communication, 1985. [6 ] Bartholdi III J. J. and Platzman L. K., "An O(nlogn) Planar Traveling Salesman Heuristic Based on Spacefilling Curves," Operations Research Letters, Vol. 1, No. 4, 1983, pp. 121-125. [7 ] Bozer, Y. A., "Optimizing Throughput Performance in Designing Order Picking Systems," Unpublished Ph.D. dissertation, Georgia Institute of Technology, Atlanta, GA, 1985. [8 ] Bozer Y. A. and White J. A., "Travel-Time Models for Automated Storage/Retrieval Systems," IIE Transactions, Vol. 16, No. 4, 1984, pp. 329-338. [9 ] Christofides N., "Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem," Management Sciences Research Report No. 388, Carnegie-Mellon University, February 1976. [10] Gillett B. E. and Miller L. R., "A Heuristic Algorithm for the Vehicle Dispatch Problem," Operations Research, Vol. 22, No. 2, 1974, pp. 340-349. [11] Goetschalckx M. P., "Storage and Retrieval Policies for Efficient Order Picking," Unpublished Ph.D. dissertation, Georgia Institute of Technology, Atlanta, GA, 1983. [12] Goetschalckx M. P., "Sequencing Picking Operations in a Man-Aboard Order Picking System," Technical Report MHRC-TR-85-17, Material Handling Research Center, Georgia Institute of Technology, Atlanta, GA, 1985. [13] Golden B., Bodin L., Doyle T. and Stewart W. Jr., "Approximate Traveling Salesman Algorithms," Operations Research, Vol. 28, No. 3, 1980, pp. 694-711. [14] Gudehus T., "Principles of Order Picking: Operations in Distribution and Warehousing Systems," (in German), W. Girardet, Essen, West Germany, 1973. [15] Karp R., "Reducibility Among Combinatorial Problems," Complexity of Computer Computations, pp. 85-104, Miller R. and Thatcher J. (eds.), Plenum Press, New York, 1972. [16] Lin S., "Computer Solutions of the Traveling Salesman Problem," Bell Systems Technical Journal, Vol. 44, 1965, pp. 2245-2269. 34

[17] Little J. D. C., Murty K. G., Sweeney D. W. and Caroline K., "An Algorithm for the Traveling Salesman Problem," Operations Research, Vol. 11, No. 6, 1963, pp. 972-989. [18] Norback J. P. and Love R. F., Geometric Approaches to Solving the Traveling Salesman Problem," Management Science, Vol. 23, No. 11, 1977, pp. 1208-1223. [19] Or I., "Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking," Unpublished Ph.D. dissertation, Department of Industrial Engineering and Management Sciences, Northwestern University, 1976. [20] Papadimitriou C. H., "The Euclidean Traveling Salesman Problem is NP-Complete," Theoretical Computer Science, Vol. 4, No. 3, 1977, pp. 237-244. [21] Parker R. G. and Rardin R. L., "The Traveling Salesman Problem: An Update of Research," Naval Research Logistics Quarterly, Vol. 30, 1983, pp. 69-96. [22] Stewart W. Jr., "A Computationally Efficient Heuristic for the Traveling Salesman Problem," Proceedings of the 13th Annual Meeting of Southeastern TIMS, South Carolina, 1977, pp. 75-83. [23] Stinson J., "A Heuristic Algorithm for Obtaining an Initial Solution for the Traveling Salesman Problem," presented at the Joint National ORSA/TIMS meeting, New York, May, 1978. [24] Syslo M. M., Deo N. and Kowalik J. S., "Discrete Optimization Algorithms with Pascal Programs," Prentice-Hall, 1983. [25] Wong C. K., "Minimizing Expected Head Movement in One-Dimensional and TwoDimensional Mass Storage Systems," Computing Surveys, Vol. 12, No. 2, 1980, pp. 167-178. 35