NEW MULTI-OBJECTIVE VRP INSTANCES MODELLING MAIL DELIVERIES FOR RIO CLARO CITY, SÃO PAULO, BRAZIL

ABSTRACT Optimization benchmarks are tools for the validation and comparison of algorithms. Routing benchmarks are particularly relevant to industry. However, there are few available VRP benchmarks based on realistic situations. This research creates a set of multi-objective (three objectives) instances for a length- constrained variant of VRP. The instances model a realistic case of mail delivery performed by mail carriers on foot in the Brazilian city of Rio Claro. A new graph of the city road map was created, and mail carriers’ activities were estimated. Streets were assigned with distinct probability densities to receive deliveries. This research produces 80 mail delivery instances with up to 50,000 deliveries per instance. Finally, bounds for a set of instances were produced. The instances are publicly available for the community to test, compare and validate multi-objective optimization algorithms.

摘要：优化基准测试集是算法验证与对比的重要工具。路径规划基准测试集尤其贴合工业场景需求，但当前基于真实场景的车辆路径问题（Vehicle Routing Problem, VRP）基准测试集较为匮乏。本研究针对带长度约束的车辆路径问题变体，构建了一套多目标（共3个优化目标）测试实例集。该实例集模拟了巴西里奥克拉罗市（Rio Claro）邮递员徒步配送邮件的真实场景：研究团队绘制了全新的城市道路路网图，对邮递员的配送活动进行建模估算，并为各街道赋予差异化的配送接单概率密度以表征真实的任务分布。本研究共生成80个邮件配送测试实例，单个实例最多可包含50000个配送任务；此外还为部分测试实例生成了优化边界。该实例集已对外开放，供学界用于多目标优化算法的测试、对比与验证工作。