基于有限调整的城市冷链物流配送优化

Limited Adjustment-Based Optimization of Distribution in Urban Cold Chain Logistics

摘要: 本研究基于有限调整的城市冷链物流配送路线优化问题，旨在最小化总配送距离，同时满足客户多样化的货物需求。研究问题涉及将客户分配到不同配送路线上，并确定每条路线上的配送顺序，需考虑实际约束条件，包括车辆常温和冷藏货物的容量限制、重量限制，以及时间窗约束。有限调整指强调初始路线的稳定性，对初始线路改动不宜过大。针对该问题，本文构建混合整数规划模型以描述目标和约束，并根据问题特征设计了求解方法框架。求解方法包括两部分，一是优化可行路线的配送顺序和通过节点剔除与重新插入修复不可行路线，以确保所有路线可行；二是通过取消客户节点较少且货物总重较低的路线并将其节点重新分配，优化配送路线数量，以减少车辆使用。数值实验验证了该方法的有效性，证明其能够优化配送路线。本文所提方法为冷链物流企业提升效率和适应性提供了实用工具。

Abstract: This paper investigates the limited adjustment-based urban cold chain logistics distribution route optimization problem, which aims to minimize the total distribution distance while satisfying the diverse demands of customers for goods. The research problem involves assigning customers to different distribution routes and determining the distribution sequence on each route, which requires consideration of practical constraints, including capacity limitations of vehicles for ambient and refrigerated goods, weight limitations, and time window constraints. Limited adjustment means emphasizing the stability of the initial routes, and the changes to the initial routes should not be too significant. To address the problem, this paper constructs a mixed-integer programming model to describe the objectives and constraints, and designs a solution method framework for the problem characteristics. The solution method consists of two parts: one is to optimize the distribution sequence of feasible routes and repair infeasible routes by node elimination and reinsertion to ensure that all routes are feasible; the other is to optimize the number of distribution routes by eliminating the routes with fewer customer nodes and lower total weight of goods and redistributing their nodes in order to reduce the use of vehicles. Numerical experiments verify the effectiveness of the method and prove that it can optimize distribution routes. The method proposed in this paper provides a practical tool for cold chain logistics companies to improve efficiency and adaptability.

1. 引言

冷链物流作为城市供应链的重要组成部分，负责确保食品、医药等易腐货物在运输过程中的质量安全与及时配送[1] [2]。随着城市化进程的加速和消费者对配送服务效率与可靠性的需求不断提升，冷链物流企业面临多重挑战，包括满足多样化的客户需求，比如常温和冷藏货物的混合运输、配送时间窗限制、车辆容量约束[1]-[4]。这些因素显著增加了配送路线规划的复杂性，要求企业在控制运营成本和提升客户满意度目标之间寻求平衡[5]。因此，针对冷链物流的车辆路径问题(Vehicle Routing Problem, VRP)成为学术界和工业界的研究热点，其优化结果直接影响企业的经济效益和市场竞争力[6] [7]。

本文聚焦于一家城市冷链物流企业面临的配送优化问题，研究目标是在有限调整的现实约束下，最小化总配送距离以及减少配送路线数量。该企业运营一支统一类型的冷链运输车队，以多温共配模式运营，即每辆车能够同时运输常温和冷藏货物，以满足客户的差异化需求[8] [9]。研究问题涉及的主要决策包括将客户分配到不同的配送路线并确定每条路线上的最优配送顺序。与传统VRP问题相比，本研究特别强调对现有路线分配的有限调整，以确保运营稳定性。有限调整是指尽量减少对初始路线改动的现实约束，这是因为现有配送路线一般由固定配送人员负责，负责某路线的配送人员对该路线上的交通情况以及客户节点信息比较熟悉，在北京、上海等国际大都市中，交通情况非常复杂，在客户节点处装卸货的位置和时间要求都比较高，增加这一现实约束可以大大节约配送时间。因此，有限调整反映了现实中保持客户与司机关系一致性、维护配送计划可预测性以及降低运营扰动的实际需求。由于客户每日需求的不确定性，该城市冷链物流企业需要每日对配送路线进行调整，剔除出不可行路线中的部分客户节点使得路线可行、拆分客户节点少且货物量少的路线以减少车辆使用，以及在最小化配送距离目标下对所有配送路线进行优化。

为解决该问题，本文构建了一个混合整数规划(Mixed Integer Programming, MIP)模型，系统描述了目标函数和约束条件，为优化提供理论基础。关于冷链物流VRP问题的求解方法，由于VRP问题的计算复杂，精确算法难以有效处理大规模问题，部分研究使用启发式方法或混合方法解决此类问题[10] [11]。考虑到问题的计算复杂性，本文提出了一种两阶段求解方法。第一阶段通过优化可行路线的配送顺序和采用节点剔除与重新插入策略修复不可行路线，确保所有路线满足约束条件；第二阶段通过识别客户节点较少且货物总重较低的路线，尝试取消这些路线并将其节点重新分配到其他可行路线，从而减少所需车辆数量，提高资源利用效率。该方法在保持初始路线稳定性的同时，兼顾计算效率与解质量，适合实际应用场景。

本文的贡献主要体现在以下几个方面：首先，结合研究问题构建了定制化MIP模型，整合了常温和冷藏货物容量、时间窗等实际约束；其次，基于有限调整的冷链物流配送优化目标设计了一种新颖的两阶段启发式方法，优先保证路线可行性并尽量减少对初始路线的调整，有效应对城市物流的需求变化；最后，通过数值实验验证了该方法的有效性，证明其能在满足企业现实约束的条件下降低总配送距离，同时保持运营稳定性，为冷链物流企业提供了高效、实用的优化工具。本文后续章节组织如下：第二节详细阐述MIP模型的构建；第三节介绍两阶段求解方法的框架与细节；第四节通过数值实验分析方法的性能；第五节总结研究成果并展望未来研究方向。

2. 问题描述及数学模型

2.1. 问题描述

考虑一家城市冷链物流企业，该企业配置了多辆冷链运输车，能够实现常温、冷藏货物同时运输的要求，企业有一组具有差异化货物需求的客户，需要安排车辆将货物运送到客户手中。研究问题涉及的决策包括将客户分配到不同路线上以及确定每条配送路线中的配送顺序，目标函数是最小化总配送距离。结合现实约束及计算复杂度，对研究问题作如下假设：1) 每条配送路线上的客户需求由一辆运输车满足；2) 只考虑一种车辆类型，并且车辆有体积和重量的限制；3) 车辆行驶时间与行驶距离线性相关；4) 存在时间窗约束，即客户只能在特定时间范围内收货；5) 该物流企业的运输车辆都放置在一个配送中心中，运输车辆从配送中心出发，在执行完配送任务后返回配送中心。

2.2. 数学模型

物流企业的需求和本文的目标是在现有路线的基础上进行优化，以修正不可行路线和优化路线，本章提供研究问题的完整MIP模型(P)，模型中出现的符号及其定义见表1，完整模型如下所示。

Table 1. Definition of notations in the mathematical model

表1. 数学模型中的符号定义

集合
$N$	节点集合，包括配送中心$\left(n=0\right)$ 和配送客户$\left(n\in N\backslash \left\{0\right\}\right)$ ；
$R$	配送路线集合，$r\in R$ ；
参数
$a_i$	客户i的常温货物需求量；
$b_i$	客户i的冷藏货物需求量；
$g_i$	客户i的配送货物重量；
$d_{ij}$	车辆从节点i到节点j的距离；
$t_{ij}$	车辆从节点i到节点j的平均行驶时间；
$l_i$	时间窗参数，最早到达客户i的时间；
$k_i$	时间窗参数，最晚到达客户i的时间；
$A$	车辆的常温货物容量；
$B$	车辆的冷藏货物容量；
$G$	车辆最大载重量；
决策变量
$x_{ri}$	0~1变量，若客户i被分配到路线r上，则$x_{ri}$ 为1，否则为0；
$y_{rij}$	0~1变量，若路线r上节点i是节点j的前一个节点，则$y_{rij}$ 为1，否则为0；
$f_i$	配送车辆到达客户i的时间；

$\min {\displaystyle \sum }_{r\in R}{\displaystyle \sum }_{i,j\in N}{y}_{rij}{d}_{ij}$

${\displaystyle \sum }_{r\in R}{x}_{ir}=1,i\in N\backslash \left\{0\right\};$ (1)

${\displaystyle \sum }_{i\in N\backslash \left\{0\right\}}{x}_{ir}{a}_i\le A,r\in R;$ (2)

${\displaystyle \sum }_{i\in N\backslash \left\{0\right\}}{x}_{ir}{b}_i\le B,r\in R;$ (3)

${\displaystyle \sum }_{i\in N\backslash \left\{0\right\}}{x}_{ir}{g}_i\le G,r\in R;$ (4)

${\displaystyle \sum }_{j\in N\backslash \left\{i\right\}}{y}_{rji}=x_{ir},r\in R,i\in N\backslash \left\{0\right\};$ (5)

${\displaystyle \sum }_{j\in N\backslash \left\{i\right\}}{y}_{rij}=x_{ir},r\in R,i\in N\backslash \left\{0\right\};$ (6)

${\displaystyle \sum }_{i\in N\backslash \left\{0\right\}}{y}_{r0i}\le 1,r\in R;$ (7)

${\displaystyle \sum }_{i\in N\backslash \left\{0\right\}}{y}_{ri0}\le 1,r\in R;$ (8)

$f_j-t_{ij}\ge f_i+\left(y_{rij}-1\right),r\in R;i\in N;j\in N\backslash \left\{0\right\};$ (9)

$l_i\le f_i\le k_i,i\in N\backslash \left\{0\right\};$ (10)

$x_{ir},y_{rij}\in \left\{0,1\right\},f_j\in {ℝ}^{+},r\in R;i,j\in N$ (11)

模型(P)中的目标函数为最小化车辆的总行驶距离。约束条件(1)表示将每个客户都分配到一条路线上。约束条件(2)~(4)表示在进行路线分配时要考虑客户的货物需求，满足车辆的常温、冷藏容量和载重量限制。约束条件(5)~(6)表示每条路线上每个客户节点的前面和后面都有且仅有一个节点。约束条件(7)~(8)表示每条路线上分别最多有一个节点在出发和返回时与配送中心节点相连接。约束条件(9)计算车辆到达每个客户的时间。约束条件(10)表示配送时间窗限制，到达客户节点的时间要在时间窗内。约束条件(11)表示对模型(P)中的变量进行限制。

3. 求解方法设计

由于客户每日需求的不确定性，物流企业需要及时进行调整，从而消除不可行路线并优化可行路线。本文针对该问题设计了特定的优化方法，方法框架如图1所示。求解方法框架可以分为两个部分，第一部分是使得所有配送路线可行并优化配送顺序，第二部分是优化配送路线数量，决策是否能够减少当前配送路线。

Figure 1. Diagram of the solution methodology framework

图1. 求解方法框架图

第一，检查所有的初始路线，优化可行的初始路线，修正不可行的初始路线。对于不可行路线，先剔除部分节点使得路线可行，然后将剔除的节点插入到其他可行路线中，重复此过程直到所有路线均可行。具体来说，对于可行的初始路线，在固定变量$x_{ir},i\in N,r\in R$ 的情况下求解模型(P)，优化该路线上的配送顺序。对于不可行的初始路线，先在模型(P)的基础上增加0~1辅助变量${\epsilon }_j$ ，表示是否将该路线上的客户节点j剔除，构造节点剔除优化模型，使得剔除尽可能少的节点并最小化该路线的配送距离。然后，尝试将剔除的节点加入到不同的可行路线中，在固定路线分配变量的情况下求解模型(P)计算插入之后的行驶距离增加值，决策各个剔除节点的插入路线，使得增加的配送距离最小。

第二，优化配送路线数量，尽量以更少的车辆完成客户配送需求。先根据路线上的客户节点数量和总配送货物重量确定要取消的路线，然后判断路线内所有节点是否均可以插入到其他路线中，如果可以则取消该路线。具体来说，当路线中的客户节点数量大于阈值时该路线就无法被取消，对于客户节点数量小于等于阈值的路线，按照路线中的配送货物总载重量升序排列，并依据顺序尝试将路线中的客户节点插入到其他路线中，若所有客户节点都可以插入，则取消该路线并通过模型(P)优化有新节点插入的路线，否则继续尝试下一条路线能否被取消，直到没有其他配送路线可以取消。

4. 数值实验

本章通过数值实验验证求解方法的有效性。考虑一个实际案例，共有691个客户节点，分配到61条初始路线中。我们在表2中整理了相关参数，由于部分数据的隐私性，使用平均值或近似值替代。数值实验在配备Intel(R) Core(TM) i5-8300H (2.30 GHz)和8GB内存的计算机上运行，操作系统为Windows 11，通过C++语言调用CPLEX 22.1.1，C++程序使用Microsoft Visual Studio 2022开发和编译。在CPLEX设置中，将并行线程数设为1，并保持其他CPLEX设置不变，以排除其他因素的潜在影响。

Table 2. Relevant problem parameters

表2. 相关问题参数

参数	取值	参数	取值
常温货体积(m^3)	0.5218	车辆常温货容量(m^3)	13
冷藏货体积(m^3)	0.1575	车辆冷藏货容量(m^3)	13
货物总重量(kg)	124.7626	车辆载重量(kg)	1800
客户节点横坐标	120.2601	时间窗上界(min)	6.5423
客户节点纵坐标	30.1324	时间窗下界(min)	23.1994

根据结果文件，优化算法对城市冷链物流配送路线进行了调整，涉及17个客户节点的路线重新分配，共影响13条路线。优化后，总行驶距离从初始解的6570.97公里减少到5674.21公里，降低了约13.65%的行驶距离，显著提高了配送效率，同时保持了路线分配的有限调整以确保运营稳定性。

具体而言，优化过程涉及以下客户节点的路线调整：

• 客户节点132从路线14重新分配到路线23。

• 客户节点139从路线15重新分配到路线16。

• 客户节点169从路线17重新分配到路线16。

• 客户节点281从路线26重新分配到路线32。

• 客户节点384、387、407、410、454、462、481、482从路线36、37、41、42重新分配到路线32。

• 客户节点486、506从路线43、45重新分配到路线52。

• 客户节点546从路线47重新分配到路线46。

• 客户节点682从路线58重新分配到路线38。

• 客户节点690从路线59重新分配到路线2。

从路线角度看，路线32接收了最多的节点(9个)，路线16、52等分别接收了1至2个节点。另一方面，有13条初始路线不可行，不可行路线中各有1至2个节点被剔除，反映了算法通过节点重新分配减少了部分路线的负载，使得初始路线可行或直接取消低效路线。优化结果表明，算法有效减少了总行驶距离，同时通过有限的节点调整实现了路线整合。这种有限调整策略符合现实中保持运营稳定性的需求，证明了所提两阶段求解方法的实用性和高效性。

5. 总结

本文针对基于有限调整约束的城市冷链物流配送优化问题进行了深入研究，旨在最小化总配送距离，同时满足客户多样化的货物需求并保持初始路线的稳定性。研究聚焦于一家城市冷链物流企业，考虑了车辆常温和冷藏货物容量限制、重量限制，以及时间窗约束。针对研究问题构建了MIP模型，并提出了一种兼顾路线可行性、效率优化和初始路线稳定性的两阶段启发式求解方法，第一阶段优化可行路线的配送顺序以及修复不可行路线，第二阶段优化路线数量，提高资源利用效率。数值实验结果验证了所提方法的有效性。优化后总行驶距离从初始解的6570.97公里降低至5674.21公里，减少了约13.65%。因此，本研究为冷链物流的智能化和可持续发展提供了理论支持和实践参考。

未来研究可从以下方向拓展：一是考虑多类型车辆的协同优化，以适应更复杂的冷链物流场景；二是引入动态时间窗，提升模型对时变环境的适应性；三是开发更加高效的求解算法，以应对复杂的现实问题。这些方向将为冷链物流配送的持续优化提供新的视角和解决方案。