轉(zhuǎn)載
來(lái)源：微信公眾號(hào) ? 數(shù)據(jù)魔術(shù)師 蘇鍔
今天為大家介紹的問(wèn)題是Talent Scheduling Problem，因?yàn)闆](méi)有合適的中文翻譯，所以下面直接簡(jiǎn)稱其為TSP (注意， 這里的TSP可不是旅行商問(wèn)題哦)。
目錄
背景介紹
模型建立
算法求解
參考文獻(xiàn)
1 背景介紹
不久之前，我們剛當(dāng)一波老板了解了選址-路徑問(wèn)題（LRP），現(xiàn)在為了更好地摸清TSP的來(lái)龍去脈，這次假設(shè)我們是學(xué)過(guò)運(yùn)籌優(yōu)化的電影制片人。
一部電影由多個(gè)場(chǎng)景組成，每個(gè)場(chǎng)景都需要持續(xù)拍攝一段時(shí)間，且可能只要部分演員參與拍攝即可。
演員只有當(dāng)他后期無(wú)拍攝任務(wù)才可離開劇組，而他的總片酬取決于其參與電影拍攝的總持續(xù)時(shí)間，即從他開始參與的第一場(chǎng)拍攝那天算起，到最后一個(gè)需要他出鏡的場(chǎng)景結(jié)束當(dāng)天，在這期間即使有些場(chǎng)景不需要其參與，都得支付其每日的片酬。
想象一下我們籌拍的這部電影，如果單純按照最終上映的場(chǎng)景順序進(jìn)行拍攝，某位客串的大咖需要很高的每日片酬，但他只出鏡第一場(chǎng)和最后一場(chǎng)，由于中間幾場(chǎng)戲的拍攝期間仍得支付他每日片酬，可就非常劃不來(lái)了。
所以尋找場(chǎng)景的最佳拍攝順序?qū)⒖梢詾閳F(tuán)隊(duì)省下不少錢。舉個(gè)具體的例子。
圖(a)表示了一部電影的拍攝任務(wù)實(shí)例。s為12個(gè)拍攝場(chǎng)景，a為6個(gè)演員，X表示演員i在場(chǎng)景j有拍攝任務(wù)，·表示演員i未出現(xiàn)在場(chǎng)景j中，c為各個(gè)演員每天的工資（無(wú)論當(dāng)天是否有拍攝任務(wù)），d為各個(gè)場(chǎng)景完成拍攝的持續(xù)時(shí)間。
圖(b)表示了按照最終上映的順序進(jìn)行拍攝所產(chǎn)生的成本計(jì)算。-表示演員i在場(chǎng)景j無(wú)拍攝任務(wù)但因?yàn)楹罄m(xù)有檔期而滯留在劇組。Cost表示每個(gè)場(chǎng)景產(chǎn)生的成本，包括了holding cost，即演員滯留所產(chǎn)生的等待成本。這種順序最終的總成本為604，包含了223的總等待成本。
而這個(gè)實(shí)例的最優(yōu)解場(chǎng)景順序?yàn)?-2-7-1-6-8-4-9-3-11-10-12，產(chǎn)生的兩類成本分別為434和53（大家可以自己動(dòng)手算一算）?？梢?jiàn)，如果你學(xué)過(guò)TSP的優(yōu)化，將節(jié)省演員開支，多余的預(yù)算還可以投入到其他方面的制作，意義重大。
雖然Cheng等(1993)【1】便提出這個(gè)問(wèn)題，但假設(shè)每個(gè)場(chǎng)景的持續(xù)時(shí)間均為1天，且每個(gè)演員拿著一樣的片酬。直到de la Banda等(2011)【2】拓展模型使其一般化，并用動(dòng)態(tài)規(guī)劃得到了小規(guī)模實(shí)例的精確解。之后對(duì)TSP的研究都是基于【2】的問(wèn)題背景，其中Qin, Zhang, Lim,and Liang (2016)【3】首次將問(wèn)題定義為混合整數(shù)線性規(guī)劃模型，下面介紹完整的模型建立。
2 模型建立
對(duì)n個(gè)場(chǎng)景、m個(gè)演員的TSP進(jìn)行如下符號(hào)定義：
綜上建立如下整數(shù)規(guī)劃模型：
目標(biāo)函數(shù)(1)表示最小化演員拍攝片酬；
約束(2)(3)分配好第一個(gè)和最后一個(gè)場(chǎng)景;
約束(4)(5)保證每個(gè)場(chǎng)景只有一個(gè)前繼節(jié)點(diǎn)和一個(gè)后繼節(jié)點(diǎn)約束;
約束(6)(7)表示場(chǎng)景的開始日期由其前一個(gè)場(chǎng)景的開始日期確定；
約束(8)(9)確保演員最早和最晚的拍攝日期為其有檔期的場(chǎng)景決定的。
注意到約束(6)是非線性的，為了線性化，符號(hào)定義里最后兩個(gè)z和L就要開始大顯神通了。通過(guò)引入以下4個(gè)線性約束：
約束(6)可改寫成：
目標(biāo)函數(shù)(1)、約束(2)-(5),(7)-(16)構(gòu)成了TSP的混合整數(shù)線性規(guī)劃模型。
3 算法求解
TSP本質(zhì)是一個(gè)NP-Hard的排列問(wèn)題，經(jīng)過(guò)眾多推文的熏陶，相信大家都知道解決這種問(wèn)題無(wú)非就是啟發(fā)式和精確解。解決TSP的關(guān)鍵在于處理場(chǎng)景的排列順序，得到一個(gè)最優(yōu)排列π。所以在這兩類算法里，有的方法因?yàn)橛胁诲e(cuò)的效果而更受青睞。
因?yàn)槭菍?duì)場(chǎng)景的順序進(jìn)行不同的排列，所以啟發(fā)式算法更偏向于基于領(lǐng)域操作的元啟發(fā)式算法，如禁忌搜索算法(TS)、變領(lǐng)域搜索算法(VNS)等，這類算法在求解大規(guī)模的TSP效果顯著（見(jiàn)文獻(xiàn)【4】）。
精確算法目前有動(dòng)態(tài)規(guī)劃(DP)和分支定界法(BB)。文獻(xiàn)【2】運(yùn)用DP求解出小規(guī)模算例，是當(dāng)前簡(jiǎn)單有效的精確算法。但BB的表現(xiàn)也不落下風(fēng)，文獻(xiàn)【3】結(jié)合DP和BB框架，提出了一種新的下界計(jì)算方式，利用緩存技術(shù)的快速存取和兩個(gè)占優(yōu)準(zhǔn)則，得到了優(yōu)于【2】的結(jié)果。
目前，世界上求解該問(wèn)題最先進(jìn)的精確算法就是由數(shù)據(jù)魔術(shù)師秦虎教授提出（見(jiàn)文獻(xiàn)【3】）。
推文發(fā)布前做了簡(jiǎn)單的review，關(guān)于TSP的精確文獻(xiàn)較少。預(yù)知詳細(xì)的技術(shù)分解，且參考評(píng)論的網(wǎng)盤鏈接。
4
參考文獻(xiàn)
[1] Cheng T C E , Diamond J E , Lin B M T . Optimal scheduling in film production to minimize talent hold cost[J]. Journal of Optimization Theory and Applications, 1993, 79(3):479-492.
[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.
