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

doi:10.19788/j.issn.2096-6369.220110

Abstract

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

CLC Number:

TU205

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.

Figures/Tables 10

Fig. 1

Fig. 2

Fig. 3

Fig.4

Fig. 5

Fig. 6

Fig. 8

Table 1

Fig.9

Fig.10

References 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]	Jiali Li, Han Yang, Jianping Qian. An Credible Traceability System for Cold Chain Logistics Developed for China’s Agricultural Products in the Context of COVID-19 [J]. Journal of Agricultural Big Data, 2022, 4(1): 14-24.
[2]	Zhe Zhang, Xinting Yang, Helong Yu, Shanshan Li, Chuanheng Sun. Progress of Research to Develop a Traceability System for Fresh Agricultural Products Using Blockchain Technology [J]. Journal of Agricultural Big Data, 2022, 4(1): 25-34.
[3]	Dasen Zhou, Jing Chen, Xin Zhang, Jilan Li, Zhicheng Li, Xiaodong Zheng, Weimin Gong, Ye Song. Research Status and Application Suggestions on Fruit and Vegetable Cold Chain Traceability System [J]. Journal of Agricultural Big Data, 2022, 4(1): 49-54.
[4]	Miao He, Xin Li, Zhiqiang Zhu, Jianying Feng. Modeling Table Grapes: Physicochemical Indexes and Sensory Quality Based on PCA-GA-SVR during Transportation Process [J]. Journal of Agricultural Big Data, 2022, 4(1): 98-108.
[5]	Ganqiong Li, Xin Li, Longhua Zhao, Shiwei Xu. A Review of Agricultural Supply Chain Management and Its Prospects for the Future [J]. Journal of Agricultural Big Data, 2020, 2(3): 3-12.
[6]	Dongnan Li, Guoyang Pan, Qian Zhou, Bin Li. The Development Direction of Fresh Agricultural Products Supply Chain in China after COVID-19 [J]. Journal of Agricultural Big Data, 2020, 2(3): 42-51.

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

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 18

Related Articles 6

Metrics

Comments

Recommended 0