基于低碳与随机需求的多目标车辆路径优化

2021-09-12张得志乔馨肖博文王日东毛成辉

铁道科学与工程学报 2021年8期

张得志，乔馨，肖博文，王日东，毛成辉

(1. 中南大学交通运输工程学院，湖南长沙410075；2. 清华大学机械工程学院，北京100084)

近年来，电子商务的发展对我国消费增长、产业升级和经济发展起到了极大的推动作用[1]。然而，在城市物流配送过程中，大量二氧化碳的排放对环境造成了严重影响，国际能源署(IEA)数据表明，交通运输业的碳排放量占能源消耗的23%[2]，其中道路运输是碳排放的主要来源，根据相关部门统计数据，我国道路运输碳排放量在交通运输业中占比高达86.32%[3]，作为电子商务的重要支撑，其排放控制问题和对策成为国内外研究的焦点；同时，B2B 模式下的客户需求往往不确定，客户满意度成为提升企业价值的关键因素。因此，在低碳与需求随机的条件下，考虑客户满意度、车队规模与配送成本并进行集成优化十分必要。目前，国内外学者围绕低碳车辆路径问题(Vehicle Routing Problem，VRP)进行了大量研究工作，多为单目标优化。KARA 等[4]以能耗最小的方式将绿色理念与车辆路径问题结合，推动了这一领域的发展；FIGLIOZZI[5]以减少CO2为目标建立了带时间窗约束的VRP 模型并以迭代算法进行优化求解，将CO2排放的测算脱离了能耗；邱雅君等[6]通过线性加权将碳排放引入VRP，并使用遗传算法进行求解；崔娥英等[7]测算了有碳税和碳交易的配送中心和配送环节的碳排放；李进等[8]将车辆速度与碳排相结合，研究了相应的碳税激励机制；张得志等[9]建立了基于CO2排放的多车型VRP 模型，考虑了市内行驶速度的时变性；程兴群等[10]同时考虑低碳政策与道路拥堵，设计了基于保优策略和移民策略的遗传算法。在多目标VRP 问题方面。陈希琼等[11]建立同时考虑车辆容量和距离约束的VRPSPD 双目标模型；ZHANG 等[12]同时考虑运输成本和每条路径间的平衡；李嫚嫚等[13]等以最大化客户满意度与最小化配送成本作为优化目标,对带时间窗的车辆路径问题进行研究。郭森等[14]综合考虑了配送中距离最短、时间最少和费用最省三个目标，但未考虑低碳因素。同时，上述研究都是基于确定性需求特征进行探索优化，一定程度上忽略了B2B 环境下需求不确定性对物流配送优化的影响，因而得到的解决方案鲁棒性较差，现实中会增加物流企业的配送成本。基于此，本文考虑电子商务环境下，大型连锁超市以B2B 为主的配送业务，考虑配送总成本、车队规模以及客户时间满意度，构建基于低碳与随机需求的多目标车辆路径模型，设计基于Pareto最优解的多目标遗传算法进行求解，并以步步高集团云通物流配送为例，进行实证分析。

1 问题分析与建模

本文提出基于低碳视角与随机需求的多目标车辆路径优化模型，使用多辆同种车辆从配送中心配送至客户点，客户点需求存在不确定性。要求规划合理的配送路线使得成本最小，同时考虑低碳经济的要求并尽可能地减少车辆使用数量。

1.1 模型假设

1)配送中心只有一个且已知；

2)客户位置和配送中心位置已知；

3)不得超过配送车辆最大容量限制；

4) 客户需求服从正态分布，其均值、方差已知；

5)车辆为同种车型，且容量已知；

6) 客户接受服务的时间窗已知，可以违反但会产生相应惩罚。

1.2 数学模型

符号表示：

V={0,1,2,…,n}：其中0 表示配送中心，1,2,…,n表示需要服务的客户点

M={1,2,3,…,k}：服务车辆集合

m= |M|：使用车辆总数

Eij：路径(i,j)上车辆的能量消耗量

δ：碳排放因子，KgCO2/L

cv：配送车辆的固定成本，元/次

cf：每单位燃料的价格，元/L

ce：单位CO2排放的纳税额，元/kg

cd：司机单位时间薪酬，元/h

Satisf ki：车辆k服务的客户i的满意度

q+：车辆的容量上限，kg

qi：客户i的需求量，kg

Tk：车辆k的总耗时，h

a：允许的路由失败次数

目标函数：

约束条件：

式(1)～(3)为目标函数。目标(1)表示配送的总成本最小，包括两部分：车辆固定使用成本与变动成本，其中变动成本包括了燃料成本、碳排放纳税额和司机报酬；目标(2)表示使用的车队规模最小；目标(3)表示客户时间满意度最大。(4)～(9)为约束条件，式(4)表示一个客户有且仅由一辆车提供服务；式(5)表示两点之间的运输必须由一辆车完成；式(6)和(7)表示每个客户点只能被服务一次；式(8)表示路径允许的需求总量；式(9)为变量的非负约束。

1.3 车辆能源消耗量

基于BARTH 等[15]提出的重型车辆综合排放测算模型，构造运用距离dij和速度vij来测算路径(i,j)上车辆的能量消耗函数。

其中，vij表示车辆在路径(i,j)上的平均速度，m/s；ρ表示空气密度，kg/m2；mij为车辆在路径(i,j)上的载重量；M为车辆自重；S为车头与空气的接触面积；ϒ为能源的空气质量比；K为引擎摩擦系数；E为引擎排量；N为引擎转速；η柴油引擎的效率；ηcd为功率传递效率；Pzs为引擎运转损失；Ckq为空气摩擦阻力系数；dij为路径(i,j)的行驶距离；τ表示能源从g/s到l/s的转化因子；κ表示燃料的发热量；将与路径相关的多个阻力变量整合为ψij=a+gsinφ+gCgdcosφ，其中a为加速度；g为引力常数；φ为道路倾斜角；Cgd为滚动摩擦阻力系数。

1.4 客户时间满意度

考虑软时间窗约束，即在客户规定的时间窗内到达为满意，若到达时间早于客户要求时间将等待，直到客户要求的开始时间，设满意度最大为1，最小为0。采用改进的降半哥西分布，设置客户敏感度系数为0.000 05：

其中：Satif(ti)表示满意度，ti为车辆到达客户i的时间，Ui，Li为时间窗上下限。

2 求解算法

参考TAN等[16]的研究，设计基于Pareto最优解的多目标遗传算法进行求解。

算法求解过程如下：

Step 1：初始化算法，对各变量进行赋值，随机产生初始种群；

Step 2：进行适应度评估与Pareto 排序，选出较优的个体组成新的种群；

Step 3：进行二元联赛选择，更新种群；

Step 4：染色体配对，进行路径交叉；

Step 5：依概率进行染色体变异(包括分裂、整合、部分交换)；

Step 6：判断染色体是否为可行解，若不是则将不满足条件的染色体去除，重新从父代中选择较优的个体插入种群中；

Step 7：判断是否满足算法的终止条件，若满足则输出当前最优解，否则返回Step 2。

算法描述如下：

1) 编码：采用实数编码法进行基因型编码。每个基因位在实际中对应于其客户编号。例如一条路径的基因位数为6(即有6个客户，其客户编号分别为1，3，4，6，7 和9)，其路由顺序为：0→1→4→3→7→9→6→0，则其基因型为(01437960)。

2) 适应度测算：使用目标函数作为适应度测量指标。

3)Pareto 最优排序：根据适应度进行Pareto 最优排序，最优个体的排序等级为0，次优排序等级为1，以此类推。

4) 选择算子：使用二元锦标赛的方式进行选择。

5)交叉算子：如图1，设定交叉概率，生成0到1之间的随机数，若小于交叉概率则随机选择群体中的2 条染色体中的2 条路径进行双点交叉，交叉之后对各条染色体删除重复客户点。为增大搜索空间，交叉后对染色体的路径依概率进行随机洗牌。

图1 交叉算子示意图Fig.1 Crossover operator diagram

图2 交叉算子示意图Fig.2 Mutation operator diagram

6) 变异算子：采取3 种变异方式进行突变[15]。①部分交换：在同一条染色体内随机选择2条路径交换部分基因位，产生新路径；②合并短路径：将染色体内2条较短路径进行合并，形成一条长路径；③分裂长路径：将染色体内过长染色体进行随机位拆分。每种突变方式依概率发生，变异后对每条路线依概率随机洗牌。

3 算例分析

本文选取步步高连锁超市的日配送数据进行实例分析。该连锁超市由云通物流中心负责该区域内超市零售配送任务。假设客户点的需求为服从正态分布的随机需求，均值和方差已知。各需求点都有软时间窗要求，违反时间窗会使客户的时间满意度降低。客户中心和配送中心位置分布如图3所示。

图3 客户和配送中心地理位置分布图Fig.3 Geographic distribution of customers and DCs

3.1 参数设置

车辆燃料为柴油，柴油价格为6.36元/L；车辆的自重3 t，最大容积为2 t；CO2排放的征税额为50 元/t。本文引用DEMIR 等[17]使用的道路数据进行模拟研究，参数设置如表1所示。

表1 测算参数数据Table 1 Calculation parameter data

3.2 求解结果

每次迭代随机正态生成10 组需求数据进行适应度评估，以10 组评估的均值作为评价依据，分别进行10次模拟，每次种群数量为500，迭代次数上限为400。

结果表示，非支配解集和最终种群中车辆数都是9辆，这表明现有运营状态下，配送中心车辆最优数量为9 辆，对应的最优配送方案如表2 所示，图4给出了最优的配送路线图，对应的配送总成本为4 779.23 元，其中车辆固定成本1 800 元，能耗成本1 322.99 元，碳排成本28.39 元(CO2排放约为620 kg)，司机报酬为1 627.85 元，客户时间满意度为27.03。

图4 配送线路图Fig.4 Distribution route

表2 最优配送方案Table 2 Optimal distribution scheme

3.3 算法性能分析

1) 算法收敛性分析

由图5可知，种群平均配送总成本和非支配集平均配送总成本在迭代300 代之后均处于收敛状态，收敛于4 800 元左右，但是收敛速度较慢；相比之下，车辆数收敛速度较快，在300代时，基本处于收敛状态，均收敛于9辆；而客户时间满意度收敛性较差，尤其是非支配解集的平均客户时间满意度，虽然明显表现出先下降后上升的趋势，但波动较大。由于未对车辆数加以限制，在初始化过程中将优先使用较多的车辆进行配送，因此客户时间满意度较高，但随着使用车辆数的优化，客户时间满意度逐步下降，在进一步优化过程中逐渐上升，趋于收敛值28。

图5 收敛性评价Fig.5 Convergence evaluation

根据种群和非支配解集内各个目标函数的均值收敛情况，可知在迭代400次之后得到的解目标基本处于收敛状态，可以认为已经接近最优解集，具有一定可靠性。

2) 方案适应性分析

研究时使用的客户需求具有不确定性，处于不断波动之中。因此，所得到的方案能否在需求发生波动之后，依然保持良好的适应性十分重要。为评价方案的适应性，本研究在得到最优方案集之后根据需求均值和方差随机生成了4 组需求数据，对得到的方案进行模拟，得到现实运营过程中目标函数值，并与得到的目标函数期望值进行对比。

图6显示需求波动对平均配送成本存在一定影响，其中测试2 和4 相对较稳定，其中值在300 附近，而测试1 和3 稳定性较差，其差距中值超过300，约占总成本的10%。可以看出，平均之后得到均值的中值处于300附近，而且其数据波动范围也较小，因此可认为其适应性优良，鲁棒性较好。

图6 适应性评价Fig.6 Adaptability evaluation

3.4 交叉目标分析

客户时间满意度与其余目标存在冲突，表现在初期阶段其他目标优化会引起客户时间满意度降低。

为更加详细地说明这种相关或冲突的程度，进行目标函数对比，使用增长的百分比作为依据，对比不同目标函数之间增长的趋势关系。从表3可知：当配送成本减少37.7%时，客户时间满意度则降低了1.7%，前者变化率是后者的22 倍。这表明，现实中要想最大化客户满意度十分困难，需要投入大量成本；但在电商环境下，客户满意度几乎是企业存亡的决定因素，因此企业往往将客户满意度作为优先考虑的目标，而低碳则属于次级目标。

表3 目标函数值前后对比分析表Table 3 Comparative analysis of objective function values

3.5 灵敏度分析

1) 碳税额对结果的影响

为进一步探究碳税额度变化对算法优化结果的影响，本文对碳税额参数的灵敏度进行分析。由表4可知，如果以征税的方式控制碳排放量，碳税额度并非越高效果越好。仅从政府管理的角度，当碳税额定为70元/t，碳排放量最低。

表4 碳税额对结果(收敛值)的影响Table 4 Influence of carbon tax on the result(convergence value)

选取成本与满意度的比值以及成本与碳排放量的比值评价碳税额度的效果。比值表示每提高一单位满意度或者降低1 kg的CO2排放量所要付出的成本。如图7 所示，从物流配送行业的角度分析，碳税额定在40 元/t最优。

图7 碳税额评价Fig.7 Carbon tax evaluation

2) 目标选择对结果的影响

如图8所示，若以碳排放最小为目标函数进行单目标优化，在收敛时，其收敛值可以低至570 kg。相对于将其并入总配送成本中，可以减少8%以上的CO2排放，从低碳的角度更有利。但客户时间满意度下降到28.2 左右，相比之前减少约1.3。可知碳排减少与服务质量提高之间是冲突的，这也是企业在节能减排工作压力的来源之一。

图8 碳排放作为单独目标结果Fig.8 Result of carbon emission as an separate target

进一步分析极端情况，对每个目标分别优化，探究多目标优化对于每个目标的影响。

如表5 所示，通过①和②的结果对比可以看出，配送车辆总成本与车辆数之间没有冲突，能够达到同时优化的目的，根据上文中的分析也可知，车辆的固定使用成本占总成本的比例很高，因此车辆数的优化也是配送总成本优化的关键；而通过①和③、②和③的对比发现，客户时间满意度与另外2个目标相冲突，将客户时间满意度提高至100%时，另外2 个目标的值都大大提高。对配送总成本进行单独优化时，其低碳优化效果最好，甚至优于同时优化3个目标。在①情境下，配送总成本减少了2%左右，车辆数减少3%，但是客户时间满意度减少6.7%；在②情景下，车辆数减少2%，但成本上升30.7%，客户时间满意度下降27.2%；在③情景下，客户时间满意度提高至30增长2%，但引起另外2 个目标大幅度恶化，成本增长63.6%，车辆数增长63.3%。相比之下，②和③作为单目标优化的目标函数是不明智的选择。

表5 单目标优化结果Table 5 Results of single objective optimization

从图9 中可以看出，若降低配送成本的重要性，碳排量将显著增加，同时在4个选择中，其客户时间满意度是最大的，最终收敛于30，最终得到的总成本也是最高的，但对车辆数并没有很大影响，这充分说明了成本与客户满意度之间的冲突；若降低客户时间满意度的重要性，其他3个量将同时达到最低，在优化过程中要重视对于客户时间满意度目标的抉择，其灵敏度较高，对优化结果影响较大；而降低车辆数的重要性对于优化过程并没有产生明显影响，说明这一目标函数在优化过程中的灵敏度较低，在现实中可以忽略或置于配送总成本中考虑。