论文题目：Recent developments in location-routing problems Deterministic single-echelon, single-objective, single-period problems

第一作者：Rossana Cavagnini RWTH Aachen University 商学院计算物流系，研究方向包括位置-路线问题、物流优化、算法设计与应用。

E-mail：cavagnini@cl.rwth-aachen.de。

通讯作者：Alberto Santini Universitat Pompeu Fabra / Barcelona School of Economics，研究方向包括位置-路线优化、多目标优化、数据驱动的物流决策。
E-mail：alberto.santini@upf.edu。


联合选址与路线设计：单层位置-路线问题最新综述

论文摘要

本文对单层、单目标、单周期、确定性的位置‑路径问题研究文献进行综述。作者指出，LRP同时考虑长期的设施选址（战略决策）与短期的车辆路径设计（运营决策），能够显著改善配送效率。文中将近250篇符合条件的论文归类为标准LRP、带取送（Pickup & Delivery）、带利润选择、带时间窗、考虑延迟和其他拓展几类，并集中讨论各类问题的建模特点和算法进展。综述强调近年来研究在模型精细化、算法加速及新应用场景方面取得突破，同时指出缺乏统一的标准模型和测试基准仍是制约学术进展的重要瓶颈。

一、研究背景与问题定义

1.1 选址与路径的协同决策

  • 选址决策：决定在候选点中开设哪些设施，并考虑固定开设成本、容量限制等。
  • 路径决策：从开放的设施出发设计车辆路线，满足客户需求并优化总成本。
  • 两类决策时域差异明显，但忽视其互动会导致劣质方案。

1.2 研究范围与分类

  • 单层、单目标、单周期、确定性：文中不涉及多层补货、随机需求或多目标情况。
  • 问题类别：分为6类——标准LRP、带取送（LRPPD）、带利润（LRPP）、带时间窗（LRPTW）、延迟型（LLRP）以及其他特殊变体。
  • 研究限制：只考虑公开发表的期刊论文或会议论文，排除学位论文、工作报告等。

二、标准位置‑路径问题

2.1 问题特点与开放式变体

  • 标准LRP要求每个客户由一个设施的一条车辆路线服务。
  • 当车辆不必返回出发设施时，称为开放式LRP（OLRP）。下图展示了标准LRP和开放式LRP的典型解：
图1 标准LRP示例（取自 Fig.1）
图1 标准LRP示例（取自 Fig.1）
图2 开放式LRP示例（取自 Fig.2）
图2 开放式LRP示例（取自 Fig.2）

2.2 求解方法综述

2.2.1 精确算法

  • Liguori等（2023）提出基于分支‑割‑定价（BCP）的精确方法，引入路线负载背包切割（RLKC）不等式，有效加强模型。
  • Granada等（2019）针对OLRP提出基于生成森林结构的混合整数规划（MIP）模型，使CPLEX求解效率显著提升。

2.2.2 启发式和元启发式算法

  • Progressive Filtering (PF) ：Arnold & Sörensen（2021）先过滤不可能的设施配置，再结合遗憾启发式和局部搜索改进路线，针对大型基准实例表现出色。
  • Iterated Local Search (ILS) ：Accorsi & Vigo（2020）在多次启动的框架内使用CROSS交换和串联重新定位等操作高效探索解空间。
  • 其他：模拟退火、遗传算法、蚁群算法等也被用于大规模实例求解。

2.3 问题洞察

作者指出，尽管标准LRP已有众多算法，研究仍存在两个问题：精确算法的规模限制和缺乏统一的基准实例和比较框架。今后可通过机器学习辅助的成本估计提高搜索效率。

三、带取送的LRP（LRPPD）

3.1 直接取送与中转流动

  • 直接取送：货物可直接由提货客户送达送货客户，设施仅作为起止点。一些研究利用列生成算法求解带时间窗的取送LRP，取得较小最优间隙。
  • 通过设施中转：被称为枢纽LRP（HLRP），货物流必须经过设施处理，类似于两层网络，但没有中央仓库。
图3 标准LRP、两层LRP与枢纽LRP网络示例（取自 Fig.3）
图3 标准LRP、两层LRP与枢纽LRP网络示例（取自 Fig.3）
  • 核心特征包括：货流是否为客户对之间的点对需求、设施之间是否采用完备或选择性的连接方式，以及客户的服务方式（分批取送或一次服务）。

3.2 代表性算法

  • Capelle等（2019）采用改进的分支‑定价方法处理带时间窗的直接取送问题，通过自适应分支策略和图预处理显著提升求解性能。
  • 对于HLRP，研究重点是设施连接方式和货物聚集机制。多项研究使用Hamilton环或车辆装载路径构建枢纽之间的运输网络，并针对不同运输需求提出划分启发式和混合算法。

四、带利润选择的LRP（LRPP）

4.1 问题描述

当并非所有客户必须服务时，需要在客户利润与设施和运输成本之间权衡。这一类问题的目标通常是最大化收益减成本，类似于旅行商问题中的收益问题和有奖巡回问题。

4.2 PTP类方法

  • Negrotto & Loiseau（2021）提出多项式规模变量的MIP模型，通过添加有效不等式和针对容量的割平面，在分支‑割框架中求解。
  • Bagheri Hosseini等（2019）研究电子废物回收中的利润选址路由，采用迭代局部搜索并引入基于奖励的需求弹性模型。
  • Ahmadi‑Javid等（2018）的利润最大化LRP（PMLRP）允许价格决策影响需求，通过分支‑定价处理复杂的资源约束路径问题。

4.3 OP类方法

当利润代表任务重要性（如军事目标），研究者采用最大收益下的时长限制模型，并发展启发式算法。总体而言，LRPP文献相对较少，研究集中在特定应用和算法框架构建。

五、带时间窗的LRP（LRPTW）

5.1 问题特点

在LRPTW中，每个客户必须在指定时间区间内被服务。这类问题常见于电商配送和现金运输。

5.2 精确与近似方法

  • Ponboon等（2016）提出第一个针对标准LRPTW的分支‑定价算法，通过解决每个设施的带时间窗资源受限最短路问题生成列。算法只适合小规模实例。
  • Farham等（2018）在Ponboon框架上加入多个加速策略，并提出两阶段启发式：先求解简化的容量设施选址问题，再固定设施求解多仓VRPTW，显著提升效率。
  • Koç等（2016）将车队规模与组合决策融入LRPTW，使用遗传算法与自适应大邻域搜索（ALNS）求解。

5.3 复杂场景

其他研究还考虑道路时间窗、载荷相关速度和不安全路段等情形。例如，Çetinkaya等（2018）处理受恐怖主义影响的道路安全窗约束；Rave & Fontaine（2025）讨论载重与坡度影响货车速度的问题。

六、延迟型LRP（LLRP）

6.1 延迟指标与模型

LLRP的目标是最小化客户的总到达时间（延迟），适用于生鲜供应链和灾后救援。其特点包括：

  • 常假设设施不收取开设成本，通常会充分开放所有可用设施。
  • 若旅行时间满足三角不等式，最优解中车辆数等于设施数与客户数的较小值。

6.2 典型方法

  • Moshref‑Javadi & Lee（2016）提出MIP模型及混合遗传算法，并证明考虑延迟目标能显著改善救援效果。
  • Nucamendi‑Guillén等（2022）设计多层网络模型并开发分支‑剪枝和分支‑检查算法，较早期模型具有更好下界。
  • Osorio‑Mora等（2023）将模拟退火（SA）与变量邻域搜索（VND）结合，通过聚类生成初始解，并在迭代中调整开放设施和车辆分配，表现稳定。
  • 强化学习与元启发式结合的算法也被用于提升搜索质量和鲁棒性。

6.3 图像示例

延迟型LRP在救援场景中的典型结构如下图所示：

图4 L&LRP示例——选址与路径并需确定客户位置（取自 Fig.4）
图4 L&LRP示例——选址与路径并需确定客户位置（取自 Fig.4）

此外，图5展示了当部分客户在覆盖范围内无需车辆服务的情形：

图5 LoRP示例（取自 Fig.5）
图5 LoRP示例（取自 Fig.5）

七、其他拓展与合作/竞争问题

7.1 结合客户选址与路线（L&LRP, LoRP）

  • L&LRP不仅决定设施位置，还需选择新的客户位置，常见于人道主义救援。
  • LoRP允许部分客户由步行或自驾方式到达设施，车辆只服务距离远的客户。研究重点在于覆盖半径、车辆限制和分层服务策略。

7.2 合作与竞争

  • 在多公司共享或竞争客户的情况下，研究者提出合作LRP与竞争LRP模型，通过博弈论分析不同合作水平下的成本与公平性。下图展示了三种合作情形的网络结构：
图6 非合作、半合作与完全合作示例（取自 Fig.6）
图6 非合作、半合作与完全合作示例（取自 Fig.6）

7.3 树网与特殊拓扑

在一些特殊地形（如山区）中，客户和设施分布在树形网络上，车辆必须沿树形走向。研究者提出动态规划算法解决此类树网LRP，其示意图如下面所示：

图7 树形LRP示例（取自 Fig.7）
图7 树形LRP示例（取自 Fig.7）

八、主要观察与未来建议

  • 慎重结合长期与短期决策：论文强调，LRP将战略的选址和运营的路径设计统一优化，但两者的时间尺度不同，模型应通过情景分析或数据驱动方式合理匹配。
  • 明确问题描述和标准化测试：许多研究未能清晰描述新变体的假设，导致难以比较。建议在引入新模型时提供清晰的文字描述，并利用或建立标准化实例集，便于同行比较算法性能。
  • 推动机器学习辅助估计：传统启发式算法需大量计算路线成本，未来可探索机器学习（如图神经网络）来快速估计路由成本，实现人机协同。
  • 关注实际可用性：简洁而有效的算法更容易被行业采用。作者呼吁审稿人重视实践价值，不应仅关注最优性能。
  • 支撑可持续发展目标：某些LRP变体可用于医疗服务、教育公平、灾后救援与环保等领域，直接关联联合国可持续发展目标。

总结与学术贡献

本文综述系统梳理了近十年单层、单目标、确定性LRP的主要研究进展。在分类整理基础上，作者评述了精确算法、启发式方法及各类特殊问题的建模思路与算法框架，指出当前研究在模型描述、实例基准和算法实践性方面的不足，并提出利用机器学习、标准化测试和关注现实需求的建议。综述为研究者了解LRP领域的发展脉络提供了结构化的认知框架，为后续研究指明了方向。


文章须知 

链上镖师团队：常文婕（AEIC）、祁园园、王一航、张仁义（EIC）、张晓乐、张巧巧

原文链接：https://doi.org/10.1016/j.ejor.2025.09.040

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。