Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem

📄 arXiv: 2403.00026v1 📥 PDF

作者: Samuel J. K. Chin, Matthias Winkenbach, Akash Srivastava

分类: cs.LG, cs.AI, math.OC

发布日期: 2024-02-28

💡 一句话要点

提出FM-MCVRP以解决蒙特利尔容量限制车辆路径问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 车辆路径问题 深度学习 自然语言处理 Transformer 优化算法 组合优化 物流管理

📋 核心要点

  1. 现有方法在解决容量限制车辆路径问题时，往往依赖于复杂的启发式算法，难以保证解的质量与效率。
  2. 本文提出的FM-MCVRP模型通过将MCVRP问题框架化为自然语言处理任务，利用Transformer架构进行训练，显著提高了解的质量。
  3. 实验结果显示，FM-MCVRP在400客户问题上，其解的平均误差仅为基准的2%，并且在不同问题规模上表现一致可靠。

📝 摘要（中文）

本文提出了蒙特利尔容量限制车辆路径问题的基础模型FM-MCVRP，这是一种新颖的深度学习模型，旨在为容量限制车辆路径问题的变体提供高质量解决方案。该问题在固定图上定义，模拟现实世界的送货场景。我们将MCVRP框架化为自然语言处理任务，利用嵌入在大型语言模型框架中的Transformer架构，通过监督学习训练模型。实验结果表明，FM-MCVRP在未见过的较大问题实例上也能有效泛化，并且在与最先进启发式方法的近似最优解比较中，FM-MCVRP的表现依然具有竞争力。

🔬 方法详解

问题定义：本文旨在解决蒙特利尔容量限制车辆路径问题（MCVRP），现有方法多依赖复杂启发式算法，难以在效率和解的质量之间取得平衡。

核心思路：FM-MCVRP模型通过将MCVRP问题视为自然语言处理任务，利用Transformer架构进行训练，能够有效捕捉问题结构并生成高质量解。

技术框架：该模型基于大型语言模型框架，采用监督学习方式，训练过程中使用算法生成的次优解作为训练数据，整体流程包括数据准备、模型训练和解的生成。

关键创新：FM-MCVRP的主要创新在于将车辆路径问题与自然语言处理相结合，形成统一模型，能够在多种问题实例上保持一致的性能。

关键设计：模型设计中，采用了Transformer架构，损失函数经过精心设计以适应MCVRP特性，参数设置经过多次实验优化，以确保模型的泛化能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，FM-MCVRP在处理400客户问题时，其解的平均误差仅为基准解的2%。与最先进的启发式方法相比，FM-MCVRP在未见过的较大问题实例上也表现出色，显示出其强大的泛化能力和竞争力。

🎯 应用场景

该研究的潜在应用领域包括城市物流、配送服务和交通管理等。通过优化车辆路径，FM-MCVRP能够有效降低运输成本，提高配送效率，具有显著的实际价值和社会影响。未来，该模型还可扩展至其他类型的组合优化问题，推动相关领域的发展。

📄 摘要（原文）

In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Vehicle Routing Problem (CVRP) that characterizes many real-world applications. The so-called Montreal Capacitated Vehicle Routing Problem (MCVRP), first formally described by Bengio et al. (2021), is defined on a fixed and finite graph, which is analogous to a city. Each MCVRP instance is essentially the sub-graph connecting a randomly sampled subset of the nodes in the fixed graph, which represent a set of potential addresses in a real-world delivery problem on a given day. Our work exploits this problem structure to frame the MCVRP as an analogous Natural Language Processing (NLP) task. Specifically, we leverage a Transformer architecture embedded in a Large Language Model (LLM) framework to train our model in a supervised manner on computationally inexpensive, sub-optimal MCVRP solutions obtained algorithmically. Through comprehensive computational experiments, we show that FM-MCVRP produces better MCVRP solutions than the training data and generalizes to larger sized problem instances not seen during training. Even when compared to near-optimal solutions from state-of-the-art heuristics, FM-MCVRP yields competitive results despite being trained on inferior data. For instance, for 400-customer problems, FM-MCVRP solutions on average fall within 2% of the benchmark. Our results further demonstrate that unlike prior works in the literature, FM-MCVRP is a unified model, which performs consistently and reliably on a range of problem instance sizes and parameter values such as the vehicle capacity.