英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
如何优化一个VRP解决方案?以特定问题的知识来建立启发式
Florian Arnoldlowast;, Kenneth Souml;rensen
摘要
启发式是解决复杂的组合优化问题的常用算法，大量的研究都集中在某个特定问题的启发式优化上，但是很少有人研究这类问题本身的结构特征。
我们认为，区分好与不太好解决方案的组合优化问题时有关结构特征的知识，有助于设计有效的启发式。我们开发了一种基于数据挖掘的方法来生成这些知识并将其应用于车辆路径问题。
我们定义了几个指标来描述VRP解决方案和VRP实例，生成并分类了192种解决方案。根据这些度量，我们可以区分最优和非最优解决方案，准确率高达90%。我们讨论了优秀VRP解决方案最显著的特征，并展示了如何使用由此产生的知识来改进现有启发式的性能。
介绍
对于许多组合优化问题，基于局部搜索或构造策略的启发式已被证明能够在解决方案质量和计算时间之间提供最佳的平衡。近年来，启发式策略的效率在很大程度上取决于它能否很好地利用所解决问题的特性。换句话说，为了尽可能高效，启发式搜索策略需要一些关于如何区分好的解决方案和不那么好的解决方案的知识。然而在许多情况下，这种认识局限于一个细微的事实，即前者的目标函数将比后者更接近于最优。有一个仍未得到答案的问题，是否能确定好的解决方案在结构上不同于不那么好的解决方案，即我们是否可以通过只看解本身而不看它们的目标函数值，来区分接近最优解和不那么接近最优解。如果有的话，这些信息可以用于指导搜索，如通过删除在接近最优解决方案中不经常出现的解决方案属性，然后用经常出现的属性替换它们。
本文的目的是研究相对于VRP不太好的解决方案，好的解决方案具有怎样的特征？这些特征可以用来指导搜索。例如，假如有可能识别出在好的解决方案中不太可能出现的边缘，那么可以采用一种策略来尝试删除这些边缘。引导启发式搜索过程并使其适用于所解决的特定问题实例的思想，已经引起了大量的关注。例如，自适应大邻域搜索(Pisinger和Ropke, 2010)试图在解决过程中找到最好的操作符。Souml;rensen等人主张在可变邻域搜索算法家族中采用类似的自适应概念。Juan等人将启发式与仿真技术相结合，允许使用来自仿真的反馈来优化启发式的设置。McNabb等人没有在搜索过程中调整操作符，而是在执行搜索之前，使用彻底的统计分析来识别良好的操作符。
比起调整已有的启发式，Burke、 Marshall等人更进一步，提出超级启发式，来自动选择和生成合适的启发式。例如，Drake等人提出了自动生成并改进可变邻域搜索算法的分量。
所有这些方法都试图通过将启发式应用于正在解决的问题实例，将搜索引向解决空间中有希望的区域。然而，这些方法都没有在搜索之前分析哪些属性有助于提高解决方案的质量。对潜在问题的分析是有用的，这已经在调度问题中得到了证明(Aickelin和Dowsland, 2000)。本文利用经验数据探讨了一个实际车辆调度问题的结构，并将研究结果成功地应用于启发式问题中。据我们所知，对于VRP(或任何其他路径问题)不存在这样的分析。
我们的方法使用数据挖掘技术来发现VRP的特征，这些特征可以将好的解决方案与不太好的解决方案区分开来。数据挖掘的目的是在大量数据中找到识别模式和建立关系的模型。与统计相反，这些模型的目标“不是推断真实的分布，而是尽可能准确地预测未来的数据”(Shmueli等人)。换句话说，使用数据挖掘，我们的目标是预测以前未见过的数据，而不是解释手上已有的数据，重点是寻找联系而不是寻找原因。因此，我们也谈到预测建模。尽管预测模型可能缺乏解释力，但以探索性的方式发现和测试新理论是有用的。
任何预测模型的输入都是一个数据集，根据经验，更多可用的数据点和每个数据点更丰富的信息会产生更好的模型。每个数据点的信息称为它的特征。例如，我们可以预测一个特定的客户是否会被一个新的营销活动所说服。前一次活动的数据集可以由特征性别、年龄、家庭状况和邮政编码组成，以及用户是否响应该活动的信息。分类学习者建立一个模型，试图在数据中找出区分不同类别的模式。那些对上一个活动做出回应的客户，来自那些没有回应的客户。这个过程也称为分类。该模型可用于预测未来的数据点，即，潜在的收件人是否会回应新的运动。从简单的决策树，到随机森林(Breiman)和支持向量机(SVM) (Hsu等人)，有各种各样的分类学习者可供选择。
预测模型不一定提供因果解释。然而，有可能推出一些因果理论。如果我们使用简单的线性模型作为预测模型，可以通过观察它们的系数来解释不同特征的相对重要性。如果内部模型是非线性的，我们可以使用规则提取来获得一组解释预测的规则(Martens等人)。这样，我们就能从数据中推断出理论。由于这些理论是广义的发现，可以很容易地应用到新的数据，我们将在下面使用术语知识。问题的特征通常是一组具有相关性或代表性的实例，例如以实际问题为基准的实例。如果关于问题的发现可以推广到所有相关的实例，我们就可以研究特定问题的知识。
本文其余部分的结构如下。在第2节中，我们将描述如何定义和生成VRP的数据点，然后这些数据会被用作分类学习器的输入，分类学习器可以洞察问题的结构。我们在第3节中提出并讨论了相应的结果。在第4节中，我们通过一个案例研究来证明这些见解有助于设计更有效的启发式，并在第5节中总结我们的结果。虽然我们从VRP的角度描述了整个过程，但是所描述的技术和思想可以适用于广泛的相关或不相关的组合优化问题。
从问题到数据
我们生成关于如何使VRP实例的解决方案更好的知识的方法由三个主要步骤组成:(1)生成数据，(2)构建预测模型，(3)从预测模型中提取知识。后两个步骤主要涉及技术挑战，而第一个是高度探索性的，需要创造力和对细节的关注。由于我们只能从我们创建的数据和定义的特性中推断出结果，因此数据生成是最重要和最困难的步骤。下面，我们将描述VRP的数据生成过程。首先，我们生成随机的和不同的实例，然后为其计算解决方案，最后将其转换为一个特征空间。
实例
VRP是一个复杂的问题，具有以下部分属性：(1)客户的定位和数量；(2)车辆段的定位；(3)需求的分布；(4)平均路线大小或路线数量（由车辆容量来定义）。通过在合理范围内随机选择特定实例的属性，我们尝试对一组具有代表性的实例进行抽样。根据这些界限的定义，我们可以自动得出不同实例类的定义。
我们定义了一组包含20-50个客户的小实例，以及一组包含70-100个客户的大实例。因此，客户随机而均匀地分布在一个平方1000times;1000的网格上。在这些实验中没有考虑顾客的聚类问题。我们还分别为仓库的位置和需求分布定义了两个类。仓库要么位于网格中心位置500x500，要么位于网格边缘，即，一个坐标随机选择，另一个设为0。同样地，客户需求的差异要么很大(随机选择1到10之间)，要么所有客户都有相同的需求。对于这三个类的每个组合，我们生成一个数据集，因此，我们总共生成八个数据集，如表1所示。最后，我们以这样的方式随机定义车辆容量，即在较小的类中有3到6条路线，在较大的类中有6到10条路线。我们注意到，我们本可以再引入两个类，其中一个包含信息少一点，路线多一点。然而，这样做会使实验的数量超出可行性。
在所有的实例中，我们解决了VRP的标准变体。在两个客户之间采取某种优势的成本是由欧几里德距离定义的，我们的目标是最小化所有路线上行驶的总距离(Laporte, 2007)。这个标准定义的距离强加了一个重要的假设上的指标被罚款如下。例如，定义两条边是否相交是很简单的，因为每条边都是直线。在真实的道路网络中，这一假设可能不再成立，定义准确的指标可能更加复杂。
表1
求解方案
我们想要了解好的解决方案的特点。以不同的方式表达，我们可以问是什么将最优或接近最优的解决方案与较差的解决方案区分开来。如果我们找到了这些区别性的性质，它们将有助于更有效地找到那些好的解决方案，这就是每一种启发式的目标。因此，我们需要计算和比较不同质量的解决方案。
近似最优解的计算和非最优解的计算，略。
解决方案的度量
实例的度量
从数据到特定问题的知识
通过上述过程，我们希望通过以下方式获得特定问题的知识。我们生成实例，并为每个实例计算接近最优和非最优的解决方案。然后，我们从两个解决方案中提取定义的特征，并使用分类学习器找到两个解决方案类型之间的区别模式。
总的来说，我们为8个实例类中的每个类生成4个数据集。在这四个数据集中，我们根据与接近最优解的差距(2%或4%)和使用的启发式(H1或H2)来改变非最优解的生成。对于较小的实例类(20-50个客户)，我们为每个数据集生成大约5000个实例和大约10,000个解决方案。更大的实例需要更长的时间来解决，因此，对于拥有70-100个客户的实例类，我们将数据限制在大约1000个实例和2000个解决方案。在本研究中，我们总共计算了大约192,000个VRP解决方案。对于每个计算的解决方案，我们派生出相应的解决方案度量S1-S10和实例度量I1-I8，它们连同一个表示解决方案是接近最优还是非最优的标志，构成数据集的一个数据点。使用启发式H1生成的非规范化原始数据可在http://antor. uantwerpen.be/problem-knowledge上获得。
我们使用MATLAB的分类学习程序对每个数据集进行分析，使用5次交叉验证。简而言之，学习者使用一定比例的随机选择的数据点(训练集)来测试一个内部预测模型，该模型试图区分接近最优解和非最优解。然后利用剩余的数据点(验证集)对该预测模型进行验证。可以量化的质量预测模型的预测精度,所定义的正确分类的百分比数据点的验证集。预测精度高于50%显示有预测模式中的数据,因为有尽可能多的数据点与算法相关的解决方案，和最优的解决方案,可以获得50%的准确性。
预测精度
作为分类学习者，我们使用简单的决策树、随机森林和线性支持向量机。因此，线性支持向量机(默认设置:框约束水平= 1和自动内核规模)表现最好的所有数据集。在使用线性支持向量机之前，我们将所有特征归一化到相同的范围(0-1)。在表2中，我们报告了每个数据集的相应预测精度。从这些结果我们可以得出以下观察结果。
对于所有数据集，我们获得的预测精度明显高于50%。换句话说，如果我们给预测模型在定义的参数范围内的任何实例的任何解决方案，它可以告诉我们解决方案是否接近最优或概率高达90%的非最优。这表明，至少在我们在上面定义的一些解决方案度量中有预测能力。因此，与非最优解相比，S1到S10的一些特征值在单独或与其他特征值相互作用时，更具有接近最优解的特征。因此，我们生成非最优解的方式，无论是H1还是H2，似乎对预测精度影响不大。我们只观察到具有中心仓库位置的小实例(类1和类2)的差异，对于这些小实例，初学者似乎很难找到用H2生成的非最优解决方案的独特特征。
一般来说，预测能力似乎取决于非最优解和接近最优解之间的差距。间隙越大，预测精度越高。这是可以预料到的，因为解值的差异越大，两个解在结构上的差异也越大。
表2
解释预测
这些结果提出了一个问题:“不同质量的解决方案之间有哪些可预测的差异?”为了获得一些解释，为什么分类学习者预测的方式，我们可以估计每个指标的个人贡献的预测模型。
对于每个数据集和解决方案度量，我们使用一个简单的决策树构建一个预测模型，只使用相应的解决方案度量和八个实例度量作为特性。我们允许树中最多有9个分割，因为我们在这个模型中有9个特性。该模型的预测精度是对相应解度量的预测能力的估计。
解释预测的准确性，略。
从解释到规则
到目前为止，我们只单独考虑解决方案度量来解释结果。在下面，我们还想考虑度量之间的相互作用，并得出一些规则，这些规则告诉我们某个解决方案是否以及为什么被归类为非最优的。对于每个数据集，我们再次构建一个简单的决策树，这次使用所有特性。一个分类树根据最具预测性的指标产生分支，它的叶子包含“接近最优”或“非最优”的类标签。指向每个叶子的分支可以转换为一个规则，由一组特定特性的值范围表示。如果一种溶液满足这些条件，它就根据被定义的类别标签被分类。
这些规则构成了关于接近最优解和非最优解之间差异的更详细的知识，可能具有很大的实践价值。假设我们有一个特定实例的非最优解，我们想知道，这个解如何进一步改进。我们只需计算相应的解决方案指标和实例指标，并找到将解决方案划分为非最优的规则(如果解决方案已经最优或接近最优，则可能不存在这样的规则)。该规则的条件指出了此解决方案非最优的可能原因。
示例，略。
特定问题知识在启发式设计中的应用
在以上几节中，我们对好的VRP解决方案的本质有了深入的了解。在本节中，我们将使用一个案例研究来描述这些知识如何有助于在实践中设计更好的启发式，即，具体问题的知识如何在搜索过程中用作指导。VRP实例的解决方案可以表示为车辆遍历的一组边。与非最优解相比，知识在接近最优解中出现的频率更高，这些知识可以用于多种启发式方法来指导搜索。
在本节中，我们研究了一种引导局部搜索(GLS) (Voudouris and Tsang, 2003)启发式算法，并对其进行了调整，以便根据上面生成的信息对边缘进行惩罚和删除。GLS已经成功地应用于TSP (Voudouris and Tsang, 2003)和VRP (Mester and Braysy, 2007)，并因其简单和有效而脱颖而出。
GLS启发式算法的应用，略。
这些发现表明，当问题实例变得复杂时，特定于问题的知识变得更有价值。随着复杂性的增加，在搜索的每一步中可能的选项的数量也会增加，因此，即使是有限的知识也可以帮助做出更好的决策。
总结 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235911]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
