新基准实例

本数据集由波恩大学离散数学研究所和豪斯多夫数学中心的研究人员开发，旨在为具有时间依赖旅行时间的车辆路径问题提供真实世界的基准测试实例。数据集包括10个不同城市的实例，每个城市有2000、1000和500个地址。这些实例基于OpenStreetMap地图和Uber发布的速度数据，模拟了不同时间段内的旅行时间变化。数据集的目的是为了更准确地评估和比较不同算法在处理时间依赖性路径规划问题时的性能。

This dataset was developed by researchers from the Institute of Discrete Mathematics at the University of Bonn and the Hausdorff Center for Mathematics, aiming to provide real-world benchmark instances for the Vehicle Routing Problem with Time-Dependent Travel Times. The dataset includes instances from 10 distinct cities, with each city having three instance scales corresponding to 2000, 1000, and 500 addresses respectively. These instances are constructed based on OpenStreetMap data and speed data released by Uber, simulating the variations of travel times across different time periods. The purpose of this dataset is to enable more accurate evaluation and comparison of the performance of different algorithms when dealing with time-dependent route planning problems.

搜集汇总

数据集介绍

构建方式

在车辆路径规划领域，时间依赖性旅行时间对算法性能具有关键影响。新基准实例的构建基于真实世界的地理数据与速度信息，采用系统化的方法生成。首先，研究团队从OpenStreetMap获取了十个主要城市的道路网络数据，并结合Uber提供的速度数据集，提取了特定时段内的历史平均速度。针对每个城市，随机选取了500至2000个地址作为配送点，并设计了包含单一仓库取货和通用取送货两种场景的实例。每个实例中的时间窗口根据实际配送需求随机生成，部分配送点设置了严格的一小时窗口，其余则采用宽松时间约束，以模拟现实物流场景的多样性。

特点

该数据集的核心特点在于其高度真实性与时间依赖性建模的精确性。实例中的旅行时间函数采用分段线性到达时间函数进行表示，严格遵循先进先出原则，确保了时间依赖模型的物理合理性。数据集覆盖了柏林、纽约、伦敦等全球不同区域的十个城市，地理多样性显著，且实例规模从500个任务扩展至2000个任务，提供了丰富的可扩展性测试基准。此外，数据集不仅包含了点对点的旅行时间矩阵，还提供了路径长度信息，支持多目标优化研究。其时间窗口设计兼具严格与宽松类型，能够有效评估算法在复杂时间约束下的性能。

使用方法

该数据集适用于车辆路径规划算法的开发、测试与比较研究，尤其侧重于时间依赖性旅行时间的处理。使用者首先需加载数据集提供的到达时间函数矩阵与任务属性文件，构建包含时间窗口、取送货地址及车辆约束的优化模型。在算法实现中，可调用数据集中的分段线性函数进行旅行时间计算，并利用其提供的真实世界路径网络进行可行性验证。评估算法性能时，应以总成本（车辆固定成本与工作时间成本之和）为主要指标，同时检查时间窗口违反情况。研究者还可通过对比固定旅行时间与时间依赖旅行时间下的求解结果，深入分析时间依赖性对路径规划的影响。

背景与挑战

背景概述

在车辆路径规划领域，传统算法多基于固定行驶时间假设，然而城市交通流量的时变性使得这一简化模型在时间窗口紧凑的实际场景中易导致方案不可行或成本高昂。为应对此局限，波恩大学离散数学研究所与Hausdorff数学中心的Jannis Blauth等学者于2024年提出了‘新基准实例’数据集，旨在为时变行驶时间的车辆路径问题提供基于真实道路网络的评估基准。该数据集依托开源地图数据与实时速度信息，构建了涵盖柏林、纽约等全球十座主要城市的配送实例，通过引入分段线性到达时间函数精确建模交通动态，推动了时变路径规划算法从理论到实践的跨越，为物流优化研究提供了关键的数据支撑。

当前挑战

该数据集致力于解决时变行驶时间下的车辆路径优化问题，其核心挑战在于如何高效处理分段线性到达时间函数的复合与最小化运算，这些运算会导致断点数量指数级增长，对算法时空复杂度构成严峻考验。在构建过程中，研究者需从异构数据源整合道路网络拓扑与实时速度信息，并保证生成实例的时空真实性；同时，为平衡计算效率与模型精度，需设计单调性保持的函数近似算法，以在可控误差内压缩断点规模，确保大规模实例下路径查询与调度优化的可行性。

常用场景

经典使用场景

在车辆路径规划领域，时间依赖性旅行时间模型对于模拟城市交通的动态变化至关重要。新基准实例数据集通过整合真实世界道路网络与时间依赖性速度数据，为研究者在复杂时空约束下评估算法性能提供了标准化测试平台。该数据集最经典的使用场景是验证时间依赖性车辆路径问题（TDVRP）的启发式与精确算法，特别是在考虑严格时间窗口、多车型异构车队及软硬时间窗混合约束时，能够系统检验解决方案的可行性与成本效益。

实际应用

在实际物流与供应链管理中，该数据集为城市配送、紧急物资调度及共享出行服务提供了高保真模拟环境。基于真实城市道路网络与时间依赖性速度数据，企业能够测试并优化在高峰时段、多时间窗口约束下的车辆调度方案，从而降低运营成本、提高配送准时率。例如，在电商物流中，利用该数据集可评估不同路径规划策略在动态交通下的表现，为实际路由决策提供数据驱动支持，增强物流系统对城市交通变化的适应能力。

衍生相关工作

该数据集衍生了一系列经典研究工作，主要集中在时间依赖性车辆路径算法的扩展与优化。例如，基于其提供的基准实例，研究者开发了融合收缩层次结构的高效最短路径查询方法、改进的局部搜索启发式算法，以及针对时间窗口与旅行时间交互的动态规划框架。这些工作不仅提升了TDVRP的求解效率，还推动了相关分支如时间依赖性取送货问题、多行程路径规划等方向的发展，为后续研究提供了算法设计与实验验证的基础。