理论教育 基于启发式搜索的调整方法研究

基于启发式搜索的调整方法研究

时间:2023-06-28 理论教育 版权反馈
【摘要】:我们早就注意到对于一个包括n个仓库的网络设计,LogNet会考虑n(n-1)种整理。一个可能性就是使用基于启发式的搜索去减少LogNet考虑的可能性数目。启发法通过利用限制一个问题可选方案的数目的规则或计算程序,从而减少寻找问题解决方案所花费的时间。有许多我们可以用来限制LogNet考虑的可能的整理和分散的启发式方法。LogNet仅考虑同一区域内的仓库整理。然后LogNet会建议关闭这个仓库,它的库存会被整理到最近的仓库。

基于启发式搜索的调整方法研究

精明的读者可能已经注意到了前面讨论的一个基于模型程序的问题:对一个有许多节点的网络设计,问题容易变为计算不可行的,因为会有很多要考虑的网络设计可能性。这样的组合问题在人工智能中是众所周知的。在第1章中,我们辨识一个很有名的例子,旅行商问题,是一个很快成为计算不可行的问题。以下是问题的概述:给定一组城市,寻找以最短的里程走过每一个城市的路线。一个可能就是试遍所有可能的路线然后选择最短的(所有可能性的穷举搜索)。但是,对n个城市就有n!条路线,随着城市数目的增加,数目很快会变得很大。

我们早就注意到对于一个包括n仓库的网络设计,LogNet会考虑nn-1)种整理。但是,我们也指出这个数目仅表示一次采用两个仓库。它不会一次三个仓库,一次四个仓库或者更多,通常一次n个仓库。很显然随着网络包含仓库的增加,尤其当我们考虑一次n个所有可能的仓库合并的时候,可能性数目就会变得很大。

如果LogNet不得不按比例增加问题的尺寸和复杂性,它的必须手段不是穷举搜索。一个可能性就是使用基于启发式的搜索去减少LogNet考虑的可能性数目。启发法是一种在寻找一个问题的满意的但不一定最优的解决方案的简捷算法程序。启发法通过利用限制一个问题可选方案的数目的规则或计算程序,从而减少寻找问题解决方案所花费的时间。有许多我们可以用来限制LogNet考虑的可能的整理和分散的启发式方法。

一种启发法是仅考虑互相靠近的仓库的整理。事实上,人类后勤决策制定者经常会用仔细打量网络设计并将看起来互相靠近的仓库进行合并。我们可能通过仅考虑两者之间nmile内的候选的整理(n会作为由用户设置的输入参量)。例如,我们可能仅考虑彼此相距400mile之内的仓库的整理。如果我们回到由图7-11给定的后勤网络(这里5×4=20整理是可能的,每次2个),那么LogNet会仅考虑DALLAS和HOUSTON之间及NEW YORK和WASHINGTON DC之间的整理。沿这些相同的轨线,我们可能使用的另一个技术就是将一个网络分成区域。也就是,我们可能将一个后勤网络分成分离的区域,如东北部的仓库、南部的仓库、西部的仓库和中西部的仓库(一个仓库的区域可作为仓库的属性指定)。LogNet仅考虑同一区域内的仓库整理。

让我们考虑由后勤决策制定者使用的另一种启发法:仓库最可能的位置那些需求最大的中心或接近中心[11]。为了实现这种启发算法,我们对由“远的”仓库服务的“高需求”的顾客区的网络设计进行观测。我们可以让用户定义高需求和远的意思。例如,如果高需求定义为大于10000,远的定义为大于500mile,那么Log-Net会寻找与相连仓库位置大于500mile的高需求顾客区,并建议一个分散。也就是,添加一个离高需求顾客区较近的仓库。(www.daowen.com)

第三个启发算法如下给定:从分布立场看花费最贵的顾客是那些少量购买的顾客(也就是低需求顾客区)并位于运输通道的末端[12]。如果目标是减少网络成本,则LogNet将观测网络去寻找在同一个城市或相近的城市有一个仓库的低需求顾客区(比如说低于1000,这里由终端用户设置一个输入参量)。然后LogNet会建议关闭这个仓库,它的库存会被整理到最近的仓库。

但是这些对在很大的设计空间去减少搜索只有很小的可能性。(不管设计任务的固有的组合种类,)有更多的可能性会使我们能够利用基于模型的推理技术去解决后勤网络设计中更广泛的一类问题。

作为选择,在商业后勤管理中的仓库位置问题可能利用管理科学中众所周知的优化技术去解决。如线性规划、整数规划和动态规划这些定量法已经成功地应用到寻找许多网络设计问题类型的最优解。例如,优化技术能找到满足各种限制(例如顾客服务水平必须至少在一定水平)的最小网络成本。

但是这些用于精确的评估选择对象的分析方法经常在解决问题状况的现实性和灵活性方面放弃得过多。它们很难让自己适合LogNet的可视的交互模型方法。另一方面,基于启发式的搜索和可视的交互建模一起,能较好地适应更多的无限制的设计任务,因为它们以一种更直接的方式提供有关商业后勤网络推理的向导。如果用户希望在不同网络设计的问题定式化,增量测试及设计方面有更多的灵活性,那么这个方法就为优化方法提供了一种选择。但是,它们的主要缺点就是它们不能保证最优解。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈