Optimizing product allocation in a polling-based milkrun picking system

Figures & data

Figure 1. Comparison of (a) batch and (b) milkrun picking.

Figure 2. Overview of the milkrun picking system.

Figure 3. Description of d_j,n.

Figure 4. Example of the partially matched crossover operator.

Figure 5. Example of the edge recombination crossover.

Table 1. Parameters of the system instances test set.

Parameter	Values
Picking times, b (second)	0.1, 1.0, 2.
Traveling times, s (second)	0.1 , 1.0 , 2.
Number of different orders, $\left|\mathcal{K}\right|$ (units)	5, 20, 35
Order sizes, ${\sum }_{i=1}^N{K}_i$	1–2, 2–5, 5–10
Overall system load, ρ	0.1, 0.5, 0.8, 0.95

Table 2. Parameters used in the GA.

Parameter	Value	Parameter	Value
Population size, M	100	Probability pSM	0.15
Stable generations, Gstable	150	Probability pPMX	0.35
Maximum number of generations, Gmax	1 000	Probability pERX	0.20
Tournament size, tsize	3

Table 3. Solution quality and accuracy of the GA on the test set.

	Symmetric instances			Asymmetric instances
	EX	LG	GG	EX	LG	GG
Average GA time (second)	3.85	3.35	< 0.01	3.22	3.21	0.24
Average enumeration time (second)	22.19	20.30	< 0.01	21.59	19.45	1.35
Average number of generations	196.3	195.3	–	192.2	191.6	186.3
Solution quality (%)	93	95	100	94	93	100
Relative difference solution (%)	0.18	0.12	–	0.21	0.24	–

Table 4. The conditional probabilities, σ_ij, that product i (row) and product j (column) are picked for a customer order.

	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8
(a) Symmetric instances (order size 2–5 product units, locally-gated and exhaustive strategy)
Q1	1.00	0.41	0.13	0.67	0.30	0.52	0.54	0.28
Q2	0.24	1.00	0.31	0.43	0.25	0.29	0.32	0.46
Q3	0.13	0.52	1.00	0.34	0.26	0.23	0.31	0.26
Q4	0.43	0.48	0.23	1.00	0.18	0.33	0.46	0.36
Q5	0.34	0.50	0.30	0.32	1.00	0.28	0.50	0.27
Q6	0.44	0.43	0.20	0.44	0.21	1.00	0.60	0.38
Q7	0.33	0.34	0.19	0.43	0.27	0.43	1.00	0.36
Q8	0.24	0.68	0.23	0.47	0.20	0.38	0.50	1.00
(b) Asymmetric instances (order size 2–5 product units, locally-gated and exhaustive strategy)
Q1	1.00	0.53	0.24	0.65	0.14	0.39	0.48	0.43
Q2	0.40	1.00	0.24	0.55	0.19	0.35	0.31	0.43
Q3	0.26	0.35	1.00	0.36	0.48	0.26	0.62	0.46
Q4	0.46	0.52	0.24	1.00	0.13	0.38	0.47	0.32
Q5	0.13	0.24	0.43	0.18	1.00	0.34	0.50	0.44
Q6	0.43	0.51	0.26	0.59	0.39	1.00	0.52	0.35
Q7	0.36	0.30	0.42	0.49	0.38	0.35	1.00	0.37
Q8	0.38	0.50	0.37	0.39	0.40	0.28	0.43	1.00

Table 5. For picking strategy exhaustive (EX), globally-gated (GG), and locally-gated (LG), the fraction of times this strategy achieves the minimal mean order throughput time given system load ρ, traveling time s, and picking time b.

	b	0.10			1.00			2.00
s	ρ	EX	GG	LG	EX	GG	LG	EX	GG	LG
(a) Symmetric instances
0.10	0.10	0.96	0.00	0.04	0.00	0.30	0.70	0.00	0.63	0.37
	0.50	0.78	0.22	0.00	0.00	0.93	0.07	0.00	1.00	0.00
	0.80	0.67	0.30	0.04	0.00	1.00	0.00	0.00	1.00	0.00
	0.95	0.63	0.37	0.00	0.00	1.00	0.00	0.00	1.00	0.00
1.00	0.10	1.00	0.00	0.00	0.96	0.00	0.04	0.67	0.00	0.33
	0.50	1.00	0.00	0.00	0.78	0.22	0.00	0.48	0.30	0.22
	0.80	1.00	0.00	0.00	0.67	0.30	0.04	0.37	0.52	0.11
	0.95	1.00	0.00	0.00	0.63	0.37	0.00	0.30	0.59	0.11
2.00	0.10	1.00	0.00	0.00	1.00	0.00	0.00	0.96	0.00	0.04
	0.50	1.00	0.00	0.00	1.00	0.00	0.00	0.78	0.22	0.00
	0.80	1.00	0.00	0.00	0.93	0.07	0.00	0.67	0.30	0.04
	0.95	1.00	0.00	0.00	0.89	0.11	0.00	0.63	0.37	0.00
(b) Asymmetric instances
0.10	0.10	1.00	0.00	0.00	0.00	0.37	0.63	0.00	0.63	0.37
	0.50	0.81	0.19	0.00	0.00	0.93	0.07	0.00	1.00	0.00
	0.80	0.70	0.26	0.04	0.00	1.00	0.00	0.00	1.00	0.00
	0.95	0.59	0.41	0.00	0.15	0.85	0.00	0.15	0.85	0.00
1.00	0.10	1.00	0.00	0.00	1.00	0.00	0.00	0.78	0.00	0.22
	0.50	1.00	0.00	0.00	0.81	0.19	0.00	0.48	0.30	0.22
	0.80	1.00	0.00	0.00	0.70	0.26	0.04	0.33	0.56	0.11
	0.95	1.00	0.00	0.00	0.59	0.41	0.00	0.41	0.48	0.11
2.00	0.10	1.00	0.00	0.00	1.00	0.00	0.00	1.00	0.00	0.00
	0.50	1.00	0.00	0.00	1.00	0.00	0.00	0.81	0.19	0.00
	0.80	1.00	0.00	0.00	0.89	0.11	0.00	0.70	0.26	0.04
	0.95	1.00	0.00	0.00	0.81	0.19	0.00	0.59	0.41	0.00

Table 6 For picking strategy exhaustive (EX), globally-gated (GG), and locally-gated (LG), the average percentual improvement in mean order throughput time given the strategies, system load ρ, traveling time s, and picking time b.

	b	0.10			1.00			2.00
s	ρ	EX / LG	EX / GG	LG / GG	EX / LG	EX / GG	LG / GG	EX / LG	EX / GG	LG / GG
(a) Symmetric instances
0.10	0.10	−0.54	−16.74	−17.17	0.70	−3.04	−2.37	0.94	0.27	1.20
	0.50	−2.04	−10.27	−11.96	4.42	10.62	15.52	5.61	15.35	21.80
	0.80	−2.33	−5.50	−7.47	9.29	20.66	31.91	11.26	26.34	40.51
	0.95	−2.06	−3.14	−4.83	12.89	26.03	42.29	15.32	32.19	52.34
1.00	0.10	−1.12	−21.75	−22.59	−0.54	−16.74	−17.17	−0.18	−13.16	−13.29
	0.50	−5.33	−18.36	−22.61	−2.04	−10.27	−11.96	−0.04	−4.63	−4.53
	0.80	−8.74	−16.17	−23.40	−2.33	−5.50	−7.47	1.38	1.78	3.44
	0.95	−10.76	−15.37	−24.38	−2.06	−3.14	−4.83	2.83	5.09	8.40
2.00	0.10	−1.17	−22.11	−22.99	−0.82	−19.22	−19.85	−0.54	−16.74	−17.17
	0.50	−5.60	−18.95	−23.39	−3.59	−14.24	−17.20	−2.04	−10.27	−11.96
	0.80	−9.28	−16.97	−24.58	−5.29	−10.71	−15.25	−2.33	−5.50	−7.47
	0.95	−11.50	−16.29	−25.85	−6.03	−9.09	−14.35	−2.06	−3.14	−4.83
(b) Asymmetric instances
0.10	0.10	−0.55	−16.99	−17.42	0.63	−2.70	−2.09	0.86	0.67	1.52
	0.50	−2.17	−9.79	−11.61	4.16	11.02	15.65	5.37	15.72	21.91
	0.80	−2.14	−4.53	−6.33	8.93	21.33	32.20	10.89	27.05	40.82
	0.95	−1.50	−1.47	−2.68	10.37	22.83	36.00	12.43	28.09	44.51
1.00	0.10	−1.10	−22.12	−22.94	−0.55	−16.99	−17.42	−0.21	−13.25	−13.41
	0.50	−5.24	−17.81	−22.03	−2.17	−9.79	−11.61	−0.26	−4.14	−4.26
	0.80	−8.03	−14.86	−21.61	−2.14	−4.53	−6.33	1.33	2.60	4.22
	0.95	−7.96	−11.43	−18.24	−1.50	−1.47	−2.68	2.25	5.31	8.01
2.00	0.10	−1.14	−22.49	−23.34	−0.81	−19.55	−20.16	−0.55	−16.99	−17.42
	0.50	−5.48	−18.40	−22.78	−3.64	−13.74	−16.76	−2.17	−9.79	−11.61
	0.80	−8.52	−15.63	−22.74	−4.87	−9.59	−13.82	−2.14	−4.53	−6.33
	0.95	−8.50	−12.17	−19.39	−4.48	−6.34	−10.29	−1.50	−1.47	−2.68

Table 7. Parameters of the China online shopping warehouse.

Parameter	Value
(a) Warehouse
Warehouse area	985 m^2
Aisles	8
Number of storage locations per aisle side	30
(b) Order pickers
Number of order pickers	30
Number of storage locations per picker, N	16
Number of aisles per picker, A	4
Number of storage locations per rack per picker, L	2
(c) Operations
Travel speed of a picker	0.48 meter/sec.
Mean picking time, $E(B_i)$	1.51 sec.
Second moment picking time, $E(B_i^2)$	3.82
Mean traveling time (depot), s0	63.0 sec.
Mean traveling time (side to side), s1	2.00 sec.
Mean traveling time (adjacent storage locations), s2	2.50 sec.
Mean traveling time (adjacent aisles), s3	9.60 sec.

Figure 6. Expected demand distribution China online shopping warehouse.

Figure 7. Results for China online shopping warehouse for different utilization ρ and the three picking strategies.

Figure 8. Box plots of mean order throughput times for 3000 different product allocations for various values of the utilization ρ.