Multi-Order Batch Optimization of Warehouse Based on Cascaded Improved Differential Evolution Algorithm

doi:10.16183/j.cnki.jsjtu.2019.176

Abstract

Abstract:

In order to improve the flexibility and response efficiency of warehouse dispatching, a cascaded improved differential evolution algorithm is proposed to construct the allocation of goods with the picking trolley running time, shelf stability, and inventory capacity as resource conditions. The maximum completion time for each item in the batch order assigned to the optimal location of the corresponding partition is the two-level target model that is re-batch-allocated for the conditional order. The Lagrangian interpolation algorithm is integrated into the improved algorithm of the standard differential evolution algorithm to solve the two-level target model, and the two-level solution process is cascaded to complete the cascaded differential evolution algorithm to solve the multi-order batch allocation problem. Based on the adaptive adjustment of differential evolution parameters, the improved differential evolution algorithm combines the local search ability of Lagrangian interpolation to optimize the differential evolution algorithm, and uses local and global switching factors to dynamically adjust the evolution direction and improve the convergence performance of the algorithm. The improved differential evolution algorithm is applied to solve the problem of multi-order batch allocation. The experimental results show that the improved algorithm optimization results are better than the particle swarm optimization algorithm, the genetic algorithm, and the standard differential evolution algorithm, which reduces the maximum completion time of each batch of orders and effectively balance the workload.

Key words: order batch allocation optimization, shelf stability, maximum completion time, Lagrangian difference, differential evolution

CLC Number:

TP18

CHEN Guangfeng, YU Lichao. Multi-Order Batch Optimization of Warehouse Based on Cascaded Improved Differential Evolution Algorithm[J]. Journal of Shanghai Jiao Tong University, 2021, 55(10): 1291-1302.

Figures/Tables 16

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Tab.1

Tab.2

Fig.7

Tab.3

Tab.4

Average value of objective function values of each algorithm running 50 times

算法	$J -$
LGDE	4.02
PSO	6.43
DE	4.03
ADE	5.23

Tab.4

Tab.5

Aaverage value of CPU consumption time of each algorithm running 50 times

算法	$t - CPU$ /s
HLIDE	89.42
PSO	130.76
DE	131.71
ADE	138.15

Tab.5

Fig.8

Fig.9

Fig.10

Fig.11

References 20

[1]	RANDALL W S, GIBSON B J, CLIFFORD DEFEE C, et al. Retail supply chain management: Key priorities and practices[J]. The International Journal of Logistics Management, 2011, 22(3):390-402. doi: 10.1108/09574091111181381 URL
[2]	ARDJMAND E, SANEI BAJGIRAN O, RAHMAN S, et al. A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 115:16-34. doi: 10.1016/j.tre.2018.04.005 URL
[3]	ARDJMAND E, SHAKERI H, SINGH M, et al. Minimizing order picking makespan with multiple pickers in a wave picking warehouse[J]. International Journal of Production Economics, 2018, 206:169-183. doi: 10.1016/j.ijpe.2018.10.001 URL
[4]	CERGIBOZAN Ç, TASAN A S. Order batching operations: An overview of classification, solution techniques, and future research[J]. Journal of Intelligent Manufacturing, 2019, 30(1):335-349. doi: 10.1007/s10845-016-1248-4 URL
[5]	ÇELK M, SÜRAL H. Order picking under random and turnover-based storage policies in fishbone aisle warehouses[J]. IIE Transactions, 2014, 46(3):283-300. doi: 10.1080/0740817X.2013.768871 URL
[6]	MATUSIAK M, DE KOSTER R, KROON L, et al. A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse[J]. European Journal of Operational Research, 2014, 236(3):968-977. doi: 10.1016/j.ejor.2013.06.001 URL
[7]	CHEN T L, CHENG C Y, CHEN Y Y, et al. An efficient hybrid algorithm for integrated order batching, sequencing and routing problem[J]. International Journal of Production Economics, 2015, 159:158-167. doi: 10.1016/j.ijpe.2014.09.029 URL
[8]	CHEN C Y, CHEN Y Y, CHEN T L, et al. Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem[J]. International Journal of Production Economics, 2015, 170:805-814. doi: 10.1016/j.ijpe.2015.03.021 URL
[9]	HENN S. Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses[J]. Flexible Services and Manufacturing Journal, 2015, 27(1):86-114. doi: 10.1007/s10696-012-9164-1 URL
[10]	ÖNCAN T. MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem[J]. European Journal of Operational Research, 2015, 243(1):142-155. doi: 10.1016/j.ejor.2014.11.025 URL
[11]	PAN J C H, SHIH P H, WU M H. Order batching in a pick-and-pass warehousing system with group genetic algorithm[J]. Omega, 2015, 57:238-248. doi: 10.1016/j.omega.2015.05.004 URL
[12]	CHEN F Y, WANG H W, XIE Y, et al. An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse[J]. Journal of Intelligent Manufacturing, 2016, 27(2):389-408. doi: 10.1007/s10845-014-0871-1 URL
[13]	CORTÉS P, GÓMEZ-MONTOYA R A, MUÑUZURI J, et al. A tabu search approach to solving the picking routing problem for large- and medium-size distribution centres considering the availability of inventory and K heterogeneous material handling equipment[J]. Applied Soft Computing, 2017, 53:61-73. doi: 10.1016/j.asoc.2016.12.026 URL
[14]	HENN S, SCHMID V. Metaheuristics for order batching and sequencing in manual order picking systems[J]. Computers & Industrial Engineering, 2013, 66(2):338-351. doi: 10.1016/j.cie.2013.07.003 URL
[15]	MENÉNDEZ B, PARDO E G, ALONSO-AYUSO A, et al. Variable neighborhood search strategies for the order batching problem[J]. Computers & Operations Research, 2017, 78:500-512. doi: 10.1016/j.cor.2016.01.020 URL
[16]	ŽULJ I, KRAMER S, SCHNEIDER M. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem[J]. European Journal of Operational Research, 2018, 264(2):653-664. doi: 10.1016/j.ejor.2017.06.056 URL
[17]	陆汉东, 何卫平, 周旭, 等. 基于禁忌搜索的柔性作业车间分批调度[J]. 上海交通大学学报, 2012, 46(12):2003-2008.
	LU Handong, HE Weiping, ZHOU Xu, et al. An integrated tabu search algorithm for the lot streaming problem in flexible job shops[J]. Journal of Shanghai Jiao Tong University, 2012, 46(12):2003-2008.
[18]	SCHOLZ A, SCHUBERT D, WÄSCHER G. Order picking with multiple pickers and due dates-simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems[J]. European Journal of Operational Research, 2017, 263(2):461-478. doi: 10.1016/j.ejor.2017.04.038 URL
[19]	STORN R, PRICE K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4):341-359. doi: 10.1023/A:1008202821328 URL
[20]	黄裘俊, 张凯, 宋锦春, 等. 基于改进粒子群优化算法的取件机械手轨迹综合优化设计[J]. 东北大学学报(自然科学版), 2018, 39(11):1636-1641.
	HUANG Qiujun, ZHANG Kai, SONG Jinchun, et al. Path synjournal optimal design of pick-up manipulator based on modified particle swarm optimization[J]. Journal of Northeastern University (Natural Science), 2018, 39(11):1636-1641.

算法参数	种群规模	迭代代数	缩放因子	交叉概率	DF_max	DF_min	CR_init
货位分配	30	500	0.5	式(19)	0.20	0.05	0.18
订单分配	35	200	0.5	式(19),(20)	0.20	0.05	0.20

算法	最优值	N_t	t_CPU/s
GA	8.66	93	95.72
PSO	6.70	15	113.59
ADE	6.58	300	118.74
DE	4.58	350	110.68
LGDE	4.47	118	68.35