专栏首页数据魔术师组合优化问题Talent Scheduling Problem(TSP)简介

组合优化问题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

参考文献

[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.

本文分享自微信公众号 - 数据魔术师(data-magician),作者:苏锷

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 实战演练| EDA应用——波士顿犯罪分析

    无论项目还是比赛,拿到一份数据,我们首先需要观测和分析数据,以更好的进行后面的数据清洗、特征工程等工作。本期我们以波士顿犯罪数据分析为例,介绍EDA的思路和方法...

    用户1621951
  • 基础算法 | 关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密

    最近双11又快到了 有女朋友的忙着帮女朋友清空购物车 有男朋友的忙着叫男朋友帮清购物车 而小编就比较牛逼了 小编沉迷学习,已经无法自拔。 那么今天小编又给大家带...

    用户1621951
  • 干货 | Python+MySQL数据库操作

    本文介绍如何利用python来对MySQL数据库进行操作,本文将主要从以下几个方面展开介绍:

    用户1621951
  • [ISUX原创]给孩子设计时光隧道

    ? 腾讯ISUX isux.tencent.com 社交用户体验设计 ? 生动有趣的学习内容,用一条穿越时空的路径慢慢展现出来,让孩子在游玩的过程中学到英语...

    腾讯ISUX
  • python lambda表达式简单用法

    程序员同行者
  • Flutter 学习笔记4-构建布局示例

    一行中有三个子元素,其中第一列子元素本身又是一列,包含两行文字。需要占用大量空间,所以它必须包装在 Expanded widget 中。

    七适散人
  • Windows 8.1 应用再出发 (WinJS) - 创建一个简单项目

    前面几篇我们介绍了如何利用 C# + XAML 完成Windows Store App 功能的实现,接下来的几篇我们来看看如何利用 Html + WinJS 来...

    Shao Meng
  • R语言实现突变信号(Mutational Signatures)分析

    突变信号(Mutational Signatures)首次2013年在《nature》进行报道。并做了相关的定义:细胞在成长过程中,基因组不断受到内源性和外源性...

    一粒沙
  • Python这五个坑,怎么避开?

    今天,跟大家探讨几个Python比较常见的坑点,希望对大家有所帮助。文末点击阅读原文,了解更多坑点。

    double
  • 【leetcode刷题】T206-范围求和 II

    https://leetcode-cn.com/problems/range-addition-ii

    木又AI帮

扫码关注云+社区

领取腾讯云代金券