实例空间分析的带容量车辆路径问题-计算机科学-机器学习-算法.pdf

实例空间分析的带容量车辆路径问题

AlessandraM.M.M.Gouvêa1ID,NunoPaulos1ID,EduardoUchoa2ID,MariáC.V.Nascimento1ID

1DivisãodeCiênciasdaComputação,InstitutoTecnológicodeAeronáutica(ITA),SãoJosédosCampos,SP,Brazil

2DepartamentodeEngenhariadeProdução,UniversidadeFederalFluminense(UFF),Niterói,RJ,Brazil

摘要—本文旨在通过解决理解实例特征与元启发式区域[5]。元启发式方法的比较分析通常依赖于先

算法（MH）性能之间微妙关系的挑战，推进CVRP研前建立的基准实例。然而，未能优先选择实例可

究。我们提出实例空间分析（ISA）作为一项有价值的工能会产生偏向某些MHs的一组有偏见的实例。因

具，可以为该领域提供新的视角。通过结合ISA方法论

此，适当考虑实例的异质性对于保证更稳健的比

本和DIMACS第12届车辆路径实现挑战的数据集，我

译们的研究能够识别出23个相关的实例特征。我们使用了较分析至关重要。此外，需要一组最优的实例可以

中PRELIM、SIFTED和PILOT阶段，这些阶段采用了揭示当前基准的局限性，并指导新实例的创建。尽

降维和机器学习方法，使我们能够创建一个二维的实例空管有这些论点，在VRP文献中很少有研究关注这

2

v间投影，以理解实例结构如何影响MH的行为。我们工作些问题[6]–[8]。

7的关键贡献之一是提供了一个投影矩阵，这使得将新实例在传统比较研究中发现的问题——特别是使

9纳入分析变得简单，并为CVRP领域的实例分析提供了

3用过于同质化的基准和基于中间性能的分析——

0新的方法。

1IndexTerms—带容量限制的车辆路径问题，实例空并不局限于VRP领域。为了解决这些不足，凯特·

.

7间分析，元启发式算法史密斯及其同事发表了一系列作品，最终形成了

0一种名为实例空间分析（ISA）[5]的方法论。ISA

5

2I.介绍作为一种有前景的替代方法，在文献中出现，其关

:

v车辆路径问题（VRP）是文献中广泛研究的注点在于评估算法的不同方式。ISA方法旨在构建

i

x一种组合优化问题[1]。目标是在满足客户需求和问题所有可能实例的全面视图。通过描述实例的

r

a运营约束的同时，找到车队的最低成本路线集。最特征并应用降维和机器学习技术将每个实例映射

经典且被深入研究的VRP变体是有容量限制的到一个二维空间（称为实例空间），ISA改变了对

VRP（CVRP），其中车队同质化，并且对路线的算法评估的关注点，转向了对实例、算法及其特性

唯一限制是服务需求之和不超过车辆的容量。关之间关系的视觉探索。通过提供可视化、分析和生

于CVRP元启发式算法（MHs）的文献丰富，因成测试实例的工具，ISA为更可靠地评估算法性能

为量身定制的MHs能够以较低的计算成本提供良以及基于实例特性的深入理解铺平了道路。

好的解决方案，特别是对于大规模实例[2],[3]。文本文通过ISA方法论评估了设计用于CVRP

献普遍认为，没有任何一种MH能够在某个特定的一组算法的实例与算法性能之间的关系，从而

优化问题的所有实例中表现出理想性能。因此，研对CVRP实例空间进行了研究。所使用数据来自

究人员自然寻求确定是什么因素使MH在特定问DIMACS第12次VehicleRouting实现挑战赛。提

题实例中的表现良好，这直