组合优化问题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的关键在于处理场景的排列顺序，得到一个最优排列π。所以在这两类算法里，有的方法因为有不错的效果而更受青睐。