考虑客户满意度的带时间窗的多中心半开放式冷链物流车辆路径优化

江雨燕，尹莉，王付宇

考虑客户满意度的带时间窗的多中心半开放式冷链物流车辆路径优化

江雨燕，尹莉，王付宇

（安徽工业大学 管理科学与工程学院，安徽 马鞍山 243002）

针对带时间窗的多中心半开放式车辆路径问题，以总配送成本最小化和客户满意度最大化为目标，提出了双目标冷链物流路径优化模型。针对NSGA-II算法容易陷入局部最优等缺点，结合粒子群算法生成种群方式，设计一种改进的NSGA-II算法。通过仿真对比实验，结果表明，所提出的算法和模型可有效解决带时间窗的多中心半开放式冷链物流车辆路径优化问题，且改进算法性能更优，同时分析了总配送成本与客户满意度之间的关系，为冷链物流企业带来一定的管理启示。

冷链物流；路径优化；带时间窗的多中心半开放式车辆路径问题；改进的NSGA-II算法

近年来，人们对生鲜品的需求不断上升，冷链物流行业发展较为迅速。同时，广大居民越来越重视物流服务的质量，比如产品是否损坏，是否按时送达。因此，如何在降低配送成本的同时提高客户满意度，这对冷链物流配送企业的长远发展是十分重要的。

国内学者对冷链车辆路径问题做了大量的研究。HSIAO等[1]设计了生鲜产品冷链物流配送模型，并采用了遗传算法对其求解。CHEN等[2]从低碳经济的角度提出了一个依赖时间的绿色车辆路径问题以及一种计算制冷成本的新思路。FAN等[3]进行了基于“互联网+”的农产品冷链物流系统规划，并给出了冷链系统优化建议。康凯等[4]综合分析了冷链物流配送中的各种成本，以配送总成本最小为目标建立了冷链物流配送模型。李倩等[5]在冷链配送路径优化模型加入了客户满意度函数，并改进了非支配排序遗传算法（non-dominated sorting genetic algorithm，NSGA-II）。任腾等[6]以碳排放量最小为目标，建立了冷链车辆路径优化模型，并改进了传统蚁群算法。丁秋雷等[7]在农产品冷链物流配送受扰恢复模型中考虑了农产品新鲜度和配送时间。这些文献研究的冷链物流VRP模型主要是一个配送中心，对多配送中心的冷链物流车辆路径优化的研究不足。

目前，大中型城市的物流配送系统中普遍存在多个配送中心，在多配送中心的路径优化问题（multi-depot vehicle routing problem，MDVRP）研究方面，SALHI等[8]研究了异构车辆的多配送中心路径问题，并提出了一种有效的可变邻域搜索实现方法。DIAO等[9]研究了无最大时间窗的模糊时间窗多车场开放式车辆路径问题，并采用混合遗传算法求解。带时间窗的MDVRP（multi-depot vehicle routing problem with time windows，MDVRPTW）是MDVRP的一个拓展问题。浦徐进等[11]针对“同日达”物流配送中的承诺送达机制，建立多目标多配送站“同日达”配送路径优化模型，并提出一种改进后的人工蜂群算法进行求解。针对车辆路径是否为闭环，又可分为封闭式车辆路径问题和开放式车辆路径问题（open vehicle routing problem，OVRP），在OVRP中，又包含半开放式车辆路径问题（half open vehicle routing problem，HOVRP），其特点为车辆将货物送达客户后可就近驶回任一配送中心，李延辉等[12]在开放式多车场VRP中提出了沿途补货策略，并设计了蚁群算法求解该模型。范厚明等[13]在多中心开放式车辆路径问题中考虑了同时配集货和需求可拆分，创建了以配送成本最小为目标的车辆路径优化模型。这些文献主要关注的是闭合式多配送中心车辆路径问题，而在冷链物流车辆路径问题中考虑半开放式多配送中心的研究成果相对较少。此外，现有研究中采用多目标优化算法求解冷链物流车辆路径问题的文献较为匮乏。

综上所述，本文以带时间窗的多中心半开放式车辆路径问题（multi-depot half open vehicle routing problem with time windows，MDHOVRPTW）为研究对象，在冷链物流配送中，建立考虑客户满意度的MDHOVRPTW模型，使得冷链车辆路径问题更具有研究意义，并针对该问题模型，采用改进的带精英策略的非支配排序遗传算法（Improved non-dominated sorting genetic algorithm，INSGA-II）求出满足决策者不同要求的配送方案，并通过对比实验证明改进算法求解模型的有效性。

1 问题描述与模型构建

1.1 问题描述与假设

问题假设：（1）配送中心不存在冷藏车辆不够使用的情况；（2）已知车辆的最大载重量等信息，且只有一种车型；（3）车辆将货物送达客户后可以到最近的配送中心添加货物，继续为下一客户提供配送服务；（4）车辆的行驶速度全程保持不变；（5）配送中心和需求点的信息是提前知道的；（6）每个客户仅由一辆车配送一次；（7）不考虑配送中心的建设或使用成本；（8）驾驶员24小时内驾驶时间不超过8小时。

1.2 符号定义

相关参数定义如表1所示。

1.3 目标函数设计

（1）假设每辆车的固定成本相同，则固定成本计算如下：

（2）运输成本计算公式如下：

（3）货损成本计算如下：

（4）制冷成本是由以下两种能源消耗成本组成：

表1 变量说明

（5）如果配送时间不能满足客户期望的时间窗，则产生的罚款成本计算如下：

图1 客户满意度

1.4 建立模型

通过以上分析，本文构建考虑客户满意度的MDHOVRPTW优化模型，其中为了算法在求解过程中计算方向统一，将客户满意度取负值变为求最小，因此，数学模型表示如下：

目标函数：

约束条件：

其中，式(14)表示车辆的载重限制；式(15)表示配送中心的车辆总数与该配送中心提供服务的车辆数之间的关系；式(16)和式(17)含义为每个客户只有一辆车提供配送；式(18)含义为车辆满载出发，它是式(19),(20)及式(21)的基础；式(19)表示车辆的载货量要满足每个客户的需求量；式(20)表示车辆通过客户时运输量发生变化的关系式；式(21)表示车辆进入配送中心添加货物量的条件；式(22)是为了防止车辆从一个配送中心到另一个配送中心；式(23)表示车辆完成配送服务后可就近返回任一配送中心；式(24)表明交付过程是连续的。

2 INSGA-II算法设计

算法流程如图2所示。

图2 INSGA-II算法流程

2.1 编码及初始种群的生成

2.2 适应度函数

适应度函数通常是将目标函数做一些数学变换得到，本文将目标函数值的倒数作为适应度函数。

2.3 遗传操作

（1）选择算子

为了提高解集的分布性，在选择操作时引入概率操作。在种群进化前期，以较大概率排除当前选出的最优个体进而选择其他个体，在种群进化末期，以较小的概率排除当前选出的最优个体。概率操作的计算公式为

（2）交叉算子

交叉算子选择部分匹配交叉（Partially-matched crossover，PMX），其保证了在一个染色体中没有重复的基因，PMX示例如图3所示。

图3 部分匹配交叉

（3）变异算子

2.4 子代种群生成方式

为了提高NSGA-II进化的方向性和适应性，扩大搜索空间，具体操作如下：在利用NSGA-II算法合并新父种群后，NSGA-II算法经过一系列操作后，生成子代种群1，同时，利用粒子群算法的更新种群方式生成子代种群2，最后将两个子代种群合并，执行下一步操作。

2.5 算法性能评估

为了评价改进算法的收敛性与多样性，通过多目标测试函数进行算法对比。如图4～7所示，在测试函数ZDT1、ZDT2、ZDT3及ZDT4中，INSGA-II的近似解比其他算法更靠近真实的Pareto前沿面，表明改进的NSGA-II算法收敛性较为良好。

此外，4种算法分别在迭代次数为50和100时独立运行20次，将超体积指标HV以及反转世代距离IGD的结果值进行平均，从表2中可以看出，INSGA-II算法的HV指标基本高于MOEAD、NSGA-II以及MOPSO，表明INSGA-II求解得到的Pareto解集能够较好地收敛到理想的Pareto前沿面。同时，从表3中可以看出，改进后的NSGA-II算法的IGD指标低于其他算法，表明INSGA-II算法的收敛性与多样性较为良好。

图4 4种算法在ZDT1测试函数的Pareto前沿

图5 4种算法在ZDT2测试函数的Pareto前沿

图6 4种算法在ZDT3测试函数的Pareto前沿

图7 4种算法在ZDT4测试函数的Pareto前沿

表2 HV对比结果

表3 IGD性能对比结果

3 算例验证及分析

3.1 算例设计

表4 配送中心信息

表5 客户相关信息

表6 模型相关参数信息

3.2 算例结果

程序使用MATLAB R2016b编写，并在Intel(R) Core(TM) i5-7200U CPU 2.50GHz的DELL 笔记本电脑（4核，8GB内存）上运行。基于前文企业案例数据，并采用INSGA-II算法求解模型，独立运行50次，INSGA-II算法参数设置如表7所示。

表7 INSGA-II算法参数设置表

图8是INSGA-II求解考虑客户满意度的MDHOVRPTW模型初始迭代收敛结果，图8中五角星表示当前搜索的最优解，空心圆表示新生成的解。为了更好地观察非支配解的分布，绘制Pareto最优解集的图像，如图9所示，可以看出当其中一个解变好时，另一个解会变差，这说明解集中的所有解互不支配，设计的算法求解得出的最优解是可靠的。

图8 初始迭代Pareto解集

图9 最终Pareto解集

经过迭代，算法得到的Pareto解集中的每个解没有好坏之分，决策者可以根据实际情况或偏好选择不同侧重的解作为最终的配送方案。本文从帕累托最优解集中选择5个方案，各个方案的目标值如表8所示，其中方案一为随机方案，方案二为配送成本最低方案，方案三为满意度最高方案，方案四为模糊方案（折中解）。仅选择方案三的Pareto解进行展示。图10为方案三的配送路径，表9为方案三的车辆配送客户行驶路径顺序，共有9辆车辆，对应9条行驶路径的甘特图如图11所示，企业可根据甘特图进行调度和配送。同时，实验结果也说明了本文所设计的INSGA-II算法能够解决MDHOVRPTW，并且取得较好的结果。

表8 各方案目标值

图10 方案三配送路径

表9 方案三车辆行驶路径

图11 甘特图

3.3 对比分析

一方面，随着人民日益增长的美好生活需要，消费者更加注重物流配送的时间要求和产品质量体验。另一方面，物流行业竞争日益激烈，生鲜冷链企业在货物配送过程中所关心的不仅是怎样的车辆行驶路径使得配送成本最低，更为重要的是提高客户对配送服务的满意度。

为验证本文算法求解模型的有效性，分别采用MOPSO、NSGA-II、MOEAD和INSGA-II算法求解了客户规模不同下的配送方案。4种算法优化的帕累托解集分别如图12～15所示，在4种客户规模下，INSGA-II形成的Pareto前沿面较为明显，说明改进的算法（INSGA-II）具有较好的收敛性，能够有效求解考虑客户满意度的MDHOVRPTW模型。

每种客户规模下的4种算法优化的折中解如表10所示。由表10可知，与MOPSO相比，用INSGA-II算法不仅计算得到的配送成本基本不高于MOPSO求解结果，而且客户满意度也几乎不低于MOPSO求解结果，当客户规模为60时求解质量较高；与NSGA-II相比，当客户规模较小时，用INSGA-II计算得到的配送成本和客户满意度均优于NSGA-II计算得到的结果，但当客户规模较大时，NSGA-II求解质量较高；与MOEAD相比，在客户规模为45时，用INSGA-II计算得到的配送成本略高于MOEAD计算的配送成本，但INSGA-II客户满意度73%明显高于MOEAD求解的客户满意度62%，其他规模下配送成本和客户满意度均优于MOEAD计算得到的结果。综合上述分析，INSGA-II算法能够较好的求解本文模型。

图12 客户数量30时的4种算法的帕累托解集

图13 客户数量45时的4种算法的帕累托解集

图14 客户数量60时的4种算法的帕累托解集

图15 客户数量90时的4种算法的帕累托解集

表10 不同案例规模下4种算法对比

为了探索模型的适用性，将本文提出的考虑客户满意度的MDHOVRPTW模型与不考虑客户满意度的MDHOVRPTW模型在不同客户规模下的较优解对比，采用INSGA-II算法对考虑客户满意度的MDHOVRPTW模型进行求解，利用传统遗传算法对不考虑客户满意度的MDHOVRPTW模型进行求解，结果如表11所示。

表11 两种模型结果对比

由表11可得出结论：（1）在4组对比数据中，与不考虑客户满意度的MDHOVRPTW配送方案相比，在客户规模为30时，考虑客户满意度的MDHOVRPTW配送方案的优化效果有待提高；但在其他规模下，虽然考虑客户满意度的MDHOVRPTW方案的配送成本略高，这是因为车辆为了满足客户时间窗，可能会绕过距离较近的客户而选择优先配送距离稍远的客户，这就导致总配送成本增加，但考虑客户满意度的MDHOVRPTW方案的客户满意度较高，这说明在成本可以接受的前提下，冷链物流企业采用考虑客户满意度的MDHOVRPTW方案可以提高服务质量，有利于企业长期良好发展。（2）在客户规模为45、60、90时，客户满意度的MDHOVRPTW策略的配送成本比不考虑客户满意度的MDHOVRPTW策略分别高于10.92%、2.55%、2.15%，但是客户满意度分别高于7.4%、6.35%、5.08%，在客户规模为45时，客户满意度的优化效果最好。（3）在不考虑客户满意度的MDHOVRPTW策略中，随着客户规模的增加，客户满意度越来越低，这是由于不考虑客户满意度层面，导致车辆没有在客户期待的时间窗内将货物送达。因此，冷链配送公司不仅要注重配送成本的降低，也要着力于提高客户满意度，只有这样，企业才能在激烈的市场竞争中稳步发展。

4 结束语

随着物流行业竞争的日益激烈，冷链物流企业越来越重视客户对配送服务的满意度。本文在冷链物流配送中建立了考虑客户满意度和配送成本的MDHOVRPTW模型，并设计了INSGA-II算法，最后通过仿真实验对比分析，验证了模型和算法的有效性，同时提出生鲜配送企业在成本可接受的前提下，考虑客户满意度有利于企业长期发展的结论。该研究可为生鲜冷链配送提供重要的决策参考价值。

本文建立的冷链配送模型中，虽然考虑了多配送中心以及半开放式的配送特点，但仍然忽略了在实际配送过程中，生鲜企业可能会派出不同类型的冷藏配送车辆，因此未来研究工作可以在本研究提出的模型基础上，考虑异型车辆，使研究的问题更符合实际。此外，本文对NSGA-II算法做了改进，虽然在实验结果上比其他算法有着优异的表现，但是忽略了算法的运行速度，在下一步研究中，设计出更加高效的启发式算法，提高算法运行速度。

[1] HSIAO Y H, CHEN M C, CHIN C L. Distribution planning for perishable foods in cold chains with quality concerns: formulation and solution procedure[J]. Trends in Food Science & Technology, 2017, 61: 80-93.

[2] CHEN J, LIAO W, YU C. Route optimization for cold chain logistics of front warehouses based on traffic congestion and carbon emission[J]. Computers & Industrial Engineering, 2021, 161(1): 1-16.

[3] FAN Y, LI H. Research on cold chain logistics operation mode under internet technology[J]. Journal of Physics: Conference Series, 2021, 1972(1): 1-8.

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

[5] 李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用，2021, 57(23): 255-262.

[6] 任腾，陈玥，向迎春，等. 考虑客户满意度的低碳冷链车辆路径优化[J]. 计算机集成制造系统，2020, 26(04): 1108-1117.

[7] 丁秋雷，胡祥培，姜洋，等. 考虑新鲜度的农产品冷链物流配送受扰恢复模型[J]. 系统工程理论与实践，2021, 41(03): 667-677.

[8] SALHI S, IMRAN A, WASSAN N A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation[J]. Computers & Operations Research, 2014, 52(PB): 315-325.

[9] DIAO X , FAN H , REN X , et al. Multi-depot open vehicle routing problem with fuzzy time windows[J]. Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, 2021(1): 40.

[10] SINGH V, GANAPATHY L, PUNDIR A K. An improved genetic algorithm for solving multi depot vehicle routing problems[M]. International Journal of Information Systems and Supply Chain Management (IJISSCM), 2019, 12(4): 1-26.

[11] 浦徐进，李秀峰，付亚平. 基于电商承诺送达机制的低碳“同日达”配送路径规划[J]. 系统工程，2018, 36(12): 47-57.

[12] 李延晖，刘向. 沿途补货的多车场开放式车辆路径问题及蚁群算法[J]. 计算机集成制造系统，2008, 14(03): 557-562.

[13] 范厚明，张轩，任晓雪，等. 多中心开放且需求可拆分的VRPSDP问题优化[J]. 系统工程理论与实践，2021, 41(06):1521-1534.

[14] 张建勇，郭耀煌，李军. 基于顾客满意度的多目标模糊车辆优化调度问题研究[J]. 铁道学报，2003(02): 15-17.

[15] LIU G, HU J, YANG Y, et al. Vehicle routing problem in cold chain logistics: a joint distribution model with carbon trading mechanisms[J]. Resources Conservation and Recycling, 2020, 156: 1-13.

[16] 范厚明，杨翔，李荡，等. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J]. 计算机集成制造系统，2019, 25(01): 256-266.

Multi-depot half-open cold chain logistics vehicle routing optimization with time window considering customer satisfaction

JIANG Yu-yan，YIN Li，WANG Fu-yu

(School of Management Science and Engineering, Anhui University of Technology, Anhui Maanshan 243002, China)

Aiming at the multi-depot half-open vehicle routing problem with time window, a dual-objective cold chain logistics routing optimization model was proposed to minimize the total distribution cost and maximize customer satisfaction. Aiming at the shortcoming that NSGA-II algorithm is easy to fall into local optimum, an improved NSGA-II algorithm is designed by combining the population generation method of particle swarm optimization algorithm. Through simulation experiments, the results show that the proposed algorithm and the model can effectively solve the multicenter ajar cold-chain logistics with time windows vehicle routing optimization problem, and the improved algorithm has better performance, at the same time analyzed the total distribution cost and the relationship between customer satisfaction, for the cold chain logistics enterprise management implications.

cold chain logistics；path optimization；multi-depot half-open vehicle routing problem with time window；improved NSGA-II algorithm

U116.2

A

1007-984X(2023)03-0074-12

2022-09-07

国家自然科学基金“基于行为运筹的灾后伤员救援车辆及手术调度优化研究”（71872002）

江雨燕（1966-），女，安徽宣城人，教授，主要从事智能计算研究，jyy@ahut.edu.cn。