面向城市智能物流的无人车-卡车协同优化：时变交通与多目标建模框架

一、研究背景与问题提出

• 两级城市配送模式。 随着电商和外卖需求增长，城市配送呈现多层结构：大型卡车从仓库送货到“卫星站”（Satellites），小型车辆或无人配送车(UGV)从卫星站完成末端配送。由于城市道路拥堵，卡车在不同时间段的行驶速度存在明显差异，导致传统的固定旅行时间模型不能真实反映实际情况。
• 问题定义。 论文提出“两层卡车‑无人车路径问题‑考虑时间相关旅行时间”（Two‑echelon Truck‑Unmanned Ground Vehicle Routing Problem with Time‑Dependent Travel Times，TTUGVRP‑TDTT）：在给定仓库、卫星站、客户和时间窗的情况下，规划卡车和UGV的行驶路径，使得总运营成本和所需UGV数量最小，并满足车辆容量、时间窗约束与道路拥堵影响。
• 研究意义。 通过协调大车与无人车配送，可提升末端配送效率和客户服务水平，降低交通拥堵带来的延误。文中还探讨了连续与离散的时间相关旅行时间模型，并开发适用于大规模实例的算法。

二、模型与问题定义

2.1 两层配送网络及基本假设

图1展示了论文中考虑的不同类型与容量的UGV车辆，为第二层末端配送提供多样化的运力配置。图2则给出了两层配送网络的空间布局：第一层由一个中心仓库和若干卫星站组成，卡车从仓库出发依次访问卫星站；第二层由卫星站向各客户发出UGV进行配送。图2中蓝色点为客户，绿色为卫星站，红色为仓库。

• 节点集合。 第一层节点包括仓库  和卫星站集合 ，第二层节点是客户集合 。定义两层网络的有序边集分别为 （卡车可通行的道路）和 （UGV可通行的道路）。
• 车辆与容量。 每辆卡车的容量为 ，每辆UGV的容量为 ，卡车最大速度 ，UGV速度 。卡车和UGV出发与返回都必须在规定的时间窗内完成。
• 时间窗。 卫星站有时间窗 ，客户有时间窗 。卡车需在卫星站时间窗内送达，UGV需在客户时间窗内完成服务。
• 旅行时间随时间变化。 为描述道路拥堵，文中根据流体排队理论建立时间相关的旅行时间函数，后文详细推导。

2.2 流体排队模型与时间相关旅行时间

论文采用 流体排队模型 模拟某路段在一段固定时段  内的到达率和出发率，推导路段的排队长度和延误。设到达率  在 （拥堵开始后排队增长最快的时刻）附近用泰勒展开近似为二次函数：

假定在  时刻到达率等于服务率 （道路饱和），并使二阶展开满足 ，可得到一个简化的抛物线到达率模型：

根据流体排队理论，排队长度  与等待时间  表达式分别为：

其中 。设路段  的长度为 ，拥堵指数为 ，在自由流状态下的旅行时间为 。则时间相关旅行时间为：

该模型可根据不同时段的到达率和服务率计算具体路段在不同时间段的旅行时间，从而反馈给路径优化。

下图直观展示了动态到达率的形状和关键时刻 （红线为服务率 ）。

2.3 双目标整数规划模型

论文将 TTUGVRP‑TDTT 转化为多目标混合整数线性规划，目标包含：

1. 最小化总运营成本。成本分为第一层卡车成本  和第二层UGV成本 。其中卡车成本包括行驶距离成本与固定启动成本，UGV成本则包括行驶距离、超时惩罚等。

2. 最小化第二层使用的UGV数量

模型约束包括车辆流平衡、每个客户恰好被一辆UGV服务、UGV容量约束、卡车与UGV时间窗约束以及卫星站的开箱数量约束等。由于空间限制，本文只列出关键约束示意：

• 卡车流平衡：

表示卡车  在每个卫星站满足流量守恒：到达卫星  后必须离开卫星 。

• UGV流平衡：

表示每辆UGV在节点  满足流量守恒：到达  后必须从  离开。

• 时间窗约束：到达时间必须在指定时间窗内，否则产生罚金纳入成本 。

三、求解方法与算法设计

考虑问题的 NP‑难性，论文结合启发式聚类与改进的多目标大邻域搜索提出求解框架，流程如图所示。

3.1 3D KNN聚类与改进Clarke‑Wright节约算法

为了减小问题规模，论文先采用带时间维度的三维 K 最近邻聚类算法将客户分配到距离最近的卫星站。其距离定义为

其中  和  分别表示样本（如客户或卫星）  和  的经纬度与时间窗起点， 为将时间差折算为距离的权重系数。聚类后的结果在图中展示，左图为平面聚类，右图为带时间维度的三维聚类。

聚类完成后，采用改进的 Clarke‑Wright 节约算法(ICWSA)为每个卫星站构造第二层UGV的初始路径。该算法利用广义节约值  计算合并配送路线的收益，结合禁忌策略调整路径。图示展示了利用节约值对路径进行合并与调整的示例。

3.2 改进多目标自适应大邻域搜索 (IMOALNS)

在获得初始解后，论文提出结合多种破坏与修复算子的改进自适应大邻域搜索算法（IMOALNS）对两层路径进行联合优化。其核心思想如下：

• 破坏算子：随机删除一部分客户或卫星站，使解空间跳出局部最优；包括随机、最差、相关、路径毁坏等多种策略。

  

• 修复算子：将被移除的客户重新插入到最佳位置，分为随机插入、贪心插入、带禁忌表的贪心插入和后悔插入(k‑regret)等。

  

• 自适应选择和接受准则：算法为不同算子动态分配权重，根据历史表现调整选择概率，并采用类似模拟退火的接受准则确保多样化搜索。

• Pareto 解选择策略：针对多目标优化，采用基于支配关系和拥挤距离的非劣解库维护策略，流程如下。

  

该改进算法兼顾探索与利用能力，在处理时间相关的动态成本以及双目标优化时表现出良好的性能。

3.3 不同时间分辨率的TDTT模型

论文还比较了离散时间和连续时间的 TDTT 模型。离散模型将整段时间  划分为 6、9 或 18 个子区间，假设每个区间旅行时间恒定；连续模型则利用流体排队公式得到光滑曲线。图示比较了不同模型下旅行时间随时间的变化。

通过仿真发现，当区间数从 6 提升到 18 时，离散模型的旅行时间曲线逐步接近连续模型；但连续模型更能精确反映拥堵的演变。

四、案例研究：大连城市配送

4.1 数据与参数

论文以中国大连市作为案例研究场景。第一层包含一个仓库和16个卫星站，第二层要服务400名客户。为量化交通拥堵影响，作者利用百度地图实时路况数据，将拥堵指数  分为“畅通”“缓行”“拥堵”和“严重拥堵”四种情景，对应参数范围如表所示。

默认模型参数取值为：卡车单位距离成本 、UGV 单位距离成本 、卡车固定启动成本 、UGV 固定成本 、UGV 容量 150、卡车容量 600、UGV 速度 10 km/h、拥堵持续时间 3 h 等。

4.2 聚类与第二层路径结果

采用3D KNN聚类后，400个客户被重新划分到16个卫星站。例如 S3 负责 36 个客户、S7负责 36 个客户、S14负责 18 个客户等。聚类结果如图所示。

4.3 优化结果与路由展示

在拥堵条件下，对第二层路径应用 IMOALNS 优化得到最小二层成本（论文表11），共需要54辆UGV 为400名客户服务。优化后的UGV路径示意如下：

为了使卡车按时到达卫星站，作者利用实时路况调整第一层路线。在 [8:00,11:00] 的拥堵时段内，卡车出发时间 t₀=8:00，拥堵在 t₂=10:00 达到峰值。优化后的卡车路线与初始路线对比如下：方案(a)为未考虑拥堵时的初始路线，方案(b)为最短距离路线，方案(c)为考虑TDTT的优化路线，方案(d)用实测拥堵指数验证某条线路的旅行时间。

从结果可见，考虑时间相关旅行时间后，卡车路线经过调整能显著缩短总旅行时间并降低拥堵峰值到达卫星站的风险。作者还进行了不同UGV容量与不同拥堵程度的敏感性分析，结果表明在严重拥堵场景下适当增加UGV数量能显著降低整体成本和卡车数目。

4.4 TDTT模型比较

论文将连续时间模型与不同离散时间间隔的模型进行比较，发现随着离散间隔增多，离散模型逐渐逼近连续模型，但连续模型在衡量道路拥堵时更准确，对优化结果和计算效率具有综合优势。

五、困难与解决策略

1. 时间相关旅行时间的建模困难。 城市道路拥堵具有不确定性，传统常数旅行时间模型难以刻画。论文通过流体排队理论建立时间相关旅行时间函数，利用泰勒展开得到可解析的形式，并与交通指数数据结合，缓解了模型复杂度。
2. 多目标优化的复杂性。 同时优化总成本与UGV数量需兼顾成本与效率，且约束众多。论文将问题建模为双目标混合整数规划，并用改进大邻域搜索在解空间中动态跳跃，利用Pareto排序保持解集多样性。
3. 求解大规模实例的计算难度。 两层网络规模大，直接用商用求解器耗时巨大。通过聚类预处理和节约算法生成高质量初解，再通过多策略扰动与修复搜索得到近似最优解，大大提升了求解效率和质量。

六、研究结论与管理启示

• 模型贡献。 文中提出的 TTUGVRP‑TDTT 将时间相关旅行时间纳入两层车‑UGV路径优化，构建了基于流体排队的旅行时间模型，并提出双目标整数规划框架。

• 算法创新。 结合三维KNN聚类、改进Clarke‑Wright节约算法和多目标自适应大邻域搜索，算法在多组标准实例与实际案例中均优于蚁群优化、多目标遗传算法等基准方法，在总运营成本、UGV数量和计算时间方面取得优势。

• 实证发现。 大连案例表明，在拥堵情景下通过调整卡车出发时间和路由可节省10%左右的运输成本；连续时间模型优于离散模型；在严重拥堵条件下适当增加UGV数量可减少总成本。

• 管理启示。

• 对企业而言，采用车‑UGV协同配送可提高最后一公里服务效率并降低人力成本。结合实时路况的数据驱动决策有助于动态调整运输计划。
• 物流公司应根据不同拥堵程度灵活配置UGV容量和车辆数量，在高峰时段可通过增加UGV共享来减少卡车数量和延误。
• 提高客户时效满意度时需要平衡调度成本与服务质量，使用多目标优化工具可得到成本‑效率的折中方案。

通过对论文的详尽解析，可以看出时间相关旅行时间建模和组合优化算法的结合，使得复杂的城市双层配送问题得到有效求解，并为未来无人配送与智慧物流提供了可行的研究范式和实际指导。