Local Optima Network Analysis of Multi-attribute Vehicle Routing Problem

Multi-Attribute Vehicle Routing Problems (MAVRP) are variants of Vehicle Routing Problems (VRP) in which, besides the original constraint on vehicle capacity present in Capacitated Vehicle Routing Problem (CVRP), there are other restrictions that model diverse real-life system attributes. Among the most common attributes studied in the literature are the vehicle capacity and the maximum route length constraints. The impact of these restrictions on the overall structure of the problem and on the performance of local search algorithms used to solve it is not well known. This paper aims to explain how constraints impact different variants of VRP by altering the structure of the underlying search space. We focus on the analysis of Local Optima Networks (LON) for multiple Traveling Salesman Problem (m-TSP), and VRP with capacity (CVRP), distance (DVRP), and both (DCVRP) constraints. We present results that indicate that metrics obtained for a sample of local optima provide valuable information on the behavior of the landscape under modifications in the constraints of the problem. <br> The dataset contains the data extracted from the local optima network for a set of variants belonging to the family of vehicle routing problems.多属性车辆路径问题（Multi-Attribute Vehicle Routing Problems, MAVRP）是车辆路径问题（Vehicle Routing Problems, VRP）的一类变体。除带容量限制车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）中固有的车辆容量约束外，该类问题还包含诸多用以建模现实场景中多样化系统属性的额外限制条件。现有文献中研究最为常见的属性包括车辆容量与最大路径长度约束。目前，这类约束对问题整体结构以及求解所用局部搜索算法性能的影响尚未被充分厘清。本文旨在通过改变底层搜索空间的结构，阐释约束如何影响各类VRP变体。我们聚焦于分析多旅行商问题（multiple Traveling Salesman Problem, m-TSP）、带容量约束的车辆路径问题（CVRP）、带距离约束的车辆路径问题（Distance Vehicle Routing Problem, DVRP）以及同时兼具容量与距离约束的车辆路径问题（Distance and Capacitated Vehicle Routing Problem, DCVRP）的局部最优网络（Local Optima Networks, LON）。研究结果表明，针对局部最优样本提取的指标，可为约束修改下问题景观的行为特征提供极具价值的参考信息。<br>本数据集包含从车辆路径问题家族的多类变体的局部最优网络中提取的相关数据。