A three-phase matheuristic algorithm for the multi-day task assignment problem
A three-phase matheuristic algorithm for the multi-day task assignment problem
复制标题
DOI：
10.1016/j.cor.2023.106313
复制
发表时间：
2023-11
期刊：
影响因子：
--
通讯作者：
Yang Wang-;Haichao Liu;Bo Peng;Haibo Wang;Abraham P. Punnen
中科院分区：
文献类型：
--
作者：
Yang Wang-;Haichao Liu;Bo Peng;Haibo Wang;Abraham P. Punnen
本文考虑了一个多天任务分配模型，该模型在广泛研究的广义分配问题中引入了几个具有实际意义的特征。与文献中研究的任务分配模型相比，该模型包含的变量和约束的数量显着增加，因此在计算上具有挑战性。为了解决这一问题，我们提出了一种创新的三阶段数学算法，该算法首先利用构造阶段来快速产生合理质量的解，然后在强化阶段和多样化阶段之间交替以达到局部最优，从而将搜索推向新的区域。在构建阶段，将原始问题分解为一系列较小的子问题，使用Gurobi优化器求解每个子问题，然后将子问题的解聚合在一起产生可行解。强化阶段执行迭代变量固定启发式，将解空间划分为不同的邻域，并通过求解简化模型来迭代地探索每个邻域。多样化阶段解决了将距离分量添加到原始目标函数中的修正模型。计算实验表明，该算法在解质量和计算时间上均优于Gurobi、LocalSolver和Tabu Search。我们的算法找到的最优解与上界(Gurobi和LocalSolver得到的)之间的百分比差距在0.82%到2.79%之间，表明它们非常接近最优解。此外，还进行了实验分析，以确定算法中一些关键组件的影响，这些组件有助于提高算法的性能。为我们的研究生成的基准实例将向公众提供，以供未来对这一问题的研究工作。
This paper considers a multi-day task assignment model that introduces several features of practical relevance into the widely-studied generalized assignment problem. This model includes a significantly increased number of variables and constraints compared to the task assignment models investigated in the literature and thus is computationally challenging. For solving this problem, we propose an innovative three-phase matheuristic algorithm that first employs a construction phase to quickly produce a reasonable quality solution and then alternates between an intensification phase to reach local optima and a diversification phase to drive the search into new regions. The construction phase decomposes the original problem into a sequence of smaller subproblems, solves each subproblem with the Gurobi optimizer, and aggregates the solutions from the subproblems to produce a feasible solution. The intensification phase executes an iterative variable fixing heuristic that divides the solution space into different neighborhoods and iteratively explores each neighborhood by solving the reduced model. The diversification phase solves a modified model that adds a distance component into the original objective function. Computational experiments demonstrate that our proposed algorithm outperforms Gurobi, LocalSolver and Tabu Search in terms of both solution quality and computational time. The best solutions found by our algorithm have percentage gaps to the upper bounds (attained by Gurobi and LocalSolver) ranging from 0.82% to 2.79%, indicating that they are very close to the optimal solutions. In addition, experimental analysis has been carried out to identify the impact of some of the key components of the proposed algorithm which are contributing to its superior performance. The benchmark instances generated for our study are made available to the public for future research works on this problem.