Optimal Model of Chicken Distribution Vehicle Scheduling Based on Order Clustering

doi:10.12133/j.smartag.2020.2.4.202011-SA006

Abstract

Abstract:

In order to solve the problems that orders are widely distributed, scheduling of distribution vehicle needs a lot of manpower,and high cost of chicken distribution in large-scale poultry enterprise, in this research, combined with the idea of solving vehicle routing optimization problem, a chicken distribution vehicle scheduling optimization model based on order location clustering was proposed. By introducing the K-means clustering algorithm, a distribution unit division method based on order location was implemented, an automated order location clustering process based on the elbow rule and contour coefficient method to realize the autonomous division of order distribution units was designed. On the basis of the divided groups of orders, the optimal delivery cost was taken as the objective function to establish a chicken delivery vehicle scheduling optimization model, and the model was solved with an improved genetic algorithm.The actual order data of a poultry company in Beijing was used to compare the results of the overall scheduling optimization in the case of orders without clustering and the scheduling optimization in the case of with clustering grouping. The results showed that the model in the case of orders with clustering could reduce the average daily mileage of delivery vehicles by 69% compared with orders without clustering, it could be seen that the optimization of order grouping with clustering algorithm was more suitable for vehicle scheduling scenarios with a large actual order position span and a large number of orders. Based on the above research, a vehicle scheduling optimization service system was developed, functions such as automatic order clustering, delivery vehicle scheduling optimization were realized, and model service application programming interface was customized.The practical application results of the model showed that, the average total mileage per day decreased by 5.04% compared with manual routing, the manual routing time took 20 to 30 minutes per day, and the average time for the model to complete the routing was 14.49 s. The goal of providing intelligent delivery vehicle scheduling optimization services for poultry industry enterprises has been achieved, which could effectively improve the operation efficiency and reduce the distribution cost of the poultry enterprise.

Key words: chicken delivery, vehicle scheduling optimization model, K-means clustering algorithm, genetic algorithm, smart poultry, API

CLC Number:

S-126

CHEN Dong, Tian'en CHEN, JIANG Shuwen, ZHANG Chi, WANG Cong, LU Mengyao. Optimal Model of Chicken Distribution Vehicle Scheduling Based on Order Clustering[J]. Smart Agriculture, 2020, 2(4): 137-148.

References

1	焦凯琳, 于自强. 智慧物流分布式计算模型与创新服务研究[J]. 计算机技术与发展, 2019, 29(1): 206-210.
1	JIAO K, YU Z. Research on distributed computing model and innovative services about intelligent logistics[J]. Computer Technology and Development, 2019, 29(1): 206-210.
2	DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6: 80-91.
3	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.
4	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.
5	LAURA C, WANG D, ANGEL J. Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands[J]. International Transactions in Operational Research, 2019, 26(2): 458-484.
6	CATTARUZZA D, ABSI N, FEILLET D. Vehicle routing problems with multiple trips[J]. 4OR-A Quarterly Journal of Operations Research. 2018, 271(1): 127-159.
7	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.
8	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.
9	邵举平, 曹倩, 沈敏燕, 等. 生鲜农产品配送中带时窗的VRP模型与算法[J]. 工业工程与管理, 2015, 20(1): 122-127, 134.
9	SHAO J, CAO Q, SHEN M, et al. Research on multi-objective optimization for fresh agricultural products VRP problem[J]. Industrial Engineering and Management, 2015, 20(1): 122-127, 134.
10	张源凯, 黄敏芳, 胡祥培. 网上超市订单分配与物流配送联合优化方法[J]. 系统工程学报, 2015(2): 251-258.
10	ZHANG Y, HUANG M, HU X. Integrated optimization approach to order allocation and delivery problem of online supermarket[J]. Journal of Systems Engineering. 2015(2): 251-258.
11	VAHDANI B, NIAKI S T A, ASLANZADE S. Production-inventory-routing coordination with capacity and time window constraints for perishable products: Heuristic and meta-heuristic algorithms[J]. Journal of Cleaner Production, 2017, 161(10): 598-618.
12	ULLRICH C A, CHRISTIAN A. Integrated machine scheduling and vehicle routing with time windows[J]. European Journal of Operational Research, 2013, 227(1): 152-165.
13	侯宇超, 白艳萍, 胡红萍, 等.基于精英蚁群算法的多目标生鲜配送路径优化研究[J]. 数学的实践与认识, 2018, 48(20): 50-57.
13	HOU Y, BAI Y, HU H, et al. Study of multi-objective fresh food distribution route optimization based on elite ant colony algorithm[J]. Mathematics in Practice and Theory, 2018, 48(20): 50-57.
14	汪涛, 潘郁, 潘芳, 等. 基于改进人工蜂群算法的生鲜农产品配送路径优化[J]. 广东农业科学, 2018, 45(10): 143-149.
14	WANG T, PAN Y, PAN F, et al. Fresh agricultural product distribution path optimization based on improved artificial bee colony algorithm[J]. Guangdong Agricultural Sciences, 2018, 45(10): 143-149.
15	侯文英, 秦驰越. 基于蚁群算法鲜活农产品配送路径优化研究[J]. 安徽农业科学, 2009, 37(1): 109-110, 118.
15	HOU W, QIN C. On the optimization of distribution routes for fresh agricultural products based on ant algorithm[J]. Journal of Anhui Agricultural Sciences, 2009, 37(1): 109-110, 118.
16	詹长书, 李正娇. 基于改进蚁群算法的鲜活农产品配送路径优化[J]. 物流技术, 2017, 36(9): 89-91, 149.
16	ZHAN C, LI Z. Optimization of fresh farm produce distribution route based on improved ant algorithm[J]. Logistics Technology, 2017, 36(9): 89-91, 149.
17	盛强, 郑鹏飞, 孙军艳. 动态时变路网下带时间窗车辆路径规划问题研究[J]. 物流技术, 2018, 37(10): 36-39.
17	SHENG Q, ZHENG P, SUN J. Research on vehicle routing problem with time windows under dynamic road network[J]. Logistics Technology, 2018, 37(10): 36-39.
18	FU Z, EGLESE R, LI L Y O. A unified tabu search algorithm for vehicle routing problems with soft time windows[J]. Journal of the Operational Research Society, 2008, 59(5): 663-673.
19	KOK A L, HANS E W, SCHUTTEN J M J. Optimizing departure times in vehicle routes[J]. European Journal of Operational Research, 2011, 210(3): 579-587.
20	WANG Y, MA X, XU M, et al. Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm[J]. Expert Systems with Applications, 2015, 42(12): 5019-5031.
21	赵冉, 石晨, 谭骥. 农机安全生产信息系统的设计——基于混合遗传资源调度算法[J]. 农机化研究, 2021, 43(6): 231-234.
21	ZHAO R, SHI C, TAN J. Design of agricultural machinery safety production information system—resource scheduling algorithm based on hybrid genetic algorithm[J]. Journal of Agricultural Mechanization Research, 2021, 43(6): 231-234.
22	李作山. 农业机械调度问题中算法改进的研究[J]. 南方农机, 2019, 50(23): 21, 26.
22	LI Z. Research on algorithm improvement in agricultural machinery scheduling problem[J]. China Southern Agricultural Machinery, 2019, 50(23): 21, 26.
23	王文权. 带时间窗农机调度问题模型及算法研究[D]. 杭州: 浙江大学, 2019.
23	WANG W. Research on model and algorithm of agricultural machinery scheduling problem with time window[D]. Hangzhou: Zhejiang University, 2019.

[1]	XIAO Shijie, WANG Qiaohua, LI Chunfang, ZHAO Limei, LIU Xinya, LU Shiyu, ZHANG Shujun. Construction of Milk Purchase Classification Model Based on Shuffled Frog Leaping Algorithm and Support Vector Machine [J]. Smart Agriculture, 2021, 3(4): 77-85.
[2]	WANG Fang, TENG Guifa, YAO Jingfa. Multi-Objective Vegetable Transportation and Distribution Path Optimization with Time Windows [J]. Smart Agriculture, 2021, 3(3): 152-161.
[3]	ZHANG Yan, LI Qingxue, WU Huarui. Rapid Recognition Model of Tomato Leaf Diseases based on Kernel Mutual Subspace Method [J]. Smart Agriculture, 2020, 2(3): 86-97.
[4]	Jiang Mei, Sun Sashuang, He Dongjian, Song Huaibo. Recognition and localization method of occluded apples based on K-means clustering segmentation algorithm and convex hull theory [J]. Smart Agriculture, 2019, 1(2): 45-54.