《Computers & Operations Research》:A matheuristic for solving the single row facility layout problem
编辑推荐:
单行设施布局问题(SRFLP)是一个被广泛研究的NP-hard组合优化问题,在制造和物流系统中有应用。在SRFLP中,给定一组具有长度的设施,以及每对设施之间的权重。设施必须排列在一条直线上,以最小化加权中心到中心距离之和。在这项工作中,研究人员引入了一种新颖
单行设施布局问题(SRFLP)是一个被广泛研究的NP-hard组合优化问题,在制造和物流系统中有应用。在SRFLP中,给定一组具有长度的设施,以及每对设施之间的权重。设施必须排列在一条直线上,以最小化加权中心到中心距离之和。在这项工作中,研究人员引入了一种新颖的数学启发式方法,将精确优化集成到基于模拟退火的元启发式框架中,以有效求解大规模SRFLP实例。具体地,研究人员提出了窗口方法数学启发式,该方法允许使用混合整数规划(MIP)求解布局子段的最优解,同时保持窗口外设施的排序。据研究人员所知,这是首个专门为SRFLP设计的数学启发式方法。研究人员在文献中广泛使用的基准实例集上评估了该方法的表现。计算结果表明,该数学启发式方法改进了70个实例中13个实例的最佳已知解值,并匹配了其余57个实例的最佳已知解值,优于当前最先进的元启发式方法。
单行设施布局问题(single row facility layout problem, SRFLP)是设施布局优化中的经典NP-hard组合优化问题,广泛应用于医院、办公室、仓库和柔性制造系统等场景。该问题定义为一组具有长度的设施和两两之间的权重,目标是将设施排列在一条直线上,最小化所有设施对之间的加权中心到中心距离之和。现有方法包括精确方法(如混合整数规划(MIP)和半定规划(SDP))和元启发式方法(如模拟退火(SA)、贪婪随机自适应搜索过程(GRASP)和变邻域搜索(VNS))。然而,精确方法在大规模实例上计算不可行,而元启发式方法难以找到局部最优解。目前尚无专门针对SRFLP的数学启发式方法,尽管问题结构适合集成精确优化与元启发式搜索。为此,研究人员提出了一种新颖的数学启发式方法,旨在结合两者优势,提升大规模实例的求解质量。该方法首次为SRFLP设计了数学启发式框架,并显著改进了当前最佳已知解。论文发表在《Computers》。
研究人员采用的关键技术方法包括:1) 多起点模拟退火(multi-start simulated annealing, MSA)阶段,用于生成多样且高质量的初始解,其核心基于Palubeckis提出的高效移动增益计算;2) 两种局部搜索策略,即插入搜索(LS_insert)和交换搜索(LS_swap),用于快速精化解;3) 窗口方法(window approach),通过基于中间性(betweenness)的MIP公式对选定窗口内的设施进行精确优化,同时固定窗口外设施的排序,窗口大小可调(MSA阶段使用13,精化阶段使用17和19);4) 加速策略,包括固定最小累积权重和改进约束(确保MIP只接受改进解)。样本队列来源:使用文献中广泛采用的Anjos-large(20个实例,规模200-500)、Sko-large(20个实例,规模200-500)和Palubeckis-large(30个实例,规模310-1000)三个基准实例集。
研究结果部分如下:
5.1 实验设置:研究人员在Julia中实现算法,使用Gurobi 12.0.0作为MIP求解器,在AMD EPYC 7543单核处理器上运行,内存6GB。时间限制按实例规模设定:≤300设施为3600秒,≤500设施为7200秒,≤1000设施为10800秒。每个实例运行10次独立试验。
5.2 参数选择:使用irace自动参数调优包,在训练集(8个Anjos-large实例,规模150-450)上确定MSA参数:冷却因子α=0.976,内部运行次数?=87×n,交换移动概率p=0.323。
5.3 加速策略影响评估:在训练集上比较有无加速策略的算法版本。结果表明,包含加速策略的版本在所有实例上均获得更优的客观值(平均值从980,249,581.81降至980,249,462.56),证明加速策略有效。
5.4 不同窗口大小的运行时间比较:对Anjos-large实例,测试窗口大小13、17、19、23、25、30等。结果显示,窗口大小13、17、19在运行时间和解质量上最佳,且对MIP部分无需时间限制即可快速求解;较大窗口(如23、29、31)显著增加MIP时间,且仅对400设施实例有轻微改善,但总体效率下降。
5.5 窗口方法带来的改进:在三个基准集上,比较有/无窗口方法的算法。在Anjos-large中,窗口方法在500设施实例上全部优于无窗口版本;在Sko-large中,窗口方法在400-500设施实例上9/10优于无窗口版本;在Palubeckis-large中,窗口方法在17/30实例上改进解值。窗口方法在较大实例上效果显著,证明其能探索新邻域。
5.6 与当前最先进算法比较:与KMPG(Tang et al., 2022)、GRASPF(Cravo and Amaral, 2019)和MSA(Palubeckis, 2017)比较。在Anjos-large上,窗口方法匹配或改进所有实例,建立2个新上界;在Sko-large上,匹配或改进所有实例,改进6个;在Palubeckis-large上,匹配或改进29/30实例,改进8个。此外,扩展时间限制后,进一步改进了4个实例(Sko-500-01、Palubeckis-800、900、1000),使总共改进13个实例,匹配57个。标准偏差低,表明算法鲁棒性强。
讨论部分:研究人员指出,窗口方法通过定义新邻域结构,成功结合了精确优化的局部精化能力与元启发式的全局搜索能力,尤其在大规模实例上表现突出。该方法可扩展到其他排列问题,如最小线性排列问题。未来工作可探索与其他元启发式的集成。
结论部分(翻译):在这项工作中,研究人员引入了一种用于求解单行设施布局问题(SRFLP)的新颖数学启发式方法。所提方法基于窗口方法这一新概念,利用了SRFLP的基于中间性的混合整数规划(MIP)公式。该方法保持全局设施排序不变,仅对选定移动窗口内的设施进行精确优化,从而定义了一种强大且新颖的邻域结构,使算法能够超越现有最先进的元启发式方法。该MIP组件被集成到一个更广泛的数学启发式框架中,该框架以多起点模拟退火(MSA)元启发式开始,生成高质量且多样化的初始解,随后通过两种互补的局部搜索过程进行精化,这两种过程均依赖与MSA阶段相同的移动增益计算,确保快速评估。这两种局部搜索策略与窗口方法结合,探索了SRFLP文献中尚未被研究的邻域。通过在Anjos-large、Sko-large和Palubeckis-large基准集上的广泛实验,该算法改进了70个实例中13个实例的最佳已知解值,并匹配了其余57个实例的最佳已知解值,证明了窗口方法在大型实例上的有效性。除SRFLP外,所提窗口方法可能适用于更广泛的设施布局问题及其他涉及排列的问题,如最小线性排列问题,且与其他元启发式的集成也是未来研究的有趣方向。