在以前的幾篇文章中，我們討論了幾個(gè)運(yùn)營(yíng)分析中的案例。其中之一就有呼叫中心的訪客分配算法，今天的案例有些相似，但不再是個(gè)別的訪客分配而是討論更廣泛的內(nèi)容。我們將使用一個(gè)與運(yùn)籌學(xué)中的運(yùn)輸算法來解決呼入分配最優(yōu)化問題。

案例研究

你擁有一個(gè)含1000個(gè)資源(席位)的呼叫中心，每個(gè)席位都經(jīng)過了一系列的培訓(xùn)。培訓(xùn)分為ABCDEF系列。例如，A類坐席是指已通過1~6號(hào)課程培訓(xùn)的客服人數(shù)，而B類客服則通過了其它系列課程。各類坐席的分布如下

A : 200

B : 200

C : 100

D : 100

E : 250

F : 150

另外，每天呼入的電話有不同的問詢類型，大致可以分為4類。我們暫稱之為X、Y、Z和W類問詢。問詢的類型可以通過IVR(互動(dòng)式語音應(yīng)答系統(tǒng))識(shí)別出來，你可以任意指定為這些客戶服務(wù)的坐席。工作日呼入問詢類型的大致分布為：

X : 20%

Y : 30%

Z : 15%

W : 35%

各工作日的呼入類型數(shù)量可能有差別，但各類問詢電話的占比基本是不變的。經(jīng)過相應(yīng)問詢類型的應(yīng)答培訓(xùn)，客服就可以獲得快速解答問詢的技巧。例如，經(jīng)過A類培訓(xùn)的客服可以在10分鐘內(nèi)解答X類問詢。以下表格給出了經(jīng)過某類培訓(xùn)的客服應(yīng)答某類問詢所需的相應(yīng)時(shí)間。

表1 時(shí)間成本矩陣

任務(wù)來了，你的建模目標(biāo)就是讓呼叫中心各坐席的總應(yīng)答時(shí)間最少。你可以讓坐席經(jīng)過不同類型的培訓(xùn)獲得問詢解答技巧，通過實(shí)時(shí)監(jiān)督來減少應(yīng)答的時(shí)間。但最終，你需要的是一個(gè)能做實(shí)時(shí)呼入分配的自動(dòng)化系統(tǒng)，以實(shí)現(xiàn)所有席位被占用的總應(yīng)答時(shí)間最小。

為簡(jiǎn)單起見，我們把實(shí)際的呼入數(shù)假設(shè)為幾個(gè)確定的值。某呼叫中心每天呼入的各類問詢分布如下：

X : 200 個(gè)呼入

Y : 300個(gè)呼入

Z : 150個(gè)呼入

W : 350個(gè)呼入

總呼入數(shù) : 1000

這時(shí)，客服的數(shù)量與呼入的數(shù)量是完全相等的。即使呼入的總數(shù)會(huì)增加，只要呼入問詢的類型保持著穩(wěn)定的比率，我們后面要討論的解決方案仍然是有效。

運(yùn)輸問題介紹

可以把呼入響應(yīng)優(yōu)化問題用運(yùn)輸問題模型來解決，解答問詢的時(shí)間可以看成是運(yùn)輸問題中的運(yùn)輸成本。運(yùn)輸問題是經(jīng)典的線性規(guī)劃問題，其典型提法是：為了把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。運(yùn)輸問題的解法有單純形法和表上作業(yè)法，運(yùn)輸問題的一般解決方案有兩個(gè)步驟：

1. 制訂基本可行方案;

2. 找出最優(yōu)方案。

運(yùn)輸問題的基本可行方案可通過三種方法獲得：

1. 西北角法(最簡(jiǎn)單的方法)

2. 最小成本法

3. 罰金成本法(伏格爾法)

西北角法

過程很簡(jiǎn)單，每一次都在表格的西北角(左上角)放上最大的可能值，然后劃掉已滿足最大值要求的行或列，再對(duì)剩下的表格重復(fù)這一操作即可。比如在下表的左上角應(yīng)該先填上200這個(gè)坐席數(shù)，然后劃掉X行和A列。

表2 西北角法初始運(yùn)算

之所以填200，是因?yàn)閤類呼入最多有200個(gè)，經(jīng)過A類培訓(xùn)的坐席也有200個(gè)，因此200是最大的可能值。劃掉X行和A列后，表的左上角變成了Y行B列，在這單元格的列向上要求有200個(gè)坐席經(jīng)過B類培訓(xùn)，行向上要求能應(yīng)答300個(gè)Y類問題的呼入，因此這一單元格可以填入的最大可能值只能為200。這時(shí)列向上的坐席數(shù)滿足了，行向上還差300-200=100個(gè)坐席，所以只能把B列劃掉而要保留Y行。當(dāng)下一個(gè)左上角變?yōu)閅行D列時(shí)，我們很容易可以判斷出這一單元格應(yīng)該填入100。以此類推，可以找出所有可靠的坐席分配數(shù)。

表3 西北角法運(yùn)算結(jié)果

根據(jù)上表的計(jì)算結(jié)果和表1成本矩陣，我們可以計(jì)算出總的應(yīng)答時(shí)長(zhǎng)：200×10+200×4+100×9+100×11+50×6+200×4+150×11=7550分鐘。按照這一計(jì)算結(jié)果，我們可以將分配方案定為：讓所有受過A類培訓(xùn)的客服應(yīng)答X類問詢;將33%的Y類問詢分配給受過C類培訓(xùn)的客服， 66%的Y類問詢分配給受過B類培訓(xùn)的客服……。顯然，這一方案并不是最優(yōu)的，以下兩種方法可以獲得更少的時(shí)間消耗。

最小成本法

最小成本法是另一種有所改進(jìn)的運(yùn)輸問題算法。在解決坐席-客戶匹配問題時(shí)我們先找出平均應(yīng)答時(shí)間最少的。比如在本案例中，通過觀察表1的成本矩陣，我們發(fā)現(xiàn)X類客戶與D類坐席匹配耗時(shí)最少。所以我們先把最大可能的資源數(shù)匹配給這對(duì)組合。由于X類客戶平均有200位，而D類坐席最多只有100位，因此匹配給這對(duì)組合的最大可能資源數(shù)為100。

表4 最小成本法初始運(yùn)算

以此類推，我們依次找出余下成本單元格中的最小值，并將相應(yīng)的最大可能資源數(shù)匹配到那些單元格中去，直到所有資源分配完畢。分配結(jié)果如下表所示：

表5 西北角法運(yùn)算結(jié)果

總的時(shí)間成本為：100×1+100×5+200×4+50×9+50×5+150×2+50×3+50×7+250×4=3900分鐘，與西北角法相比，總耗時(shí)減少了將近50%。

罰金成本法

這也是一種對(duì)初始分配過程有更多改進(jìn)的算法。首先，我們計(jì)算每一行、每一列上最小成本和次小成本的差值，這一差值意味著如果我們沒有選出最小值而會(huì)遭受的成本損失，罰金成本法也因此得名(也稱伏格爾法)。其確定初始基本可行解的思路是：罰金成本最高的行或列中成本最低者優(yōu)先考慮。以下為將成本矩陣轉(zhuǎn)化后的罰金成本表(最右側(cè)增加了各行罰金列，最下端增加了各列罰金行)。

表6罰金成本法初始運(yùn)算

我們發(fā)現(xiàn)最大罰金出現(xiàn)在D列，我們應(yīng)該馬上把該列最大的資源數(shù)分配給這列中的最小成本單元格。接下來，在余下的表格中我們?cè)僖来味ㄎ涣P金最大成本行/列，及其最小的單元格，并進(jìn)行相應(yīng)資源數(shù)的分配(原則依然是不能超過行或列上的資源數(shù)限制)。完成分配后的結(jié)果如下表所示：

表7 罰金成本法運(yùn)算結(jié)果

累計(jì)可得，總的時(shí)間成本為4400。可見，這種改進(jìn)方法并不比最小成本法耗時(shí)少。這是因?yàn)榍『迷谶@個(gè)案例中，最小成本法的迭代過程中并沒有出現(xiàn)因未選最低成本而使總成本懲罰性增加的情形。

找出最優(yōu)解

通過上述算法的計(jì)算，可以基本斷定最小成本法就是我們要找的最優(yōu)解。但在解決更一般的成本優(yōu)化問題時(shí)，往往需要引入進(jìn)一步的討論：最優(yōu)解的判別與解的改進(jìn)。本例中我們不再深入介紹這一過程，留待讀者自行學(xué)習(xí)?？梢蕴崾镜氖?解的最優(yōu)性檢驗(yàn)包含閉回路法和位勢(shì)法;而從一個(gè)方案調(diào)整到最優(yōu)方案的過程，就是單純形法的過程。

“運(yùn)輸問題”在運(yùn)籌學(xué)方面應(yīng)用很廣，但在數(shù)據(jù)分析領(lǐng)域應(yīng)用不多。通過本例，我們可以看到將呼叫響應(yīng)優(yōu)化問題轉(zhuǎn)化為運(yùn)輸問題解決時(shí)，所帶來的顯著的成本優(yōu)化。