考虑技能水平的呼叫中心多技能客服排班研究

Research on the Shift Scheduling of Multi-Skill Call Center with Skill Level Coefficient

摘要: 随着呼叫中心精益化管理的发展，多技能排班需求日益突出，多技能的引入提升了排班复杂度。根据多技能客服的服务能力不同，构建引入技能水平系数的多技能客服排班问题整数规划模型，以人力差值绝对值最小化作为目标函数，确保充分调用当前人力。由于目标函数具有非线性，无法直接用CPLEX求解，本文提出变邻域搜索算法生成解方案。计算结果表明本文所提出的邻域结构与扰动方法能够有效提升求解优越性与稳定性，证明了模型的可行性与算法有效性。

Abstract: With the development of lean management in call centers, multi-skill scheduling problem has be-come prominent and increased scheduling complexity. According to the different capabilities of multi-skilled staff, an integer program model with skill level coefficients was constructed. Minimizing the absolute value of manpower difference as the objective function to ensure that the current manpower is fully utilized. Due to the non-linear objective function, a variable neighborhood search algorithm was proposed. The experimental results show that the local search structure and shaking process can effectively improve the superiority and stability of the solution, which proves the feasibility of the model and the effectiveness of the algorithm.

1. 引言

呼叫中心作为连接顾客和企业的纽带，在提高顾客满意度，维护企业良好的信誉方面扮演着重要的角色。呼叫中心是一个人力密集型行业，其运营成本中有60%~70%是客服的人力成本。由于客服排班关系到运营成本与服务水平之间的平衡问题，是呼叫中心运营管理的难点。因此，合理高效的排班至关重要。目前大量研究集中在短期计划上。Dietz [1] 提出6种不同的休班方式，构建多周排班问题二次整数规划模型，利用二分法与凑整技巧构造启发式搜索算法进行求解。Mattia等 [2] 考虑不同时段的人力需求情况具有相互关联性，构建随机整数规划模型。以上呼叫中心排班研究仅考虑单技能的情况，所有的顾客的需求被认为是相同的，可由任意一位当班客服进行服务。随着呼叫中心行业的不断发展，规模不断扩大，服务产品变得多样化，呼叫中心客服人员面对的顾客需求更加复杂多变，而他们需要掌握的技能也随之增多。因此呼叫中心的多技能排班需求日益突出。但由于不同客服之间具有技能交叉或覆盖特点，多技能的引入会使排班问题复杂程度上升。Omari等 [3] 通过仿真对比了各种不同情况下的服务水平，发现将多技能客服与单技能客服组合配置，能够有效地提高服务水平。Taskiran和Zhang [4] 通过交叉培训的方式应对需求波动，并考虑休息时间、周末、班次轮换等约束构建整数规划模型，通过两阶段启发式算法进行求解。Pisacane [5] 建立了以成本最小化为目标的多技能客服人员排班模型，并通过割平面法求解，研究结果表明客户耐心度与客服需求量呈正相关的关系。多技能的引入会增加排班灵活性但同时也增加了模型的复杂度。在以上研究中，均将不同客服服务同类技能视为同一服务水平，但在实际工作场景中，尽管一位多技能客服能够处理不同类型的业务，由于培训程度以及对技能掌握的熟练程度不同，不同客服处理同一项业务时的服务水平和耗费时间也会有所差异，特别是对于专业程度要求较高的需求，服务水平之间的差异更为明显。一般情况下，客服会对自己的第一技能掌握的最熟练，服务水平也就最高，而对于第二、第三以及其他技能的服务水平会依次降低，这种服务水平的差异会直接影响到呼叫中心整体的服务能力。因此，本文针对多技能客服引入技能水平系数，以便更准确地刻画呼叫中心实际运营问题。

2. 问题描述及模型化

2.1. 问题描述

呼叫中心客服排班时，通过将工作时间分成若干时段，根据预测的人力需求，通过班次覆盖时段来配置人力。在大量短期计划相关文献中，通常将成本最小化作为目标函数，但在实际呼叫中心运营中，客服薪资为月薪制，排班情况对成本影响较为有限。呼叫中心排班的理想状态是每个时段的人力配置均满足人力需求，但是由于每个时段人力需求都会产生变动，而客服人员上班时段是连续的，必然无法保证每个时段人力需求与人力安排刚好匹配。因此，本文以人力差值最小化作为目标函数，旨在实现人员总成本不变的前提下，充分利用当前人力，使上班人数尽量贴合顾客需求的变化。多技能呼叫中心排班优化问题可以描述为：在一个排班周期内，将客服人员按照技能类别分成不同技能组，根据客服对不同技能掌握的熟练程度不同的特点，引入技能水平系数。在满足各约束条件下，确定客服人员每天的当班情况及各类需求在各时段的当班客服人数。以最小化人力差值的绝对值为目标函数，建立考虑技能水平的多技能客服人员排班模型。

2.2. 整数规划模型

定义下列参数和决策变量符号。

1) 参数符号：

E：客服人员集合 $E=\left\{e_1,e_2,\cdots ,e_n\right\}$， $e\in E$ 表示第e个客服人员。

S：顾客需求种类集合 $S=\left\{s_1,s_2,\cdots ,s_n\right\}$， $s\in S$ 表示技能s。

G：技能组集合 $G=\left\{g_1,g_2,\cdots ,g_n\right\}$， $g\in G$ 表示第g技能组。

D：由周一到周日组成的日期集合 $D=\left\{d_1,d_2,\cdots ,d_7\right\}$， $d\in G$ 表示星期d。

T：一天内的时间段集合 $T=\left\{t_1,t_2,\cdots ,t_n\right\}$， $t\in T$ 表示一天的第t时段。

K：班次集合 $K=\left\{k,k_2,\cdots ,k_n\right\}$， $k\in K$ 表示第k班次。

r_sdt：表示在第d天的第t时段对技能s的人数需求。

M：一个排班周期内每位客服人员的上班天数。

c_eg：班组系数，取值0-1，等于1表示客服e属于技能组g。

a_kt：班次系数，取值0-1，等于1表示班次k的工作时间包含时间段t。

b_sg：技能水平系数，表示技能组g中的客服对于技能s掌握的熟练程度。

2) 决策变量：

X_ed：0-1变量，等于1表示客服e在第d天上班。

W_ked：0-1变量，等于1表示客服e在第d天上k班次。

Z_kgd：表示第g技能组的客服人员在第d天上k班次的人数。

Y_sgtd：表示第d天的第t时间段技能组g中以技能s当班的客服人数。

构建考虑技能水平的呼叫中心多技能客服排班优化问题整数线性规划模型如下。

目标函数：

$Z=\min \underset{1}{\overset{S}{{\displaystyle \sum }}}\underset{1}{\overset{D}{{\displaystyle \sum }}}\underset{1}{\overset{T}{{\displaystyle \sum }}}\left|\underset{1}{\overset{G}{{\displaystyle \sum }}}{Y}_{sgtd}*b_{sg}-r_{sdt}\right|$ (1)

约束条件：

$\underset{1}{\overset{E}{{\displaystyle \sum }}}{W}_{ked}*c_{eg}=Z_{kgd},\forall g,\forall d,\forall k$ (2)

$\underset{1}{\overset{S}{{\displaystyle \sum }}}{Y}_{sgtd}=\underset{1}{\overset{K}{{\displaystyle \sum }}}{Z}_{kgd}*a_{kt},\forall t,\forall g,\forall d$ (3)

$Y_{sgtd}\le \underset{1}{\overset{K}{{\displaystyle \sum }}}{Z}_{kgd}*b_{sg},\forall d,\forall g,\forall t,\forall s$ (4)

$\underset{1}{\overset{K}{{\displaystyle \sum }}}{W}_{ked}=X_{ed},\forall e,\forall d$ (5)

$\underset{1}{\overset{K}{{\displaystyle \sum }}}{W}_{ked}\le 1,\forall e,\forall d$ (6)

$\underset{1}{\overset{d}{{\displaystyle \sum }}}{X}_{ed}\le M,\forall e$ (7)

$X_{ed},W_{ked}\in \left\{0,1\right\},Y_{sgtd},Z_{kgd}\in Z^{+}\cup \left\{0\right\}$ (8)

其中，目标函数表示人力供给与人力需求的差值绝对值最小。式(2)表示W_ked和Z_kgd的相关关系，即每天各技能组g在同一班次k当班的人数之和等于技能组g的所有的客服人员在d天k班次当班的客服人员数量。式(3)表示Y_sgtd和Z_kgd的相关关系，即在各时间段t服务各类技能s的客服总人数等于在该时间段t上班的总人数。式(4)表示各时段服务于各技能的客服人数约束。式(5)、式(6)表示客服人员一天只能上一个班次。式(7)表示客服人员每一排班周期上班天数不超过M天。式(8)表示Y_sgtd，Z_kgd为正整数，W_ked，X_ed均属于0~1变量。

3. 优化算法

由于目标函数中带有绝对值使模型非线性，无法用CPLEX直接求解，本文通过变邻域搜索算法进行求解。变邻域搜索通过在寻优过程中系统地改变邻域结构来扩展求解范围，通过局部搜索流程以获得局部最优解，再基于此局部最优解重复上述过程获得另一个局部最优解，如此不断迭代最终获得收敛、实现优化 [6]。

3.1. 初始解构造

该方法采用整数编码的方式进行编码，具体步骤如下。

步骤1班次编码。如图1所示，按照当班时间的先后顺序对班次库中的班次从小到大进行排序。假设某呼叫中心有3种班次，分别用1、2、3表示，休息用0表示。

Figure 1. Shift setting list

图1. 班次设置列表

步骤2客服排班。生成一个M行N列的矩阵，其中，M代表客服数量，N代表排班天数。矩阵中的每个元素代表客服m在第n天的当班班次。步骤3 休息日安排。在每位客服的排班周期中任选两天，将其班次替换成0，即表示休息，确保每位客服的休息天数符合约束条件。如图2所示，可以看出5位客服在7天的排班情况。

Figure 2. Examples of legal initial solutions

图2. 合法初始解示例

3.2. 邻域结构设计

单一的邻域结构可能使算法过早陷入局部最优，而多个邻域结构可广泛探索解空间，进而提高算法的求解效率和稳定性 [6]。因此，本文设计了一组邻域结构集合，通过改变客服当班班次的方式进行结构变换，并按照固定顺序逐一实现邻域拓展动作。邻域结构集包含三个邻域结构N1、N2和N3。其中，邻域结构N1是随机选择两个客服交换任意一天的班次；邻域结构N2是随机选择两个客服交换相邻两天的班次；邻域结构N3是随机选择两个客服交换相邻三天的班次。

3.3. 扰动过程设计

上述邻域结构是基于客服之间班次交换展开的有规律的解空间探索，当邻域搜索不能再进一步改进当前解时，算法可能陷入局部最优。为了进一步扩大解空间的搜索范围，通过有效的扰动保证多样化的探索并最终实现全局优化。本文采用以下两种扰动方式：

1) 随机选取偶数天进行扰动

随机生成一个偶数M (2 <= M <= 6)，选取不重复的M天，交换客服在这偶数天的当班班次。如图3所示，随机抽取第1、4、5、7天共计4天进行扰动，交换每位客服在第1天和第4天的班次及第5天和第7天的班次。

Figure 3. Examples of random selection of even-numbered day disturbance

图3. 随机选取偶数天扰动示意图

2) 随机选取偶数位客服进行扰动

随机抽取偶数位客服，两两交换这偶数位客服在某一天的排班班次。由于该扰动可能会产生不合法解，需要后续进行约束检验，若产生的解不合法，需要重新扰动，直至产生合法解或满足停止原则。

3.4. 变邻域搜索算法流程

对呼叫中心多技能排班问题，提出变邻域搜索算法。该算法实现流程见图4。

4. 实验计算及分析

4.1. 实例计算

为验证本文提出的算法的有效性和可行性，选取小中大三组不同规模的算例进行计算，即10人/2班次、20人/3班次、50人/5班次，通过Matlab2016b平台进行数值实验，采用遗传算法、邻域搜索和变邻域搜索三种算法进行对比。其中，邻域搜索与变邻域搜索均采用本文设计的邻域结构，但邻域搜索无扰动过程。在每种情况下分别运算10次，图5为三组算例在不同算法下每次的运行结果。由图5可知，邻域搜索和变邻域搜索的解质量及稳定性均要优于遗传算法。

Figure 4. Flow chart of VNS algorithm

图4. 变邻域搜索算法流程图

Figure 5. 3 groups of example calculation results

图5. 3组算例运算结果图

4.2. 计算结果分析

多次运算结果所得的平均解、最优解、最差解及标准方差如图6所示。在算法稳定性方面，采用邻域和变邻域算法求解的3组不同规模算例的标准方差均优于遗传算法。除了在10人的小规模算例中，邻域搜索标准方差比变邻域搜索高出4%；在其余两组算例中，变邻域搜索获得的解的稳定性更优，分别比邻域搜索高出75.5%和20.9%。由于邻域搜索容易陷入局部最优，随着问题规模的扩大，陷入局部最优的可能性增加。变邻域搜索通过在邻域搜索的基础上增加扰动过程来跳出局部寻优，扩大解空间求解范围。该结果表明本文设计的扰动方法可在规模较大的算例中有效避免陷入局部最优的问题。

Figure 6. Comparison of the solution quality and stability of three groups of examples under different algorithms

图6. 3组算例在不同算法下的解质量及稳定性比较

在求解质量方面，变邻域搜索和邻域搜索的平均解、最优解、最差解均优于遗传算法。图7为三组平均值的结果比较，其中GAP表示与变邻域搜索算法比较下的差值百分比。

$\text{GAP}=\frac{{\text{T}}_1-{\text{T}}_2}{{\text{T}}_2}\times 100\text{\%}$ (9)

式(9)中， ${\text{T}}_1$ 为其他算法得到的目标函数均值， ${\text{T}}_2$ 为变邻域搜索算法得到的目标函数均值。由图7可知，变邻域搜索求解质量最优，除了在小规模算例中略低于邻域搜索，其余情况下均高于另外两个算法。由于变邻域搜索和邻域搜索采用相同的邻域结构，因此二者求解结果较为接近。相较于遗传算法，本文所提出的邻域结构有较好的寻优能力。

Figure 7. Comparison of the average values of the 3 groups of calculation examples under different algorithms

图7. 3组算例在不同算法下的平均值比较

4.3. 人力需求对比分析

选取规模为20人的算例分别在遗传算法和变邻域搜索算法下的某次运算结果，计算各时段的实际人力安排。下图为人力需求对比图。由图8可知，相较于遗传算法，变邻域搜索算法所得的班表人力拟合情况更好，但依然存在部分时段人力冗余，部分时段人力不足的情况，呼叫中心可根据运营目标采取调整班次、加班、招聘兼职等方式进行改善，具体调整情况取决于呼叫中心在运营成本与服务水平之间的权衡。

Figure 8. Manpower demand comparison chart

图8. 人力需求对比图

5. 结论

本文研究呼叫中心多技能客服排班问题，通过构建整数规划模型和设计变邻域搜索算法来求解排班问题优化方案。根据多技能客服的服务能力不同，在模型中引入客服的技能水平系数，并以人力差值的绝对值最小化作为目标函数。本文提出变邻域搜索算法进行求解，计算结果表明本文所提出的邻域结构与扰动方法能够有效提升求解优越性与稳定性，证明了模型的可行性与算法有效性，可为呼叫中心的运营管理提供一些参考意见。但通过人力需求对比发现，依然存在人力不足与人力短缺的情况，有待进一步深入研究。