摘 要：在很多企业工厂，安排巡检排班都是很重要的一部分，本文将“巡检路线排班最佳”转化为TSP 动态规划问题，用贪婪算法分析每班每人近似最佳路线，画出赋权图，然后用C 语言编程运行得到可行路线方案，进行均衡度比较从而选定最佳巡查方案。在此基础上考虑错时交班得出遍历图，应用Mathematica 编辑对路线进行模拟分析，从而得到人数最少的配置，使人力资源分配更加高效合理。
关键词：TSP 动态规划；排班问题；遍历法；均衡度
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）01-0155-03
Research on Scheduling Problem of Patrol Line Based onTSP Dynamic Programming
LI Jianjun
（Department of Basic Sciences，Northern Beijing Vocational Education Institute，Beijing 101400，China）
Abstract：In many enterprises，scheduling of patrol is a very important work. This paper transforms “the best scheduling of patrol route” into the TSP dynamic programming problem. The greedy algorithm is used to analyze the approximate best route of each class，and the weight map is drawn，then the feasible route plan is worked out by C language programming，and the equilibrium degree is compared，so as to select the best patrol plan. On this basis，the ergodic graphcome to consider the staggered office hours，using the Mathematica editor to simulate and analyze the route to obtain the minimum number of configuration，make human resource allocation more efficient and reasonable.
Keywords：TSP dynamic programming；scheduling problem；ergodic method；equilibrium degree
参考文献：
[1] Cook W. 迷茫的旅行商：一个无处不在的计算机算法问题：mathematics at the limits of computation [M]. 北京：人民邮电出版社，2013.
[2] 孙惠泉. 图论及其应用 [M]. 北京：科学出版社，2004.
[3] 朱旭，李换琴，籍万新.MATLAB 软件与基础数学实验 [M]. 西安：西安交通大学出版社，2008.
作者简介：李建军（1982-），女，河北承德人，蒙古族，硕士研究生，副教授，主要研究方向：数学应用、智能计算研究。