The solution of homework #4(ISyE 6202)
The Solution of Homework #6
# Problem 1
Sol)
a)Since the motions across the two axes are independent from each other, the most appropriate “distance” metric for this context is the Chebychev norm, which essentially measures the maximum time required for traveling between two locations with coordinates and .
Let’s label each picking location with a letter from A to G as follows:
The travel time per one bay and one level are respectively . If we assume that the travel time is computed to the center of each location, then we can compute the travel time between any two locations as follows:
O / A / B / C / D / E / F / GO
/ - / 15/200 / 13.5/200 / 22.5/200 / 28.5/200 / 34.5/200 / 33/200 / 33/200A / - / 9/200 / 18/200 / 24/200 / 30/200 / 18/200 / 21/200
B / - / 9/200 / 15/200 / 21/200 / 24/200 / 24/200
C / - / 12/200 / 12/200 / 18/200 / 18/200
D / - / 12/200 / 30/200 / 30/200
E / - / 24/200 / 18/200
F / - / 15/200
G / -
We can apply the closest insertion algorithm as follows:
Sp0= <O>, Sa0= {A, B, C, D, E, F, G}, C0 = [A(O), B(O), C(O), D(O), E(O), F(O), G(O)]
1)j* = arg min{CAO, CBO, CCO, CDO, CEO, CFO, CGO}
= arg min{15/200, 13.5/200, 22.5/200, 28.5/200, 34.5/200, 33/200, 33/200} = B
i*=1
Sa1={A, C, D, E, F, G}, Sp1=<O, B>, C1 = [A(B), C(B), D(B), E(B), F(B), G(B)]
2)j* = arg min{CAB, CCB, CDB, CEB, CFB, CGB}
= arg min{9/200, 9/200, 15/200, 21/200, 24/200, 24/200} = A (or C)
i*= arg min{COA+CAB-COB=(15+9-13.5)/200=10.5/200,
CBA+CAO-CBO= (9+15-13.5)/200=10.5/200} = 1 (or 2)
Sa2={C, D, E, F, G}, Sp2=<O, A, B>, C2 = [C(B), D(B), E(B), F(A), G(A)]
3)j* = arg min{CCB, CDB, CEB, CFA, CGA}
= arg min{9/200, 15/200, 21/200, 18/200, 21/200} = C
i*= arg min{ COC+CCA-COA= (22.5+18-15)/200=25.5/200,
CAC+CCB-CAB= (18+9-9)/200=18/200,
CBC+CCO-CBO= (9+22.5-13.5)/200=18/200} = 2 (or 3)
Sa3={D, E, F, G}, Sp3=<O, A, C, B>, C3 = [D(C), E(C), F(A, C), G(C)]
4)j* = arg min{CDC, CEC, CFC, CGC}
= arg min{12/200, 12/200, 18/200, 18/200} = D (or E)
i*= arg min{ COD+CDA-COA= (28.5+24-15)/200=37.5/200,
CAD+CDC-CAC= (24+12-18)/200=18/200,
CCD+CDB-CCB= (12+15-9)/200=18/200,
CBD+CDO-CBO= (15+28.5-13.5)/200=30/200} = 3 (or 2)
Sa4={E, F, G}, Sp4=<O, A, C, D, B>, C4 = [E(C, D), F(A, C), G(C)]
5)j* = arg min{CEC(D), CFA(C), CGC}
= arg min{12/200, 18/200, 18/200} = E
i*= arg min{ COE+CEA-COA= (34.5+30-15)/200=49.5/200,
CAE+CEC-CAC= (30+12-18)/200=24/200,
CCE+CED-CCD= (12+12-12)/200=12/200,
CDE+CEB-CDB= (12+21-15)/200=18/200,
CBE+CEO-CBO= (21+34.5-13.5)/200=42/200} = 3
Sa5={F, G}, Sp5=<O, A, C, E, D, B>, C5 = [F(A, C), G(C, E)]
6)j* = arg min{CFA(C), CGC(E)}
= arg min{18/200, 18/200} = F (or G)
i*= arg min{ COF+CFA-COA= (33+18-15)/200=36/200,
CAF+CFC-CAC= (18+18-18)/200=18/200,
CCF+CFE-CCE= (18+24-12)/200=30/200,
CEF+CFD-CED= (24+30-12)/200=42/200,
CDF+CFB-CDB= (30+24-15)/200=39/200,
CBF+CFO-CBO= (24+33-13.5)/200=43.5/200} = 2
Sa6={G}, Sp6=<O, A, F, C, E, D, B>, C6 = [G(F)]
7)i*= arg min{ COG+CGA-COA= (33+21-15)/200=39/200,
CAG+CGF-CAF= (21+15-18)/200=18/200,
CFG+CGC-CFC= (15+18-18)/200=15/200,
CCG+CGE-CCE= (18+18-12)/200=24/200,
CEG+CGD-CED= (18+30-12)/200=36/200,
CDG+CGB-CDB= (30+24-15)/200=39/200,
CBG+CGO-CBO= (24+33-13.5)/200=43.5/200} = 2
Sp7=<O, A, F, G, C, E, D, B>
Then the solution is OAFGCEDBO and the total travel time is (15+18+15+18+12+12+15+13.5)/200 = 118.5/200 min.
b) Consider the following figure.
First of all, notice that if S/R vehicle travels from the aisle picking station at full speed to both directions x and y, it travels along a line L with slope . If our destination is below line L, which means that the slope of travel direction is less than the one of L, horizontal travel takes longer than vertical travel and the travel time is dominated by . But if the destination is above line L, which means that the slope of travel direction is greater than the one of L, the travel time is dominated by .
Let’s consider the single-line order concerning an item located at bay 7 and level 2 in the rack. Assuming that we pick this item by visiting the center of the corresponding cell, the considered picking location is represented by the point P(19.5, 4.5) annotated in the figure above. Since P is below line L, the travel time to it is determined by the required motion on the x-axis, and it is equal to min. Motion on the y-axis can be carried out with any profile for speed which guarantees that the AS/R machine will be at coordinate Py by the time that it is also at coordinate Px. The following two scenarios constitute the most extreme ways to achieve this condition, and therefore, they delineate the region in which any other motion satisfying the above condition can take place:
1)Initially, move only along the x-axis with , ; at some point A, start moving also full speed along the y-axis, so that you reach coordinate Py exactly at the same time that you reach coordinate Px on the x-axis. Notice that the second part of the motion outlined by this scenario, corresponds to a line segment AP, which is parallel to line L.
2)Move along line L with speeds , overshooting the target coordinate Py on the y-axis; however, when you reach some point B on line L, reverse directions for the motion on the y-axis, so that the new motion is performed with speeds ; pick point B so that the line representing the motion during the second phase of this scenario will pass through the target point P.
The travel region with the same minimum travel time to reach P from the I/O point O, is limited to the trapezoid OAPB. Next, we characterize analytically this region, by determining the coordinates for points A and B.
1)Determining the coordinates of A
As it was mentioned above, line AP is parallel to L and passes through P(19.5, 4.5). Therefore, the equation of the line AP is . So if we substitute , we get A(10.5, 0). Notice that if we choose A(11,0), which is over A(10.5, 0) on the x-axis, the travel time is time(OA) + time(AP) = .
2)Determining the coordinates of B
In this case, line BP passes through point P(19.5, 4.5), but its slope is the equal to negative slope of L, Therefore, the equation for line BP is and this line intersects with . Since B is the intersection point, we get B(14.25, 7.125). Notice that if we choose B(15, 7.5), which is over B(14.25, 7.125) on the line L, then the travel time is time(OB) + time(BP) = .
So the trapezoid OAPB with O(0,0), A(10.5, 0), P(19.5, 4.5), and B(15, 7.5) is the rack region that could be visited at zero additional travel cost(time), while filling the item located at bay 7 and level 2.
Generalization
For any other item located in the rack below the line L, we can apply the same reasoning presented above for point P. For items located above the line L, the gist of the reasoning presented above remains the same, but the roles of the x and y axes will be interchanged. Finally, notice for a point P located on line L, the aforementioned trapezoid OAPB collapses to the line segment OP.
# Problem 2
a)A numbering scheme based on Sierpinski’s space-filling curve and a picking tour based on the bay-numbering scheme
If we super-impose Sierpinski’s space-filling curve on the considered picking area, we can get a numbering scheme and a picking tour based on the bay-numbering scheme, where the picking tour is constructed based on the minimum length tour between two consecutive locations, as follows:
b)(i) Why a bay-numbering scheme based on Sierpinski’s space filling curve might not be the most appropriate for the considered picking area ?
As we mentioned in class, a numbering scheme based on Sierpinski’s space filling curve essentially assumes/characterizes proximity according to Euclidean metric. However, in an aisle-based picking environment, the Euclidean distance is not the most appropriate metric for characterizing proximity, since locations that are physically close to each other might still require significant traveling through the aisles for consecutive picking among them. As a more concrete example, consider the locations 39, 40, 41, 42, 43, 44 and imagine that corresponding route for a picking list that picks from all these locations. In fact, the presented route demonstrates this type of inefficiency in the picking from the locations numbered 78 and 79 in the figure.
(ii) An alternative efficient bay-numbering scheme
Such a scheme must consider the aisle structure supporting the picking operation. Hence, in the considered case, the picking area can be divided into two sub-regions, upper and lower picking area, defined by the middle cross-aisle. Then, each of these two regions is numbered according to a numbering scheme based on the S-shaped heuristic.
(iii) Efficiency of the new number scheme
Based on the S-shaped heuristic, we can develop a numbering scheme and a new picking route with less travel distance as follows:
If we let the height of the picking area be 12m and the length between aisle be 2m, we can show the improvement of solution by computing picking tours with minimum length for each case in part a) and b). All computations are based on the assumption that we travel in the middle of the aisle so that the travel length from bottom to top is 11m.
The length of the solution in part a) = 62m
The length of the solution in part b) = 54m
Notice that the efficiency of the new tour came essentially from the elimination of the “backtracking” taking place in the original tour due to the impertinent numbering of locations 78 and 79.
Problem 3
Sol)
a)Seed algorithm
Seed selection: The largest number of aisles to be visited
Order addition: To minimize the number of new aisles
Sort while pick: Orders are picked on a picking cart with three separate compartments. So the maximum size of batching is 3.
Picking routes are designed according to the S-shaped heuristic
Assumption
-Each compartment is big enough to contain any number of one order.
-All computation of travel length is based on the assumption that we travel in the middle of the aisle so that the travel length from bottom to top is 11m.
-After picking the last item and there is no more item to pick, then we return to the docking station by Just taking the shortest way back.
From Figure 3, we have the following information:
order / a / b / c / d / e / f / g / h# of items / 7 / 4 / 4 / 4 / 6 / 2 / 4 / 1
# of aisles / 3 / 2 / 2 / 3 / 4 / 2 / 3 / 1
1)1st seed : e
order to be added / # of new aisles / selectiona / 1
b / 0 / *
c / 1
d / 0 / *
f / 1
g / 0
h / 0
Batch1 = {b, d, e}
Travel distance = 56(=4+11+2+11+2+11+2+11+2)
2)2nd seed : a
order to be added / # of new aisles / selectionc / 0 / *
f / 0 / *
g / 1
h / 1
Batch2 = {a, c, f}
Travel distance = 60(=4+11+6+11+2+11+11+4)
3)3rd seed : g
Batch3 = {g, h}
Travel distance = 44(=4+11+2+11+2+7+7)
So the total travel distance = 56 + 60 + 44 = 160.
b)Savings algorithm
Assumption
-Travel time is proportional to the travel distance so that we can use the travel distance to select a batch instead of travel time.
-All computation of travel length is based on the assumption that we travel in the middle of the aisle so that the travel length from bottom to top is 11m.
-After picking the last item and there is no more item to pick, then we return to the docking station by Just taking the shortest way back.
Following is the computation of the travel distance required for picking an order.
order / Travel distancea / 4+11+6+11+2+8+8+4=54
b / 4+11+2+11+2=30
c / 2+11+2+11+4=30
d / 4+11+2+11+2+5+5=40
e / 4+11+2+11+2+11+2+11+2=56
f / 2+11+2+11+4=30
g / 4+11+2+11+2+7+7=44
h / 2+10+10+2=24
Following is the computation of the travel distance required for picking each pair of orders and the distance savings.
order / Travel distance / Distance savings / Max(a,b) / 4+11+2+11+4+11+2+11+4=60 / 54+30-60=24
(a,c) / 4+11+6+11+2+11+11+4=60 / 54+30-60=24
(a,d) / 4+11+2+11+2+11+2+11+2+8+8+4=76 / 54+40-76=18
(a,e) / 4+11+2+11+2+11+2+11+2+8+8+4=76 / 54+56-76=34
(a,f) / 4+11+6+11+2+8+8+4=54 / 54+30-54=30
(a,g) / 4+11+2+11+2+11+2+11+2+8+8+4=76 / 54+44-76=22
(a,h) / 4+11+2+11+4+11+4+11+4=62 / 54+24-62=16
(b,c) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,d) / 4+11+2+11+2+5+5=40 / 30+40-40=30
(b,e) / 4+11+2+11+2+11+2+11+2=56 / 30+56-56=30
(b,f) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,g) / 4+11+2+11+2+7+7=44 / 30+44-44=30
(b,h) / 4+11+2+11+2=30 / 30+24-30=24
(c,d) / 4+11+2+11+2+11+2+11+2+11+11+4=82 / 30+40-82= -12
(c,e) / 4+11+2+11+2+11+2+11+2+11+11+4=82 / 30+56-82=4
(c,f) / 2+11+2+11+4=30 / 30+30-30=30
(c,g) / 4+11+2+11+2+11+2+11+2+11+11+4=82 / 30+44-82= -8
(c,h) / 2+11+4+11+2+11+11+4=56 / 30+24-56= -2
(d,e) / 4+11+2+11+2+11+2+11+2=56 / 40+56-56=40
(d,f) / 4+11+2+11+2+11+2+11+2+5+5+4=70 / 40+30-70=0
(d,g) / 4+11+2+11+2+7+7=44 / 40+44-44=40
(d,h) / 4+11+2+11+2+5+5=40 / 40+24-40=24
(e,f) / 4+11+2+11+2+11+2+11+2+5+5+4=70 / 56+30-70=16
(e,g) / 4+11+2+11+2+11+2+11+2=56 / 56+44-56=44 / *
(e,h) / 4+11+2+11+2+11+2+11+2=56 / 56+24-56=24
(f,g) / 4+11+2+11+2+11+2+11+2+5+5+4=70 / 30+44-70=4
(f,h) / 2+11+4+11+2+5+5+4=44 / 30+24-44=10
(g,h) / 4+11+2+11+2+7+7=44 / 44+24-44=24
The maximum savings is achieved by merging of order e and g. Let batch1={e, g}. It is interesting to notice that the merging of order c with d, g, or h results in the negative savings. So, they should not be merged in a batch.
Now we can compute the travel distance and the time savings considering batch1 and the remaining orders as follows.
order / Travel distance / Distance savings / Max(a,b) / 4+11+2+11+4+11+2+11+4=60 / 54+30-60=24
(a,c) / 4+11+6+11+2+11+11+4=60 / 54+30-60=24
(a,d) / 4+11+2+11+2+11+2+11+2+8+8+4=76 / 54+40-76=18
(a,e,g) / 4+11+2+11+2+11+2+11+2+8+8+4=76 / 54+56-76=34
(a,f) / 4+11+6+11+2+8+8+4=54 / 54+30-54=30
(a,h) / 4+11+2+11+4+11+4+11+4=62 / 54+24-62=16
(b,c) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,d) / 4+11+2+11+2+5+5=40 / 30+40-40=30
(b,e,g) / 4+11+2+11+2+11+2+11+2=56 / 30+56-56=30
(b,f) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,h) / 4+11+2+11+2=30 / 30+24-30=24
(c,d) / 4+11+2+11+2+11+2+11+2+11+11+4=82 / 30+40-82= -12
(c,e,g) / 4+11+2+11+2+11+2+11+2+11+11+4=82 / 30+56-82=4
(c,f) / 2+11+2+11+4=30 / 30+30-30=30
(c,h) / 2+11+4+11+2+11+11+4=56 / 30+24-56= -2
(d,e,g) / 4+11+2+11+2+11+2+11+2=56 / 40+56-56=40 / *
(d,f) / 4+11+2+11+2+11+2+11+2+5+5+4=70 / 40+30-70=0
(d,h) / 4+11+2+11+2+5+5=40 / 40+24-40=24
(e,g,f) / 4+11+2+11+2+11+2+11+2+5+5+4=70 / 56+30-70=16
(e,g,h) / 4+11+2+11+2+11+2+11+2=56 / 56+24-56=24
(f,h) / 2+11+4+11+2+5+5+4=44 / 30+24-44=10
The maximum savings is obtained by merging of order d,e, and g. Since the number of orders is 3, this constitutes one batch as batch1 = {d, e, g} with travel distance 56.
Now we have orders {a, b, c, f, h} and can compute the travel distance and the time as follows.
order / Travel distance / Distance savings / Max(a,b) / 4+11+2+11+4+11+2+11+4=60 / 54+30-60=24
(a,c) / 4+11+6+11+2+11+11+4=60 / 54+30-60=24
(a,f) / 4+11+6+11+2+8+8+4=54 / 54+30-54=30 / *
(a,h) / 4+11+2+11+4+11+4+11+4=62 / 54+24-62=16
(b,c) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,f) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,h) / 4+11+2+11+2=30 / 30+24-30=24
(c,f) / 2+11+2+11+4=30 / 30+30-30=30 / *
(c,h) / 2+11+4+11+2+11+11+4=56 / 30+24-56= -2
(f,h) / 2+11+4+11+2+5+5+4=44 / 30+24-44=10
The maximum savings is taken by merging of order a and f or c and f. We can choose one of them. Let’s choose a and f as a batch2 = {a, f}.
Then we have the following computation for possible pairs of orders.
order / Travel distance / Distance savings / Max(a,f,b) / 4+11+2+11+4+11+2+11+4=60 / 54+30-60=24 / *
(a,f,c) / 4+11+6+11+2+11+11+4=60 / 54+30-60=24 / *
(a,f,h) / 4+11+2+11+4+11+2+11+4=60 / 54+24-60=18
(b,c) / 4+11+2+11+4+11+2+11+4=60 / 30+30-60=0
(b,h) / 4+11+2+11+2=30 / 30+24-30=24 / *
(c,h) / 2+11+4+11+2+11+11+4=56 / 30+24-56= -2
The maximum savings is obtained by merging of order (a, f) and b or (a, f) and c. But if we select batch2 = {a, b, f}, then the savings from batch3 = {c, h} is -2. Otherwise, by selecting batch2 = {a, c, f}, the savings from batch3 = {b, h} is 24. So let’s choose batch2 = {a, c, f} and batch3 = {b, h} with travel distances 60 and 30 respectively.
So we have Batch1 = {d, e, g}, Batch2 = {a, c, f}, and Batch3 = {b, h} with the total travel distance is 160.
Extra Credit
Problem 1
Since the warehouse layout is the same as the one we dealt with in class, we can have the same 7 possible characterizations for an Lj(- or +) PTS and use the same notations.
Consider the following graph-based representation of the underlying topology. All computation of travel length is based on the assumption that we travel in the middle of the aisle so that the travel length from bottom to top is 11m.
Then the application of Ratliff & Rosenthal’s algorithm for the computation of the minimal length picking tour evolves as follows:
1)In the following tables, the leftmost column represents the classes of the starting sub-tour, used for visiting the nodes involved in the previous stage, and the topmost row represents the classes for the sub-tour constructed for the considered stage, through the addition to the starting sub-tour of new nodes, according to one of the possible schemes enumerated in the paper (e.g., I-i, I-ii, II-I, etc.) Each table cell represents the length of the resulting sub-tour and the applied extension scheme. For example, in the table for L2-, cell (1,1) states that a sub-tour for L2-, belonging to class (U,U,1C), can be constructed from a sub-tour for L1+, belonging to class (U,U,1C), by applying extension scheme II-i. The length of the new sub-tour is 15. The last line identifies the minimum-length sub-tour constructed for each class, the class of the starting sub-tour, and the applied extension scheme.
2)L1- : None
3)L1+
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
- / 11, I-i / 22, I-ii / 0, I-iii / 22, I-v / - / - / -
4)L2-
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 11+4=15, II-i
2.(E,0,1C) / 22+4=26, II-ii / 22+8=30,II-iv / 22,II-v
3.(0,E,1C) / 0+4=4, II-iii / 0+8=8,II-iv / 0,II-v
4.(E,E,1C) / 22+4=26, II-ii / 22+4=26,II-iii / 2+8=30,II-iv / 22,I-v
5.(E,E,2C)
6.(0,0,0C)
7.(0,0,1C)
min / 15, 1, II-i / 26, 2, II-ii
26, 4, II-ii / 4, 3, II-iii / 30, 4, II-iv / 8, 3, II-iv / 0, 3, II-v
5)L2+
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 15+20=35,I-ii
15+16=31,I-iii
15+16=31,I-iv
15+14=29,I-iv
15+22=37,I-v / 15+11=26,I-i
2.(E,0,1C) / 26+11=37,I-i / 26+20=46,I-ii / 26+22=48,I-v / 26+16=42,I-iii
26+16=42,I-iv
26+14=40,I-iv
3.(0,E,1C) / 4+11=15,I-i / 4+16=20,I-iii / 4+22=26,I-v / 4+20=24,I-ii
4+16=20,I-iv
4+14=18,I-iv
4.(E,E,1C) / 30+11=41,I-i / 30+20=50,I-ii
30+16=46,I-iii
30+16=46,I-iv
30+14=44,I-iv
5.(E,E,2C) / 8+11=19,I-i / 8+22=30,I-v / 8+20=28,I-ii
8+16=24,I-iii
8+16=24,I-iv
8+14=22,I-iv
6.(0,0,0C)
7.(0,0,1C)
min / 15, 3, I-i / 46, 2, I-ii / 20, 3, I-iii / 26, 3, I-v
26, 1, I-i / 18, 3, I-iv
6)L3-
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 15+4=19,II-i
2.(E,0,1C) / 46+4=50,II-ii / 46+8=54,II-iv / 46,II-v
3.(0,E,1C) / 20+4=24,II-iii / 20+8=28,II-iv / 20,II-v
4.(E,E,1C) / 26+4=30,II-ii / 26+4=30,II-iii / 26+8=34,II-iv / 26,II-v
5.(E,E,2C) / 18+8=26,II-iv
6.(0,0,0C)
7.(0,0,1C)
min / 19, 1, II-i / 30, 4, II-ii / 24, 3, II-iii / 34, 4, II-iv / 26, 5, II-iv / 20, 3, II-v
7)L3+
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 19+14=33,I-ii
19+8=27,I-iii
19+22=41,I-v / 19+11=30,I-i
2.(E,0,1C) / 30+11=41,I-i / 30+14=44,I-ii / 30+22=52,I-v / 30+8=38,I-iii
3.(0,E,1C) / 24+11=35,I-i / 24+8=32,I-iii / 24+22=46,I-v / 24+14=38,I-ii
4.(E,E,1C) / 34+11=45,I-i / 34+14=48,I-ii
34+8=42,I-iii
34+22=56,I-v
5.(E,E,2C) / 26+11=37,I-i / 26+22=48,I-v / 26,14=40,I-ii
26+8=34,I-iii
6.(0,0,0C)
7.(0,0,1C)
min / 27, 1, I-iii / 44, 2, I-ii / 32, 3, I-iii / 30, 1, I-i / 34, 5, I-iii
8)L4-
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 27+4=31,II-i
2.(E,0,1C) / 44+4=48,II-ii / 44+8=52,II-iv / 44,II-v
3.(0,E,1C) / 32+4=36,II-iii / 32+8=40,II-iv / 32,II-v
4.(E,E,1C) / 30+4=34,II-ii / 30+4=34,II-iii / 30+8=38,II-iv / 30,II-v
5.(E,E,2C) / 34+8=42,II-iv
6.(0,0,0C)
7.(0,0,1C)
min / 31, 1, II-i / 34, 4, II-ii / 34, 4, II-iii / 38, 4, II-iv / 40, 3, II-iv / 30, 4, II-v
9)L4+
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 31+16=47,I-ii
31+20=51,I-iii
31+8=39,I-iv
31+22=53,I-v / 31+11=42,I-i
2.(E,0,1C) / 34+11=45,I-i / 34+16=50,I-ii / 34+22=56,I-v / 34+20=54,I-iii
34+8=42,I-iv
3.(0,E,1C) / 34+11=45,I-i / 34+20=54,I-iii / 34+22=56,I-v / 34+16=50,I-ii
34+8=42,I-iv
4.(E,E,1C) / 38+11=49,I-i / 38+16=54,I-ii
38+20=58,I-iii
38+8=46,I-iv
38+22=60,I-v
5.(E,E,2C) / 40+11=51,I-i / 40+22=62,I-v / 40+16=56,I-ii
40+20=60,I-iii
40+8=48,I-iv
6.(0,0,0C)
7.(0,0,1C)
min / 39, 1, I-iv / 50, 2, I-ii / 54, 3, I-iii / 42, 1, I-i / 42, 2, I-iv
42, 3, I-iv
10)L5-
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 39+4=43,II-i
2.(E,0,1C) / 50+4=54,II-ii / 50+8=58,II-iv / 50,II-v
3.(0,E,1C) / 54+4=58,II-iii / 54+8=62,II-iv / 54,II-v
4.(E,E,1C) / 42+4=46,II-ii / 42+4=46,II-iii / 42+8=50,II-iv / 42,II-v
5.(E,E,2C) / 42+8=50,II-iv
6.(0,0,0C)
7.(0,0,1C)
min / 43, 1, II-i / 46, 4, II-ii / 46, 4, II-iii / 50, 4, II-iv / 50, 5, II-iv / 42, 4, II-v
11)L5+
ToFrom / 1.(U,U,1C) / 2.(E,0,1C) / 3.(0,E,1C) / 4.(E,E,1C) / 5.(E,E,2C) / 6.(0,0,0C) / 7.(0,0,1C)
1.(U,U,1C) / 43+22=65,I-iv
43+0=43,I-vi / 43+11=54,I-i
2.(E,0,1C) / 46+11=57,I-i / 46+0=46,I-vi / 46+22=68,I-v
3.(0,E,1C) / 46+11=57,I-i / 46+0=46,I-vi / 46+22=68,I-v
4.(E,E,1C) / 50+11=61,I-i / 50+22=72,I-v
50+0=50,I-vi
5.(E,E,2C) / 50+11=61,I-i / 50+22=72,I-v / 50+0=50,I-vi
6.(0,0,0C)
7.(0,0,1C) / 42+0=42,I-vi
min / 43, 1, I-vi / 46, 2, I-vi / 46, 3, I-vi / 50, 4, I-vi / 50, 5, I-vi / 42, 7, I-vi
The following tables summarize the above computation.
PTS-class
/ L1- / L1+ / L2- / L2+ / L3-1.(U,U,1C) / 11, -, I-i / 15, 1, II-i / 15, 3, I-i / 19, 1, II-i
2.(E,0,1C) / 22, -, I-ii / 26, 2, II-ii
26, 4, II-ii / 46, 2, I-ii / 30, 4, II-ii
3.(0,E,1C) / 0, -, I-iii / 4, 3, II-iii / 20, 3, I-iii / 24, 3, II-iii
4.(E,E,1C) / 22, -, I-v / 30, 4, II-iv / 26, 1, I-i
26, 3, I-v / 34, 4, II-iv
5.(E,E,2C) / 8, 3, II-iv / 18, 3, I-iv / 26, 5, II-iv
6.(0,0,0C)
7.(0,0,1C) / 0, 3, II-v / 20, 3, II-v
PTS-class
/ L3+ / L4- / L4+ / L5- / L5+1.(U,U,1C) / 27, 1, I-iii / 31, 1, II-i / 39, 1, I-iv / 43, 1, II-i / 43, 1, I-vi
2.(E,0,1C) / 44, 2, I-ii / 34, 4, II-ii / 50, 2, I-ii / 46, 4, II-ii / 46, 2, I-vi
3.(0,E,1C) / 32, 3, I-iii / 34, 4, II-iii / 54, 3, I-iii / 46, 4, II-iii / 46, 3, I-vi
4.(E,E,1C) / 30, 1, I-i / 38, 4, II-iv / 42, 1, I-i / 50, 4, II-iv / 50, 4, I-vi
5.(E,E,2C) / 34, 5, I-iii / 40, 3, II-iv / 42, 2, I-iv
42, 3, I-iv / 50, 5, II-iv / 50, 5, I-vi
6.(0,0,0C)
7.(0,0,1C) / 30, II-v / 42, 4, II-v / 42, 7, I-vi
From the L5+ column in the above table, we can see that the minimum-length picking tour has a length equal to 42, and belongs to class (0,0,1C). Furthermore, this tour was obtained from a sub-tour belonging to the class (0,0,1C) by applying the extension scheme I-vi. This sub-tour was, in turn, obtained from a sub-tour of class (E,E,1C) by applying the extension scheme II-v. Working backward in a similar fashion all the columns of the above table, we eventually get the minimum-length tour depicted in the following figure:
Remarks: We notice that, in the general case, one must check the feasibility of the resulting tour, before it is accepted as the minimum-length tour for considered set of picking locations. To exemplify this need in a more concrete manner, suppose there is no aisle 5 in the considered problem. Then the final stage in the above computations is L4+, and the obtained tables indicate that the minimum-length tour belongs to the class (U,U,1C) with a total length of 39 units. Furthermore, this tour is obtained from a sub-tour belonging to the class (U,U,1C) by applying the extension scheme I-iv. The complete construction of this tour will reveal that it is infeasible, if one is to start his/her trip from the node corresponding to the annotated I/O point. Hence, in this case, we need to consider the tour with the next smallest length. A feasible minimum-length tour is that belonging to the class (E,E,1C) with length 42, and, in fact, it is the one depicted in the above figure.
- 1 -