基于数据挖掘的调度枚举方法，用于加速大规模人员调度问题的解决

《ACM Transactions on Evolutionary Learning and Optimization》：Data Mining-Driven Shift Enumeration for Accelerating the Solution of Large-Scale Personnel Scheduling Problems

服务行业人员排班优化通过结合数学规划与k近邻算法，利用历史解压缩小问题规模，实现决策变量减少85.5%和求解速度提升15.5倍，同时保持成本增加在1.2%以内。

　　

摘要

本研究通过结合数学编程和数据挖掘技术，解决了服务业中大规模人员调度问题，以提高效率。研究的目标是在一周的规划时间内高效安排技术娴熟的员工，同时降低成本并满足多样化的工作需求。在服务业中，排班计划与客户需求密切相关，导致潜在的排班方案众多，这类优化问题难以通过商业混合整数规划求解器轻松解决。然而，这些问题属于重复性问题，即不同实例具有共同的特征和解决方案结构，仅在某些参数上随时间有所变化。我们提出使用一种数据挖掘技术——$k$最近邻算法来加速问题解决过程，同时保持解决方案的质量。我们建议利用以往的解决方案来缩小问题的规模。对于即将到来的任务，我们识别出类似的历史实例，并简化排班方案的枚举过程，使其与历史实例的排班安排保持一致。这种方法使我们能够在合理的时间内使用商业求解器解决问题，同时保证解决方案的质量。此外，我们的方法为决策者提供了灵活性，使他们能够决定在多大程度上简化问题。我们在基于真实历史数据生成的实例（包含最多12个工作任务和252名员工）上进行了实验，平均减少了85.5%的决策变量。实验结果显示，平均求解速度提高了15.5倍，而平均成本仅增加了约1.2%。