【資源調度】2-如何解決資源調度問題？

導讀：本期是全網最全【資源調度】系列推文的第2期(共50期左右)。上期我們在《何為調度？》中，對調度的定義與作用、計劃與調度的關系、調度問題的拆解做了詳細介紹。從本期開始，我們選擇【客服調度】場景作為【資源調度】問題的具象化代表，為大家展開后續一系列推文。本期將為大家詳細介紹 【客服調度】的業務背景、問題抽象、技術路徑和解決方案等內容。

作者1：張哲銘，某互聯網大廠算法專家
作者2：向杜兵，某制造業龍頭算法專家

大家好！我們是IndustryOR團隊，致力于分享業界落地的OR+AI技術。歡迎關注微信公眾號/知乎/CSDN【運籌匠心】。

誠邀大家 【加入粉絲群】，群里經常分享硬核內容，且大佬多多，說不定你未來的leader就在其中！【加群方式附在文章結尾】~~

本篇文章共分為5個部分，依次為：
01 業務背景
02 問題抽象
03 技術路徑
04 解決方案
05 小結

01 業務背景

當今的企業普遍面臨客戶服務的挑戰，特別是在高度競爭和不斷變化的市場環境下。為了提供卓越的客戶體驗和滿意度，有效的客服調度成為關鍵。隨著業務規模的由小到大，客服調度技術也隨之由易到難。對于一些超大型toC企業，可以說客服調度技術的成熟與否直接影響了其業務發展，甚至決定企業的生死存亡。

02 問題抽象

1）問題描述

在客服調度場景中，一個客戶的需求從產生到滿足的業務流程可被拆解為以下4步：

請求發起：客戶通過電話咨詢、工單填報等方式向調度系統發出請求，希望自身的某些需求能被滿足。
調度決策：調度系統或通過人工、或通過規則、或通過算法為客戶請求分配最合適的客服人員。
需求履約：客服人員為客戶提供服務，直至用戶需求被滿足。
用戶反饋：客戶對客服的服務進行評價反饋。

由于客戶請求隨時隨地都有可能產生，因此客服調度場景的業務流程就是在時間上連續且并行的重復這個過程。

2）調度本質

我們在《何為調度？》的中已經為【資源調度】問題的本質做出了定義，即：調度問題的本質就是求解供給和需求在時空上的最優匹配，【客服調度】問題也是如此。

供給方面：客服調度場景中的供給通常是指提供服務的人，如：接線員、售后專家、家政阿姨、機場地勤等服務人員。客服人員通常具備用戶需要的一些職業技能，以便解決客戶需求的問題，同時同一行業不同經驗的人往往具有不同的技能熟練度。
需求方面：客服調度場景中的需求一般指是用戶的需求，通常以任務的形式出現，如：接線任務、售后任務、保潔任務、地勤任務等。任務通常具有任務類型、最早/最晚開始(結束)時刻、任務時長等屬性，需要具有匹配技能的人去執行。
匹配方面：客服調度一般是指人去完成任務，即服務客戶。線上場景的業務重點關注人和任務在時間上的最優匹配，如：接線、售后咨詢等場景；線上場景的業務需同時關注人和任務在時間和空間上的最優匹配，如：上門保潔、地勤保障等場景。

3）調度目標

最優匹配是定性的概念，需要調度目標的方式定量表示。場景不同，調度目標也有很大不同，我們可以將調度目標歸納為以下5類：

(系統)成本型指標：周期內(年/月/周/日)，最少用工人數、最少資源消耗等；
(系統)效率型指標：周期內(年/月/周/日)，最大工時利用率、最短完工時間、最大服務任務數、最快響應時間、最快服務時間等；
(客戶)體驗型指標：周期內(年/月/周/日)，最高客戶滿意度、最少投訴率等；
(客服)公平型指標：周期內(年/月/周/日)，服務時長公平、休息天數公平、早晚班公平、服務任務數公平、服務任務難度公平、薪資水平公平等；
(系統)安全型指標：周期內(年/月/周/日)，最高系統可用率、最低系統故障率等(這一部分屬于調度系統穩健性方面的內容，與調度算法關系不大)；

小到幾乎所有的調度問題，大到整個社會的治理問題，都是緊緊圍繞 “如何平衡成本、效率、體驗、公平、安全等多目標之間的關系” 而展開的。

4）調度規則

調度需要在一定的業務規則下進行。與調度目標類似，盡管不同場景下的調度規則千差萬別，但我們也可以將其歸納為以下4類：

數值類規則：周期內(年/月/周/日)，在崗時長上下限、服務時長/任務數上下限、休息天數上下限、特種任務服務時長/次數上下限等
時間類規則：用餐時間窗、間休時間窗、請假日等
空間類規則：任務間地點銜接、人與任務地點匹配、人隨任務空間位移相關要求等
技能類規則：
- 匹配類規則：人與任務之間的技能匹配，即具備某些技能的人才能服務特定的任務。
- 搭配類規則：人與人之間的技能搭配，即服務某些特定任務需要不同技能的人相互配合。

03 技術路線

實際生產中的客戶調度問題通常屬于NP-Hard問題，其需求(甚至是供給)一般呈現強隨機性特征，其核心的矛盾是：問題的復雜性與調度的實時性之間的矛盾，其落地技術大致需要經歷以下迭代過程：

業務初期：這個階段業務剛開始起步試點，業務規模小且復雜程度低，粗放式管理即可滿足當時的發展需求，最緊迫的任務是基于人工規則實現業務的自動化運轉，在此之上能有些許的OR技術應用即可。
業務發展期：隨著業務的擴張，業務精細化管理的需求逐漸顯露出來，OR相關的技術和人員儲備也跟了上來。此時，便是傳統OR技術大顯身手的時候。但這個時期由于信息化、數字化基建設施尚未建設完成，導致數據積累不足，還無法采用數據驅動的方法解決問題。
業務成熟期：隨著業務數據的不斷積累以及數據治理能力的不斷提升，業務被海量的數據精準量化，數據驅動的智能決策技術開始逐步應用，該階段會融合OR、ML、DL、RL等各類算法技術解決該問題。

因此，我們【客服調度】系列推文的內容也將圍繞上圖的技術路徑展開，力爭還原整個技術路徑的發展。

04 解決方案

1）方案設計

由于沒有真實業務場景，且人手有限，因此整個解決方案不會以還原線上系統為目標，而是緊緊圍繞我們最關注的調度算法展開。除了講解最核心的調度算法外，我們還將講解調度衍生問題、指標檢驗系統以及仿真系統等內容，方案圖如下：

下面分模塊介紹一下各模塊及其之間的關系：

仿真系統模塊：
- 數據仿真模塊：主要負責生成歷史數據和實時數據，歷史數據用于調度算法迭代測試，實時數據用于模擬真實調度場景，為調度仿真提供輸入。
- 調度仿真模塊：只進行數據仿真，不進行物理世界仿真(成本太高，也沒必要)。模擬真實調度場景，調度算法運行在仿真系統中，以便于對比不同版本算法間的效果。
調度算法模塊
- 靜態問題求解算法模塊：這是整個調度算法模塊中最重要的部分。盡管從整體上看，調度問題是實時的動態問題，但從局部上看(每一個調度決策的時間段內)，調度問題是靜態的，也就是說求解動態的實時調度問題可以看成是一連串靜態調度問題的序列決策過程，上個時間段的調度決策執行結果是下個時間段調度決策的輸入，即整個調度決策過程可以看做是 馬爾可夫決策過程(Markov Decision Process, MDP) 。因此靜態問題求解算法效果好壞對線上實時調度的效果影響很大。該模塊的作用主要就是指導實時調度算法設計，使其不斷逼近最優調度。
- 實時調度算法模塊：該算法是真正在線上發揮作用的算法，其算法形態與靜態問題求解算法相同。與靜態問題求解算法更偏重于求解質量不同，實時調度算法更關注求解質量與求解效率之間的平衡。
指標檢驗模塊：該模塊屬于調度算法的外圍模塊，主要用于算法上線前業務指標和技術指標的檢驗。
衍生問題模塊：該模塊包含的問題主要是調度算法依賴的上游問題，如：需求預測問題、資源規劃問題、人員排班問題等。