考虑道路坡度影响的多约束冷链配送问题研究

闵德权，孙晓娜，李宇航，江可鉴

绿色包装与循环经济

考虑道路坡度影响的多约束冷链配送问题研究

闵德权，孙晓娜，李宇航，江可鉴

（大连海事大学 交通运输工程学院，辽宁 大连 116026）

为改进传统冷链VRP将配送区域默认为二维平面，使得实际调度与理想状态产生差异而造成配送成本增加的问题，本文对相关问题进行深入研究，旨在合理规划资源配置，提升企业经济效益。通过引入坡度函数对油耗成本和碳排放成本进行计算，综合考虑三维空间位置、多车型、载质量变化、客户取送货需求和时间窗要求等多种现实约束，并提出一种基于K–means多维时空聚类的改进遗传算法进行求解。求解结果表明，若最初将道路坡度考虑在成本计算内，可有效降低9.58%的配送成本。同时，应避免大型车辆在重载时突然发生海拔变化。当发生海拔变化时，大型车辆可在卸载一部分货物后改变至更高的高度。本文研究的模型更加贴近实际路网，具有更高的适用性，特别是对有明显道路坡度城市的冷链品的配送具有现实的借鉴意义。

道路坡度；多约束；冷链配送；K–means多维时空聚类；改进的遗传算法

随着生鲜电商崛起、人工智能、大数据、物联网等技术的爆发，冷链物流产业得以迅速发展，其中“最后一公里”的配送已成为冷链物流市场普遍反映的最大问题[1]。“最后一公里”是指通过一辆冷链车将货物从配送中心运送至客户点的过程，研究发现，“最后一公里”配送成本已成为供应链网络中最昂贵的部分，可占到总运输过程的28%[2]。因此如何建立符合实际和适合城市特点的数学模型，以更高效运输和降低成本是冷链中心必须解决的问题。

为解决制约生鲜电商“最后一公里”发展的瓶颈，众多学者已将如何最小化配送成本作为优化目标，其中油耗成本作为主要的成本因素，其不仅与车辆的速度、距离、载值量和燃料类型有关，道路坡度也会对成本造成较大的影响[3]。现阶段，学者们对车辆油耗成本和碳排放成本的研究仍专注于速度、距离、载质量的变化。Zhang等[4]考虑了载质量的变化对燃油消耗的影响，利用改进的禁忌搜索算法求解了最小化成本的数学模型；康凯等[5]认为距离和载质量会影响成本，并采用改进的蚁群算法进行求解；狄卫民等[6]考虑车速、距离和载质量对油耗成本的影响，并设计头脑风暴优化算法进行求解；刘长石等[7]在时变路网考虑了车速、载质量和行驶距离对成本的影响，并设计了一种改进的蚁群算法进行求解。

以上文献都是将配送区域假设在二维平面上，忽视了节点间不对称这一事实，使得最优求解方案在实际调度中与理想化状态产生差异，造成因车辆路径规划错误而导致配送过程中额外成本的增加。Joubert等[8]为证实道路坡度在燃油消耗过程中起着重要作用，模拟了一个道路坡度在[−8°, 8°]内变化的场景，为重型车辆选择路径提供了必要的依据；Lajevardi等[9]提出将路面坡度剖面与给定速度和时间相匹配的方法，并在加拿大的大不列颠哥伦比亚省进行了验证；Ritter等[10]提出了一种基于道路坡度和车辆质量的估计理论分析，并在实验验证方面证实了其模型的实用性；Brunner等[11]构建了考虑道路等级信息和车载质量对油耗成本影响的模型，称其为陡峭道路VRP(VRP–SR)模型，并通过启发式算法求解。

通过对以往文献的整理与分析发现，现阶段文献仍有如下不足。

1）现有多数文献都将配送区域理想在二维平面上，忽视了道路坡度对车辆油耗和碳排放的影响，导致研究成果与实际调度产生较大差距，停留在理论层面。

2）针对多车型的行驶路线和车型选择的研究中，现有文献忽视了道路坡度对车辆分配的影响，主要体现在大型车辆虽会提升满载率，但过度爬坡会造成额外成本的增加，而小型车辆单位费用较高，如若考虑道路坡度只选择小型车辆也不现实。

3）针对MDOVRP的求解方法上，通过聚类和启发式2种算法结合已被广泛证明并应用，但已有文献的聚类方法大多采用二维空间上的任意2点间的欧式距离作为划分聚类簇的依据，忽略了节点间的不对称性问题，而导致聚类结果不全面。

综上，针对上述现有文献的不足，本文通过引入坡度函数对油耗成本和碳排放成本进行计算，综合考虑三维空间位置、多车型、载质量变化、客户取送货需求和时间窗要求等多种现实约束研究冷链产品的配送问题，并设计一种基于K–means多维时空聚类的改进遗传算法进行求解。这一研究旨在对有明显道路不对称性城市的生鲜品配送提供现实的借鉴意义，如我国的重庆、大连等地区。

1 问题描述与假设

1.1 问题描述

本文研究问题可描述如下：某一区域内有实行联合配送的多家冷链中心，车辆自某一中心出发，在多约束下完成指定的取送货任务，完成后车辆按就近原则返回任意配送中心。在此过程中，综合考虑道路坡度的影响，主要体现在对油耗成本、碳排放成本的影响和车辆安排的选择上，旨在为车辆规划合理的路径，使企业物流成本最低。

1.2 模型假设

针对本文研究问题，为方便建模，假设条件如下：

1）配送中心及客户点位置已知，且中心拥有不同车型车辆。

2）不考虑配送车辆中途返回配送中心，配送车辆自出发直至返回配送中心即为一次服务完成。

3）客户的时间窗和取送货量信息均已知。

4）节点位于不同的高度，即车辆在节点间行驶时需考虑坡度影响。

5）客户取送货需求不可拆分，即每个客户只允许一辆配送车为其进行配货和取货服务，且服务总量应在配送车辆的最大载质量以内。

1.3 参数说明

2 模型构建

2.1 道路坡度的影响

道路坡度定义为高程变化与水平距离的比值[12]，准确的道路坡度是现实路网中不可忽视的一个重要因素，在许多方面可以促进与交通相关的研究，但在研究分析中通常会被忽略，导致车辆在燃油经济性和污染排放中的研究不够全面。研究表明，车辆总质量和道路坡度是影响车辆动力系统的2个重要因素。随着道路坡度的增加，燃油消耗和尾气排放都在增加，就平均而言，与平坦路面相比，在坡度等级为1%的路面上油耗增加了15%，而在坡度等级为6%的路面上油耗大约增加了1倍。在观察完整路线时，研究发现，与平坦路线相比，丘陵路线的消耗增加了15%～20%。同时车辆质量的改变，油耗成本也会改变10%左右。因此路线的选择是车辆类型和道路坡度的共同作用[11]。本文通过引入坡度函数[13]以考虑高度变化对油耗成本的影响，公式见式（1）。

2.2 成本分析

1）油耗成本。在现实路网中，道路不可能总是处在同一高度上，因此导致了配送网络具有不对称的特征。本文在油耗模型中引入坡度函数，采用Brunner等[11]提出的改进的车辆油耗模型，具体如下：其认为单位时间的燃料消耗函数可近似表示为式（2）。

后者产生的碳排放量近似看作与时间呈正线性相关[14]，见式（7）。

式中：为制冷设备消耗每单位体积油耗时产生的碳排放量。为排放每单位体积二氧化碳需要支付的碳税，则碳排放成本见式（8）。

3）货损成本。不论道路坡度如何变化，本文运输的生鲜产品的货损都是不可避免且不可逆的，且其只与时间相关，参考文献[15]有：

前者为运输过程中造成的货损成本，后者为卸货过程中造成的货损成本。

2.3 数学模型

目标函数：

约束条件：

目标函数依次为车辆使用成本、油耗成本、碳排放成本、货损成本及时间惩罚成本。式（11）表示车辆行驶距离不超过其自身最大行驶距离的限制；式（12）表示不允许车辆在各配送中心之间直接行驶；式（13）表示车辆最终停留在配送中心；式（14）表示节点处车辆进出平衡，即车辆到达客户点服务完成后必须从客户点处离开；式（15）表示客户取送货需求不可拆分，每个客户点只能由类型的车辆进行服务；式（16）表示配送区域内的客户都被访问到且仅访问一次；式（17）表示车辆在访问后的装载量仍不能超过车最大载质量限制；式（18）表示车辆必须在客户最大限度接受服务时间窗内进行配送任务；式（19）表示消除子回路；式（20）—（22）表示决策变量取值范围。

3 算法设计

本文研究的问题是VRP变种问题，文中所构建的模型是在传统VRP模型的基础上进行的扩展和延伸，因此其求解原理与方法是一致的，属于NP–Hard问题。启发式算法在求解这类问题时具有明显的优越性，遗传算法具有鲁棒性强、并行性高和搜索能力强的特点，但收敛速度慢且容易陷入局部最优，不能保证整体最优[16]。为改进该缺陷，本文设计了一种改进的遗传算法对模型进行求解，并在此基础上采用时空相似测度对节点进行分组和聚类，从而提高初始种群的质量，更好地提升算法的求解效率。综上，本文通过结合模型特点设计了一种基于K–means多维时空聚类的改进遗传算法并对其进行求解。

3.1 K–means多维时空聚类算法

3.2 基于K–means多维时空聚类的改进遗传算法

1）初始种群的产生。首先用式（24）对全客户进行聚类簇划分，每个聚类簇的初始路径构造步骤如图1所示。

2）适应度函数。本文是求解配送成本最小化的问题，因此将目标函数的倒数作为适应度函数。

3）交叉、变异操作。本文选择改进的双切点交叉方法作为交叉算子，两点互换法作为变异算子。与传统两点交叉法不同的是将互换的基因序列放到对方个体的最前方，并依次删除原个体中与互换后的交叉区域内相同的基因。

4）进化逆转操作。为提高算法的局部搜索能力，在交叉、变异操作后引入连续多次的进化逆转操作，但该操作只能朝着目标值更优的方向进行。

5）2–OPT顺序扰动策略。为避免算法早熟而陷入局部最优解，本文引入顺序扰动策略，对当前的不同线路的解进行拆分重构。若不符合多约束要求，则重新进行扰动操作，直至满足约束要求，如图2所示。

图1 初始种群生成步骤

图2 2–OPT顺序扰动操作

4 算例验证与结果分析

4.1 算例描述

本文采用文献[17]的方法生成算例，共有3家冷链中心为52名客户进行服务，有A1，A22种车型可指派，载质量分别为3 000、5 000 kg，发车费用分别为300、400元。其余各车辆配置均统一。此外，其余部分数据参考表1。

算法采用Matlab2022b进行实验，并在操作系统为Windows10、电脑内存为8GB、CPU为Inter(R)Core (TM)i5–6200U、主频率为2.30GHz的电脑上实现。经测试，算法参数设置如下：种群规模为100、最大迭代次数为300、交叉概率为0.5、变异概率为0.03。

4.2 结果分析

本文采用基于K–means多维时空聚类的改进遗传算法对4.1节中的算例进行求解。为使结果稳定，算法运行10次，平均运行时间为73.63 s。从表2可知，其最优配送方案总花费为20 228.3元，使用配送车辆6辆；最差配送方案总花费21 539.7元，使用配送车辆7辆；10次运行结果平均值为20 885.3元，最优解偏差为2.99%，最差解偏差为3.04%。图3是最优配送方案的迭代趋势，可以看出，本研究中使用的方法能够稳定地收敛到最优解，且求解运行时间可接受。

表1 参数设置

Tab.1 Parameter setting

表2 算例求解结果

Tab.2 Solution result of numerical example

图3 最优配送结果迭代

图4a是表1中最优配送方案的车辆行驶路径图，其俯视图如图4b所示。表3列举了图4b对应的车辆行驶最优路径。

4.3 对比分析

为验证道路坡度对配送路径和车型选择的影响，本研究将道路坡度前期考虑在成本计算中和后期加入成本计算中进行对比分析，并引入新型冷藏车A3。A3的载质量为8 000 kg，发车费用为500元，其余配置与前文统一。前者计算方法与前文一致，后者计算方法如下：首先采用上述算法求解出该算例在同一高度即对称下的配送方案并记录，然后将该方案不变，通过计算得出其在不同高度下即非对称下的成本。为使结果稳定，算法运行10次，结果如表4所示。

图4 车辆行驶最优路径

表3 最优配送方案路线

Tab.3 Route of optimal distribution scheme

由表4可知，前期将道路坡度考虑在成本计算中（即非对称下），最佳配送方案总成本为21 603.1元，最优配送方案如表5所示，其平均配送成本为22 109.7元；而在后期将道路坡度加到成本计算中（即对称下），最优配送方案总成本为23 761.4元，最优配送方案如表5所示，其平均配送成本为24 583.2元。对比可知，配送成本平均降低了9.58%。

综合表4、表5可以得出，非对称情况下配送方案更倾向于安排A1、A2车型的选择，而较少安排A3车型的派发，其目的是减少大型车辆因频繁爬坡而造成的额外成本增加。但对称情况下不存在此目的，因此更倾向于将大型车辆参与到派送中。成本的增加在一定程度上说明了模型的不适用性，特别是针对一些山地城市，若长期采用此类模型，不仅会造成短期的效益低下，而且不利于企业的长期发展。综上，将道路坡度直接考虑在模型内的求解调度方案，对企业在现实路网中的配送路线和车辆类型的选择有更大的帮助，其可有效降低配送成本，是物流中心降低营运成本的重要改进措施。

表4 运行10次的算例结果

Tab.4 Results of numerical examples running for 10 times

表5 非对称与对称下的最优配送方案路线

Tab.5 Route of optimal distribution scheme under asymmetry and symmetry

5 结语

针对目前冷链物流研究所存在因缺少考虑实际路网的道路坡度而造成配送方案在城市实际调度中增加成本和车辆安排不合理等问题，本文在考虑道路坡度对油耗、碳排放和车辆行驶路径影响的基础上，综合考虑了多中心开放、多车型、客户具备取送货需求及软时间窗等多种现实约束。建立了以配送总成本最小为目标的优化模型，并设计了一种基于K–means多维时空聚类的改进遗传算法对模型进行研究和求解。结果表明，若冷链中心将道路坡度作为一个影响成本的因素考虑在车辆路径安排和车型选择时，其能够采用更加符合现实路网和城市特点的模型，从而有效降低冷链中心的配送成本，也可有效避免大型车辆安排不合理的现象即减少大型车辆在过度爬坡中造成的油耗浪费和对环境的污染。同时，在配送路线的选择上，也对大型车辆在重载时的行驶路线给出建议，即应减少其在行驶过程中海拔的突然变化，可选择在卸载一部分货物后改变至更高的高度。

本文丰富了现有的冷链产品配送模型，为建立更加贴合实际调度的路径规划提供了理论基础和实践指导，并对有明显道路坡度的城市，如我国的重庆、大连等地区的冷链产品配送提供了现实的借鉴意义。未来在研究道路坡度影响冷链配送问题中，在模型方面，可将建立更加准确的坡度函数模型、更加细致地划分节点间路径状况作为研究内容，以便模型能更贴合实际调度应用。

[1] 宋寒业. 冷链物流成行业新风口[N]. 中华工商时报, 2021, 15(004).

SONG Han-ye. Cold Chain Logistics Has Become a New Wind in the Industry[N]. China Business Times, 2021, 15(004).

[2] HOCHFELDER B. What Retailers can do to Make the Last Mile More Efficient[N/OL]. Supply Chain News And Analysis, 2017-05-22.https://www.supplychaindive. com

[3] PSYCHAS I D, MARINAKI M, MARINAKIS Y, et al. Non-Dominated Sorting Differential Evolution Algorithm for the Minimization of Route Based Fuel Consumption Multi-Objective Vehicle Routing Problems[J]. Energy Systems, 2017, 8: 785-814.

[4] ZHANG Jiang-hua, ZHAO Ying-xue, XUE Wei-li, et al. Vehicle Routing Problem with Fuel Consumption and Carbon Emission[J]. International Journal of Production Economics, 2015, 170: 234-242.

[5] 康凯, 韩杰, 普玮, 等. 生鲜农产品冷链物流低碳配送路径优化研究[J]. 计算机工程与应用, 2019, 55(2): 259-265.

KANG Kai, HAN Jie, PU Wei, et al. Optimization Research on ColdChain Distribution RoutesConsideringCarbonEmissionsfor Fresh Agricultural Products[J]. Computer Engineering and Applications, 2019, 55(2): 259-265.

[6] 狄卫民, 杜慧莉, 张鹏阁. 考虑动态拥堵的多车型绿色车辆路径问题优化[J]. 计算机工程与设计, 2021, 42(9): 2614-2620.

DI Wei-min, DU Hui-li, ZHANG Peng-ge. Optimization of MultiVehicle Green Vehicle Routing Problem Considering Dynamic Congestion[J].Computer Engineering and Design, 2021, 42(9): 2614-2620.

[7] 刘长石, 王松, 罗亮, 邓胜前. 时变路网条件下联合配送的开放式车辆路径问题[J]. 运筹与管理, 2021, 30(11): 26-33.

LIU Chang-shi, WANG Song, LUO Liang, et al. Open Vehicle Routing Problem for Joint Distribution under Time-VaryingRoad Network[J]. Operations Research and Management, 2021, 30(11): 26-33.

[8] JOUBERT J W. Multi-Agent Model of Route Choice When Vehicles are Sensitive to Road Grade[J]. Procedia Computer Science, 2017, 109: 869-874.

[9] LAJEVARDI S M, AXSEN J, CRAWFORD C. Examining the Role of Natural Gas and Advanced Vehicle Technologies in Mitigating CO2Emissions of Heavy- Duty Trucks: Modeling Prototypical British Columbia Routes with Road Grades[J]. Transportation Research Part D: Transport and Environment, 2018, 62: 186-211.

[10] RITTER A, WIDMER F, VETTERLI B, et al. Optimization-Based Online Estimation of Vehicle Mass and Road Grade: Theoretical Analysis and Experimental Validation[J]. Mechatronics, 2021, 80: 1-10.

[11] BRUNNER C, GIESEN R, KLAPP M A, et al. Vehicle Routing Problem with Steep Roads[J]. Transportation Research Part A: Policy and Practice, 2021, 151(6): 1-17.

[12] FAN Peng-fei, SONG Guo-hua, ZHU Zi-jun, et al. Road Grade Estimation Based on Large-Scale Fuel Consumption Data of Connected Vehicles[J]. Transportation Research Part D: Transport and Environment, 2022, 106: 103262.

[13] 饶卫振, 金淳, 王新华, 等. 考虑道路坡度因素的低碳VRP问题模型与求解策略[J]. 系统工程理论与实践, 2014, 34(8): 2092-2105.

RAO Wei-zhen, JIN Chun, WANG Xin-hua, et al. A Model of Low-Carbon Vehicle Routing Problem Considering Road Gradient and Its Solving Strategy[J]. SystemsEngineering-Theory & Practice, 2014, 34(8): 2092-2105.

[14] 肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 2022, 42(9): 2926-2935.

XIAO Zhi-hao, HU Zhi-hua, ZHU Lin. A Hybrid Adaptive Large Neighborhood Search Algorithm for TimeDependent Vehicle Routing Problem in Cold Chain Logistics[J]. Computer Application, 2022, 42(9): 2926-2935.

[15] WANG X, WANG M, RUAN J, et al. The Multi-Objective Optimization for Perishable Food Distribution Route Considering Temporal-Spatial Distance[J]. Procedia Computer Science, 2016, 96: 1211-1220.

[16] 范厚明, 田攀俊, 吕迎春, 等. 时变路网下考虑时空距离的同时配集货车辆路径优化[J]. 系统管理学报, 2022, 31(1): 16-26.

FAN Hou-ming, TIAN Pan-jun, LYU Ying-chun, et al. Vehicle Routing Problem with Simultaneous Delivery and Pickup Considering Temporal-Spatial Distance in Time- Dependent Road Network[J]. Journal of Systems & Management, 2022, 31(1): 16-26.

[17] ZHOU J, LEE M. A Lagrangian Relaxation-Based Solution Method for a Green Vehicle Routing Problem to Minimize Greenhouse Gas Emissions[J]. Sustainability, 2017, 9: 776.

Research on Multi Constraint Cold Chain Distribution Problem Considering the Effect of Road Slope

MIN De-quan, SUN Xiao-na, LI Yu-hang, JIANG Ke-jian

(College of Transportation Engineering, Dalian Maritime University, Liaoning Dalian 116026, China)

In order to solve the problem that the traditional cold chain VRP defaults the distribution area to a two-dimensional plane, which makes the actual scheduling different from the ideal state and causes the distribution cost to increase, the work aims to make an in-depth research on related problems, aiming at rationally planning the allocation of resources and improving the economic benefits of enterprises. The fuel consumption cost and carbon emission cost were calculated by introducing the slope function, and various realistic constraints such as three-dimensional space location, multiple models, load changes, customer's pickup and delivery requirements, and time window requirements were comprehensively considered. The improved genetic algorithm of K-means multi-dimensional spatiotemporal clustering was solved. The solution results indicated that if the road slope was initially considered in the cost calculation, the distribution cost could be effectively reduced by 9.58%. At the same time, large vehicles should avoid sudden altitude changes when heavily loaded. When the altitude changed, large vehicles could change to a higher altitude after some goods were unloaded. The model studied is closer to the actual road network and has higher applicability, especially for the distribution of cold chain products in cities with obvious road slopes, which has practical reference significance.

road slope; multi constraint; cold chain distribution; K-means multi-dimensional spatiotemporal clustering; improved genetic algorithm

TB485.3；U492.2+2

A

1001-3563(2023)13-0236-09

10.19554/j.cnki.1001-3563.2023.13.028

2022−11−25

国家社科基金（18VHQ005）

闵德权（1963—），男，硕士，教授，主要研究方向为旅游管理、交通运输规划与管理。

责任编辑：曾钰婵