基于K均值聚类算法的生鲜运输路径优化模型

doi:10.19788/j.issn.2096-6369.220110

农业大数据学报 ›› 2022, Vol. 4 ›› Issue (1): 89-97.doi: 10.19788/j.issn.2096-6369.220110

• 专题——农产品冷链物流智能管控与大数据 • 上一篇下一篇

基于K均值聚类算法的生鲜运输路径优化模型

周蓉蓉^1,³(), 陈栋^2,³(), 刘思远^2,⁴

^1.南京国家现代农业产业科技创新中心，南京 211800
^2.国家农业信息化工程技术研究中心，北京 100097
^3.智慧农业技术集成与应用创新农业农村部重点实验室，南京 211800
^4.广西大学计算机与电子信息学院，南宁 530004

收稿日期:2022-01-08 出版日期:2022-03-26 发布日期:2022-06-29
通讯作者: 陈栋 E-mail:jstfzzrr@163.com;chend@nercita.org.cn
作者简介:周蓉蓉，女，硕士，研究方向：农业信息技术 ; E-mail:jstfzzrr@163.com
基金资助:
北京市科技计划课题(Z191100004019007)

Optimization Model of Vehicle Scheduling for Fresh Food Distribution Using the K-means Clustering Algorithm

Rongrong Zhou^1,³(), Dong Chen^2,³(), Siyuan Liu^2,⁴

^1.Nanjing National Modern Agricultural Industry Science and Technology Innovation Demonstration Park Management Committee, Nanjing 211800, China
^2.National Engineering Research Center for Information Technology in Agriculture(NERCITA), Beijing 10097, China
^3.Agricultural Core (Nanjing) Institute of Intelligent Agriculture, Nanjing 211800, China
^4.Guangxi University, Nanning 530004, China

Received:2022-01-08 Online:2022-03-26 Published:2022-06-29
Contact: Dong Chen E-mail:jstfzzrr@163.com;chend@nercita.org.cn

摘要/Abstract

摘要：

针对生鲜农产品供应企业面临的生鲜配送时效性高，生鲜配送过程损耗高，配送车辆调度人工依赖性强的问题。本研究基于车辆路径优化方法，面向生鲜农产品城市配送场景，针对以上问题提出了基于K均值聚类算法的生鲜运输路径优化模型。模型求解过程引入K均值聚类算法，实现了根据配送目的地位置的配送单元划分，以配送车辆使用数量较少情况下配送距离和货物损耗最小为目标函数，并使用改进的遗传算法进行求解，从而实现了生鲜农产品城市配送场景下的车辆最优调度、路径自主优化等功能。本研究采用北京某生鲜供应企业实际的配送过程数据作为研究数据对模型进行训练求解，结果显示在对配送目的地不进行聚类情况下配送的里程为3753.01公里，使用的车辆数量为32辆；在对配送目的地进行聚类情况下配送的里程为2105.4公里，使用过的车辆数量为34辆；在使用的车辆数量没有大幅度增长的情况下，经过聚类分组的模型求解相比未进行聚类分组的模型求解其配送总里程降低了43.9%。因此，可以得出基于K均值聚类算法的生鲜运输路径优化模型适合城市生鲜配送场景的应用。最后，本研究基于以上研究模型设计研发了适用于城市生鲜农产品配送的车辆路径优化服务系统，实现了生鲜配送车辆调度优化等功能，为生鲜供应企业降低配送成本，提升企业效率提供了有效手段。

关键词: 城市生鲜配送, 多目标路径优化, K均值聚类, 生鲜农产品, 农产品物流, 农产品供应链

Abstract:

Key issues facing enterprises engaged in the supply of fresh agricultural products include the timeliness of the distribution of fresh food, the high cost of this distribution, and predominantly manual scheduling of distribution vehicles. A method to optimize vehicle routes, using the K-means clustering algorithm, was used to develop a model for optimizing transport routes by projecting the urban distribution scenario of fresh agricultural products. The K-means clustering algorithm, an improved genetic algorithm, was introduced into a model for optimizing the distribution paths of fresh produce, which enabled the division of distribution units to be matched with the distribution locations. Consequently, distribution distances and cargo losses were minimized, and the time window as an objective function was not violated. Actual data derived from the distribution orders of a fresh food supply company in Beijing were used in the study. The results of the analysis indicated that without clustering the distribution destinations, the distribution mileage amounted to 3,753.01 km, and the number of vehicles used was 32. The corresponding delivery mileage covered when the delivery destinations were clustered was 2,105.4 km, and the number of vehicles used was 34. When the number of vehicles used exceeded a small number, the total delivery mileage calculated by clustering grouping model was 43.9% lower than that calculated without clustering grouping model. Therefore, it can be concluded that the clustering algorithm based on K-means is suitable for developing distribution scenarios entailing a wide geographical range. A service system for the distribution of urban fresh agricultural products can be designed and developed using the above model. It provides effective means for fresh supply enterprises to reduce distribution cost and improve enterprise efficiency.

Key words: fresh food delivery, vehicle scheduling optimization model, K-Means clustering algorithm, fresh agricultural products, agricultural product logistic, Agri-food supply chain

中图分类号:

TU205

周蓉蓉, 陈栋, 刘思远. 基于K均值聚类算法的生鲜运输路径优化模型[J]. 农业大数据学报, 2022, 4(1): 89-97.

Rongrong Zhou, Dong Chen, Siyuan Liu. Optimization Model of Vehicle Scheduling for Fresh Food Distribution Using the K-means Clustering Algorithm[J]. Journal of Agricultural Big Data, 2022, 4(1): 89-97.

图/表 10

图 1

图2

图3

图4

图5

图6

图8

表1

图9

图10

参考文献 18

1	陈栋, 陈天恩, 姜舒文, 等. 基于订单位置聚类的雏鸡配送车辆调度优化模型[J]. 智慧农业(中英文), 2020,
	2(4): 137-148. Chen D, Chen T E, Jiang S W, et al. Optimal model of chicken distribution vehicle scheduling based on order clustering[J]. Smart Agriculture, 2020, 2(4): 137-148.
2	Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6: 80-91.
3	刘思远, 陈天恩, 陈栋, 等. 时变多车型下的生鲜农产品配送路径优化模型[J]. 智慧农业(中英文), 2021, 3(3): 139-151.
	Liu S Y, Chen T E, Chen D, et al. Time-varying heterotypic-vehicle cold chain logistics distribution path optimization model[J]. Smart Agriculture, 2021, 3(3): 139-151. (in Chinese with English
	abstract)
4	焦凯琳, 于自强. 智慧物流分布式计算模型与创新服务研究[J]. 计算机技术与发展, 2019, 29(1): 206-210.
	Jiao K L, Yu Z Q. Research on distributed computing model and innovative services about intelligent logistics[J]. Computer Technology and Development, 2019, 29(1): 206-210.
5	El-Sherbeny N A. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods[J]. Journal of King Saud University - Science, 2010, 22(3): 123-131.
6	Zhang D, Cai S, Ye F, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences, 2017: 167-182.
7	Calvet L, Wang D, Juan A. Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands[J]. International Transactions in Operational Research, 2019, 26(2): 458-484.
8	Cattaruzza D, Absi N, Feillet D. Vehicle routing problems with multiple trips[J]. Ann. Oper. Res. 2018, 271(1): 127-159.
9	Xia Y, Fu Z. An adaptive tabu search algorithm for the open vehicle routing problem with split deliveries by order[J]. Wireless Personal Communications, 2018, 103(1): 595-609.
10	Zhang Q, Xiong S. Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm[J]. Applied Soft Computing, 2018, 71: 917-925.
11	陈久梅, 周楠, 王勇. 生鲜农产品多隔室冷链配送车辆路径优化[J]. 系统工程, 2018, 36(8): 106-113.
	Chen J M, Zhou N, Wang Y. Optimization of multicompartment cold chain distribution vehicle routing for fresh agricultural products[J]. Systems Engineering, 2018, 36(8): 106-113.
12	张倩, 熊英, 何明珂, 等. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8):
	1582-1590. Zhang Q, Xiong Y, He M K, et al. Multi-objective model of distribution route problem for fresh electricity commerce under uncertain demand[J]. Journal of System Simulation, 2019, 31(8): 1582-1590.
13	肖建华, 王超文, 陈萍,等. 基于城市道路限行的多能源多车型车辆路径优化[J]. 系统工程理论与实践,
	2017, 37(5): 1339-1348. Xiao J H, Wang C W, Chen P, et al. The multi-energy heterogeneous fleet vehicle routing optimization under urban traffic restriction[J]. Systems Engineering-Theory & Practice, 2017, 37(5): 1339-1348.
14	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3):
	883-890. Zhao Z X, Li X M, Zhou X C. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas[J]. Journal of Computer Applications, 2020, 40 (3): 883-890.
15	李军涛, 刘明月, 刘朋飞. 生鲜农产品多车型冷链物流车辆路径优化[J]. 中国农业大学学报, 2021, 26(7):
	115-123. Li J T, Liu M Y, Liu P F. Route optimization of multi-vehiclecold chain logistics for fresh agricultural products[J].Journal of China Agricultural University, 2021, 26(7):115-123.
16	王芳, 滕桂法, 姚竟发. 带时间窗的多目标蔬菜运输配送路径优化算法[J]. 智慧农业(中英文), 2021, 3(3): 152-161.
	Wang F, Teng G F, Yao J F. Multi-Objective Vegetable Transportation and Distribution Path Optimization with Time Windows[J]. Smart Agriculture, 2021, 3(3): 152-161.
17	吴亮然, 林剑, 刘毅志, 等. 基于车辆配送线路的区域协同配送方法[J]. 计算机工程与应用, 2020, 56(1): 244-250.
	Wu L R, Lin J, Liu Y Z, et al. Regional collaborative distribution method based on vehicle distribution line[J]. Computer Engineering and Application, 2020, 56 (1): 244-250.
18	杜琛, 李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究[J]. 工业工程与管理, 2020, 25(6): 163-171.
	Du C, Li Y J. Research on cold chain distribution routing problem based on customer satisfaction and minimum loss[J]. Industrial Engineering and Management, 2020, 25(6): 163-171.

编号	不聚类优化里程/Km	聚类优化里程/Km	不聚类优化车辆数量/辆	聚类优化车辆数量/辆
1	3901.21	2016.12	30	34
2	3589.33	2102.34	32	31
3	3980.89	2050.56	34	32
4	3789.79	2210.82	29	33
5	3698.98	2020.76	35	34
6	3495.09	2103.80	28	32
7	4002.33	2118.33	29	35
8	3738.89	2430.76	32	34
9	3568.90	2001.54	32	32
10	3765.34	1998.98	34	34

[1]	李佳利, 杨涵, 钱建平. 新冠肺炎疫情下中国农产品冷链物流可信追溯研究[J]. 农业大数据学报, 2022, 4(1): 14-24.
[2]	张哲, 杨信廷, 于合龙, 李珊珊, 孙传恒. 基于区块链技术的生鲜农产品追溯系统研究进展[J]. 农业大数据学报, 2022, 4(1): 25-34.
[3]	张新, 彭祥贞, 李悦, 王小艺, 赵峙尧, 许继平. 基于可信区块链和可信标识的粮油食品全供应链信息追溯模型[J]. 农业大数据学报, 2022, 4(1): 35-48.
[4]	周大森, 陈静, 张鑫, 李继兰, 李志成, 郑晓冬, 公维敏, 宋烨. 果蔬冷链追溯体系研究现状与应用建议[J]. 农业大数据学报, 2022, 4(1): 49-54.
[5]	贺苗, 李鑫, 朱志强, 冯建英. 基于PCA-GA-SVR的鲜食葡萄运输过程品质建模[J]. 农业大数据学报, 2022, 4(1): 98-108.
[6]	李干琼, 李欣, 赵龙华, 许世卫. 农业供应链管理研究进展综述及展望[J]. 农业大数据学报, 2020, 2(3): 3-12.
[7]	李冬男, 潘国杨, 周倩, 李斌. 新冠疫情后我国生鲜农产品供应链发展方向[J]. 农业大数据学报, 2020, 2(3): 42-51.
[8]	杨晨雪, 孙志国. 基于区块链技术的农产品供应链数据管理系统设计[J]. 农业大数据学报, 2020, 2(2): 74-83.

基于K均值聚类算法的生鲜运输路径优化模型

Optimization Model of Vehicle Scheduling for Fresh Food Distribution Using the K-means Clustering Algorithm

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 18

相关文章 8

Metrics

本文评价

推荐阅读 0