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个优化目标）测试实例集，该实例集建模了巴西里约克拉罗市邮递员步行投递邮件的真实场景。研究团队构建了该市全新的道路路网图，并对邮递员的投递活动进行了量化估算，为各街道分配了差异化的投递需求概率密度。本研究共生成80个邮路投递测试实例，单实例最大投递量可达50000件。此外，本研究还为部分测试实例推导了优化边界。该实例集已对外公开，供学界测试、对比与验证多目标优化算法使用。