带时间窗的多目标蔬菜运输配送路径优化算法

doi:10.12133/j.smartag.2021.3.3.202109-SA010

摘要/Abstract

摘要：

为了解决蔬菜运输耗时长、成本高、保鲜时间短，导致送达到客户手上蔬菜质量降低等问题，在考虑了车辆载重和时间窗等约束条件下，本研究提出了一种带时间窗多目标蔬菜配送路径优化的遗传-模拟退火（Genetic Algorithm and Simulated Annealing，GA-SA）算法。在遗传算法（Genetic Algorithm，GA）操作过程中引入模拟退火（Simulated Annealing，SA）算法自适应（Metropolis）接受准则：首先将原始种群进行遗传算法的选择、交叉、变异等操作，形成新一代路径种群，此时通过引入Metropolis准则，对新一代路径种群分布情况进行修正、选择、交叉、变异，得到目标路径种群，达到全部车辆配送完返回到配送中心的耗时最少、成本最低、车辆使用最少的多目标，求得蔬菜运输的最优路径。设计以保定市为配送中心以及向保定市下辖的各个乡镇为配送点进行蔬菜运输路径优化的试验，结果证明，与传统的GA、SA相比，GA-SA能够有效增快其收敛速度，优化后的配送路线总成本分别降低了约23.7%和4%，总路程分别减少了22.6%和3%，耗时分别减少了26.2和2.6 h，车辆分别少使用2辆和1辆。本研究可为冷鲜食品以及其他运输路径优化研究提供参考价值。

关键词: 遗传算法, Metropolis准则, 车辆路径问题, 蔬菜运输, SA算法, 耗时, 成本, 路径优化

Abstract:

There are higher requirements for the timeliness of vegetable transportation and distribution. In order to solve the problems of long transportation time, high total transportation cost and short preservation time of vegetables during transportation, considering the constraints such as vehicle load and time window, this study proposed a genetic simulated annealing algorithm (GA-SA) for multi-objective vegetable distribution path optimization with time windows. That was, the simulated annealing algorithm (SA) adaptive (Metropolis) acceptance criterion was introduced into the operation process of genetic algorithm (GA). The basic idea was: First, the original population was selected, crossed and mutated by genetic algorithm to form a new generation of path population. At this time, by introducing metropolis acceptance criterion, and then, after modifying the sub situation of the new generation path population and selecting cross mutation, a new target path population was obtained. The improved algorithm retained the excellent individual, and the convergence speed, jumped out of the local optimal solution found based on genetic algorithm, and then found the global optimal solution. Then, the multi-objective of returning all vehicles to the distribution center after distribution was the least time-consuming, the lowest cost and the least use of vehicles was achieved, and the optimal path of vegetable transportation was obtained. Taking Baoding city in Hebei province as the distribution center and some towns under the jurisdiction of Baoding city as the distribution points, the experiment of vegetable transportation path optimization was designed. The experiments of genetic algorithm, simulated annealing algorithm and genetic simulated annealing algorithm were carried out, respectively. The comparative analysis was carried out from the aspects of convergence speed, total distance, total time, vehicles and total cost. The experimental results showed that, compared with the genetic algorithm and simulated annealing algorithm, GA-SA could effectively accelerate its convergence speed. The total cost of the optimized distribution route reduced by about 23.7% and 4% respectively, the total distance reduced by 22.6% and 3% respectively, the time consumption reduced by 26.2 and 2.6 hours respectively, and 2 and 1 vehicles were used less respectively. This study could also provide reference for the research of cold fresh food and other transportation path optimization.

Key words: genetic algorithm, Metropolis guidelines, vehicle routing problem, vegetable transportation, simulated annealing algorithm, time consuming, cost, path optimization

中图分类号:

王芳, 滕桂法, 姚竟发. 带时间窗的多目标蔬菜运输配送路径优化算法[J]. 智慧农业(中英文), 2021, 3(3): 152-161.

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.

参考文献

1	董波. 盐城市亭湖区大棚蔬菜有机肥施用研究[D]. 南京: 南京农业大学, 2019.
1	DONG B. Application of biofertilizer in greenhouse vegetable growth in Tinghu district, Yancheng city[D]. Nanjing: Nanjing Agricultural University, 2019.
2	SHI Y, ZHOU Y, YE W, et al. A relative robust optimization for a vehicle routing problem with time-window and synchronized visits considering greenhouse gas emissions[J]. Journal of Cleaner Production, 2020, 275: ID 124112.
3	WANG X, WASIL E. On the road to better routes: Five decades of published research on the vehicle routing problem[J]. Networks, 2021, 77(1): 66-87.
4	ASGHAR A, HOSSEINABADI R, SLOWIK A, et al. An ameliorative hybrid algorithm for solving the capacitated vehicle routing problem[J]. IEEE Access, 2019, 7(4): 175454-175465.
5	RIVERA J C, AFSAR H M, PRINS C. A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem[J]. Computational Optimization and Applications, 2015, 61(1): 159-187.
6	周洋, 陆轶. A蔬菜运输公司物流配送路径优化研究[J]. 现代商贸工业, 2016, 37(24): 49-50.
6	ZHOU Y, LU Y. Research on logistics distribution route optimization of a vegetable transportation company[J]. Modern Commerce and Industry, 2016, 37 (24): 49-50.
7	陶涛, 朱家明. 基于Floyd算法对蔬菜运输的研究[J]. 赤峰学院学报(自然科学版), 2018, 34(7): 13-15.
7	TAO T, ZHU J. Research on vegetable transportation based on Floyd algorithm[J]. Journal of Chifeng University (Natural Science Edition), 2018, 34 (7): 13-15.
8	苏贝贝. 应急物资配送选址—路径规划干扰管理模型研究[D]. 武汉: 武汉理工大学, 2020.
8	SU B. Research on disruption management model of location-routing problem in emergency material distribution [D]. Wuhan: Wuhan University of Technology, 2020.
9	MENDES S, LUSH V, WANNER E F, et al. Online clustering reduction based on parametric and non-parametric correlation for a many-objective vehicle routing problem with demand responsive transport[J]. Expert Systems with Applications, 2020, 170: ID 114467.
10	LESPAY H, SUCHAN K. A case study of consistent vehicle routing problem with time windows[J]. International Transactions in Operational Research, 2021, 28(3): 1135-1163.
11	MOLINA J C, SALMERON J L, EGUIA I. An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows[J]. Expert Systems With Applications, 2020, 157: ID 113379.
12	赵邦磊. 基于改进多目标蚁群算法的冷链物流路径优化研究[D]. 淮南: 安徽理工大学, 2020.
12	ZHAO B. Cold chain logistics path optimization via improve multi-objective ant colony algorithm[D]. Huainan: Anhui University of Technology, 2020.
13	JEA B, AS A. Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones[J]. Physical Communication, 2021, 44: ID 101236.
14	杜芋颖. 基于启发式算法的物流配送路径设计与实现[D]. 南京: 南京邮电大学, 2020.
14	DU Y. Design and implementation of logistics distribution path based on heuristic algorithm[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2020.
15	尹秋霜. 考虑越库作业的连锁超市配送路径优化研究[D]. 重庆: 重庆交通大学, 2019.
15	YIN Q. Research on optimization of distribution path of chain supermarkets considering cross-docking operations[D]. Chongqing: Chongqing Jiaotong University, 2019.
16	杨爱芳. 外卖配送路径优化研究[D]. 西安: 西安电子科技大学, 2020.
16	YANG A. Research on optimization of takeaway distribution route[D]. Xi'an: Xi'an University of Electronic Science and Technology, 2020.
17	李军涛, 刘明月, 刘朋飞. 生鲜农产品多车型冷链物流车辆路径优化[J]. 中国农业大学学报, 2021, 26(7): 115-123.
17	LI J, LIU M, LIU P. Route optimization of multi-vehicle cold chain logistics for fresh agricultural products[J]. Journal of China Agricultural University, 2021, 26(7): 115-123.
18	范利阳. 基于改进遗传算法的多能源车辆路径问题研究[D]. 成都: 西南交通大学, 2020.
18	FAN L. Multi-energy vehicle routing problem based on improved genetic algorithms[D]. Chengdu: Southwest Jiaotong University, 2020.
19	余梅. 基于蚁群-遗传融合改进算法的物流车辆路径优化[D]. 南充: 西华师范大学, 2020.
19	YU M. Optimization of logistics vehicle path based on ant colony-genetic fusion algorithm[D]. Nanchong: West China Normal University, 2020.
20	徐卓. 考虑模糊时间窗的生鲜产品多目标配送路径优化研究[D]. 广州: 暨南大学, 2019.
20	XU Z. Research on multi-objective distribution path optimization of fresh products considering fuzzy time window[D]. Guangzhou: Jinan University, 2019.
21	裴玉青. 面向智慧医药的物流配送路径优化研究[D]. 南京: 南京邮电大学, 2020.
21	PEI Y. Research on logistics distribution path optimization for intelligent medicine[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2020.
22	ZHANG K, HE F, ZHANG Z, et al. Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach[J]. Transportation Research Part C, 2020, 121: ID 102861.
23	范厚明, 刘文琪, 徐振林, 等. 混合粒子群算法求解带软时间窗的VRPSPD问题[J]. 计算机工程与应用, 2018, 54(19): 221-229.
23	FAN H, LIU W, XU Z, et al. Hybrid particle swarm optimization for solving VRPSPD problems with soft time windows[J]. Computer Engineering and Application, 2018, 54(19): 221-229.
24	鄢栋, 陈家琪. ICP策略下带软时间窗的动态车辆路径优化问题研究[J]. 软件导刊, 2018, 17(3): 172-175.
24	YAN D, CHEN J. The dynamic vehicle routing optimization problem with soft time windows based on ICP strategy[J]. Software Guide, 2018, 17 (3): 172-175.
25	李红. 基于改进遗传算法的便利店配送中心选址路径优化研究[D]. 武汉: 华中科技大学, 2019.
25	LI H. Research on location and path optimization of convenience store distribution center based on improved genetic algorithm[D]. Wuhan: Huazhong University of Science and Technology, 2019.
26	张丽, 郭夕英, 史立君. 物联网在设施蔬菜大棚种植上的有效应用[J]. 农业工程技术, 2021, 41(9): 67-68.
26	ZHANG L, GUO X, SHI L. Effective application of Internet of things in greenhouse planting of protected vegetables[J]. Agricultural Engineering Technology, 2021, 41 (9): 67-68.
27	WU L, WANG S, GILBERT L. The robust bulk ship routing problem with batched cargo selection[J]. Transportation Research Part B, 2021, 143(1): 124-159.
28	TOTH P, VIGO D. The vehicle routing problem(车辆路径问题)[M]. 北京: 清华大学出版社, 2011.
29	吴亮然, 林剑, 刘毅志, 等. 基于车辆配送线路的区域协同配送方法[J]. 计算机工程与应用, 2020, 56(1): 244-250.
29	WU L, LIN J, LIU Y, et al. Regional collaborative distribution method based on vehicle distribution line[J]. Computer Engineering and Application, 2020, 56 (1): 244-250.
30	GóMEZ M R A, CANO J A, CORTéS P, et al. A discrete particle swarm optimization to solve the put-away routing problem in distribution centres[J]. Computation, 2020, 8(4): 1-17.
31	郄东翔, 狄政敏, 张建峰, 等. 河北省塑料大棚蔬菜生产现状及建议[J]. 中国瓜菜, 2020, 33(6): 63-66.
31	JIA D, DI Z, ZHANG J, et al. Current situation and suggestions of vegetable production in plastic greenhouse in Hebei Province[J]. Chinese Melons and Vegetables, 2020, 33(6): 63-66.

[1]	秦英栋, 贾文珅. 基于NB-IoT网络的兔舍环境实时监测系统[J]. 智慧农业(中英文), 2023, 5(1): 155-165.
[2]	刘思远, 陈天恩, 陈栋, 张驰, 王聪. 时变多车型下的生鲜农产品配送路径优化模型[J]. 智慧农业(中英文), 2021, 3(3): 139-151.
[3]	陈栋, 陈天恩, 姜舒文, 张驰, 王聪, 鲁梦瑶. 基于订单位置聚类的雏鸡配送车辆调度优化模型[J]. 智慧农业（中英文）, 2020, 2(4): 137-148.
[4]	李扬, 张萍, 苑进, 刘雪美. 白芦笋采收机器人视觉定位与采收路径优化方法[J]. 智慧农业（中英文）, 2020, 2(4): 65-78.
[5]	李华龙, 李淼, 詹凯, 刘先旺, 杨选将, 胡泽林, 郭盼盼. 蛋鸡设施养殖环境质量评价预测模型构建方法及性能测试[J]. 智慧农业（中英文）, 2020, 2(3): 37-47.