基于级联的改进差分进化算法的仓储多订单分批优化

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

中图分类号:

TP18

陈广锋, 余立潮. 基于级联的改进差分进化算法的仓储多订单分批优化[J]. 上海交通大学学报, 2021, 55(10): 1291-1302.

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.

图/表 16

图1

图2

图3

图4

图5

图6

表1

表2

图7

表3

表4

各个算法运行50次目标函数值平均值

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

表4

表5

各个算法运行50次CPU消耗时间的平均值

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

表5

图8

图9

图10

图11

参考文献 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