冷链物流配送的绿色车辆路径模型及其求解算法

doi:10.16381/j.cnki.issn1003-207x.2022.0461

摘要/Abstract

摘要：

针对冷链物流配送的绿色车辆路径问题，引入新鲜度衰减函数计算配送过程中冷链产品的货损；考虑载重、行驶速度、低温制冷等因素对油耗和碳排放率的影响，确定油耗和碳排放的度量函数；根据配送时间和顾客满意度的关系，建立顾客满意度函数。在此基础上，以车辆使用成本、货损成本、油耗和碳排放成本、惩罚成本之和最小化和顾客平均满意度最大化作为优化目标，构建双目标数学模型，设计了一种基于NSGA-II和变邻域搜索的混合算法进行求解。算例仿真结果表明，构建的模型和提出的算法能在多个优化目标之间取得平衡，降低车辆使用成本和货损，减少油耗和碳排放，提高顾客满意度。

关键词: 冷链物流配送, 绿色车辆路径问题, NSGA-II, 变邻域搜索

Abstract:

In recent years， fresh food e-commerce in China has developed rapidly， with a significantly growing demand for cold-chain logistics distribution. In order to promote energy conservation and emission reduction in cold-chain logistics， the Green Vehicle Routing Problem in Cold-chain Logistics Distribution （GVRPCLD） has attracted increasing attention from both academia and industry. The GVRPCLD discussed in this paper involves set constraints， including （1） distribution center locations，（2） capacity-constrained homogeneous refrigerated vehicles，（3） customers’ number， locations， demands， time windows， service times， and （4） a low temperature kept in the cabin during distribution. The optimal vehicle routing plan is expected to realize the dual goals of total cost minimization and customer satisfaction maximization. Specifically， there are five types of costs that are included in the total cost， which are vehicle usage cost， deterioration cost， cooling cost， fuel consumption and carbon emission cost， and piecewise penalty costs for earliness and tardiness of deliveries. In the design， a freshness decay function is firstly applied to calculate the deterioration cost during distribution. Based on the comprehensive mode emission model （CMEM）， the measurement functions of fuel consumption and carbon emission are determined， with the consideration of the influence of vehicle load， speed， low temperature and other factors on fuel consumption and carbon emission rate. Then， a customer satisfaction function is established according to the relationship between delivery time and customer satisfaction. Finally， a dual-objective GVRPCLD optimization model is constructed. In order to solve the GVRPCLD model， a hybrid algorithm （VNSNSGA-II） is designed in this paper， which is based on the Non-dominated Sorting Genetic Algorithm II （NSGA-II） and the Variable Neighborhood Search （VNS）. The basic idea of the algorithm can be described as follows. Firstly， the VNS is used to optimize some chromosomes in the population to expand the solution space. Secondly， the NSGA-II is performed to obtain non-dominated sorting and crowding degree. Thirdly， based on the individual's rank and crowding distance， the top 50% of chromosomes are obtained and retained as new parent population. Finally， the Pareto-optimal set is obtained by iteration. The simulation results show the following. For one thing， the GVRPCLD model can achieve multi-objective optimization among logistics cost， deterioration cost， fuel consumption and carbon emissions， and customer satisfaction. Furthermore， it is found that logistics cost is negatively correlated with customer satisfaction， indicating that the delivery plan makers can choose different delivery options according to their preference. Last but not least， the proposed VNSNSGA-II is tested， and it is confirmed that the algorithm can contribute to a Pareto-optimal set.

Key words: cold-chain logistics distribution, green vehicle routing problem, NSGA-II, variable neighborhood search

中图分类号:

F252

周鲜成,蒋涛营,贺彩虹,王莉,吕阳. 冷链物流配送的绿色车辆路径模型及其求解算法[J]. 中国管理科学, 2023, 31(12): 203-214.

Xian-cheng ZHOU,Tao-ying JIANG,Cai-hong HE,Li WANG,Yang LV. Green Vehicle Routing Model and Its Solution Algorithm in Cold-chain Logistics Distribution[J]. Chinese Journal of Management Science, 2023, 31(12): 203-214.

图/表 17

表1

符号、变量及集合的含义"

符号	含义
$A$	配送网络节点集合 $A = {0,1, 2, …, N}$ ，共N+1个节点，0表示配送中心
$A'$	顾客点集合 $A' = A \ {0}$ ，共N个顾客
$B$	配送车辆集合 $B = {1,2, …, K}$ ，共K辆冷藏车
$d i j$	从节点i到节点j的距离
$D$	所有车辆配送距离之和
$Q$	车辆最大容量
$w i j k$	车辆k行驶在道路 $(i, j)$ 上的载重
$q i$	顾客点i的需求量
$Z 1$	配送总成本
$Z 2$	顾客平均满意度
$M i$	顾客点i的满意度
$t s i$	顾客点i的服务时间
$t i j k$	车辆k在道路 $(i, j)$ 上的行驶时间
$v$	配送车辆的行驶速度
$τ 0$	车辆从配送中心出发的时刻
$t i k$	车辆k到达节点i的时刻
$[e 0, l 0]$	配送中心时间窗
$[e T i, l T i]$	顾客i期望的理想服务时间窗（硬时间窗）
$[E T i, L T i]$	顾客i可接受的服务时间窗（软时间窗）
$F i j k$	车辆k从节点i行驶到节点j产生的油耗量（单位：升）
$F i j k'$	车辆k从节点i到节点j因制冷产生的油耗量（单位：升）
$ψ$	燃油排放参数
$E i j k$	车辆k从节点i行驶到节点j产生的碳排放量（单位：千克）
$E i j k'$	车辆k从节点i到节点j因制冷产生的碳排放量（单位：千克）
$φ$	配送车辆的固定发车费用（单位：元/辆）
$μ$	车辆使用单位时间成本（单位：元/小时）
$ρ$	冷链产品单位重量的价格（单位：元/千克）
$θ$	车辆行驶过程中货物新鲜度衰减系数；
$σ 1$	车辆行驶过程中制冷系统的油耗率（单位：升/小时）
$σ 2$	车辆在配送服务期间制冷系统的油耗率（单位：升/小时）
$λ f$	单位油耗费用（单位：元/升）
$λ e$	单位碳排放费用（单位：元/千克）
$ω e$	早到顾客点服务的时间窗违背惩罚系数（单位：元/小时）
$ω l$	晚到顾客点服务的时间窗违背惩罚系数（单位：元/小时）
$x i j k$	0-1变量，当车辆k由节点i向节点j行驶时其值为1，否则为0
$y i k$	0-1变量，当顾客i由车辆k服务时其值为1，否则为0

表1

图1

图2

表2

模型参数取值"

模型参数	取值
$φ$	200元/辆
$ρ$	5元/千克
$v$	50千米/小时
$ω e$	6元/小时
$ω l$	9元/小时
$θ$	0.005
$σ 1$	3升/小时
$σ 2$	6升/小时
$μ$	60元/小时
$β 1$	1.004×10^-3
$β 2$	1.265×10^-2
$β 3$	4.312×10^-4
$w 0$	1930千克
$Q$	3000千克
$ψ$	2.621千克/升
$λ f$	6.5元/升
$λ e$	0.07元/千克

表2

表3

算法参数设置"

算法参数	取值
$p c$	1
$p m$	0.3
$ξ 1$	50个
$ξ 2$	40%
genmax	800代
VNSgenmax	10代
H	10次

表3

表4

双目标GVRPCLD模型的Pareto最优解集"

前沿点	优化目标							D	K
前沿点	Z₁	Z₂	C₁	C₂	C₃	C₄	C₅	D	K
1	6748.20	0.920	2990.30	1117.91	1960.96	55.35	623.68	825.25	5
2	6781.02	0.922	2999.41	1126.06	1973.33	55.70	626.52	832.84	5
3	6792.45	0.923	3001.96	1126.14	1974.54	55.73	634.07	834.97	5
4	6837.06	0.926	3018.14	1125.97	1993.16	56.26	643.54	848.45	5
5	6839.06	0.929	3028.17	1097.79	2007.95	56.68	648.47	856.81	5
6	6853.43	0.931	3038.55	1107.40	2021.71	57.07	628.70	865.46	5
7	6870.99	0.932	3045.78	1137.42	2034.28	57.42	596.10	871.48	5
8	6881.21	0.934	3053.00	1105.18	2040.49	57.60	624.95	877.50	5
9	6905.57	0.936	3054.74	1112.69	2043.50	57.68	636.96	878.95	5
10	6922.91	0.937	3057.86	1117.61	2048.24	57.81	641.39	881.55	5
11	6955.64	0.938	3072.57	1143.62	2064.86	58.28	616.30	893.81	5
12	7007.06	0.941	3113.77	1127.06	2121.59	59.88	584.75	928.15	5
13	7064.86	0.942	3119.87	1167.71	2135.21	60.27	581.80	933.23	5
14	7079.98	0.943	3121.24	1169.90	2136.99	60.32	591.54	934.37	5
15	7131.49	0.944	3146.46	1152.16	2167.38	61.18	604.31	955.39	5
16	7136.47	0.944	3157.24	1174.33	2159.67	60.96	584.28	964.36	5
17	7159.99	0.948	3194.84	1138.59	2231.85	63.00	531.72	995.70	5
18	7189.64	0.950	3169.95	1144.62	2197.16	62.02	615.89	974.96	5
19	7192.27	0.953	3176.11	1189.71	2193.64	61.92	570.90	980.09	5
20	7215.48	0.954	3183.59	1189.22	2203.70	62.20	576.77	986.33	5
21	7243.31	0.955	3194.09	1195.25	2219.76	62.66	571.56	995.08	5
22	7261.61	0.956	3199.41	1189.96	2224.38	62.79	585.07	999.51	5
23	7273.49	0.957	3204.25	1196.38	2230.70	62.96	579.20	1003.54	5
24	7284.97	0.959	3223.97	1179.87	2263.31	63.88	553.94	1019.98	5
25	7297.84	0.961	3213.13	1203.90	2253.61	63.61	563.59	1010.94	5
26	7342.02	0.963	3228.95	1205.35	2274.42	64.20	569.10	1024.13	5
27	7350.58	0.964	3237.90	1188.93	2284.04	64.47	575.25	1031.58	5
28	7387.23	0.964	3249.49	1203.08	2300.87	64.94	568.85	1041.24	5
29	7404.43	0.965	3268.26	1201.76	2324.95	65.62	543.84	1056.88	5
30	7462.23	0.969	3296.17	1218.69	2362.80	66.69	517.88	1080.14	5
31	7480.08	0.969	3306.96	1215.13	2376.49	67.08	514.41	1089.13	5
32	7499.79	0.971	3308.33	1218.50	2378.48	67.14	527.35	1090.28	5
33	7559.18	0.971	3335.27	1215.51	2412.16	68.09	528.15	1112.72	5
34	7583.55	0.972	3338.10	1259.96	2420.09	68.31	497.09	1115.08	5
35	7618.04	0.974	3350.26	1259.42	2435.70	68.75	503.91	1125.22	5
36	7755.90	0.977	3357.55	1321.94	2448.89	69.12	558.40	1131.29	5
37	7786.98	0.977	3372.00	1320.55	2467.81	69.66	556.96	1143.33	5
38	7802.03	0.978	3373.37	1322.68	2469.57	69.71	566.70	1144.48	5
39	7849.50	0.981	3407.70	1315.43	2518.75	71.09	536.53	1173.08	5
40	7891.09	0.982	3411.24	1334.76	2525.80	71.29	548.00	1176.03	5
41	7903.19	0.983	3421.18	1326.79	2537.98	71.64	545.61	1184.31	5
42	8052.04	0.984	3470.83	1346.36	2608.69	73.63	552.53	1225.69	5
平均值	7277.47	0.954	3202.67	1195.51	2239.27	63.21	576.82	1002.22	5

表4

图3

图4

表5

图5

图6

图7

表6

图8

图9

图10

图11

参考文献 22

1	Brito J， Martinez FJ， Moreno JA， et al. Fuzzy optimization for distribution of frozen food with imprecise times［J］. Fuzzy Optimization and Decision Making， 2012， 11 （3）： 337-49.
2	王淑云，孙虹. 随机需求下冷链品多温共配路径优化研究［J］. 工业工程与管理， 2016， 21（2）： 49-58.
	Wang Shuyun， Sun Hong. Optimization of multitemperature joint distribution with stochastic demands［J］. Industrial Engineering and Management，2016，21（2）： 49-58.
3	Qi Chengming， Hu Lishuan.Optimization of vehicle routing problem for emergency cold chain logistics based on minimum loss［J］. Physical Communication， 2020，40（2）：101085.
4	姚源果，贺盛瑜.基于交通大数据的农产品冷链物流配送路径优化研究［J］.管理评论， 2019， 31（4）： 240-253.
	Yao Yuanguo， He Shengyu. Research on optimization of distribution route for cold chain logistics of agricultural products based on traffic big data［J］.Management Review， 2019， 31 （4）： 240-253.
5	刘春玲，王俊峰，黎继子，等.众包模式下冷链物流配送模型的仿真和优化分析［J］.计算机集成制造系统， 2019， 25（10）： 2666-2675.
	Liu Chunling， Wang Junfeng， Li Jizi， et al. Simulation and optimization model of cold chain logistics delivery under crowdsourcing mode［J］. Computer Integrated Manufacturing Systems， 2019， 25（10）： 2666-2675.
6	杜琛，李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究［J］. 工业工程与管理， 2020， 25（6）： 163-171.
	Du Chen， Li Yijing. Research on cold chain distribution path problem based on customer satisfaction and minimum loss［J］. Industrial Engineering and Management， 2020， 25（6）： 163-171.
7	Song Meixian， Li Junqing， Han Yunqi， et al. Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics［J］. Applied Soft Computing，2020， 95（2）： 106561.
8	潘茜茜，干宏程. 考虑碳排放的冷链物流配送路径优化研究［J］. 数学的实践与认识， 2016， 46（2）： 62-68.
	Pan Xixi， Gan Hongcheng. Study on cold chain logistics distribution path optimization of considering carbon emissions［J］. Practice and Understanding of Mathematics， 2016， 46（2）： 62-68.
9	方文婷，艾时钟，王晴，等.基于混合蚁群算法的冷链物流配送路径优化研究［J］. 中国管理科学， 2019， 27（11）： 107-115.
	Fang Wenting， Ai Shizhong， Wang Qing， et al. Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm［J］. Chinese Journal of Management Science，2019，27（11）： 107-115.
10	Zhang Liyi， Minglang Tseng， Wang Chinghsin， et al. Low-carbon cold chain logistics using ribonucleic aci-dant colony optimization algorithm［J］. Journal of Cleaner Production， 2019， 233（1）： 169-180.
11	康凯，韩杰，普玮，等. 生鲜农产品冷链物流低碳配送路径优化研究［J］. 计算机工程与应用， 2019， 55（2）： 259-265.
	Kang Kai， Han Jie， Pu Wei， et al. Optimization research on cold chain distribution routes considering carbon emissions for fresh agricultural products［J］. Computer Engineering and Applications， 2019， 55（2）： 259-265.
12	鲍春玲，张世斌.考虑碳排放的冷链物流联合配送路径优化［J］.工业工程与管理，2018， 23（5）： 95-100+107.
	Bao Chunling， Zhang Shibin.Route optimization of cold chain logistics in joint distribution： with consideration of carbon emission［J］. Industrial Engineering and Management， 2018， 23（5）： 95-100+107.
13	Alkaabneh F， Diabat A， Gao H O. Benders decomposition for the inventory vehicle routing problem with perishable products and environmental costs［J］. Computers & Operations Research， 2020， 113（1）： 104751 .
14	Zulvia F E， Renjieh Kuo， Nugroho D Y. A manyobjective gradient evolution algorithm for solving agreen vehicle routing problem with time windows and time dependency for perishable products［J］. Journal of Cleaner Production， 2020， 242（1）： 118428.
15	王宁，胡大伟，徐杰，等.基于客户价值和满意度的城市冷链物流时变路径问题［J］. 中国公路学报， 2021， 34（9）： 297-308.
	Wang Ning， Hu Dawei， Xu Jie， et al. Timedependent vehicle routing of urban cold-chain logistics based on customer value and satisfaction［J］. China Journal of Highway and Transport， 2021， 34（9）：297-308.
16	王敏. 基于遗传算法的冷链物流网络节点选址研究［D］. 湖南大学， 2010.
	Wang Min. Genetic algorithm based cold chain logistics network node location research ［D］. Hunan University， 2010.
17	Barth M， Younglove T， Scora G. Development of a heavy-duty diesel modal emissions and fuel consumption model［R］. Working Paper， UC Berkeley： California Partners for Advanced Transportation Technology， 2005.
18	Fukasawa R， He Qie， Song Yongjia. A disjunctive convex programming approach to the pollutionrouting problem［J］. Transportation Research Part B： Methodological， 2016， 94（12）： 61-79.
19	Toro E M， Franco J F， Echeverri M G， et al. A multiobjective model for the green capacitated location-routing problem considering environmental impact［J］．Computers & Industrial Engineering， 2017， 110（8）： 114-125．
20	Tang Jiafu， Pan Zhendong， Fung R Y K， et al. Vehicle routing problem with fuzzy time windows［J］. Fuzzy Sets and Systems， 2009， 160（5）： 683-695.
21	Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6 （2）： 182-197.
22	陈久梅，李英娟，胡婷，等. 开放式带时间窗车辆路径问题及变邻域搜索算法［J］. 计算机集成制造系统， 2021， 27（10）： 3014-3025.
	Chen Jiumei， Li Yingjuan， Hu Ting， et al. Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm［J］.Computer Integrated Manufacturing Systems， 2021， 27（10）： 3014-3025.

优化目标	总成本最小	货损最小	碳排放最小
Z₁	6617.2	6812.6	6752.5
Z₂	0.897	0.912	0.910
C₁	3009.8	3086.9	2966.4
C₂	1032.2	1001.8	1117.8
C₃	1991.1	2071.3	1933.8
C₄	56.23	58.46	54.58
C₅	526.86	594.16	680.00
D	841.53	905.72	805.32
K	5	5	5

算例	PN	优化目标							D	K
算例	PN	Z₁	Z₂	C₁	C₂	C₃	C₄	C₅	D	K
R202	41	7680.0	0.853	2772.1	1167.6	1957.1	55.2	1727.8	810.1	4
R204	41	6949.7	0.973	2905.5	1254.7	2129.8	60.1	599.6	921.2	4
R206	42	7723.4	0.886	2986.9	1247.9	2236.2	63.1	1189.2	989.1	4
R208	41	6675.9	0.976	2901.5	1167.6	2115.6	59.7	431.5	917.9	4
RC202	40	8440.9	0.853	3269.3	1172.3	2319.7	65.5	1614.1	1024.1	5
RC204	42	7277.5	0.954	3202.6	1195.5	2239.2	63.2	576.8	1002.2	5
RC206	41	8729.1	0.841	3371.4	1291.0	2458.2	69.3	1539.2	1142.8	5
RC208	42	8293.4	0.906	3507.6	1396.5	2648.8	74.8	665.8	1277.4	5

[1]	高佳静, 镇璐. 多卡车多机器人联合配送系统路径问题研究[J]. 中国管理科学, 2023, 31(3): 48-57.
[2]	李阳, 范厚明, 张晓楠. 动态需求下车辆路径问题的周期性优化模型及求解[J]. 中国管理科学, 2022, 30(8): 254-266.
[3]	王勇, 张杰, 刘永, 许茂增. 基于资源共享和温度控制的生鲜商品多中心车辆路径优化问题[J]. 中国管理科学, 2022, 30(11): 272-285.
[4]	李迁, 陶莎, 周晓园, 盛昭瀚. 考虑作业空间干涉的工程项目时间-成本均衡优化研究[J]. 中国管理科学, 2019, 27(10): 170-178.
[5]	王征, 张俊, 王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J]. 中国管理科学, 2011, 19(2): 99-109.