Capacitated route planning for supermarket distribution based on order splitting

doi:10.3969/j.issn.1000-5641.2022.05.013

Abstract

Abstract:

Vehicle stowage and route planning are common problems for various delivery methods related to supermarket distribution. In order to resolve these problems, we propose capacitated route planning for supermarket order distribution based on order splitting. We construct the problem model with the goal of minimizing the total cost of delivery. Combined with real cases, an improved gray wolf optimization algorithm adding a genetic mutation operation is proposed. The effectiveness of the model and algorithm is verified by comparing performance with the genetic algorithm. The results show that when the total demand of supermarkets is close to an integer multiple of the vehicle capacity, our proposed planning approach is better. This is mainly reflected in the fact that the order splitting plan can make full use of vehicle capacity, reduce the empty driving rate for vehicles, and reduce the total distribution cost.

Key words: supermarket distribution, vehicle routing problem, capacity limitation, order splitting strategy, improved grey wolf optimization algorithm

CLC Number:

TP311
C93

Xiao PAN, Dongna LU, Shuhai WANG. Capacitated route planning for supermarket distribution based on order splitting[J]. Journal of East China Normal University(Natural Science), 2022, 2022(5): 147-164.

Figures/Tables 16

Fig.1

Table 1

Glossary of grey wolf optimization algorithm"

术语		概念	本文含义
灰狼个体		所需解决问题的1个候选解	1个完整配送方案对应的所有车辆经过的商超客户序列
灰狼种群		许多灰狼个体组成的群体, 多个候选解的集合	多个完整配送方案对应的所有车辆经过的商超客户序列集合
灰狼社会等级划分	狼α	当前候选解集合中的第一最佳解决方案	多个完整配送方案集合中的第一最佳方案所对应的所有车辆经过的商超客户序列
	狼β	当前候选解集合中的第二最佳解决方案	多个完整配送方案集合中的第二最佳方案所对应的所有车辆经过的商超客户序列
	狼δ	当前候选解集合中的第三最佳解决方案	多个完整配送方案集合中的第三最佳方案所对应的所有车辆经过的商超客户序列
	狼ω	当前候选解集合中的其余候选解	多个完整配送方案集合中的其余方案所对应的所有车辆经过的商超客户序列
猎物		全局最佳解决方案	全局最佳的配送方案所对应的所有车辆经过的商超客户序列
适应度函数		灰狼种群中个体的社会等级划分指标	用于计算每个配送方案的总成本, 作为判断最佳配送方案的指标
狩猎行为	包围	计算灰狼个体与猎物的距离, 以进行灰狼位置更新	计算每个配送方案中车辆经过的商超客户序列与全局最佳配送方案中车辆经过的商超客户序列之间的距离
	追捕	假设狼α、狼β、狼δ更了解猎物潜在位置, 狼ω依据它们进行位置更新	将配送方案集合中排在前三的方案假定为当前的全局最佳方案, 并进行其余方案中车辆经过商超客户序列的更新
	攻击	确定最优解范围, 锁定最佳解决方案	在获得当前最佳配送方案的基础上, 继续改进, 以获得更佳的方案
	搜索	跳出局部最优解, 探索其他解决方案	跳出当前最佳配送方案, 探索其他更多方案

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 2

Table 3

Table 4

Table 5

Fig.7

Fig.8

Table 6

Fig.9

Table 7

References 19

1	刘菲. 大型连锁商超纳税筹划浅议. 中国市场, 2019, (29): 158- 159.
2	郑其明, 窦亚芹, 郑明轩. “新零售”背景下智慧物流治理策略探讨. 铁道运输与经济, 2020, 42 (4): 12- 17.
3	ARCHETTI C, BIANCHESSI N, SPERANZA M G. Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 2014, 238 (3): 685- 698.
4	DANTZIG G B, RAMSER J H. The truck dispatching problem. Management Science, 1959, 6 (1): 80- 91.
5	THANGIAH S R, POTVIN J Y, TONG S. Heuristic approaches to vehicle routing with backhauls and time windows. Computers and Operations Research, 1996, 23 (11): 1043- 1057.
6	范厚明, 杨翔, 李荡, 等. 基于生鲜品多中心联合配送的半开放式车辆路径问题. 计算机集成制造系统, 2019, 25 (1): 256- 266.
7	曾正洋, 许维胜, 徐志宇, 等. 应急物流中的累计时间式多车场车辆路径问题. 控制与决策, 2014, 29 (12): 2183- 2188.
8	周鲜成, 刘长石, 周开军, 等. 时间依赖型绿色车辆路径模型及改进蚁群算法. 管理科学学报, 2019, 22 (5): 57- 68.
9	CHEN P, GOLDEN B, WANG X Y, et al. A novel approach to solve the split delivery vehicle routing problem [J]. International Transactions in Operational Research, 2017, 24(1/2): 27-41.
10	YANG F, DAI Y, MA Z J. A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas. Transportation Research Part E: Logistics and Transportation Review, 2020, 141, 102024. doi: 10.1016/j.tre.2020.102024
11	揭婉晨, 侍颖, 杨珺, 等. 需求可拆分电动汽车车辆路径问题及其改进分支定价算法研究. 管理学报, 2020, 17 (12): 1873- 1880.
12	张亚明, 李艳明, 刘海鸥. 满意度约束多车型冷链物流VRP优化研究. 统计与决策, 2019, 35 (4): 176- 181.
13	XU H T, PU P, DUAN F. A hybrid ant colony optimization for dynamic multidepot vehicle routing problem. Discrete Dynamics in Nature and Society, 2018, 2018, 3624728. doi: 10.1155/2018/3624728
14	符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法. 中国管理科学, 2017, 25 (5): 78- 86.
15	SITEK P, WIKAREK J. Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): Model and implementation using hybrid approach. Annals of Operations Research, 2019, 273, 257- 277.
16	李阳, 范厚明. 求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法. 控制与决策, 2018, 33 (7): 1190- 1198.
17	GÖKALP O, UGUR A. A multi-start ILS–RVND algorithm with adaptive solution acceptance for the CVRP. Soft Computing, 2020, 24 (4): 2941- 2953.
18	MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer. Advances in Engineering Software, 2014, 69 (7): 46- 61.
19	田青文. 空间测角网三维平差. 地球科学与环境学报, 1988, (3): 106- 114.

编号	x/km	y/km	订单需求量/个	基于拆分的订单需求量/个
0	2828	997
1	3947	2042	537	410, 102, 25
2	3202	1208	160	102, 58
3	3592	1262	20	20
4	3483	800	35	35
5	3976	131	158	102, 56
6	3153	316	30	30
7	3221	706	42	42
8	2781	–78	233	205, 28
9	4571	1645	83	83
10	4833	1789	723	410, 205, 102, 6
11	4092	1196	1604	410, 410, 410, 205, 102, 67
12	3908	826	30	30
13	4796	143	1049	410, 410, 205, 24
14	4106	628	13	13
15	4191	974	45	45
16	4411	1706	80	80
17	2472	1156	649	410, 205, 34
18	2645	1638	72	72
19	3446	1710	30	30
20	2229	1201	442	410, 32

参数	取值
商超客户数( $ {n} $ )	20
最大迭代次数( $ {M} $ )	300 次
种群规模( $ {S} $ )	100
收敛因子( $ {\overrightarrow{a}} $ )	$ 2\to 0 $
最大变异次数( $ {T} $ )	60

迭代次数/次	标准灰狼优化算法		改进灰狼优化算法		$ \Delta z $ /%
迭代次数/次	运行时间 /s	配送总成本 /元	运行时间/s	配送总成本/元	$ \Delta z $ /%
100	50.31	1942.42	52.24	1651.38	14.98
200	100.83	1871.44	108.16	1578.99	15.63
300	150.78	1848.16	170.55	1508.18	18.40
400	200.41	1848.16	228.59	1553.38	15.94
500	251.27	1848.16	279.59	1527.49	17.35

种群规模	标准灰狼优化算法		改进灰狼优化算法		$ \Delta z $ /%
种群规模	运行时间 /s	配送总成本 /元	运行时间 /s	配送总成本 /元	$ \Delta z $ /%
20	90.88	1894.44	96.22	1628.40	14.04
40	146.05	1872.53	158.93	1562.16	16.57
60	203.97	1871.44	227.60	1563.04	16.47
80	255.69	1871.44	258.71	1553.38	16.99
100	317.21	1848.16	342.88	1508.18	18.39

订单状态	配送方案
无订单拆分	0→⑤→?→?→?→0
	0→⑥→⑧→?→?→?→0
	0→①→⑩→⑨→?→0
	0→②→?→③→?→?→④→⑦→0
有订单拆分	0→?→?→?→?→?→⑤→0
	0→⑦→②→?→?→?→④→⑥→⑧→?→?→?→0
	0→①→⑩→⑨→?→③→②→0