一种适用于有容量限制的机器人站点最后一公里配送的分支定价方法

《European Journal of Operational Research》：A branch-and-price approach for last-mile deliveries with capacitated robot stations

　　•针对有站点容量的卡车与机器人配送问题的扩展建模方法。•相较于紧凑型建模，具有更强的线性松弛界。•针对大规模问题场景的高效分支定价算法。•定价过程可解决非线性基础最短路径问题。•对站点容量、配送截止时间以及客户分布模式的敏感性分析。

引言
在现代城市环境中，随着电子商务的飞速发展以及对高效物流需求的增加，配送优化变得越来越重要。研究表明，优化的配送路线能够显著降低运营成本，并在交通拥堵的城市环境中提升服务质量。物流链中的最后一段配送——即“最后一公里”配送——尤为重要，因为它占据了总配送成本和环境影响的大部分。根据Joerss等人（2016）的研究，最后一公里配送可能占整个运输成本的53%，同时也会造成严重的城市污染，这凸显出寻求创新解决方案的必要性。自主配送机器人系统被视为应对最后一公里配送挑战的一种极具前景的方法。这类系统不仅能降低配送成本，还能减少交通拥堵和污染物排放，从而助力可持续的城市物流发展。从监管角度来看，由于严格的安全和运营规定，尤其是在城市地区，使用无人机进行配送的实际应用面临着越来越大的挑战。相比之下，自动驾驶机器人设计为以类似行人的低速度行驶，因此能够安全地在与行人共享的人行道和自行车道上穿行。这类机器人为城市配送提供了更为安全且受更好监管的替代方案。尽管自动驾驶配送机器人的出现时间晚于无人机，但其发展势头极为迅猛。例如，Starship Technologies、Nuro和Kiwibot等公司已在包括英国的米尔顿凯恩斯、美国的休斯顿和山景城以及哥伦比亚的波哥大在内的全球多座城市成功测试了他们的机器人产品。亚马逊也推出了自己的自动驾驶配送机器人Scout，反映出业界对这项技术日益增长的兴趣和投资力度。预计全球无人机配送市场将实现快速增长，有研究预测，从2024年到2030年，该市场的复合年增长率将超过37%（Research and Markets，2024年）；而从2025年到2033年，这一增长率则为38%（Straits Research，2024年）。另有研究指出，企业向消费者进行的无人机配送量可能会从2024年的数百万次增长到十年后的数亿次（PwC，2024年）。

自主机器人可应用于多种与配送相关的场景中。然而，由于它们的活动范围有限，不太可能成为从公司仓库直接将货物送达最终客户家中的唯一配送方式。一种较为可行的方案是：首先用卡车将包裹运送到仓库，然后在距离客户住所较近的不同设施（或机器人站点）处集中这些包裹，最后再利用自主机器人完成最后的配送任务。在相关文献中，这种场景被称为路由调度问题。每位客户都有规定的配送时间，且必须从某个固定站点接受配送服务。如果机器人未能在指定时间内送达，那么该客户的配送延迟就会被记录下来。解决路由调度问题的核心在于为卡车选择最优的行驶路线，并为每位客户分配合适的处理设施，从而最小化整体的配送延迟。在本研究中，我们探讨的是带容量限制的路由调度问题，该问题还额外规定了每个处理设施所能服务的客户数量上限。研究带容量限制版本的模型之所以有实际意义，主要有两个原因：其一，企业的配送机器人数量是固定的，且在任何时刻每个站点上驻留的机器人数量也是有限的；其二，如果放弃让机器人每次都往返于同一站点，而是在完成配送后将它们重新分配到网络中的其他站点，这种重新定位可能会带来高昂的成本（可能需要额外的卡车或货车来实现快速转移），或者需要耗费大量时间——毕竟卡车的行驶速度通常为30公里/小时，而机器人的速度仅为5公里/小时。不过，重新定位能够提高应对站点容量不足问题的灵活性，因此这也是未来值得研究的潜在方向。需要说明的是，带容量限制的问题需要采用与Alfandari等人（2022年）针对无容量限制问题所使用的Benders分解法完全不同的求解方法。在后者中，每个Benders子问题都是通往某位客户的最短路径，可被建模为可进行对偶化的线性规划问题。而当加入连接不同客户的容量约束后，问题就不再能按客户进行分解，因此无法使用Benders方法。

本文的创新贡献如下：
•我们为带容量限制的路由调度问题开发了一种扩展建模方法，即包含大量变量的建模形式，经验证，相比现有路由调度问题研究中的紧凑型建模方法，该扩展模型能为线性规划松弛问题提供更严格的界。在该模型的列生成方案中，每一列都代表通往一位客户的一条路径，这与传统的车辆路径问题不同，在传统车辆路径问题中，列则是连接多位客户的行驶路线。
•我们设计并实现了一种高效的分支定价算法，可用于将该模型精确求解。其中的定价子问题是一种新型的非线性基础最短路径问题，我们通过定制的动态规划算法来解决这一问题。
•我们通过计算实验验证，与传统针对紧凑型建模方法的商用求解工具相比，我们的方法始终能得到更优的解，这充分体现了其处理复杂问题实例的能力。
•此外，我们还分析了相关配送系统的特性，并进行了敏感性分析，以评估设施数量、客户数量、机器人站点容量以及配送截止时间等关键参数变化所带来的影响。

我们的决策模型也存在一定的局限性。主要局限在于它适用于单舱式机器人，这类机器人是目前市场上最为常见的配送机器人类型（例如Starship、Speedybot（Alpharobotics）、GAMEI（Robotis）、Avride、Peykbot、Lomby等）。对于单舱式自主配送机器人而言，电池消耗和续航里程并非关键问题，因为它们可以完成往返配送，且在短途行程结束后可以在机器人站点为电池充电。例如，作为参考模型的Starship自主配送机器人的续航时间为18小时，这一时间完全足够完成一次往返配送。我们在文章结尾部分提到了多舱式机器人可能带来的新研究方向，这类机器人可能会面临续航和电池更换方面的问题。

本文的结构如下：第2节简要回顾相关研究文献；第3节正式定义所研究的问题，并介绍该问题的紧凑型数学建模形式；第4节介绍扩展建模方法，并将其与其他建模方法的优劣进行比较；第5节阐述我们用于解决该问题的分支定价算法；第6节展示计算实验的结果；第7节进行管理层面的敏感性分析，为实际应用提供参考；最后，第8节对全文内容进行总结，归纳核心研究发现，并指出未来研究的方向。

文献综述
关于最后一公里配送以及与之相关的决策制定和运筹学难题，Boysen等人（2021年）以及Archetti和Bertazzi（2021年）的综述文章中对这些内容进行了全面梳理。传统上，最后一公里配送问题与带容量限制的车辆路径问题密切相关，在这类问题中，多辆具有固定承载能力的车辆从仓库出发并返回仓库，需要在规定的时间窗口内将货物送达客户手中，相关研究可参考相关文献。

问题定义与紧凑型建模
为正式定义我们所研究的问题，我们先列出该系统的主要特征：
1. 有一辆卡车在仓库设施处开始配送行程并结束行程。我们假设这辆卡车具备足够的承载能力，能够将所有包裹运送至各个机器人作业设施。
2. 给定了一组候选的机器人-设施对集合F，我们将从中挑选出实际的作业设施，也就是客户将在此处接受配送服务的地点。卡车必须访问所有的作业设施。
3. 客户集合C中的每一位客户k……

扩展建模
模型1属于车辆路径问题中经典的模型类型，通常被称为弧流建模模型，在这类模型中，变量代表各个单独路径上的流量（例如模型1中的变量fijk）。与弧流建模模型不同，另一种用于描述此类问题的经典建模方法是基于路径的建模方法，在这类方法中，变量代表从起点到终点的整条路径上的流量；这类建模方法往往与集覆盖、集装填或集划分模型相关联。

分支定价算法
分支定价算法可被定义为一种分支定界法，其在搜索树中用于剪枝节点的界限值，是由扩展建模模型的线性规划松弛问题通过列生成方法计算得出的，具体原理将在后文阐述。

实验设置
在本节中，我们将评估我们的模型以及相应的求解方法在处理基准问题实例时的实际性能，随后会对所得结果进行详细分析。相关代码是用C++语言实现的，其中标签生成算法是基于Boost Graph库（boost.org）开发的。实验是在一台配备英特尔i7-10700处理器、时钟频率为2.9吉赫兹、拥有16GB内存、运行Windows 10操作系统的计算机上进行的，所使用的线性规划求解软件版本为CPLEX 20.1.1.0。

管理层面启示
为了对关键参数进行敏感性分析，本节我们使用了包含16个问题实例的基准数据集，随后以可控的方式进一步生成更多问题实例，不断调整客户数量、设施数量以及容量等参数值。该基准数据集是根据以下参数生成的：
• 设施数量 |F|∈{4,8}
• 客户数量 |C|∈{20,40}
• 容量系数 ρK∈{0.5,2.5}，该系数用于按照统一标准确定F集合中各个设施的容量值

结论
在本研究中，我们解决了带容量限制的路由调度问题，该问题的目标是在一个结合了卡车与自主机器人的物流系统中，最小化配送延迟。现有关于无容量限制版本的路由调度问题的研究结果表明，无论从理论层面还是实际应用层面，这类问题都很难求解（属于NP难问题）。在本研究中，我们提出了一种扩展的……

CRediT作者贡献声明
Yerlan Kuzbakov：写作——审稿与编辑，写作——初稿撰写，可视化，验证，软件，资源，方法论，研究调查，形式化分析，数据整理，概念构建。Laurent Alfandari：写作——审稿与编辑，写作——初稿撰写，可视化，验证，监督，项目管理，方法论，研究调查，形式化分析，概念构建。Diego Delle Donne：写作——审稿与编辑，写作——初稿撰写，可视化，验证。

利益冲突声明
作者声明，他们不存在任何可能影响本文研究结果的已知财务利益关系或个人关系。

Yerlan Kuzbakov|Laurent Alfandari|Diego Delle Donne