组合优化问题Talent Scheduling Problem(TSP)简介

今天为大家介绍的问题是Talent Scheduling Problem，因为没有合适的中文翻译，所以下面直接简称其为TSP (注意， 这里的TSP可不是旅行商问题哦)。

目录

• 背景介绍

• 模型建立

• 算法求解

• 参考文献
  

1

背景介绍

不久之前，我们刚当一波老板了解了选址-路径问题（LRP），现在为了更好地摸清TSP的来龙去脉，这次假设我们是学过运筹优化的电影制片人。

一部电影由多个场景组成，每个场景都需要持续拍摄一段时间，且可能只要部分演员参与拍摄即可。

演员只有当他后期无拍摄任务才可离开剧组，而他的总片酬取决于其参与电影拍摄的总持续时间，即从他开始参与的第一场拍摄那天算起，到最后一个需要他出镜的场景结束当天，在这期间即使有些场景不需要其参与，都得支付其每日的片酬。

想象一下我们筹拍的这部电影，如果单纯按照最终上映的场景顺序进行拍摄，某位客串的大咖需要很高的每日片酬，但他只出镜第一场和最后一场，由于中间几场戏的拍摄期间仍得支付他每日片酬，可就非常划不来了。

所以寻找场景的最佳拍摄顺序将可以为团队省下不少钱。举个具体的例子。

图(a)表示了一部电影的拍摄任务实例。s为12个拍摄场景，a为6个演员，X表示演员i在场景j有拍摄任务，·表示演员i未出现在场景j中，c为各个演员每天的工资（无论当天是否有拍摄任务），d为各个场景完成拍摄的持续时间。

图(b)表示了按照最终上映的顺序进行拍摄所产生的成本计算。-表示演员i在场景j无拍摄任务但因为后续有档期而滞留在剧组。Cost表示每个场景产生的成本，包括了holding cost，即演员滞留所产生的等待成本。这种顺序最终的总成本为604，包含了223的总等待成本。

而这个实例的最优解场景顺序为5-2-7-1-6-8-4-9-3-11-10-12，产生的两类成本分别为434和53（大家可以自己动手算一算）。可见，如果你学过TSP的优化，将节省演员开支，多余的预算还可以投入到其他方面的制作，意义重大。

虽然Cheng等(1993)【1】便提出这个问题，但假设每个场景的持续时间均为1天，且每个演员拿着一样的片酬。直到de la Banda等(2011)【2】拓展模型使其一般化，并用动态规划得到了小规模实例的精确解。之后对TSP的研究都是基于【2】的问题背景，其中Qin, Zhang, Lim,and Liang (2016)【3】首次将问题定义为混合整数线性规划模型，下面介绍完整的模型建立。

2

模型建立

对n个场景、m个演员的TSP进行如下符号定义：

综上建立如下整数规划模型：

• 目标函数(1)表示最小化演员拍摄片酬；

• 约束(2)(3)分配好第一个和最后一个场景;

• 约束(4)(5)保证每个场景只有一个前继节点和一个后继节点约束;

• 约束(6)(7)表示场景的开始日期由其前一个场景的开始日期确定；

• 约束(8)(9)确保演员最早和最晚的拍摄日期为其有档期的场景决定的。

注意到约束(6)是非线性的，为了线性化，符号定义里最后两个z和L就要开始大显神通了。通过引入以下4个线性约束：

约束(6)可改写成：

目标函数(1)、约束(2)-(5),(7)-(16)构成了TSP的混合整数线性规划模型。

3

算法求解

TSP本质是一个NP-Hard的排列问题，经过众多推文的熏陶，相信大家都知道解决这种问题无非就是启发式和精确解。解决TSP的关键在于处理场景的排列顺序，得到一个最优排列π。所以在这两类算法里，有的方法因为有不错的效果而更受青睐。

因为是对场景的顺序进行不同的排列，所以启发式算法更偏向于基于领域操作的元启发式算法，如禁忌搜索算法(TS)、变领域搜索算法(VNS)等，这类算法在求解大规模的TSP效果显著（见文献【4】）。

精确算法目前有动态规划(DP)和分支定界法(BB)。文献【2】运用DP求解出小规模算例，是当前简单有效的精确算法。但BB的表现也不落下风，文献【3】结合DP和BB框架，提出了一种新的下界计算方式，利用缓存技术的快速存取和两个占优准则，得到了优于【2】的结果。

目前，世界上求解该问题最先进的精确算法就是由数据魔术师秦虎教授提出（见文献【3】）。

推文发布前做了简单的review，关于TSP的精确文献较少。预知详细的技术分解，且参考评论的网盘链接。

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.

 赞 赏 

---The End---