论文部分内容阅读
【摘要】该问题属于最佳推销员回路问题，文中首先对化工厂的检测点巡检进行概述，然后分析化工厂的巡检现状，并运用节约算法、启发算法对测站巡检线路进行优化，最后提出最优方案。
【关键词】最佳推销员回路问题；赋权图；近似算法；均衡度
【基金项目】吉安职业技术学院校级科研项目（16JY137）资助
【中图分类号】TQ086.2；TP274.4 【文献标识码】B 【文章编号】2095-3089（2017）17-0292-02
一、问题重述
某化工厂有26个点需要进行巡检以保证正常生产，每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。巡检线路是指从巡检调度中心（XJ0022）出发，走遍所有的点，再回到巡检调度中心的路线。
（1）如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。
（2）如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。
（3）如果采用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。
二、问题分析
本题给出了某工厂巡检线路图及各个点的巡检周期、巡检耗时、两点之间的连通关系、行走所需时间，要求的是在不同的条件下，巡检排班的线路及巡检人数、时间表。将每个巡检点看作一个图的顶点，各巡检点之间的线路看作此图对应顶点间的边，各条线路行走所需要时间看作对應边上的权，所给线路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点巡检调度中心（XJ0022）出发，使所有顶点都能按要求完成巡检，使得总权（路程或时间）最小。
本题是旅行售货员问题的延伸-多旅行售货员问题。本题所求的分班巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）。
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法。显然本问题更应属于NP完全问题。有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解。
三、模型假设
1.巡检人员行走所用时间总是一定，忽略天气等因素的影响。
2.各个点巡检周期、两点之间的连通关系总是一定，忽略故障等其他因素的影响；
3.巡视当中，各巡检点的巡检耗时一定，不会出现特殊情况而延误时间；
4.每个点每次巡检只有一名工人；
四、符号说明
w（i，j）：任意两点i，j间的间距；ei：各点的巡检耗时，即点权；V：各巡检点构成的集合。
五、模型建立与求解
巡视线路图中，每个巡检点看作图中的一个节点，各巡检点之间的线路看作此图对应顶点间的边，各条线路行走所需要时间看作对应边上的权，所给线路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点巡检调度中心（XJ0022）出发，使所有顶点都能按要求完成巡检，此即最佳推销员回路问题。
此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题。由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法。我们需要去寻求一种较合理的划分准则，对图（1）进行初步划分后，分成巡查圈I、巡查圈I、巡查圈I所示的三个组
经过分析我们得出每班至少需要四名工人寻遍所有的巡查点。四名工人分别记为A、B、C、D。工人A负责巡查圈I，工人B、C负责巡查圈II，工人D负责巡查圈III。为了耗费的人力资源尽可能的少，并且每名工人在同一时间段内工作量尽可能均衡。工人A按路线一进行巡查。工人B、工人C分别按路线二、三进行第一次巡查，工人D按路线四进行第一次巡查。第一次四名工人巡检路线如下。
经过第一次巡查后，我们对巡查路线作进一步的优化（如下表），四名工人按照优化后的巡检路线进行巡检。工人A按巡逻圈Ⅰ进行巡检（循环进行，直到换班）；工人B、C按照巡逻圈Ⅱ（3-23路线）交替相向而行进行巡检；工人D按照巡逻圈Ⅲ进行巡检（循环进行，直到换班）。
因为该组检测路线的每个检测周期内有效的每人检测的均衡度
所以这种路线的周期内的每人检测的均衡性较好。
根据巡检路线并考虑巡检工人在一时间段内的工作量尽量平衡，巡检时间表如下：
问题二：顶替轮班
由于巡查人员每巡查2小时左右需要休息一次，8小时工作时间内共计需要休息3次，每个点大约检查15次，休息时间是15到30分钟。
在考虑到工厂巡查的不间断性，工人要在中午12点和下午6点进餐，因此，在原有4个人的基础之上，增加一人，实行顶替轮班的方法。每次一个人进餐，另一人顶替进餐者进行巡检，进餐者用完餐后立刻返回其岗位，让顶替者到另一路线顶替其他工人进餐，以此类推，该顶替者共计要连续工作0.5×4=2小时，并且当其他工人休息时顶班工作，时间为15×4=1小时，所以顶班工人实际工作时间为3小时。综合以上分析，在保证工厂巡检正常进行，第一班0：00-8：00需要工人4人，第二班8：00-16：00需要工人5人，第三班16：00-24：00需要工人5人。如果采用每天三班倒，共计需要14人。其巡查的时间表如下：
问题三：采用错时上班
由于问题一不考虑巡检人员的休息时间，也不考虑工人的进餐时间，所以错时上班对是否节省时间没有太大影响。工人每天工作8小时左右，每班需要4人，一天依旧需要12名工人巡检。
由于问题二中巡检人员每巡检2小时左右需要休息一次，在中午12：00和下午6：00需要进餐一次，12：00与下午6：00相距6小时，并且采取错时上班制，在8：00-16：00和16：00-24：00的两次巡检中，只需一名工人顶替这两班工人的休息和进餐时间，所以第一班0：00-8：00需要工人四名，第二班和第三班8：00-24：00需要工人9名，共计一天需要13人，所以采用错时上班可以节省人力。
优缺点分析：
优点：
1.本文提出的分组准则简便易行，可操作性强，且可逐步调整使分组达到均衡；
2.用均衡度的概念定量的刻画了分组的均衡性；
3.在用近似算法求近似最佳推销员回路时，采取了三种不同的方法产生初始圈，使得算法比较完善，得到了误差很小的近似最优解；
缺点
1.时间精确度存在一定误差。
参考文献
[1]赵静，数学建模与数学实验（第三版），北京：高等教育出版社，2008.
[2]胡运权，运筹学基础及应用（第三版），哈尔滨：哈尔滨工业大学出版社，1998.
[3]孙惠泉，图论及其应用，北京：科学出版社，2004.
作者简介：费荔枝（1982—），女，硕士，中级.研究方向：生物数学。
通讯作者：E-mail：lvhengmin2005@163.com
【关键词】最佳推销员回路问题；赋权图；近似算法；均衡度
【基金项目】吉安职业技术学院校级科研项目（16JY137）资助
【中图分类号】TQ086.2；TP274.4 【文献标识码】B 【文章编号】2095-3089（2017）17-0292-02
一、问题重述
某化工厂有26个点需要进行巡检以保证正常生产，每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。巡检线路是指从巡检调度中心（XJ0022）出发，走遍所有的点，再回到巡检调度中心的路线。
（1）如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。
（2）如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。
（3）如果采用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。
二、问题分析
本题给出了某工厂巡检线路图及各个点的巡检周期、巡检耗时、两点之间的连通关系、行走所需时间，要求的是在不同的条件下，巡检排班的线路及巡检人数、时间表。将每个巡检点看作一个图的顶点，各巡检点之间的线路看作此图对应顶点间的边，各条线路行走所需要时间看作对應边上的权，所给线路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点巡检调度中心（XJ0022）出发，使所有顶点都能按要求完成巡检，使得总权（路程或时间）最小。
本题是旅行售货员问题的延伸-多旅行售货员问题。本题所求的分班巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）。
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法。显然本问题更应属于NP完全问题。有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解。
三、模型假设
1.巡检人员行走所用时间总是一定，忽略天气等因素的影响。
2.各个点巡检周期、两点之间的连通关系总是一定，忽略故障等其他因素的影响；
3.巡视当中，各巡检点的巡检耗时一定，不会出现特殊情况而延误时间；
4.每个点每次巡检只有一名工人；
四、符号说明
w（i，j）：任意两点i，j间的间距；ei：各点的巡检耗时，即点权；V：各巡检点构成的集合。
五、模型建立与求解
巡视线路图中，每个巡检点看作图中的一个节点，各巡检点之间的线路看作此图对应顶点间的边，各条线路行走所需要时间看作对应边上的权，所给线路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点巡检调度中心（XJ0022）出发，使所有顶点都能按要求完成巡检，此即最佳推销员回路问题。
此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题。由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法。我们需要去寻求一种较合理的划分准则，对图（1）进行初步划分后，分成巡查圈I、巡查圈I、巡查圈I所示的三个组
经过分析我们得出每班至少需要四名工人寻遍所有的巡查点。四名工人分别记为A、B、C、D。工人A负责巡查圈I，工人B、C负责巡查圈II，工人D负责巡查圈III。为了耗费的人力资源尽可能的少，并且每名工人在同一时间段内工作量尽可能均衡。工人A按路线一进行巡查。工人B、工人C分别按路线二、三进行第一次巡查，工人D按路线四进行第一次巡查。第一次四名工人巡检路线如下。
经过第一次巡查后，我们对巡查路线作进一步的优化（如下表），四名工人按照优化后的巡检路线进行巡检。工人A按巡逻圈Ⅰ进行巡检（循环进行，直到换班）；工人B、C按照巡逻圈Ⅱ（3-23路线）交替相向而行进行巡检；工人D按照巡逻圈Ⅲ进行巡检（循环进行，直到换班）。
因为该组检测路线的每个检测周期内有效的每人检测的均衡度
所以这种路线的周期内的每人检测的均衡性较好。
根据巡检路线并考虑巡检工人在一时间段内的工作量尽量平衡，巡检时间表如下：
问题二：顶替轮班
由于巡查人员每巡查2小时左右需要休息一次，8小时工作时间内共计需要休息3次，每个点大约检查15次，休息时间是15到30分钟。
在考虑到工厂巡查的不间断性，工人要在中午12点和下午6点进餐，因此，在原有4个人的基础之上，增加一人，实行顶替轮班的方法。每次一个人进餐，另一人顶替进餐者进行巡检，进餐者用完餐后立刻返回其岗位，让顶替者到另一路线顶替其他工人进餐，以此类推，该顶替者共计要连续工作0.5×4=2小时，并且当其他工人休息时顶班工作，时间为15×4=1小时，所以顶班工人实际工作时间为3小时。综合以上分析，在保证工厂巡检正常进行，第一班0：00-8：00需要工人4人，第二班8：00-16：00需要工人5人，第三班16：00-24：00需要工人5人。如果采用每天三班倒，共计需要14人。其巡查的时间表如下：
问题三：采用错时上班
由于问题一不考虑巡检人员的休息时间，也不考虑工人的进餐时间，所以错时上班对是否节省时间没有太大影响。工人每天工作8小时左右，每班需要4人，一天依旧需要12名工人巡检。
由于问题二中巡检人员每巡检2小时左右需要休息一次，在中午12：00和下午6：00需要进餐一次，12：00与下午6：00相距6小时，并且采取错时上班制，在8：00-16：00和16：00-24：00的两次巡检中，只需一名工人顶替这两班工人的休息和进餐时间，所以第一班0：00-8：00需要工人四名，第二班和第三班8：00-24：00需要工人9名，共计一天需要13人，所以采用错时上班可以节省人力。
优缺点分析：
优点：
1.本文提出的分组准则简便易行，可操作性强，且可逐步调整使分组达到均衡；
2.用均衡度的概念定量的刻画了分组的均衡性；
3.在用近似算法求近似最佳推销员回路时，采取了三种不同的方法产生初始圈，使得算法比较完善，得到了误差很小的近似最优解；
缺点
1.时间精确度存在一定误差。
参考文献
[1]赵静，数学建模与数学实验（第三版），北京：高等教育出版社，2008.
[2]胡运权，运筹学基础及应用（第三版），哈尔滨：哈尔滨工业大学出版社，1998.
[3]孙惠泉，图论及其应用，北京：科学出版社，2004.
作者简介：费荔枝（1982—），女，硕士，中级.研究方向：生物数学。
通讯作者：E-mail：lvhengmin2005@163.com