面向实时供应链计划的混合主动系统优化工具及其应用

可在www.sciencedirect.com上在线获取计算设计与工程学报4（2017）698www.elsevier.com/locate/jcde面向实时供应链计划Jonathan Gaudreault，Claude-Guy Quimper，Philippe Mariern，Mathieu Bouchard，FrançoisChéné，Jean BouchardFORAC研究联盟，拉瓦尔大学，魁北克，加拿大G1V 0A6接收日期：2016年8月23日;接收日期：2016年11月21日;接受日期：2016年12月26日2016年12月30日在线发布摘要混合主动系统（MIS）是一种混合决策系统，在这种系统中，人和机器协作以产生解决方案。本文描述了一个适用于企业优化问题的管理信息系统这些问题通常可以在不到一个小时的时间内解决，因为它们显示出线性结构。然而，这种延迟对于用户需要提供其输入的迭代和交互式决策环境是不可接受的。因此，我们提出了一个系统，为决策者提供了一个凸包的最佳解决方案，最小化/最大化的变量的利益。用户可以交互式地修改变量的值，系统能够在几毫秒内重新计算新的最优解。四个实时再优化方法的描述和评价。我们还提出了一个改进的基本方案，以允许用户探索接近最优的解决方案。给出了我们如何利用这个框架内的交互式决策支持软件的真实情况下（http://creativecommons.org/licenses/by-nc-nd/4.0/）中找到。关键词：线性优化;混合主动系统;供应链优化;人机交互;战术规划1. 介绍企业中的大多数决策系统（例如计划或调度系统）都依赖于以下范式之一。第一个是全自动系统。这是典型的情况下，当一个算法被用来找到一个最佳的解决方案的决策问题。在其他情况下，规划是由人类专家完成的，有时在视觉界面的帮助下，他可以得到关于他的决定和选择的实时反馈。令人惊讶的是，相当多的优化问题是手动计划的。实际上，自动规划工具缺乏政治敏感性，或者更普遍地说，没有考虑许多重要的软约束，这些软约束通常很难建模（约束n通讯作者。电子邮件地址：philippe. forac.ulaval.ca（P。Marier）。由计算设计与工程学会负责进行同行评审。即使是人类在看到违反它们的解决方案之前也不会意识到它们的存在）。混合主动系统（Mixed-Initiative-Systems，MIS）[1，2]是一种混合决策系统，在这种系统中，人类和机器协作以产生解决方案。大多数与MIS相关的研究都是由人工智能完成的。社区，并适用于离散组合优化问题。我们的研究的目标是提出适合业务优化问题的MIS方法，表现出线性结构，如中期/长期生产计划问题。我们的方法可能适用于许多类型的行业，因为它更面向问题，而不是面向行业。它特别适合于人类参与最终决策的问题（需要人类对解决方案进行微调，或者人类想要执行假设分析）。在这两种情况下，都需要系统的实时支持（而不是长达一小时的重新优化）第2节提供了有关MIS和供应链优化的初步概念。提出的混合主动系统的线性优化进行了描述，http://dx.doi.org/10.1016/j.jcde.2016.12.0012288-4300（http://creativecommons.org/licenses/by-nc-nd/4.0/）中找到。70J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）6985在第3节中，对一个实际规模的工业供应链问题进行了评估。第4节介绍了最优容差，以改进探索解决方案的灵活性。最后，第5节展示了我们如何在决策支持软件中利用这个框架，并介绍了最近的工业应用。第六节是论文的总结。2. 初步概念2.1. 混合主动系统（MIS）MIS背后的动机是人类和机器表现出不同的力量[3]。人类对问题有一种隐含的知识，这种知识并不总是形式化的。人工指导可以提高搜索算法的性能[4]。此外，决策者通常不知道一个约束或一个问题，直到他看到它在机器提出的解决方案。在这种情况下，让人类参与寻找解决方案具有一定的价值。人类参与模型优化的想法可以追溯到早在1971年Benayoun等人的工作。[5]在多目标优化的背景下。正如一些作者[6，7]所提到的，现在人们普遍认为人机交互在解决复杂的优化问题中是有价值的。根据不同的情况，MIS提供不同的好处。在某些情况下，使用更少的计算时间产生解决方案，因为用户可以根据他的直觉指导搜索[4]。这是因为人类在视觉感知和战略思维方面通常优于计算机。在其他情况下，主要利益是最终解决方案得到决策者更好的接受程度，因为它更符合公司/决策者的非正式目标。决策者也更容易证明和改进他们参与的解决方案，他们可以实现他们的偏好和对现实世界的了解，而无需复杂的，有时几乎不可能的数学建模。虽然理论上可以通过使用解释功能来增加用户对解决方案的信心，但对于决策支持系统的设计者来说，构建这样的功能是一项艰巨的任务[8]。Meignan等人[6]对运筹学中的交互优化方法进行了广泛的回顾和分类。他们的审查使他们能够列举五类交互式优化方法。作者解释说，交互式重新优化的目的是调整全局解决方案时，由用户对一个给定的解决方案进行局部更改。由于所有约束仍然被强制执行，局部变化通过重新优化传播到全局解[9]。在[10]中报告了一些交互式重新优化方法。在这些情况下，在决策者修改解决方案后应用重新优化程序。这是通过在再次优化之前将用户所做的修改冻结到问题中来完成的。当优化本身需要很长时间时，这种类型的方法不适合。此外，在交互式地找到满意解的同时，一次又一次地添加约束可以消除求解器找到具有良好目标的值另一方面，仅固定最后作出的修改并不能确保所有先前作出的修改均会得到尊重。例如，Williams等人[11]正在使用基于游戏的实验来评估碎片收集问题背景下“人在回路中“优化的潜力在他们的方法中，用户可以自己调整多个目标，并且可以使用工具来创建解决方案，并对他们正在构建的解决方案提供即时反馈。大多数MIS相关的研究针对离散的组合优化问题，如调度[12]，空间任务规划和调度[13不同的应用程序域提出了独特的挑战。一个问题是出现在许多领域的规划和调度约束的多样性。Smith等人[19]开发了一个计算机化的框架，允许构建针对特定领域需求的混合主动系统。他们的系统主要用于部队部署的规划和时间安排。混合主动系统还没有进入商业管理系统，如用于供应链管理（SCM）的系统。我们认为主要原因是（1）大多数这些情况可以建模为线性优化问题，存在良好的算法，以及（2）为经典AI开发的方法。规划不容易适用于这类问题。2.2. 供应链优化我们的研究目标是提出适合于线性结构模型的商业问题，如供应链优化问题的MIS方法。供应链是由一组合作生产商品的业务单元组成的。战术供应链计划包括计算给定时间框架内每个时期的产品生产、消费、储存或运输量，并有一个精确的优化目标。共同目标是成本最小化或利润最大化[20，21]。战术供应链规划是森林产品行业非常重要的问题[22]。一个单一的业务单元从一种原材料同时这导致了业务单位之间的重要相互依赖性（例如，森林业务同时为许多不同类型的行业提供服务，锯木厂为再制造工厂提供木材，以及为造纸厂提供芯片等）。已经提出了许多数学模型[23，24]，但大多数时候，它们并没有利用决策者这 些 问 题 通 常 使 用 商 业 上 可 用 的 软 件 （ 如 IBMCPLEX）来解决。他们可以在几分钟内解决具有数十万个变量的问题，这要归功于著名的算法，如Dantzig的单纯形法[25]。这些求解器的一个缺点是，它们通常会为给定的问题（定义为一组变量，约束和目标函数）大多数时候，返回的解决方案是不充分的，因为问题J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）698571图1.一、决策者用来分析供应链优化问题解决方案的图表示例例如，该图表可以是在未来12个月内在给定市场中交付的产品系列的数量具体化没有考虑到只有决策者才知道的背景和政治信息[4]。在数学模型中考虑用户的所有偏好确实非常困难。此外，决策者并不确切地知道所有的约束;当他看到解决方案违反这些约束时，他会尽管求解器产生的解通常包含数十万个变量，但在实践中，决策者仅通过查阅几个图表来分析解，每个图表包含几十个变量（例如，52个变量匹配一年中的52周）。这种类型的图表的一个例子是提供在图。1.一、当解决方案不满足决策者的要求时（例如，他不喜欢特定变量的值），数学模型必须进行修改和重新优化，以便找到新的解决方案（图2）。这个过程不仅非常长（解决一个集成的供应链计划问题可能很容易需要60分钟），而且这也是一个令人沮丧的迭代过程，因为当决策者对变量的值不满意时，他永远不知道变量是否真的被限制在该特定值以使解决方案成为最佳，或者是否存在其他变量的其他值的其他最佳解决方案。他别无选择，只能运行新的优化。3. 线性优化问题一个好的线性优化的混合主动系统将为用户提供关于感兴趣的变量是否被约束到某个值的信息，以使解决方案是最佳的。它还允许用户交互式地修改变量的值，并实时查看其他变量应如何修改以响应该修改。我们提出的系统允许用户可视化一组给定变量的最优解的隐式子空间。用户可以交互式地增加或减少图二. 寻找合适解决方案的典型过程。图三. MIS概念应用于线性规划。值的变量和系统的反应，计算和显示，在实时，新的子空间的最佳解决方案（图。 3）。不同的决策者所关心的变量可能不同。这必须由决策支持系统所针对的用户来确定。这些变量通常是聚合变量（例如：按市场划分的季度销售额;每月生产线使用量这些变量的良好表示（例如在Excel图表中）必须设置为从人类的角度来看是可管理的3.1. 获得并显示最优解的子空间为了缓和经典求解器返回单个解的事实，我们如下进行。我们使用经典求解器来计算问题P的最优解。一旦最优目标值已知，我们就搜索其他最优解。我们通过用约束增强实例P来创建新实例P72J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）6985.Σ¼公司简介¼¼（十）n.Σ[001 pdf1st-31files]图四、一个最优解，具有变量的最优范围等于P的最优值。因此，P'的可行解对于图上显示的n个变量xi中的每一个，我们搜索最小化xi的解si和最大化xi的解si，同时保持解的最优性。这2n个计算可以用一台超级计算机1然后，可以在图表上显示（见图4）每个变量xi的最优范围（变量在最优解中可以取此外，可以通过对2 n个解向量求和并将结果除以标量2n来构造要显示给用户的这个过程的有效性依赖于我们提出空间SxAxrb;xZ0包含线性规划的可行解。设xAS和yAS是两个解。我们证明了x和y的任何凸组合都属于S。Aαx1- αyαAx1- αAyrαb1-αb，因为αA ½0;1]1/4b假设x和y是线性规划的两个最优解，即x使标积c T x最大化，y也使标积c T x最大化。设cncT x cT y为最优成本。我们证明了x和y的任何凸组合也是最优解。⎕一组点X的凸壳！x1;.;！Xn是包含X中所有点的凸组合的空间。正式地，我们注意到贝娄.一个n维向量表示分配给n的值变量，因此是问题的解决方案一种载体还conv. ！x1;.;！联系我们n1/1αi！Xi.αiZ0;iX¼1（1）表示n维空间中的一点。设x和y是两个n维向量.线性组合是两个或多个向量的加权和，例如，αx<$βy。线性从定理1，如果点！x1;.;！xn是线性规划的最优conv！x1;.;！xn是最佳可行解。如果权重之和等于1，则组合是有效的，例如：αx1-αy。直线上任何一点经过点x和在我们的系统中，解si和si的凸包，y是x和y的最佳组合。一个线性组合是凸的，如果它是无偏的，并且每个权重都是非负的，例如αx1αy对于αA0;1。通过x和y的凸组合可以得到的点是连接x和y的线段上的点。一个空间S是凸的，如果S中两点的任何凸组合也在S中。定理1是线性规划文献中的一个众所周知的结果（例如[26]）。它展示了如何从不同的最优解的凸组合中获得线性规划的最优解。我们重现定理的证明，因为它显示了我们将在我们的系统中利用的属性。定理1. 线性规划的两个最优解的凸组合也是最优解。1如果并行计算不可用，则可以在使用交互式工具之前在单个计算机上运行过夜。最小化和最大化n个变量中的每一个形成最优解的子空间3.2. 最优解图4所示的图表允许用户查看他对任何感兴趣的变量的可伸缩性（最优范围）。因此，他可以在变量的最优范围内更改该变量的值，例如通过向上或向下拖动图表中的条形图的顶部。然后，系统应该调整其他变量所取的值，使得解决方案仍然是最优的。通常，此操作需要对问题进行冗长的完全重新优化。基于定理1，可以通过生成从前一部分获得的最优解的新凸组合来计算新的最优解。为了找到一个给定变量分配给一个特定值的解，计算一个新的凸组合就足够了。J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）698573ðÞ¼..我¼--我-..i¼1.我们得到如下的图五. 可用凸组合的最优区域。响应速度以毫秒为单位。稳定性由原始解x和修改后的解x'之间的欧几里得距离由于响应性是一个重要的标准，我们排除了从头开始解决原始问题的方法。我们限制自己找到一个解决方案，在凸包的2n预先计算的解决方案s1;s1;以下是建议的方法。1. 最小化Euclidean距离这种方法的目的是在凸包convs1;s1;...; s n ; s n中找到欧氏距离最接近x的解。设S为列为解的n~2n矩阵s1;s1;我们要找的解是一个凸这些解决方案的组合因此，我们正在寻找极端的解决方案。如果这可以实时完成，我们可以即时刷新图表并显示用户的影响向量α使得x0<$Sα，P2 nαi<$1，αiZ 0。更多-结束，我们需要x0修改其他变量。因此，用户可以在解决方案空间中导航，连续修改几个变量，直到找到合适的解决方案图5说明了一个有两个变量的小问题的这个想法。多边形表示由最小化和优化每个变量的最优解形成的凸组合的集合。2当用户修改一个变量时，我们不只是想在子空间中找到任何一个点，使得修改后的变量取所需的值;我们想找到一个解决方案，使得其他变量尽可能少地移动，以便整个系统看起来是稳定的。如果不是这样，那么对一个变量所做的任何修改都可能抵消之前对其他变量所做的修改，用户永远不可能收敛到令人满意的解。给定一个解x，一个变量xi和一个值v，找到一个新的解x0，其中x0ivaxi，同时尽可能少地改变其他变量的值是一个优化问题。我们提出了四种方法来解决这个优化问题。它们中的每一个都是响应性和稳定性之间的权衡。定义1. 响应性是指决策者每次修改变量时获得新解所需的计算时间。它确定软件可以显示新的优化解决方案之前的时间。定义2. 稳定性是计算尽可能接近当前解的新解的属性。响应性保证了软件对决策者的变化做出实时反应，而稳定性保证了软件不会将解决方案从决策者先前做出的选择[2]这个例子（图5）还表明，可能存在未被这个子空间覆盖的最优解。这就是为什么我们说用户在一个空间（由我们的极端解的凸组合形成）中导航，这个空间实际上是最优解的子空间。i等于v二次问题，其中e i是具有零分量except的向量，用于hit hi thiisequatone，！1是与所有组件相等的矢量，并且！0是最后一个向量：min α-Sα-δ2时间：eTSv！1Tα 1阿尔法Z0平方欧几里德距离<$x Sα<$2可以重写为αTST Sα2xTSα xT x。这个问题是一个半无限程序。目标函数为二次凸函数，约束条件为线性。像CPLEX这样的求解器可以使用内点算法来解决这个问题。2. 最小化最大距离。即使半定问题可以有效地解决，它们比线性规划更需要计算。我们提出了另一种可能更快的方法。我们不是最小化新旧解之间的欧氏距离，而是最小化最大距离之间两 变量，即我们尽量减少g¼ max jx j-x0j. 我们提出的线性规划是受前一个的启发。我们再一次计算向量α，它用存储在S（x0Sα）列中的2n个解的凸组合来表示x这个线性规划的前两个约束迫使变量g至少要像x0j-x j一样大。这个问题的未知数是向量α和间隙变量g。minGs：t：Sα-！1gRx-S-！1g r-xeTSα¼v！1Tα1阿尔法Z074J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）6985ð-Þ ð-Þ联系我们¼[1/2][2019 -04-21]¼--¼¼¼¼.Σ¼¼1个 1个;;n;n这个问题可以用单纯形法来解决，它通常比以前的方法中用于半有限问题的内点法更快。明显的缺点是目标函数不完全符合我们的稳定性度量。即使我们最小化两个相距最远的变量之间的距离，我们也不会最小化其他变量之间的距离。一个所有变量都改变相同数量的解x3. 一个两极启发式。我们引入了第三种方法，重点是响应性。双极启发式是一种非常快速的计算新解的方法。假设决策者希望将变量xi设置为值v，我们计算唯一的凸组合x0<$asi1αs i等 的 x0iv . 到 做 因此， 我们 设置 αS IIv=s iiSII 其中sii和sii是预先计算的解中的xi见图7。 说明三角形方法。x0¼αx±1-α±si哪里Xi. 这种方法的几何解释是，选择x到s i和平面xiv.这个解决方案是迄今为止响应最快的一个，因为它没有涉及任何解决方案。然而，它没有考虑稳定性度量。实际上，变量xi的一个小的变化可以对解的其他变量产生很大的变化例如，考虑平面中的一个示例，其中我们具有s11 1/4 / 2 -1;0]、s111/4/2 1;0]、s21/4/2 0;-1]和ds21/4/20;1]（see图6）。 设当前解为x 0：5;0的情况。一个小将变量x2从0移动到ε会导致x00;ε的解发生变化，即使解x00： 5;ε是a 更好的选择4. 三角启发法。为了减轻以前方法的不稳定性，我们提出了三角启发式（图7）。首先，该方法确定变量xi是增加（v4xi）还是减少（voxi）。如果变量增加，我们计算当前解x和si之间与平面xi¼v。如果变量减少，我们计算αsii-vsiixi如果决策者减少变量xi，我们设置x0¼αx±1-α±si哪里αsiivsiixi回到图6的示例，其中x[0.5，0]。增加X2通过ε集的新溶液到x00： 5ε= 2;ε。 这比双极启发式更稳定。两极启发式和三角启发式之间还有第二个区别对于给定的j，双极启发式只能产生位于连接解si和解si的线段上的解。三角启发式可以产生任何解决方案在这个convexhullconv.她...她...她... 我需要，这里当前解x之间的唯一凸组合和与平面xiv相交的si。换句话说，如果决策者增加xi，我们设置见图6。 说明双极方法的稳定性缺陷。决策者可以做出一系列的动作从而在凸空间中得到任何解财产1. 用三角启发法从解x开始的一系列移动可以到达任何解在凸包卷积中，s1;s1;...; s n ; s n n.证据设x设S是其列是凸壳的极值点的矩阵。存在一个非负向量α，其分量之和为1且满足x我们通过对α中非零分量个数的归纳证明了任意x假设α中存在一个非零分量。这个分量等于1，我们有x将当前解中的xj的值增加到其最大值或最小值，使得三角启发式fix新的解决方案xJ. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）698575¼¼þ¼þno.Σ设可达解xSα中有k40个非零分量，证明了可达解x'Sα与kβ中的1个非零分量。 设x'S β是一个有k的解β中的1个非零分量。设j是β中任何非零分量的指数。我们构造向量α如下。（0 ifi¼j每种产品的窑干体积和每种产品的刨平体积以及使用的刨平配方销售在北美森林产品工业中，木材市场价格遵循季节性模式。战术规划模型考虑到这一点，并可能建议提前生产一定数量的给定产品，将于年内稍后时间出售，届时市场ai¼βi1-βj如果我是j价格更有利可图。它还考虑了每个产品每个时期在给定市场上的解x^Sα是可达的，因为它只有k个非空值件. 此外，委员会认为， 让 是一个s k;s k被 溶液与分量βj相关联。可以使用三角启发法从解x移动到xx0<$1-βjxβjs<$Sβ这是当决策者将xk的值更改为x0k时计算出的关系。⎕性质1确保了凸包中的任何解都可以被达到。3.3. 对拟议办法以下案例研究的行业合作伙伴正在寻求制定一个有效的综合销售和运营规划（S OP）流程。作为该过程的一部分，使用了在[21]中引入的具有超过200，000个变量和100，000个约束的大规模线性规划模型。该模型为生产和分销网络生成统一的战术计划。该计划分为52个每周周期，并整合了与生产、分销和销售有关的决策。3.3.1. 工业案例生产锯木厂的木材生产包括三个主要过程：锯切、干燥和刨平。锯切过程是发散的，因为进入生产线的单个产品不同的生产配方可供选择，以提高产品木材干燥是在大型窑炉中分批进行的，该过程可持续2至5天，具体取决于几个因素，如品种，木材尺寸和原始含水量。窑干之前可能会进行空气干燥操作，持续2至18周。最后，刨削是使木材具有最终和精确尺寸的过程。由于木材的特性和缺陷，没有两个木材单位进入刨平过程是完全相同的。因此，在给定一组输入产品的情况下，不可能精确地预测退出计划过程的最终产品。历史生产计划数据用于估计给定投入产品的生产。战术生产计划有助于为网络中的每个锯木厂和每周确定要使用的锯切配方，每个锯切产品的风干量，运行该模型的用户还可以限制用于服务每个市场的生产分布该公司在加拿大魁北克省经营三家锯木厂，并利用美国东部的两个配送中心和魁北克的一个配送中心木材产品并运输也可以发生在工厂之间，因为在公司从没有刨削能力的锯木厂，干木材可以被转移到另一个有刨削能力的锯木厂，或者可以被运输到配送中心或直接发送给客户。该模型有助于确定将木材发送到哪里以及使用的运输方式，可以是卡车或铁路。考虑到市场需求、价格波动、生产能力和运输方案以及成本，规划整个锯木厂网络并非易事。为了解决这个完整的问题，使用CPLEX可能需要45分钟，CPLEX是解决线性规划模型的领先软件之一。3.3.2. 实验这些实验的主要目的是评估系统在稳定性和响应性指标（如第3.2节所定义）方面的行为。我们首先为前面介绍的工业案例生成了一个最佳解决方案。然后，我们模拟了决策者可视化不同数量的变量（1，10，20，30，40和52个变量）的各种图表的情况。对于每个变量，我们计算了它的最优范围。然后，我们模拟了决策者要求修改某些变量值的情况。我们测试了系统在小修改（变量增加或减少对应于其最优范围7%的差距）、中等修改（范围的45%）和大修改（范围的75%）时每次修改后，使用四种方法之一来计算最佳解决方案，并测量响应性（计算时间）和稳定性（原始和重新计算的解决方案之间的欧几里得距离）。3.3.3. 结果图8提供了系统响应性的结果（以毫秒为单位）。我们记得，解决每个原始问题76J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）6985见图8。根据显示的变量数量，对小（a）、中（b）和大（c）变量值修改的反应的解决方案重新计算时间（毫秒）。见图9。原始解与重新计算的解之间的欧几里得距离，根据显示的变量数量，经过小（a）、中（b）或大（c）变量值修改后。用户要求修改的时间将需要45分钟进行每次修改。使用所提出的方法，观察到的最坏情况是重新计算时间为600毫秒（欧几里得距离方法的最小化），见子图i。我们没有预料到这种方法的表现如此之好，因为解决二次优化问题所需的计算时间。尽管如此，问题似乎很小，足以提供良好的性能。然而，正如预期的那样，计算时间随着图表上显示的变量数量的增加而迅速增长。显然，在决策者需要可视化4或5个图表，每个图表上有52个变量的情况下，欧几里得方法无法满足我们的实时期望。子图i、ii和iii表明，用户要求的修改的大小对欧几里得方法的响应性有很大影响。修改越大（以最优范围的%表示），新解的计算就越容易。解释如下。在用户约束变量取其值xi的极端情况下，系统被限制为对应于我们的凸包的极值点的解。换句话说，没有太多的探索可以执行。最小化最大距离的方法的响应性不受变量更改量的影响。它的线性优化问题很小，很容易解决然而，这三种方法满足了我们的实时期望。图9显示了原始解和经过小（i）、中（ii）或大（iii）修改后的重新计算的解之间的欧几里得距离，并根据显示的变量数量。最小化欧氏距离的方法总是提供最佳结果。正如第3.2节所预期的那样，双极启发式给出了最差的结果。一个变量值的微小修改（子图i）会导致其他变量的巨大修改。更糟糕的是，beta测试人员认为新的解决方案是在没有考虑他们之前所做的任何更改的情况下计算的，这是不可接受的。对于小的修改（子图i），最大距离的最小化或使用三角启发式提供了非常接近于欧几里得方法的稳定性。实际上，对于最大距离的最小化，图上的结果与欧几里德方法的结果是模糊的J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）698577no我我见图10。当提供具有最优性间隙的解空间时，原始三角启发式的行为。然而，最小化最大距离有时会导致3.2节中讨论的问题情况，即，最大的变化被最小化，但是其他变量没有正当的原因而移动。三角启发式没有这个缺点。然后，我们分析了小型、中型和大型修改的影响（比较子表i、ii和iii）。用户要求的修改越大，不同的方法给出的结果就越相似。如前所述，对变量值的大修改导致所有方法都受到限制的非常小的最优解我们可以总结这一节，说最大距离的最小化和双极算法在解的稳定性方面都有缺点。在这方面，欧几里得距离的最小化是最佳的。它应该用于决策者基于对一小部分变量（通常是一个有十几个变量的图表）的分析做出决策的情况，尽管优化问题可能有数十万个变量。如果决策者需要同时分析和修改具有数百个变量的图表，则应该使用三角启发式，因为我们的实验报告了接近最佳的性能。4. 引入最优容差到目前为止，所提出的方法允许探索最佳解决方案。决策者也可能对探索接近最优的解决方案感兴趣（因为用于建模问题的数据通常是粗略的估计，不包括仅减少几美元利润的解决方案）。一变量的值在两个解之间插值，与这些解相关的利润值也是如此。因此，如果一个解是最优的而另一个不是，除非最优解的权重是0而非最优解的权重是1，否则由这些解的组合产生的新解将不是最优的。这不是原始三角形方法（前一节）的问题，其中所有解都是最优的。但是，如果我们包含最优性容差，我们就组合了非最优解。该结果是：（1）一旦变量被修改为与非最优解相关联的极值，即使目标值在该变量的最优范围内，系统也返回非最优解;以及（2）一旦达到非最优解，系统不返回最优解，除非变量被设置为与最优解相关联的极值。这种行为在图10中解释。在这个例子中，深灰色区域是真正的最优解空间。浅灰色区域显示了当我们容忍最优性差距时，这个空间是如何扩展的。在这个例子中，我们假设系统首先显示y最大化的解，然后用户要求逐渐减小x。一旦x开始减小，三角启发式算法在y和x之间插值时就会得到一个次优解。这是一个遗憾，因为很明显，对于x的某些值，我们仍然可以有一个最优（深灰色）的解决方案。由于以下原因，情况甚至更糟。假设我们使用求解器（例如单纯形法）来找到一个最小化/最大化给定变量的解，约束条件是网络的利润至少应为原始最优解利润单纯形可以返回一个最小化/最大化利润为95%的变量的解，即使存在另一个解，其中变量取完全相同的值，同时显示利润。100%为了缓解这种情况，我们在下一小节中引入了一种多阶段方法。4.1. 多阶段办法我们希望系统尽可能返回最优解。为了实现这一点，我们需要为用户有兴趣修改的每个变量xi提供两对解决方案。如原方法，一对解nx;xo最小化/最大化天真的方法可能是以下。当计算解决方案最小化/最大化一个给定的变量，我们容忍新的解决方案的利润和原始问题的最佳解决方案之间的差距。然而，当使用三角启发式时，这种方法不会很好地工作。与系统的互动显示，经常出现这样的情况：将变量调整到最佳空间内的值将返回接近最佳的解决方案，而一些现有的最佳解决方案显然是更好的选择。我们的目的是解释这种行为的原因，并提出另一种方法。当用三角启发式算法计算新的解变量值，同时保持最优性和另一对xi;xi最小化/最大化获得当最优性约束被放松时（根据用户指定的一些间隙）。我们还修改了三角启发式，使用容许极值点xi和xi进行只有在必要的时候。这种行为在图11中示出。在这个例子中，我们假设系统首先显示y最大化的解。然后用户要求逐渐减小x。只要x大于它在解x中的值，我们78J. Gaudreault et al. / Journal of Computational Design and Engineering 4（2017）6985见图11。 多阶段方法的行为。图十三.当在解决方案目标函数上提供5%的差距见图12。 小型木材供应链在解y和x之间插值，解仍然是最优的。过了那个点，我们在解x和x之间插值。4.2. 实验我们比较了所提出的多阶段方法与原始三角形方法和有容差的三角形方法。我们考虑了另一个供应链优化问题（木材库存供应链）。 这个问题在图12中用图形表示。从森林中收获的木材可以制成纸张或颗粒。这两种产品的生产成本相同，每根原木产生的收入相同纸张需求低于产能，这意味着必须生产最少量的颗粒以实现利润最大化。我们假设一个规划期为3个时期，总共有37个变量。一个变量是目标函数“利润“变量（1个然后，我们有从森林到每个工厂和从每个工厂到他们的市场（16个变量）的三个变量（3个时期和总数）每个市场（8个变量）的销售量（3个时期和总数）最后，我们有森林采伐和生产在每个工厂（3个时期和总数），这占12个变量。在这种小的情况下，所有的决策变量（除了代表目标函数值的一个被允许由用户改变，但在供应链的情况下，用户通常会想要改变网络中的单元和设施利用率之间使用原始三角形原始方法，变量的最优性范围决策者现在希望交互式地探索/发现接近最优的解决方案（最大差距）。5%），最符合他的喜好。引入耐受性应允许减少颗粒生产和/或减少森林采伐量。使用带间隙公差的三角形方法，变量应提供更大范围的最优性（在允许的5%间隙内），但用户对变量的大多数操作应导致非最优解（即使变量在其最优性范围内操作）。使用多阶段方法，我们应该对变量具有相同的最优范围，但是对这些变量进行小的修改应该会导致最优解。在下面的实验中，我们根据这些标准正式比较了这些方法：（1）变量的最优性范围，以及（2）在修改变量后计算的解决方案的最优性。对于每种方法，我们计算了每个变量的最优范围。然后，对于每个变量，我们递增/递减变量值，并测量新解决方案与原始解决方案之间的差距。图13显示了当我们允许5%的差距时，各个变量的最优范围是如何扩展的（与原始三角形方法相比）对于16个变量，当使用我们的新方法而不是原来的这些主要是与供应链中的纸张部分相关的变量：从森林到造纸厂的产品流量、造纸厂产量、从造纸厂到纸张市场的产品流量、销售的纸张数量。我们看到其他6个变量的最优范围增加了5%（供应链能源部分的总运输量;森林采伐总量和总利润），其他15个变量增加了15%（与供应链能源部分和森林采伐相关的变量的单期值）。带间隙公差的三角形方法的不良影响出现在预期之中。在72个“极端”解决方案中x最小化/最大化36个可操纵变量），52个是非最优的。除了颗粒生产和森林采伐变量外，即使对变量进行微小修改也会导致次优解决方案（其中颗粒生产和森林采伐减少）。因此，系统给用户一种错误的印象，他们不能修改这些变量而不改变最优性。J. Gaudreault等人/Journal of Computational Design and Engineering4（2017）69 8579使用多阶段方法，在对应于x;x;x;x的144个解决方案中，只有20个是次优的（它们对应于x0x或x4x）的情况所有其他在x和x之间的范围内的变量的操作导致最优解。这可以对任何变量进行验证，但我们在图14中报告了一个特定变量的结果。为了演示的目的，我们选择了一个即使在最优性差距为零时也具有一定最优性范围见图14。交互过程中返回解的最优性比较。对于这个变量，x和x的解是相同的，这就是为什么x没有出现在图表中。蓝色曲线表明，使用原始三角形方法，我们可以将变量从x修改为x，以及从x修改为x，并且新计算的解总是最优的。使用带间隙公差的三角形方法（红色），我们一从x向x移动，就离开了最优区域。使用多阶段方法（绿色），解决方案在x和x之间是最优的。只有当我们从x以下向x方向移动时，我们才离开最优性，这是预期的行为。类似的当我们回到x时，会显示行为。5. 在交互式决策支持软件5.1. LogiLab中的交互式供应链策略优化FORAC研究联合会以前开发了一个名为LogiLab的软件，用于设计、分析和规划森林产品供应链。LogiLab使用的数学优化模型由Jerbi等人描述。[23]。由于LogiLab的数据呈现对规划者来说具有强烈的吸引力和自然性，因此它为我们的交互式系统的集成奠定了自然的基础。在最初的LogiLab中，从一个业务单元到另一个业务单元的产品流是通过连接相应节点的弧来表示的。每个弧的厚度与从其起点到目的地的物流量成正比（见图1）。15）。由于我们现在要显示“范围图15. LogiLab图形用户界面。80J. Gaudreault等人/Journal of Computational Design and Engineering4（2017）69 85为了确定每个变量的“最优性根据这个比喻，管道的直径代表了Wavelow变量可以采用的最大值。管道的彩色部分表示通过管道的货物的当前水平（即当前最优解中变量的值）。为了表示最小值，使解决方案是最佳的，管道中的管道流的底部部分显示为较暗的颜色（见图1）。 17）。允许用户与管道交互的最简单和最直观的方法（为了让他调整变量的值）是简单地允许他点击管道，然后在最优范围内拖动鼠标。然而，大多数的窗口往往太小，无法进行适当的操作。因此，当用户将光标滚动到窗口上时，会出现放大的横截面并允许更容易的操作（参见图16）。交互场景如下：（1）用户在一个窗口上滚动;出现缩放气泡（类似于管道的横截面），允许用户（2）为这个窗口变量设置一个新值。最后（3），系统实时更新其他变量的值，从而计算出仍然是最优的可行解在最初的LogiLab中，使用类似于进度条的矩形显示业务单元的总容量百分比。我们为这些变量添加了最优性数据范围的可视化，使用的颜色代码类似于我们为Escherow变量提出的颜色代码。图17呈现了集成这些概念的图形用户界面。我们向我们的工业合作伙伴展示了这种与供应链解决方案的实时交互，他们对这种工具所提供的可能性他们不再需要图16. 与拟议系统内的数据流相互作用。更改数据输入或添加新的约束，并在他们认为某个变量不符合其值偏好时重新优化。他们只需单击并拖动一个流量/百分比利用率变量，就可以在拖动时实时查看其他变量值的变化它使他们能够更快地探索解决方案空间，以找到最适合他们偏好的解决方案5.2. 用于交互式优化的可定制通用仪表板Arabi等人。[27]提出了一个林产品行业的供应链战术规划问题，其形式与我们在前一节中所展示的相同。对于这个问题，优化是给了很大的结果相比，由公司所做的手工规划。他们的经理对供应链的建模感到满意，但