Journal of East China Normal University(Natural Science) ›› 2022, Vol. 2022 ›› Issue (5): 147-164.doi: 10.3969/j.issn.1000-5641.2022.05.013
• Spatio-temporal Data Analysis and Intelligent Optimization Theory for Logistics • Previous Articles
Xiao PAN1,2,*(), Dongna LU1, Shuhai WANG2
Received:
2022-07-07
Online:
2022-09-25
Published:
2022-09-26
Contact:
Xiao PAN
E-mail:smallpx@stdu.edu.cn
CLC Number:
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.
Table 1
Glossary of grey wolf optimization algorithm"
术语 | 概念 | 本文含义 | |
灰狼个体 | 所需解决问题的1个候选解 | 1个完整配送方案对应的所有车辆经过的商超客户序列 | |
灰狼种群 | 许多灰狼个体组成的群体, 多个候选解的集合 | 多个完整配送方案对应的所有车辆经过的商超客户序列集合 | |
灰狼社会 等级划分 | 当前候选解集合中的第一最佳解决方案 | 多个完整配送方案集合中的第一最佳方案所对应的所有车辆经过的商超客户序列 | |
狼β | 当前候选解集合中的第二最佳解决方案 | 多个完整配送方案集合中的第二最佳方案所对应的所有车辆经过的商超客户序列 | |
狼δ | 当前候选解集合中的第三最佳解决方案 | 多个完整配送方案集合中的第三最佳方案所对应的所有车辆经过的商超客户序列 | |
狼ω | 当前候选解集合中的其余候选解 | 多个完整配送方案集合中的其余方案所对应的所有车辆经过的商超客户序列 | |
猎物 | 全局最佳解决方案 | 全局最佳的配送方案所对应的所有车辆经过的商超客户序列 | |
适应度函数 | 灰狼种群中个体的社会等级划分指标 | 用于计算每个配送方案的总成本, 作为判断最佳配送方案的指标 | |
狩猎行为 | 包围 | 计算灰狼个体与猎物的距离, 以进行灰狼位置更新 | 计算每个配送方案中车辆经过的商超客户序列与全局最佳配送方案中车辆经过的商超客户序列之间的距离 |
追捕 | 假设狼α、狼β、狼δ更了解猎物潜在位置, 狼ω依据它们进行位置更新 | 将配送方案集合中排在前三的方案假定为当前的全局最佳方案, 并进行其余方案中车辆经过商超客户序列的更新 | |
攻击 | 确定最优解范围, 锁定最佳解决方案 | 在获得当前最佳配送方案的基础上, 继续改进, 以获得更佳的方案 | |
搜索 | 跳出局部最优解, 探索其他解决方案 | 跳出当前最佳配送方案, 探索其他更多方案 |
Table 2
Supermarket delivery information after order split"
编号 | 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 |
Table 4
Comparison of algorithm solution effects under different iterations"
迭代次数/次 | 标准灰狼优化算法 | 改进灰狼优化算法 | | |||
运行时间 /s | 配送总成本 /元 | 运行时间/s | 配送总成本/元 | |||
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 |
Table 5
Comparison of algorithm solution effects under different population sizes"
种群规模 | 标准灰狼优化算法 | 改进灰狼优化算法 | | |||
运行时间 /s | 配送总成本 /元 | 运行时间 /s | 配送总成本 /元 | |||
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 |
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. |
[1] | Jiling LI, Baolin LI, Songru YAN. Research on user behavior portrait and subject mining in the express logistics field during Coronavirus epidemic [J]. Journal of East China Normal University(Natural Science), 2022, 2022(5): 100-114. |
[2] | Yiming YU, Yuchen HONG, Ye WANG, Qiwen DONG. Design of experimental data governance module for chemical material formulation [J]. Journal of East China Normal University(Natural Science), 2022, 2022(5): 1-13. |
[3] | Xin GONG, Lihua XU, Liang DOU, Ruixiang ZHAO. Redundancy measurement and reduction of automated tests in financial technology [J]. Journal of East China Normal University(Natural Science), 2022, 2022(4): 43-55. |
[4] | Ping YU, Huiqi HU, Weining QIAN. Research on multi-objective cargo allocation based on an improved genetic algorithm [J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 185-198. |
[5] | Xiaoqin MA, Xiaohe GUO, Yufeng XUE, Lin YANG, Yuanzhe CHEN. Data augmentation technology for named entity recognition [J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 14-23. |
[6] | JI Yu, HE Yi-xuan, WU Guo-qun, WU Min. On evaluation of Bessel functions of the first kind via Prony-like methods [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(6): 42-60. |
[7] | XIE Qing-cheng, MAO Jia-li, LIU Ting. Dynamic scheduling strategy for bicycle-sharing in cities [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(6): 88-102. |
[8] | SHEN Hang-jie, JU Sheng-gen, SUN Jie-ping. Performance prediction based on fuzzy clustering and support vector regression [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(5): 66-73,84. |
[9] | JIANG Qun, DAI Ge-nan, ZHANG Sen, GE You-ming, LIU Yu-bao. Optimal route search based on user preferences [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(5): 100-112. |
[10] | LIU Zi-hao, HU Hui-qi, XU Rui, ZHOU Xuan. Implementation of LevelDB-based secondary index on two-dimensional data [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(5): 159-167. |
[11] | ZHANG Tao, ZHANG Xiao-lei, LI Yu-ming, ZHANG Chun-xi, ZHANG Rong. Woodpecker+: Customized workload performance evaluation based on data characteristics [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(5): 190-202. |
[12] | GAO Zhi-qiang, YUAN Min, ZHANG Jie. User requirements oriented service recommendation for a cloud desktop [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(4): 97-110. |
[13] | HUANG Ping, DU De-hui. A co-modelling approach for cyber-physical systems with SysML/MARTE/pCCSL [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(1): 48-57. |
[14] | XU Yang, WANG Zhi-jie, QIAN Shi-you. Distributed spatio-textual analytics based on the Spark platform [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 120-134,153. |
[15] | ZHANG Heng, CHEN Liang-yu. Optimization of the Levenshtein algorithm and its application in repeatability judgment for test bank [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 154-163. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||