《European Journal of Operational Research》：Pattern-based adaptive large neighborhood search algorithm for roll–on roll–off vehicle routing problem
编辑推荐：
•我们研究了考虑运营约束的滚装滚卸车辆路径问题（roll-on roll-off vehicle routing problem，RRVRP）。•为该问题建立了一个全面的混合整数规划模型。•提出了一种基于行程模式的自适应大邻域搜索算法。•所提算法在基准测试上表现良好，尤其是在
- •
我们研究了考虑运营约束的滚装滚卸车辆路径问题（roll-on roll-off vehicle routing problem，RRVRP）。
- •
为该问题建立了一个全面的混合整数规划模型。
- •
提出了一种基于行程模式的自适应大邻域搜索算法。
- •
所提算法在基准测试上表现良好，尤其是在大规模实例上。
引言
根据联合国环境规划署（2024）的数据，预计到2050年全球废弃物产生量将增加1.8倍，而废弃物管理成本预计将几乎翻倍，达到6403亿美元。这些预测凸显了废弃物收集与管理领域亟需取得进展。在这一背景下，废弃物收集车辆路径问题（waste collection vehicle routing problem，WCVRP）具有相当重要的意义，因为生成高效的路线可以大幅降低废弃物管理成本。
如Hess等人（2024）所指出的，WCVRP已在广泛的问题型中被研究，包括网络设计、选址路径、弧路径、车辆路径和库存路径问题。在这些各种问题设定中，一个核心的运营问题是废弃物收集路线的优化。在这方面，WCVRP通常以三种代表性形式被讨论：商业型、居民型和滚装滚卸型。商业废弃物收集问题（commercial waste collection problem，CWCP）涉及访问各个商业地点以收集废弃物。相应地，CWCP被建模为一个节点路径问题。相比之下，居民废弃物收集问题（residential waste collection problem，RWCP）涉及居民废弃物，并被建模为一个弧路径问题：车辆不是直接访问每个家庭，而是沿代表家庭群体的弧行进，从而在一次通行中收集弧上所有废弃物。滚装滚卸车辆路径问题（roll-on roll-off vehicle routing problem，RRVRP）与CWCP和RWCP不同之处在于废弃物是在集装箱层面处理的：服务包括从客户处收集满载的集装箱并在填埋场卸载，或向客户交付空集装箱。与RWCP和CWCP涉及相对简单、车辆装满废弃物后到填埋场卸载的操作不同，RRVRP本质上更为复杂，因为客户请求不同类型的服务（Golden等，2002；Kim等，2006）。
CWCP和RWCP主要处理市政固体废物（municipal solid waste，MSW），而RRVRP则针对建筑垃圾和拆除废物，后者在美国的产量是MSW的两倍以上（美国环境保护署，2020）。这一对比凸显了对RRVRP的研究关注度应与其在RWCP和CWCP上获得的研究重视程度相当。在现有文献中，WCVRP的许多与实际密切相关方面，尤其是RRVRP的这些方面，往往被忽视（Markov等，2016）。随着WCVRP重要性的日益提升，RRVRP在运营约束下也需要进一步研究。据我们所知，本研究以最为全面的形式处理了RRVRP，纳入了迄今为止所考虑范围最广泛的运营约束。特别地，研究引入了暂存（staging）这一特性，允许车辆临时存储空集装箱，并定义了六种新的服务类型。
在本研究中，我们将RRVRP正式定义为一个考虑全面运营约束的混合整数线性规划（mixed-integer linear programming，MILP）模型。由于MILP无法求解现实规模的问题实例，因此引入了一种高效的启发式算法，以确保实际的可求解性。在RRVRP中，车辆容量极其有限（仅为一或两个集装箱），这要求对堆场、填埋场等中间设施进行多次访问，因此减少此类访问次数成为生成高效路线的关键因素。本研究利用这一特征，预先生成高效的行程模式，并将其作为自适应大邻域搜索（adaptive large neighborhood search，ALNS）框架中的基本构件。由此提出了一种基于模式的自适应大邻域搜索算法（pattern-based ALNS，PALNS）。PALNS始终优于目前最为全面的先前RRVRP研究，该研究考虑了最为广泛的运营约束集（Wy等，2013）。与MILP模型的比较进一步表明，该算法能够在小规模实例上获得最优解。此外，基于真实世界数据的实验证实，PALNS能够有效地为大规模实例找到高质量解。
本文余下部分组织如下。第2节回顾了与RRVRP相关的文献。第3节介绍了问题描述，包括本研究考虑的各种约束以及相应的MILP。第4节详细说明了所提出的算法，第5节评估了算法的性能。最后，第6节总结全文并概述了未来研究方向。
章节片段
文献综述
本节回顾了关于RRVRP的文献。Bodin等人（2000）在集装箱类型和废弃物类型均同质化的前提下，提出了RRVRP的一个基础模型，并假设存在单一填埋场，同时定义了四种一般服务类型：取空还满（Empty and Return，ER）、换出（Switch Out，SO）、配送（Delivery，DEL）和暂不返回（Do Not Return，DNR）。其中，ER指从客户处收集满载集装箱、在填埋场将其清空后送回同一客户；SO指交付一个空集装箱
问题描述
本研究处理的RRVRP纳入了规模最大的服务类型集以及范围广泛的运营约束。3.1节对考虑了多种运营约束的RRVRP进行了详细描述。3.2节随后给出了RRVRP的MILP。
基于模式的自适应大邻域搜索算法（PALNS）
由于MILP无法高效求解现实世界的实例，本研究提出了一种元启发式算法PALNS。PALNS的设计基于MILP模型中的两点考量。第一，请求不同服务类型的客户应以统一方式处理，以降低算法复杂度，并使新服务类型的纳入更加容易。第二，计算负担不应随中间设施数量的增加而显著上升。
计算实验
本节评估了PALNS算法的性能。由于尚无现有的RRVRP研究同时处理了本研究考虑的所有约束，我们采用Wy等人（2013）提出的基准进行测试，该基准模拟了先前研究中报告的最为全面的约束集下的RRVRP。对于小规模实例，我们将其与所提出的MILP模型进行比较。为了展示该算法在大规模
结论
本研究考虑了迄今为止最为广泛的RRVRP约束集，纳入了六种新的服务类型，并首次引入了暂存概念。与传统的车辆路径问题不同，RRVRP允许客户请求不同的服务，并允许多次访问中间设施。为解决这一问题，客户被划分为三类，并引入了内部路径的概念以区分对中间设施的重复访问。基于这些定义，开发了一个MILP。
CRediT作者贡献声明
Sangil Han：撰写——初稿、可视化、验证、软件、方法学、调查研究、形式化分析、数据整理、概念构思。Seungyeop Lee：撰写——审阅与编辑、软件、方法学、数据整理。Byung-In Kim：撰写——审阅与编辑、验证、监督、资源、项目管理、方法学、获取经费、数据整理、概念构思。
关于撰写过程中使用生成式人工智能及人工智能辅助技术的声明
在准备本作品过程中，作者使用了ChatGPT以提升语言和可读性。在使用该工具/服务后，作者对所撰写内容进行了审阅和按需编辑，并对本出版物内容承担全部责任。
利益冲突声明
作者声明，他们没有已知的可能影响本文所报告工作的竞争性经济利益或个人关系。
致谢
本工作由韩国国家研究基金会（NRF）资助，其经费由韩国政府（MSIT）提供（编号：2022R1A2C2006665）。
Sangil Han|Seungyeop Lee|Byung-In Kim
