基于TSP模型改进的巡检工作调度实证研究

邹腊英

基于TSP模型改进的巡检工作调度实证研究

邹腊英

（江西财经职业学院，江西 九江 332000）

多点巡检问题在生产生活中非常普遍，如何精准、有效地解决这个问题已迫在眉睫。TSP数学模型是数学中解决旅行经销商遍历各城市的经典问题，通过对此模型的改进，并使用LINGO及MATLAB软件编程，有效地解决了多点巡检的线路设计及人员调度安排问题，实现了人员安排最优、巡检时间精确的效果，大大提高了企业运行效率。

巡检线路；巡检时间；TSP模型；MATLAB

在生产和生活中，很多工作都与巡检有关，包括电网巡检、网络巡检、化工厂巡检及保安巡逻等。多点巡检是一个涉及面广而又复杂的问题，涉及到巡检人员安排、巡检路线的设定及巡检点时间的计算，处理不好会直接影响企业效益，甚至造成重大安全事故。如何合理、精准地设计巡检线路、聘用和安排工人的具体巡检工作，是一个亟待解决的重要问题。随着科技的进步，人工手动设计巡检路线及人员安排因效率过低，已不适应市场需要，信息化设计才是解决问题的主流，既可以提高效率，又计算精确。本文通过改进TSP数学模型，并使用LINGO及MATLAB软件编程，可以很好地解决多点巡检问题线路设计及人员安排。

1 TSP问题的介绍

TSP问题即旅行经销商问题（Traveling Salesman Problem），TSP模型是运筹学的一个著名命题，即一名推销员准备从某个城市出发，前往多个城市推销产品，并且经过每个城市恰好1次，最后返回到他的出发地。如何为他设计一条最短的旅行路线这个问题称为旅行商问题，即TSP问题。

解决TSP问题的关键是效率，即遍历每个地点所用时长最短；其次是约束，即遍历一圈后每个地点到达且只能到达1次。

根据要求引入0-1整数变量ij（≠），ij=1表示从地点到地点，ij=0表示地点不到地点，ij表示地点到地点的时间，则历时最短可写成模型：

2 巡检工作调度实证研究

2.1 问题描述

某化工厂有26个作业点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中已给出，且每个点每次巡检需要1名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始从起始点巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如1周或1月等）的工作量尽量平衡。

2.2 问题分析

本案例要解决两种情况的巡检线路安排：①固定时间上下班，这种情况下要分多条线路巡检，因为一条线路巡检不能满足巡检点巡检周期为35 min的要求；②错时上下班，可只建立一条线路，这条巡检线路包含所有巡检点，让工人不同时间上班，从而满足巡检点巡检周期为35 min的需求。

2.3 巡检线路算法分析及模型建立

无论是固定时间上班还是错时上下班，都要形成巡检线路，在这个线路循环中都要满足巡检点巡检周期安排，相当于巡检线路是一个遍历的过程，在这个过程中要满足以下要求。每个巡检点的入点和出点都只能衔接唯一一个点，以保证每个巡检点遍历而且不会再形成小圈，所以得到公式：

即每个巡检点的入点和出点都只有1个，ij=0指第点与第点不连通，ij=1指第点与第点连通。

巡检线路是个巡回路线，要达到遍历，又只能有一条巡回路线，即不能含子回路，则i－j+ij≤－1，=1，2，…，；=2，3，…，；≠。

整数规划模型：

2.4 固定时间上下班情况下巡检调度研究

在上下班时间固定的条件下，巡检人员巡检时间受到巡检点的巡检周期影响，每个巡检工人必须在第一个巡检点的巡检周期时间到达之前回到第一个巡检点，所以，不能建立所有巡检点遍历的大循环，只能以第一个巡检点的巡检周期时间为一个巡检圈，找寻巡检圈的点。

根据就近相连的原则，大致分隔出6条巡检路线。本问题的目标函数是使得每个巡检路线形成的巡检圈内的巡检时间及行走时间最短，所以目标函数为：

式（1）中：ij为第点与第点行走所花时间；j为第点巡检所花时间。

使用上述模型中的约束，由编写的LINGO程序得到具体的巡检线路安排。在固定时间上下班的情况下，总共需要6个工人同时上下班，工人在巡检调度中心（XJ0022）打卡上班后各自到自己的巡检线路上进行巡检工作，时间相对固定和均衡。

2.5 错时上下班情况下的巡检调度研究

因为错时上班，所以巡检人员巡检时间不受巡检点的巡检周期影响，可以建立所有巡检点遍历的大循环。

在巡检点巡检周期一致的情况下，即每个巡检点巡检周期都为35 min，利用巡检线路模型，只要将模型中的巡检点改为==26，由LINGO软件编程得到整个26个点的遍历，整个遍历需要耗时135 min，在错时上下班情况下仅需要安排4名巡检员巡检（共140 min）。每名巡检人员的巡检线路如表1所示。

表1 巡检点巡检周期一致下错时上下班巡检最优线路

巡检线路具体巡检点总耗时/min 线路221920214213571461011131618151226178259242322135

2.6 巡检点巡检周期不一致情况下算法的进一步研究

一般来说，巡检点的巡检周期不尽相同，则研究巡检点巡检周期不尽相同的情况更具有复杂性和普遍性。要解决巡检点巡检周期不尽相同的问题，首先要确定每一条巡检线路所经过的巡检点有哪些。

2.6.1 每条巡检线路巡检点的确定

要想确定巡检点，首先要找到每个巡检点周期与最小巡检周期的关系，即按最小巡检周期倍数来过滤每条巡检线路不经过的点。

按以上规律使用for循环编程，可得到每条巡检线路经过的巡检点。

2.6.2 巡检周期不一致下错时上下班实证分析

按照上述介绍的方法确定好每条巡检线路的巡检点后，采用巡检调度模型，利用LINGO软件计算可得出每条线路的巡检点和时间节点，巡检点巡检周期不一致情况下，虽然线路巡检点不一致，但是会产生循环，就本例而言，20条不同巡检线路后就会重新开始。

3 结束语

基于以上实例得出，无论是固定时间上下班，还是错时上下班的巡检工作的调度，改进的TSP模型都能成功地求解，并科学、精准地安排员工的巡检工作。在固定时间上下班的情况下，TSP模型的求解比较被动，需要预先估算巡检线路的条数，再利用LINGO编程求解，求得的巡检线路不一定最优，但在错时上下班的情况下，改进的TSP模型的作用被发挥得淋漓尽致，不需要任何手动的辅助，就能精准计算员工巡检线路的具体巡检点及巡检精确时间，为巡检工作调度提供科学、有效的帮助。

综上所述，使用改进的TSP模型及其对应的程序可以很好地解决生活及生产当中很多繁杂的巡检调度问题，不仅科学有效，而且精准可靠，有效地避免了人工调度中人力、物力的浪费，极大优化了人员安排及巡检调度工作，这些模型在同类巡检问题的解决中可以广泛推广使用。

［1］汪晓银，邹庭荣.数学软件与数学实验［M］.北京：科学出版社，2008.

［2］汪晓银，周保平.数学建模与数学实验［M］.北京：科学出版社，2010.

［3］韩中庚.数学建模方法及其应用［M］.北京：高等教育出版社，2005.

［4］敬振毅，张泽兵，董霖.MATLAB7.0实用宝典［M］.北京：中国铁道出版社，2008.

［5］曹卫华，郭正编.最优化技术方法及MATLAB的实现［M］.北京：化学工业出版社，2005.

［6］袁新生，邵大宏，郁时炼.LINDO和Excel在数学建模中的应用［M］.北京：科学出版社，2007.

［7］谢金星，薛毅.优化建模与LINDO/LINGO软件［M］.北京：清华大学出版社，2005.

TS48

A

10.15913/j.cnki.kjycx.2019.16.007

2095－6835（2019）16－0020－02

〔编辑：张思楠〕