在以前的几篇文章中，我们讨论了几个运营分析中的案例。其中之一就有呼叫中心的访客分配算法，今天的案例有些相似，但不再是个别的访客分配而是讨论更广泛的内容。我们将使用一个与运筹学中的运输算法来解决呼入分配最优化问题。

案例研究

你拥有一个含1000个资源(席位)的呼叫中心，每个席位都经过了一系列的培训。培训分为ABCDEF系列。例如，A类坐席是指已通过1~6号课程培训的客服人数，而B类客服则通过了其它系列课程。各类坐席的分布如下

A : 200

B : 200

C : 100

D : 100

E : 250

F : 150

另外，每天呼入的电话有不同的问询类型，大致可以分为4类。我们暂称之为X、Y、Z和W类问询。问询的类型可以通过IVR(互动式语音应答系统)识别出来，你可以任意指定为这些客户服务的坐席。工作日呼入问询类型的大致分布为：

X : 20%

Y : 30%

Z : 15%

W : 35%

各工作日的呼入类型数量可能有差别，但各类问询电话的占比基本是不变的。经过相应问询类型的应答培训，客服就可以获得快速解答问询的技巧。例如，经过A类培训的客服可以在10分钟内解答X类问询。以下表格给出了经过某类培训的客服应答某类问询所需的相应时间。

表1 时间成本矩阵

 

 

任务来了，你的建模目标就是让呼叫中心各坐席的总应答时间最少。你可以让坐席经过不同类型的培训获得问询解答技巧，通过实时监督来减少应答的时间。但最终，你需要的是一个能做实时呼入分配的自动化系统，以实现所有席位被占用的总应答时间最小。

为简单起见，我们把实际的呼入数假设为几个确定的值。某呼叫中心每天呼入的各类问询分布如下：

X : 200 个呼入

Y : 300个呼入

Z : 150个呼入

W : 350个呼入

总呼入数 : 1000

这时，客服的数量与呼入的数量是完全相等的。即使呼入的总数会增加，只要呼入问询的类型保持着稳定的比率，我们后面要讨论的解决方案仍然是有效。

运输问题介绍

可以把呼入响应优化问题用运输问题模型来解决，解答问询的时间可以看成是运输问题中的运输成本。运输问题是经典的线性规划问题，其典型提法是：为了把某种产品从若干个产地调运到若干个销地，已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确定一个总运输费或总运输量最少的方案。运输问题的解法有单纯形法和表上作业法，运输问题的一般解决方案有两个步骤：

1. 制订基本可行方案;

2. 找出最优方案。

运输问题的基本可行方案可通过三种方法获得：

1. 西北角法(最简单的方法)

2. 最小成本法

3. 罚金成本法(伏格尔法)

西北角法

过程很简单，每一次都在表格的西北角(左上角)放上最大的可能值，然后划掉已满足最大值要求的行或列，再对剩下的表格重复这一操作即可。比如在下表的左上角应该先填上200这个坐席数，然后划掉X行和A列。

表2 西北角法初始运算

 

 

之所以填200，是因为x类呼入最多有200个，经过A类培训的坐席也有200个，因此200是最大的可能值。划掉X行和A列后，表的左上角变成了Y行B列，在这单元格的列向上要求有200个坐席经过B类培训，行向上要求能应答300个Y类问题的呼入，因此这一单元格可以填入的最大可能值只能为200。这时列向上的坐席数满足了，行向上还差300-200=100个坐席，所以只能把B列划掉而要保留Y行。当下一个左上角变为Y行D列时，我们很容易可以判断出这一单元格应该填入100。以此类推，可以找出所有可靠的坐席分配数。

表3 西北角法运算结果

 

 

根据上表的计算结果和表1成本矩阵，我们可以计算出总的应答时长：200×10+200×4+100×9+100×11+50×6+200×4+150×11=7550分钟。按照这一计算结果，我们可以将分配方案定为：让所有受过A类培训的客服应答X类问询;将33%的Y类问询分配给受过C类培训的客服， 66%的Y类问询分配给受过B类培训的客服……。显然，这一方案并不是最优的，以下两种方法可以获得更少的时间消耗。

最小成本法

最小成本法是另一种有所改进的运输问题算法。在解决坐席-客户匹配问题时我们先找出平均应答时间最少的。比如在本案例中，通过观察表1的成本矩阵，我们发现X类客户与D类坐席匹配耗时最少。所以我们先把最大可能的资源数匹配给这对组合。由于X类客户平均有200位，而D类坐席最多只有100位，因此匹配给这对组合的最大可能资源数为100。

表4 最小成本法初始运算

 

 

以此类推，我们依次找出余下成本单元格中的最小值，并将相应的最大可能资源数匹配到那些单元格中去，直到所有资源分配完毕。分配结果如下表所示：

表5 西北角法运算结果

 

 

总的时间成本为：100×1+100×5+200×4+50×9+50×5+150×2+50×3+50×7+250×4=3900分钟，与西北角法相比，总耗时减少了将近50%。

罚金成本法

这也是一种对初始分配过程有更多改进的算法。首先，我们计算每一行、每一列上最小成本和次小成本的差值，这一差值意味着如果我们没有选出最小值而会遭受的成本损失，罚金成本法也因此得名(也称伏格尔法)。其确定初始基本可行解的思路是：罚金成本最高的行或列中成本最低者优先考虑。以下为将成本矩阵转化后的罚金成本表(最右侧增加了各行罚金列，最下端增加了各列罚金行)。

表6罚金成本法初始运算

 

 

我们发现最大罚金出现在D列，我们应该马上把该列最大的资源数分配给这列中的最小成本单元格。接下来，在余下的表格中我们再依次定位罚金最大成本行/列，及其最小的单元格，并进行相应资源数的分配(原则依然是不能超过行或列上的资源数限制)。完成分配后的结果如下表所示：

表7 罚金成本法运算结果

 

 

累计可得，总的时间成本为4400。可见，这种改进方法并不比最小成本法耗时少。这是因为恰好在这个案例中，最小成本法的迭代过程中并没有出现因未选最低成本而使总成本惩罚性增加的情形。

找出最优解

通过上述算法的计算，可以基本断定最小成本法就是我们要找的最优解。但在解决更一般的成本优化问题时，往往需要引入进一步的讨论：最优解的判别与解的改进。本例中我们不再深入介绍这一过程，留待读者自行学习。可以提示的是:解的最优性检验包含闭回路法和位势法;而从一个方案调整到最优方案的过程，就是单纯形法的过程。

“运输问题”在运筹学方面应用很广，但在数据分析领域应用不多。通过本例，我们可以看到将呼叫响应优化问题转化为运输问题解决时，所带来的显著的成本优化。