2. 湖南工商大学 移动商务智能湖南省重点实验室,长沙 410205;
3. 电子科技大学 经济与管理学院,成都 611731
2. Key Laboratory of Hu'nan Province for Mobile Business Intelligence, Hu'nan University of Business and Technology, Changsha 410205, China;
3. School of Economics and Management, University of Electronic Science and Technology of China, Chengdu 611731, China
生鲜电商已成为生鲜农产品上行的主要渠道之一, 但物流配送一直是生鲜电商发展的瓶颈问题.
解决生鲜电商配送问题的关键在于科学求解农产品配送的车辆路径问题(vehicle routing problem, VRP).起初, 学者们研究了常温条件下生鲜农产品配送的VRP[1-3], 这些文献具有一定参考价值.随着研究的拓展, 学者们研究了冷链环境下的农产品配送问题.文献[4]以农产品冷链总成本最小为目标构建带时间窗车辆路径问题(vehicle routing problem with time windows, VRPTW)模型; 文献[5]以农产品冷链物流网点建设与运营成本之和最小为目标构建VRP模型; 文献[6]以收益最大为目标建立冷链VRPTW模型; 文献[7]以冷链总成本最小为目标构建VRP模型; 这些研究为农产品冷链配送提供了有益借鉴.鉴于生鲜农产品具有易腐性, 文献[8]以利润最大为目标建立易腐品生产与配送协同优化模型, 设计混合智能算法求解; 文献[9]以总配送费用最小为目标构建易腐品生产-配送协同优化模型, 设计混合启发式算法求解.为保障生鲜农产品送达客户时的新鲜度, 文献[10]研究了不同配送环境与不同产品变质系数条件下生鲜农产品的新鲜度与配送成本; 文献[11]以总配送成本最小和顾客满意度最大为目标建立生鲜农产品VRP模型; 文献[12]以总配送成本最小、交付产品的新鲜度最大为目标建立易腐品生产-配送协同优化模型.这些文献为提高生鲜农产品配送的客户满意度提供了理论支撑.
梳理国内外文献, 以下方面仍可深入研究:
1) 已有文献大都假设车辆速度固定, 与生鲜电商配送的实际情况不够吻合.生鲜电商客户主要分布在城市, 由于早晚交通高峰、道路限速等原因, 车辆在不同时间段内以不同速度行驶.
2) 已有研究主要考虑经济成本, 较少关注环境影响, 不利于节能减排.
3) 生鲜农产品的新鲜度随时间推移而下降.新鲜度直接影响身体健康, 相关成果不多.
4) 已有文献大都假设车辆在0时刻从配送中心出发, 关于车辆不同时刻出发的研究缺乏.
尽管文献[10-12]已研究了具有新鲜度限制的生鲜农产品配送VRP, 文献[13]考虑了车辆不同出发时刻的VRPTW, 文献[14]探讨了时变网络下农产品配送的VRP, 但都没有综合考虑.因此, 本文基于经济成本与环境成本兼顾的视角研究生鲜电商配送的带时间窗车辆路径问题(time-dependent vehicle routing problem with time windows, TDVRPTW), 并分析配送经济成本与环境成本之间的关系, 期望能为生鲜电商配送提供决策参考.
1 问题描述某配送中心为客户配送生鲜农产品, 客户位置、需求量、时间窗与服务时间已知, 农产品具有最低新鲜度限制.车辆可以提前到达客户, 但必须等待至客户最早服务时间才能配送.决策问题:如何制定配送计划, 使得总配送成本最小?为明确论文适用范围, 提出如下假设:
1) 车辆为同一类型, 不同时间段内行驶速度不同, 可以在不同时刻出发, 完成任务后回到配送中心;
2) 客户需求量小于车辆容量, 有且仅有一辆车为其服务;
3) 车辆有固定使用成本、油耗成本、碳排放成本与人力成本;
4) 车辆在等待与客户服务时间内, 发动机关闭, 不产生油耗与碳排放.
2 数学模型 2.1 跨时间段的路段行驶时间计算方法时变路网条件下, 不同时间段内的车辆行驶速度不同, 行驶时间难以直接计算, 需要合理处理.
文献[15-17]将车辆在足够短时间段内的实时速度视作其在该时间段内的固定行驶速度.本文参考已有方法, 综合分析时间段、路段距离、车辆速度、行驶距离与行驶时间之间的关系, 设计基于时间段划分的路段行驶时间计算方法(图 1): 1)将配送中心工作时间划分为多个时间段; 2)不同时间段内的车辆行驶速度如图 1(a)所示, 车辆行驶距离与行驶时间如图 1(b)所示; 3)根据图 1(a)各时间段内的行驶速度与图 1(b)的行驶距离, 可以计算车辆在各时间段的行驶时间, 得出车辆行驶完路段全程的行驶时间.
令U为时间段的时间长度; T={T0, T1, …, TL}为配送中心工作的时间段集合; [TR-1, TR]为第R个时间段; tijkR为时间段R内车辆k在路段(i, j)上的行驶时间; sijkR为时间段R内车辆k在路段(i, j)上的行驶速度; FijkR为时间段R内车辆k在路段(i, j)上的行驶距离; Jij为路段(i, j)的距离,
step 1:开始时间段的车辆行驶时间计算. FijkR=sijkRRk.如果FijkR≥Jij, 则tijkR=Jij/sijkR, tijk=tijkR, 计算完毕; 否则, JijR=Jij-FijkR, tijkR=Rk, 转step 2.
step 2:其余时间段的车辆行驶时间计算.
step 2.1:令ξ=1;
step 2.2:
采用文献[13]提出的常温条件下生鲜农产品的新鲜度度量函数
(1) |
其中: 0<ti≤Tp, ti为农产品送达客户i的时间, 1为农产品从配送中心运出时的新鲜度, Tp为农产品的保质时间.
2.3 符号与变量符号: A为所有节点集合, A={0, 1, …, n }, 其中0表示配送中心, A'=A\{0}表示客户集合; V为配送车辆集合; Q为车辆容量; qi为客户i的需求量; gi为客户i的服务时间; [Bi, Ei]为客户i的服务时间窗; aik为车辆k到达节点i的时间; σik为车辆k到达节点i的等待时间, 如果aik<Bi, 则σik=Bi-aik, 否则σik=0;w为农产品的最低新鲜度限制; G为车辆固定使用费用; Y为车辆使用的单位时间人力成本; fijkR为车辆k在时间段R内行驶在路段(i, j)上的油耗率; cijkR为车辆k在时间段R内行驶在路段(i, j)上的碳排放率; H为单位油耗成本; C为单位碳排放成本; Z为配送中心的最晚服务时间.
决策变量: xk为0-1变量, 当车辆k被使用时值为1, 否则值为0; yijk为0-1变量, 当车辆k从节点i行驶到节点j时值为1, 否则值为0; zik为0-1变量, 当客户i由车辆k服务时值为1, 否则值为0.
2.4 数学模型构建带最低新鲜度限制的TDVRPTW模型如下:
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
(10) |
(11) |
(12) |
(13) |
(14) |
(15) |
(16) |
(17) |
式(2)为目标函数, 最小化配送经济成本与环境成本之和.其中, 经济成本由车辆固定使用成本与人力成本组成, 人力成本包括车辆行驶时间、等待时间与服务时间的人力成本, 环境成本包括油耗成本与碳排放成本.式(3)表示客户必须且只能被服务一次.式(4)表示路段行驶时间与各时间段内的车辆行驶时间之间的关系.式(5)保证车辆到达与离开的是同一个节点.式(6)表示每辆车最多只能使用一次.式(7)表示路段距离与各时间段内的车辆行驶距离之间的关系.式(8)和(9)表示客户时间窗约束.式(10)表示车辆到达客户时间、等待时间、服务时间与离开客户时间之间的关系.式(11)表示车辆从上个节点行驶到下个节点的时间关系.式(12)表示车辆容量约束.式(13)表示农产品送达客户的时间.式(14)表示农产品的最低新鲜度限制.式(15)表示生鲜农产品送达客户的时间不大于保质时间.式(16)表示生鲜农产品的保质时间限制.式(17)表示变量的取值约束.
2.5 车辆碳排放与油耗计算采用MEET模型[18]计算车辆碳排放, 具体如下:
时间段R内车辆k的碳排放率(g/km)为
(18) |
其中: ϑvR为车辆空载且在坡度为0的道路上以速度v(v=sijkR)行驶时的碳排放率, ω0、ω1、ω2、ω3、ω4、ω5与ω6为预定义参数, 根据货车类型取值.
碳排放率的载重修正因子ψ为
(19) |
其中: γ为车辆在路段(i, j)上的实际载重与其容量的比值, χ0、χ1、χ2、χ3、χ4、χ5、χ6与χ7为预定义参数, 根据货车类型取值.
时间段R内车辆k的碳排放率(kg/km)为
(20) |
车辆k在路段(i, j)上的油耗率为
(21) |
由于蚁群算法具有分布计算、信息正反馈和启发式搜索等特征[17], 本文根据问题与模型特点设计一种自适应改进蚁群算法, 具体步骤如下.
step 1:算法初始化.初始化变量与参数, 将M只蚂蚁都放置在配送中心, 令m=1.
step 2:构建可行解.
step 2.1:将蚂蚁m的所有未访问节点放入集合allowedm.
step 2.2:计算蚂蚁m从节点i到节点j的转移概率
(22) |
其中: τij为信息度浓度; ηij为能见度, ηij=1/Jij; δ、μ与ε分别为3种因子的重要性.
step 2.3:找出Pijm值最大的节点jmax, 如果满足w与Q等条件, 则蚂蚁m行驶到节点jmax; 否则, 蚂蚁回到配送中心, 转step 1, 直到所有节点访问完毕.
step 2.4:计算各车辆从物流中心出发的时间.
step 2.5: m=m+1, 如果m<M, 则转step 1.
step 3:目标函数值计算.
step 3.1:计算本次迭代的最优目标函数值Oiter.
step3.2:如果best cos t>Oiter, 则best cos t=Oiter.
step 3.3: iter=iter+1.
step 4:自适应信息素启发式因子和期望启发式因子.根据文献[17]提出的方法, 令δ=1+3(iter/max iter), μ=3-2(iter/max iter).
step 5:更新信息素, 所有蚂蚁完成周游后更新最优路径, 组成路段的信息素, 即
(23) |
(24) |
其中: ρ为信息素挥发性, 0≤ρ < 1;Δτijm为信息素增加量; W为常数; fm为蚂蚁m的总配送成本.
step 6:算法结束判断.如果iter<max iter, 则转step 2, 否则, 算法结束.
4 算例实验 4.1 实验设置由于没有TDVRRTW测试数据库, 并考虑到生鲜电商的客户分布具有多种情况, 采用VRPTW数据库[19]中的C类型算例(集中分布)、R类型算例(随机分布)与RC类型算例(混合分布)的所有数据作为本文测试数据.各算例都有100个客户与一个配送中心.为符合测试要求, 补充如下数据:
1) 令配送中心最早工作时间为7: 00(设为0时刻, 对应配送中心的READY TIME, 即0 min), 最晚工作时间为23: 00(对应DUE TIME, 即960 min).每10 min作为一个时间段.
2) 根据城市交通规律, 将7: 30~9: 00、17: 30~19 : 00设为交通拥堵时间段(车速为20 kM/h), 其余时间为正常行驶时间段.
3) 令ϖ=0.1, 设计3种车速[60(1-ϖ), 60(1+2ϖ), 60(1-3ϖ)].根据时间段R的值, 采用求余函数λ=mod(R, 3), 当λ分别取值[1, 2, 0]时, 对应正常时段的3种时变车速[15].
算法采用Matlab R2016a编程, 在CPU 1.90 GHz、内存4 G的微机上运行.参考文献[15, 17]的方法, 将参数设置如下: G=150元/辆车、Y=0.3元/min, Q=1 000单位, max iter=600, m=30, ρ=0.2, ε=3, W=20, Tp=840 min, w=0.7, H=7.5/L, C=0.052 8元/kg, Z=960 min, ω0=110, ω1=0, ω2=0, ω3=0.000 375, ω4=8 702, ω5=0, ω6=0, χ0=1.27, χ1=0.061 4, χ2=0, χ3=-0.001 1, χ4=-0.002 35, χ5=0, χ6=0, χ7=-1.33.
4.2 实验结果 4.2.1 不同客户分布算例的车辆路径规划采用多类型算例实验.实验结果如表 1所示. 表 1中, EX表示算例名称, TC表示总配送成本(单位:元), VD表示总行驶距离(单位: km), VT表示总行驶时间(单位: min), HC表示总人力成本(单位:元), FC表示总油耗与碳排放成本(单位:元), VN表示车辆使用数量(单位:辆), CPUT表示程序运行时间(单位: s).
由表 1可知: 1)程序最大运行时间为408.14 s, 说明本文算法能在较短时间内有效求解不同算例. 2) C类型算例的总配送费用最高, 车辆行驶距离最短, 行驶时间最短, 油耗费用最低, 但是车辆使用数量最多.原因在于C类型算例的客户集中分布在几个区域, 客户之间的距离较短, 但各客户的时间窗比较窄、且服务时间高达90 min, 使得车辆仅仅可以配送少量客户. 3) R类型与RC类型算例的总配送费用与车辆使用数量显著低于C类型算例, 但车辆行驶距离、行驶时间与油耗费用却相反.这是由于R类型与RC类型算例的客户随机均匀分布, 客户之间距离相对较长, 但各客户的时间窗相对较长, 且服务时间只有10 min, 使得车辆可以配送多个客户.
算例C103、R203与RC203的路径规划如图 2所示.由图 2可知, 客户坐标为集中分布的C类型算例的配送路径比较有规律, R类型(均匀分布)与RC类型(混合分布)算例的配送路径没有明显规律.所有实验的目标函数值普遍在400次迭代以后收敛, 说明改进蚁群算法能有效解决早熟收敛问题, 实现决策目标.
将本文方法与以车辆总行驶距离最短、以油耗与碳排放费用之和最小为目标的车辆路径规划方法作对比实验.实验结果如表 2所示.表 2中符号的含义同表 1.
由表 2可知: 1)本文算法在不同目标都能取得比其他目标更优的结果. 2) C类型算例3种目标的总配送成本浮动范围低于2.67 %, 没有明显区别. 3) R类型与RC类型算例的计算结果有着显著区别.算例R204以最低油耗与碳排放费用为目标的总配送成本, 比本文方法要高15.63 %.算例RC206以最短行驶距离为目标的总配送成本, 比本文方法要高24.41 %. 4)本文方法能求得最优总配送成本.算例R204的路径规划方案如表 3所示. 表 3中, N表示车辆序号, VR表示车辆路径(0表示配送中心, 其余数字代表客户序号), TVAN表示农产品送达客户时间(首数字为车辆的出发时间, 尾数字为车辆回到配送中心的时间), ST表示车辆的出发时间段.
由表 3可知: 1)从VR来看, 各车辆的配送任务具有显著差异性.原因在于配送规划受到路网状况、时间窗与最低新鲜度等条件限制. 2)由TVAN可知, 车辆1、车辆2、车辆3与车辆4都在0时刻从配送中心出发, 其余车辆的出发时间各不相同.为保障农产品新鲜度, 车辆6与车辆7分别在第676.52 min与第589.79 min出发.如果所有车辆都在0时刻出发, 生鲜农产品送达较晚时间窗的客户时, 将不能满足最低新鲜度条件.说明企业应根据交通路网、客户时间窗与农产品新鲜度等实际情况, 合理规划车辆出发时间. 3)综合分析TVAN与ST的数据可知, 车辆1、车辆2、车辆3与车辆4都仅进入早高峰拥堵时间段, 车辆5与车辆8完全避开早晚高峰拥堵时间段, 车辆6与车辆7仅进入晚高峰拥堵时间段.说明有些客户的时间窗属于拥堵时间段, 车辆必须在该时间段进行配送; 同时也说明本文方法能有效规避拥堵时间段, 降低总配送成本.
4.2.3 算法对比实验将本文算法与经典蚁群算法[20]作对比实验, 实验结果如表 4所示. 表 4中的符号含义同表 1.
由表 4可知: 1)关于C类型算例, 改进蚁群算法要优于经典蚁群算法.总配送费用最高降低6.71 %, 车辆使用数量最多节约2辆. 2)关于R类型算例, 改进蚁群算法具有明显优越性.总配送费用最高降低10.12 %, 车辆使用数量最多节约4辆. 3)关于RC类型算例, 改进蚁群算法具有显著优越性.总配送费用最高降低12.42 %, 车辆使用数量最多节约4辆.因此, 改进蚁群算法更优.
4.2.4 经济成本与环境成本的关系分析在其他变量参数不变的情况下, 将经济成本(EC)、环境成本(FC)分别赋予权重w1与w2, 且w1 +w2=1, w1 < 1, w2 < 1.为突出节能减排, 令w1≤w2.权重以0.1的梯度赋值, 算例RC205在各种权重组合下的计算结果如表 5所示. 表 5中, CC表示总碳排放费用(单位:元), CO2表示总碳排放量(单位: kg), 其余符号的含义同表 1.
由表 5可知: 1)经济成本占总配送成本的比例最低为64.5 %, 最高达到70.22 %, 这说明总配送成本主要来自经济成本. 2)环境成本占总配送成本的比例较低, 最高只有35.5 %, 最低只达到29.78 %, 且主要为油耗成本.碳排放成本最高只占总配送成本的0.66 %.这说明当前0.052 8元/kg的碳排放价格过低, 难以有效促进物流配送领域的节能减排. 3)当w1、w2均为0.5时, 总配送成本最低, 总碳排放量最高, 对环境影响最大; 随着权重w2增加, 总配送成本不断增加, 碳排放量不断减少, 对环境影响不断降低.这说明考虑环境目标, 强调节能减排, 导致总配送成本增加.
5 结论为降低生鲜电商配送成本, 兼顾环境保护, 本文构建具有最低新鲜度限制的TDVRPTW数学模型, 设计自适应改进蚁群算法求解.实验结果表明:
1) 企业应根据交通路网、时间窗与最低新鲜度等实际情况, 合理规划车辆从配送中心出发的时间, 有效规避交通拥堵时间段, 降低总配送费用;
2) 改进蚁群算法能有效降低配送费用, 减少车辆使用数量;
3) 节能减排导致总配送费用增加, 环境保护需要更多努力.
[1] |
吴晓明, 杨信廷, 邢廷炎, 等. 生鲜农产品配送中库存运输联合优化问题[J]. 计算机工程与设计, 2016, 37(3): 819-824. (Wu X M, Yang X T, Xing T Y, et al. Inventory- distribution joint optimization in fresh agricultural products distribution[J]. Computer Engineering and Design, 2016, 37(3): 819-824.) |
[2] |
Chen H K, Hsueh C F, Chang M S. Production scheduling and vehicle routing with time windows for perishable food products[J]. Computers & Operations Research, 2009, 36: 2311-2319. |
[3] |
何有世, 马腾飞. B2C环境下生鲜农产品物流配送路径优化研究[J]. 商业经济研究, 2017(5): 93-95. (He Y S, Ma T F. Study on optimization of distribution of fresh agricultural products under B2C environment[J]. Journal of Commercial Economics, 2017(5): 93-95.) |
[4] |
范立南, 董冬艳, 李佳洋, 等. 基于生鲜农产品的冷链物流配送路径优化[J]. 沈阳大学学报:自然科学版, 2017, 29(2): 125-131. (Fan L N, Dong D Y, Li J Y, et al. Route optimization of cold chain logistics based on fresh agricultural products[J]. Journal of Shenyang University: Natural Science, 2017, 29(2): 125-131.) |
[5] |
张文峰, 梁凯豪. 生鲜农产品冷链物流网络节点和配送的优化[J]. 系统工程, 2017, 35(1): 119-123. (Zhang W F, Liang K H. Optimization of cold-chain network nodes and delivery for fresh agricultural products[J]. System Engineering, 2017, 35(1): 119-123.) |
[6] |
Ahumada O, Villalobos J R. Operational model for planning the harvest and distribution of perishable agricultural products[J]. International Journal of Production Economics, 2011, 133(2): 677-687. DOI:10.1016/j.ijpe.2011.05.015 |
[7] |
范厚明, 杨翔, 李阳. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J]. 计算机集成制造系统, 2019, 1: 256-266. (Fan H M, Yang X, Li Y. Studying on half-open multi-depot vehicle routing problem based on the joint distribution mode of fresh food[J]. Computer Integrated Manufacturing Systems, 2019, 1: 256-266.) |
[8] |
马雪丽, 王淑云, 刘晓冰, 等. 易腐食品二级供应链生产调度与配送路线的协同优化[J]. 工业工程与管理, 2017, 22(2): 46-52. (Ma X L, Wang S Y, Liu X B, et al. Integrated optimization of production scheduling and distribution for perishable food products in two-echelon supply chain[J]. Industrial Engineering and Management, 2017, 22(2): 46-52.) |
[9] |
Devapriya P, Ferrell W, Geismar N. Integrated production and distribution scheduling with a perishable product[J]. European Journal of Operational Research, 2016, 259(3): 906-916. |
[10] |
Amorim P, Almada-Lobo B. The impact of food perishability issues in the vehicle routing problem[J]. Computer & Industrial Engineering, 2014, 67(1): 223-233. |
[11] |
邵举平, 曹倩, 沈敏燕, 等. 生鲜农产品配送中带时窗的VRP模型与算法[J]. 工业工程与管理, 2015, 20(1): 122-127. (Shao J P, Cao Q, Shen M Y, et al. Research on multi-objective optimization for fresh agricultural products VRP problem[J]. Industrial Engineering and Management, 2015, 20(1): 122-127.) |
[12] |
吴瑶, 马祖军, 郑斌. 有新鲜度限制的易腐品生产-配送协同调度[J]. 计算机应用, 2018, 38(4): 1181-1188. (Wu Y, Ma Z J, Zhen B. Integrated scheduling of production and distribution for perishable products with freshness requirements[J]. Journal of Computer Applications, 2018, 38(4): 1181-1188.) |
[13] |
Ma Z J, Wu Y, Dai Y. A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery[J]. Computers & Industrial Engineering, 2017, 114: 101-113. |
[14] |
吴瑶, 马祖军. 时变路网下带时间窗的易腐食品生产-配送问题[J]. 系统工程理论与实践, 2017, 37(1): 172-181. (Wu Y, Ma Z J. Time-dependent production-delivery problem with time windows for perishable foods[J]. Systems Engineering — Theory & Practice, 2017, 37(1): 172-181.) |
[15] |
Xiao Y, Konak A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J]. Transportation Research Part E, 2016, 88: 146-166. DOI:10.1016/j.tre.2016.01.011 |
[16] |
李妍峰, 高自友, 李军. 动态网络车辆路径派送问题研究[J]. 管理科学学报, 2014, 17(8): 1-9. (Li Y F, Gao Z Y, Li J. Dynamic vehicle routing and dispatching problem[J]. Journal of Management Sciences in China, 2014, 17(8): 1-9.) |
[17] |
李琳, 刘士新, 唐加福. 改进的蚁群算法求解带时间窗的车辆路径问题[J]. 控制与决策, 2010, 25(9): 1379-1383. (Li L, Liu S X, Tang J F. Improved ant colony algorithm for solving vehicle routing problem with time windows[J]. Control and Decision, 2010, 25(9): 1379-1383.) |
[18] |
Hickman A J. Methodology for calculating transport emissions and energy consumption[R]. Luxembourg: Office for official publications of the European communities, 1999: 1-362.
|
[19] |
Solomon M M. Algorithms for the vehicle routing problem with time windows constrains[J]. Operations Research, 1987, 35(2): 254-265. DOI:10.1287/opre.35.2.254 |
[20] |
Calvete H I, Galé C, Oliveros M J. Bilevel model for production-distribution planning solved by using ant colony optimization[J]. Computers & Operations Research, 2011, 38(1): 320-327. |