基于CS 的带时间窗多技能人力资源路径优化

摘 要：针对带时间窗多技能人力资源路径优化问题，分别构建了两种数学模型，利用改进的布谷鸟搜索算法（Cuckoo Search Algorithm， CS）对模型进行求解。求出不同类型客户群企业或组织的运作成本，并对模型的适用性进行了讨论，对密集型客户适合模型Ⅱ，即先分区后指派；对分散型客户适合模型Ⅰ，即直接指派。该研究可为企业或组织的决策提供参考，为员工的招聘和安排提供理论指导。

关键词：布谷鸟搜索算法；人力资源路径优化；时间窗；多技能

中图分类号： TP3 文献标识码： A 文章编号： 1673-8462（2023）03-0086-05

0 引言

随着劳动力数量和质量的双变导致企业用工成本增加，给企业的经营管理带来巨大压力。具备多技能的员工能适应多种工作岗位，使企业的人员安排更加灵活，能有效降低企业的人力成本，因此，在企业实践管理中，多技能员工越来越受到企业的青睐。然而，在不同技能员工的工作安排中涉及多个任务，每个任务有时间窗要求和所需不同技能，如何合理安排不同技能员工的工作任务，使企业的运作成本最低，成为企业亟待解决的问题。

近年来，不少专家学者对人力资源管理从不同角度进行研究，袁方洁等人［1］提出基于多阶段遗传算法的人力资源管理，针对企业员工雇佣计划的优化问题建立数学模型，通过合理控制不同时段解聘数量来提高雇员的平均工作能力，从而实现项目的人力资源优化。李明等人［2-3］分别提出基于均衡优化的项目多技能人力资源指派与调度方法和项目多技能人力资源指派与调度混合算法，其在文献［2］中首先采用启发式方法对项目进行资源均衡化并建立整数规划模型，通过编程计算验证了可以有效降低项目人力资源成本，在文献［3］中将原问题分为指派问题和调度问题构建模型，编程实现提高多技能人力资源的使用率。康丽等人［4］提出基于时间窗的家庭医疗护理人力资源分配，其在资源分配阶段考虑时间窗约束和所提出的层次优化算法，实验结果验证了模型的有效性。王一凡等人［5］提出求解多技能人力资源约束的项目调度问题的两阶段算法，实验结果显示其是一种有效方法。段鹏飞等人［6］提出求解广义优先关系下多技能人员项目调度问题的改进布谷鸟搜索算法，实验结果表明其是一种有效方法。李松等人［7］提出人力资源调度的蚁群算法模型，实例证明该算法能有效节省人力资源成本。沈国军等人［8］提出基于改进遗传算法的人力资源指派模型，简化了人力资源指派流程，产生较好的项目绩效。伊雅丽等人［9］提出基于蚁群算法求解研发型多项目人力资源调度研究，为人力资源调度方案提供了新的解决途径。但鲜有研究将时间窗与多技能约束统筹考虑，虽然文献［10］将两者综合考虑，但未对客户类型进行细分研究。本文根据现实管理需求，建立两种数学模型分别用CS 算法求解，通过六种不同类型客户群的仿真实验，针对不同类型客户群适合哪种数学模型企业的运作成本最小给出了理论指导。

1 问题描述与数学模型

1.1 问题描述

在企业或管理者安排技术人员服务客户时，多个客户在地理位置上的分布一般较为不同，在同一时间内，不同客户所提需求也不尽相同，从而构成一个复杂的服务网络。本文以带时间窗的多技能约束服务网络为研究对象，网络由一个服务总站，若干个客户节点构成，如图1 所示。服务总站即图中编号为0的节点，由其派遣多个专业技术人员为不同需求的客户进行服务，每个技术人员从服务总站出发，完成任务后返回出发点；每个客户具有需求技能约束和时间窗约束，在图1 中分别用不同形状进行表示。对管理者而言，如何合理安排各种专业技术人员在满足各客户技能约束和时间窗约束的基础上，使组织的运作成本最小化。

1.2 数学模型Ⅰ

假设服务总站需派遣K （ k = 1，2，…，K ） 名技术人员服务L （ i = 1，2，…，L ） 个客户，每个客户的服务时间为si （ i = 1，2，…，L ），客户i 到客户j 的路径成本为cij、行程时间为tij （ i，j = 0，1，2，…，L ），技术人员到达客户i 的时间为Ti（ i = 1，2，…，L ），客户i 的服务时间窗约束为[ ETi，LTi ]，技术人员的工资成本为f（k 不同技术人员工资标准参见表1），每个技术人员所服务的客户数为Rk，显然，在成本结构上，除了路径成本以外，还有人员工资成本、时间约束惩罚成本。其数学模型如下：

式（1）表示目标函数，式（2）～式（4）表示每个客户只能被一名技术人员服务，式（5）表示时间窗约束，式（6）～式（7）表示0-1 变量，式（8）中的a，b 分别表示早晚到惩罚系数。

1.3 数学模型Ⅱ

由于客户地理位置分布不同，通常的做法是将地理位置较近的客户划分为一个片区，然后再安排相关的技术人员对其进行服务。假设L 个客户需要划分K 个片区，使得K 个片区总距离最短及所需技能最少，每个客户的技能需求为qi，每个客户只能由一名技术人员服务，假设服务总站的技术人员足以满足客户群的技能需求。因此片区划分数学模型为：

式（9）表示片区划分的目标函数，distij 表示客户i与客户j 之间的距离，uij 为1 时表示第j 个客户由第i名技术人员服务，式（10）～式（13）为约束条件。

2 算法设计

2.1 布谷鸟搜索算法

布谷鸟搜索算法（Cuckoo Search Algorithm，CS）由Yang 于2010 年提出，［11］该算法模拟布谷鸟寻窝产卵的过程来求解连续优化问题，其位置更新公式为：

式（14）中xti 表示第i 鸟巢在第t 的位置，α 表示步长控制量，一般取值为0.01；⊕ 表示点乘，L （ λ ） 为Levy 飞行的搜索路径，且L～u = t-λ，（ 1 lt; λ ≤ 3 ）。位置更新并评价目标函数后，用随机数r ∈ [ 0，1 ] 与弃巢概率pa 比较，如果r gt; pa，则对xt + 1i 位置随机改变，否则不变。最后保留最优鸟巢。

2.2 布谷鸟搜索算法离散化

显然基本布谷鸟搜索算法不能直接求解离散优化问题，因此，采用文献［12］的方式将其离散化，现假设最优解best＝［2 8 3 5 4 6 7 1］，第i 个Customer＝［2 1 8 3 5 7 4 6］，随机产生num、Length∈ [ 1，8 ] 之间的两个整数，比如num＝3，Length＝4，即将Cus⁃tomer 的值从第3 个位置开始取长度为4 的元素变换成最优解best 一致，变换后的Customer'＝［2 1 3 5 46 8 7］，通过这种随机选择位置和改变长度的方式趋向最优解。

2.3 编码与解码

编码是智能算法求解问题的关键，它影响着算法的求解性能与效率，本文采用自然数的编码方式。以图1 为例，即需求技能r=3，则相应的技术人员按表1 分为2r - 1=7 种类型：

那么，对一个有L 个客户的带时间窗多技能人力资源问题，设计双倍L 编码：假设客户编号为Cus⁃tomer，技术人员编号为Staff。则图1 所示的一个可行解可以表示为：

Customer：1，7，17，2，16，4，11，5，3，19，15，8，10，14，12，9，18，13，6。

Staff：1，2，4，5，1，3，2，4，5，1，5，3，2，4，1，3，5，2，3

其解码过程为：

员工1：0–1–16–19–12–0

员工2：0–7–11–10–13–0

员工3：0–4–8–9–6–0

员工4：0–17–5–14–0

员工5：0–2–3–15–18–0

2.4 遗传算法操作

由于本文算法采用双倍体编码方式，遗传算法不能直接作用于客户Customer 编码上，如果这样在交叉过程中会产生重复客户编号，因此，将其作用于技术人员Staff 编码方式上，这样既可以减少客户重复编码的处理又可以改变技术人员服务不同的客户。同时在遗传算法的选择、交叉和变异过程中均采用精英保留策略。

2.5 CS 算法求解步骤

（1） CS 算法求解带时间窗多技能人力资源路径优化问题的实施步骤如下（简称算法1）。

Step1：参数初始化：种群规模n、弃巢概率pa ，交叉概率pc，最大迭代次数Iter max，遗传算法迭代次数ga_num、计划安排人数k 和导入客户信息等数据。

Step2：按2.3 节介绍的编码方式随机产生客户编号和员工编号，并按式（8）计算每个鸟巢的目标函数值，求出最优值及最优解。

Step3：判断迭代次数是否达到最大迭代次数，如果是，则退出循环，输出结果；否则进入Step4。

Step4：执行离散布谷鸟搜索位置的更新，评价此时最优值与最优解；如果随机数r gt; pa，则对xt + 1i 位置随机改变，再评价此时最优值与最优解，然后再执行一定次数遗传算法操作并评价此时最优值与最优解。

Step5：判断若此时最优值较Step2 中的最优值优越，则替换最优值和最优解，算法进入Step3。

（2） CS 算法求解客户片区划分（简称算法2）。

算法2 的片区划分的求解过程，只需要改变算法1 的编码方式，采用文献［13］编码方式（其过程在此不再赘述），目标函数值的计算采用式（9）即可，其余操作与算法1 相同。

（3） CS 算法求解片区内客户顺序（简称算法3）。

将算法2 计算的片区划分结果作为算法3 的输入，其编码方式依然采用自然数编码，目标函数值的计算采用式（8），其余操作与算法1 相同。

3 仿真实验与分析

为了将两种不同数学模型+算法设计对企业所产生的成本进行对比。由于本文所研究内容业界尚缺乏标准的数据库，故采用Solomn 提出的算例库，其中包含C1、C2、R1、R2、RC1、RC2 六种类型，其中C类表示客户位置是聚集分布的，R 类表示客户位置是随机分布的，RC 类表示客户位置是混合分布的。另外，又将C，R，RC 类分为1 类和2 类：1 类表示客户所处范围较小，2 类表示客户所处范围较大。每种类型均包含服务总站、客户坐标、服务时间、货物需求量和时间窗。所不同的是将货物需求量改为客户所需技能种类，技能种类在［1，3］之间随机生成，其余不变。

所有的实验均运行在操作系统为Win10，处理器为Intel（R） i6-6750H CPU， 2.60 GHZ 、内存为8 G的PC 上，采用Matlab R2010a 编程。参数设置见表2所示，由于本文算法是启发式算法，无法保证每次运行结果一致，故取其运行30 次结果中最好的一次进行分析。所有实验假设安排10 名技术人员进行服务。

3.1 C201 客户类型测试

对C201 客户类型进行实例演算并详细分析，先展示数学模型Ⅱ+算法2 的计算结果，片区的划分结果如表3 所示，片区划分示意图如图2 所示。采用算法3 优化客户顺序及所支出成本结果如表4 所示。

再展示数学模型Ⅰ+算法1 的运行结果，计算结果如表5 所示。

对客户位置较分散的C201 客户类型来说，从表4 和表5 可得出如下结论：

（1） 如果先分区再指派相应的技术人员进行片区服务与数学模型Ⅰ+算法1 求解结果比较可知，企业或组织所承担的费用需多支出4.1E+04。

（2） 从表3 可知，尽管将距离较近的客户划分成一个片区再由技术人员进行服务，仅考虑了距离成本及所需技能，既没有考虑技能需求的差异，也要求员工全部掌握3 种技能；而从表5 可知，各种技术人员的合理搭配比单纯的路径优化重要，一组合理的人员搭配可以大大减少企业的运作成本。因此在实践管理中，不同种类的多技能员工合理搭配可以使企业员工调度更加灵活，并有效降低生产成本。

（3） 从表5 可知，在服务范围和路径顺序不变的情况下，若全部派遣7 类人员则企业需要多支出的费用。

3.2 其他客户类型测试

上述仅对一种客户类型进行实验演算，下面对其他五种类型进行同样实验，计算结果如表6 所示。

从表6 可知，对地理位置分布较小的客户群C101、R101 和RC101 来说，模型Ⅰ + 算法设计所求成本高于模型Ⅱ + 算法设计；即该类客户群适用于先分区后指派员工，即适合采用模型Ⅱ+算法2+算法3，由于客户所处位置分布较小，优化距离比优化多技能员工的合理搭配效果更明显。而对地理位置分布较大的客户群C201、R201 和RC201 来说，模型Ⅰ + 算法设计所求成本低于模型Ⅱ + 算法设计；即该类客户群适合采用模型Ⅰ+算法1，而且越分散优化效果越好，多技能员工的合理搭配效果显著。因此，对不同类型客户群需采用不同数学模型和算法进行求解，可以有效降低企业运作成本。

4 结 语

本文利用改进的布谷鸟搜索算法求解带时间窗的多技能人力资源路径优化问题，考虑了路径成本、人力成本、等待成本和延误成本，更加符合实际情况。通过六种不同类型客户群，验证了模型的有效性。同时对模型的适用性进行了讨论，对密集型客户适合模型Ⅱ，即先分区后指派；对分散型客户适合模型Ⅰ，即直接指派。该研究可为企业或组织的决策提供参考，为员工的招聘和安排提供理论指导。

［参考文献］

[1] 袁方洁，张佳萍. 基于多阶段遗传算法的人力资源管理[J].云南民族大学学报（自然科学版），2016，25（3）：275-279.

[2] 李明，徐哲. 基于均衡优化的项目多技能人力资源指派与调度方法[J]. 工业工程，2016，19（1）：108-114.

[3] 李明，李前进. 项目多技能人力资源指派与调度混合算法[J]. 数学的实践与认识，2017，47（19）：20-28.

[4] 康丽，马塔·安德瑞. 基于时间窗的家庭医疗护理人力资源分配[J]. 工业工程与管理，2017，22（3）：83-92.

[5] 王一帆，刘士新，陈迪. 求解多技能人力资源约束的项目调度问题的两阶段算法[J]. 东北大学学报（ 自然科学版），2014，35（2）：184-189.

[6] 段鹏飞，余杰，聂慧，等．求解广义优先关系下多技能人员项目调度问题的改进布谷鸟搜索算法[J]. 计算机应用研究，2018，35（5）：1315-1319．

[7] 李松，姜楠. 人力资源调度的蚁群算法模型[J]. 辽宁工程技术大学学报（自然科学版），2014，33（5）：679-682.

[8] 沈国军. 基于改进遗传算法的人力资源指派模型及方法[J]. 统计与决策，2014（16）：52-55.

[9] 伊雅丽. 研发型企业多项目人力资源调度研究——基于蚁群优化的超启发式算法[J]. 工业工程，2018，21（4）：104-109.

[10] 吴建林. 含时间窗和多技能约束的人力资源路径问题模型与算法研究[D]. 武汉：华中师范大学，2018.

[11] YANG X S， DEB S.Cuckoo search via Levy flights [C]／／proceedings of World Congress on nature amp; Biologically In⁃spired Computing，India：IEEE Publications，2009：210-214.

[12] 魏小迪，郑洪清. 求解带时间窗车辆路径问题的改进离散花朵授粉算法[J]. 数学的实践与认识， 2020， 50（2）：193-200．

[13] 刘敏. 改进的花朵授粉算法在物流配送中心选址问题中的应用[J]. 计算机应用与软件，2019，36（6）：277-281，361．

［责任编辑 苏琴］