組合優(yōu)化問題Talent Scheduling Problem(TSP)簡介
今天為大家介紹的問題是Talent Scheduling Problem，因為沒有合適的中文翻譯，所以下面直接簡稱其為TSP (注意， 這里的TSP可不是旅行商問題哦)。
目錄
背景介紹
模型建立
算法求解
參考文獻
1
背景介紹
不久之前，我們剛當一波老板了解了選址-路徑問題（LRP），現(xiàn)在為了更好地摸清TSP的來龍去脈，這次假設我們是學過運籌優(yōu)化的電影制片人。
一部電影由多個場景組成，每個場景都需要持續(xù)拍攝一段時間，且可能只要部分演員參與拍攝即可。
演員只有當他后期無拍攝任務才可離開劇組，而他的總片酬取決于其參與電影拍攝的總持續(xù)時間，即從他開始參與的第一場拍攝那天算起，到最后一個需要他出鏡的場景結(jié)束當天，在這期間即使有些場景不需要其參與，都得支付其每日的片酬。
想象一下我們籌拍的這部電影，如果單純按照最終上映的場景順序進行拍攝，某位客串的大咖需要很高的每日片酬，但他只出鏡第一場和最后一場，由于中間幾場戲的拍攝期間仍得支付他每日片酬，可就非常劃不來了。
所以尋找場景的最佳拍攝順序?qū)⒖梢詾閳F隊省下不少錢。舉個具體的例子。
圖(a)表示了一部電影的拍攝任務實例。s為12個拍攝場景，a為6個演員，X表示演員i在場景j有拍攝任務，·表示演員i未出現(xiàn)在場景j中，c為各個演員每天的工資（無論當天是否有拍攝任務），d為各個場景完成拍攝的持續(xù)時間。
圖(b)表示了按照最終上映的順序進行拍攝所產(chǎn)生的成本計算。-表示演員i在場景j無拍攝任務但因為后續(xù)有檔期而滯留在劇組。Cost表示每個場景產(chǎn)生的成本，包括了holding cost，即演員滯留所產(chǎn)生的等待成本。這種順序最終的總成本為604，包含了223的總等待成本。
而這個實例的最優(yōu)解場景順序為5-2-7-1-6-8-4-9-3-11-10-12，產(chǎn)生的兩類成本分別為434和53（大家可以自己動手算一算）。可見，如果你學過TSP的優(yōu)化，將節(jié)省演員開支，多余的預算還可以投入到其他方面的制作，意義重大。
雖然Cheng等(1993)【1】便提出這個問題，但假設每個場景的持續(xù)時間均為1天，且每個演員拿著一樣的片酬。直到de la Banda等(2011)【2】拓展模型使其一般化，并用動態(tài)規(guī)劃得到了小規(guī)模實例的精確解。之后對TSP的研究都是基于【2】的問題背景，其中Qin, Zhang, Lim,and Liang (2016)【3】首次將問題定義為混合整數(shù)線性規(guī)劃模型，下面介紹完整的模型建立。
2
模型建立
對n個場景、m個演員的TSP進行如下符號定義：
綜上建立如下整數(shù)規(guī)劃模型：
目標函數(shù)(1)表示最小化演員拍攝片酬；
約束(2)(3)分配好第一個和最后一個場景;
約束(4)(5)保證每個場景只有一個前繼節(jié)點和一個后繼節(jié)點約束;
約束(6)(7)表示場景的開始日期由其前一個場景的開始日期確定；
約束(8)(9)確保演員最早和最晚的拍攝日期為其有檔期的場景決定的。
注意到約束(6)是非線性的，為了線性化，符號定義里最后兩個z和L就要開始大顯神通了。通過引入以下4個線性約束：
約束(6)可改寫成：
目標函數(shù)(1)、約束(2)-(5),(7)-(16)構(gòu)成了TSP的混合整數(shù)線性規(guī)劃模型。
3
算法求解
TSP本質(zhì)是一個NP-Hard的排列問題，經(jīng)過眾多推文的熏陶，相信大家都知道解決這種問題無非就是啟發(fā)式和精確解。解決TSP的關(guān)鍵在于處理場景的排列順序，得到一個最優(yōu)排列π。所以在這兩類算法里，有的方法因為有不錯的效果而更受青睞。
因為是對場景的順序進行不同的排列，所以啟發(fā)式算法更偏向于基于領域操作的元啟發(fā)式算法，如禁忌搜索算法(TS)、變領域搜索算法(VNS)等，這類算法在求解大規(guī)模的TSP效果顯著（見文獻【4】）。
精確算法目前有動態(tài)規(guī)劃(DP)和分支定界法(BB)。文獻【2】運用DP求解出小規(guī)模算例，是當前簡單有效的精確算法。但BB的表現(xiàn)也不落下風，文獻【3】結(jié)合DP和BB框架，提出了一種新的下界計算方式，利用緩存技術(shù)的快速存取和兩個占優(yōu)準則，得到了優(yōu)于【2】的結(jié)果。
目前，世界上求解該問題最先進的精確算法就是由數(shù)據(jù)魔術(shù)師秦虎教授提出（見文獻【3】）。
推文發(fā)布前做了簡單的review，關(guān)于TSP的精確文獻較少。預知詳細的技術(shù)分解，且參考評論的網(wǎng)盤鏈接。
4
參考文獻
[2] de la Banda, M. G., Stuckey, P J. , Chu, G., Solving talent scheduling with dynamic programming. INFORMS Journal on Computing, 2011, 23(1):120-137.
[3] Qin, H., Zhang, Z., Lim, A., & Liang, X. (2016). An enhanced branch-and-bound algorithm for the talent scheduling problem. European Journal of Operational Research, 2016, 250(1), 412–426.
[4] Ranjbar, M., Kazemi, A., A generalized variable neighborhood search algorithm for the talent scheduling problem. Computers & Industrial Engineering, 2018,?126(2018), 673–680.
?贊 賞?
長按下方二維碼打賞感謝您，支持學生們的原創(chuàng)熱情！
?
---The End---
文案?&&?編輯：蘇鍔排版：蘇鍔
審稿人：秦時明岳（華中科技大學管理學院）指導老師：秦時明岳（華中科技大學管理學院）