数学建模D18之研究巡检路线的排班状况及优化问题

1研究巡检路线的排班状况及优化问题摘要在确保某工厂能正常运行的情况下，以减少人力资源为目的，让工人生产力得到充分发挥且每名工人的工作量尽可能均衡，确定巡检人员数量，制定恰当的工作时间表和工作路线图。针对问题一：以时间最短为目标函数建立多目标优化模型，采用0-1规划进行建立，先利用excel对附件的数据进行处理，借助lingo软件运行，结合人工对数据的整理，得出要完成该任务每班需要5个工人巡检较为理想，该5个工人具体巡检时间（见表6-1至表6-5）和巡检路线（如图6-2至图6-6）。针对问题二：在问题一的基础上满足巡检工人2小时左右休息一次，因固定上班时间，三班倒，则假设三个班在固定时间进餐，不考虑进餐时间，以时间最少为目标函数，增加约束条件，建立0-1规划，利用lingo软件运行以及对数据的整理，得到每班需要6个工人巡检较为理想，其巡检时间（见表6-7至表6-12）和巡检路线（如图6-9至图6-14）。针对问题三：在问题一和问题二的基础上，采用错时上班，从而增加目标函数，对其建立0-1规划模型，对问题一及问题二再次分别进行讨论，得出错时上班的问题一每班安排4人巡检合理，错时上班的问题二每班安排5人巡检合理，根据相关数据对比，可见错时上班更节省人力资源。关键词0-1规划排班LINGOEXCEL21.问题重述1.1情况说明为保障某化工厂正常运行，需对26个位号进行巡检，每个巡检点要一个工人巡检，且每个工人巡检起始点为位号XJ0022，每个班的上班时间可以固定也可错时，在能完成巡检任务的情况下，尽可能减少人力资源且使每个工人达到工作量均衡。1.2相关信息附件（shift1）:各个位号的周期与巡检耗时的基本信息附件（shift2）:两个位点之间的连通以及行走的耗时数据附件（shift3）:各个位点间的连通图1.3需要解决的问题（1）固定上班时间，三班倒，预测每班需要多少人，并呈现出巡检时间表以及巡检路线图。（2）不固定上班时间，三班倒，每个工人工作量达到2小时左右，需要休息5至10分钟，并且在中午12点及下午6点左右进餐，进餐时间为半个小时，预测每班需要多少人，并呈现出巡检时间表以及巡检路线图。（3）在问题一和问题二的基础上，错时上班，再分别讨论问题一及问题二，进行比较，分析得出采用哪种上班方式更能减少人力资源。2.问题分析2.1问题一分析问题一在固定时间上班，不涉及巡检人员的休息时间的情况下，采用三班倒，每班每天工作8小时左右，且尽量保障每名工人工作量平衡，且每个巡检点在8小时左右都能按时完成巡检任务，为了让每个工人能充分发挥生产力，结合题意假设每个工人工作量之差的绝对值相差10分钟，同时考虑上个巡检点到下个巡检点的时间之和刚好等于下个巡检点的周期，以上均作为限制条件。为降低人力资源消耗，以时间最短（即所用工人最少）建立目标函数[1]，欲借助excel、linggo软件进行数据处理和优化结果。因此为解决此问题，方便讨论，以一个班为基准建立0-1规划模型，得出满足限制条件的最优安排工人人数、巡检时间表和巡检路线图。32.2问题二分析在问题一的基础上，需满足巡检工人2小时左右休息一次，休息时间为5-10分钟，并且在中午12点及下午6点左右进餐，进餐时间为半个小时，为了方便建立优化模型，规定休息时间为10分钟，且不考虑进餐时间，类似问题一，以一个班为基准，同样为尽可能减少人力资源，以时间最少建立目标函数，增加了约束条件，利用lingo程序进行优化，得出满足限制条件的最优安排工人人数、巡检时间表和巡检路线图。2.3问题三分析在问题二的基础之上，采用错时上班，将问题1与问题2中的情况再次重新分析，综合考虑人力资源消耗尽可能的少和每名工人在8小时左右的工作量均衡等方面因素，为使工作最大化，人力资源最小化，建立合理多目标函数，利用lingo软件分别给出错时上班最优化的巡检人数及巡检时间安排，并对问题一、问题二分别进行比对讨论，得出固定上班与错时上班哪一种上班方式更节省人力资源。42.4解题思路模型建立数据处理模型准备数据检测建立目标函数约束条件模型求解结果分析推广与评价运行结果符合实际运行结果不合实际更正相关信息53.问题假设（1）附件中给出的数据来源有效。（2）在巡检过程中，每个巡检人员的技术熟练程度相同，巡检耗时一定，不会出现特殊情况而耽误时间。（3）为减少人力资源且保障工作量均衡的情况下，假设每个班每个人均工作8小时左右。（4）每名工人从第i处到第j处巡检点不考虑速度，则所需路程时间相同。（5）每个巡检点在同一时刻仅需一名工人解决巡检，且同一时刻一名工人只能巡检一个点。（6）每个班每次巡检完不考虑返回时间，只要工作时间达到就可以离开工作岗位。4.符号说明ijt第i处到第j处巡检点路途中所消耗的时数（单位：分钟）其中ij时，0ijtit第i处巡检所消耗时数(分钟)iT第i处巡检周期（分钟）:01kia变量01kikia第个人没有到第处巡检点第k个人到第i处巡检点:01kja变量01kjkjak第个人没有到第处巡检点第个人到第j处巡检点:01ksa变量01ksknakn第个人没有到第s处巡检点第个人有到第s处巡检点22:01ia变量22122022iiia从第处巡检点到第处巡检点从第处巡检点没有到第处巡检点:01kpa变量10kpa从第k处巡检点到第p处巡检点从第k处巡检点没有到第p处巡检点6():01xkia变量10xkiaX班第k个工人在第i处巡检X班第k个工人不在第i处巡检表示巡检点；表示经过巡检点而不巡检表示行走路线方向5.模型准备5.1数据处理（1）为了方便建立下列模型，对附件的巡检点位号进行编号由下表所示：表5-1巡检点位号编号位号XJ-0001XJ-0002XJ-0003XJ-0004XJ-0005XJ-0006XJ-0007编号1234567位号XJ-0008XJ-0009XJ-0010XJ-0011XJ-0012XJ-0013XJ-0014编号891011121314位号XJ-0015XJ-0016XJ-0017XJ-0018XJ-0019XJ-0020XJ-0021编号15161718192021位号XJ-0022XJ-0023XJ-0024XJ-0025XJ-0026编号2223242526（2）采用穷举法将第i处到第j处巡检点所需最短时间计算出来，得出第i处到第j处巡检点所需最短时间汇总图[3]（见附件1）5.2有效数据检测因诸多原因，避免不了数据发生错误，下面分别对给出的周期、巡检耗时的数据中相对特别大的数据视为错误数据，对其进行检测（路程远近不同，因此巡检点之间的路程耗时数不在检测范围之内）[2]：在26个巡检点的周期中其中有4个数据相对平均值特别大，则周期数据正确率为：22%85%26在26个巡检点的巡检耗时数据中有2个数据相对平均值特别大，则7巡检耗时数据正确率为：24%92%26根据数据正确率达85%以上，在后面数据运用中认为是有效的。6.模型的建立与求解6.1问题一模型建立与求解6.1.1模型建立在保障某化工厂26个巡检点能正常运行的情况下，需安排工人巡检，为了减少消耗的人力资源，使用工人人数尽可能少的情况下完成巡检任务。该问题因为固定时间上班，不考虑休息，采用三班倒的方式上班，故假设一个班在8小时左右工作时间内巡检完了之后，下一个班再巡检，则以一个班建立模型即可。下面是一个班从i到j巡检点之间所有时间之和最小（即所用工人最少）为优化目标[4]，建立如下模型:目标函数1：2626i22111min(1)nkikjijikkijZaattTaN（一个班中所有工人从i到j巡检点所有时间，即包括从i到j路上耗时+巡检耗时+周期）目标函数2：12326min,,,,Nbbbb(第k个人从巡检点22到巡检点i所有路程耗时的时间中取最短的时间)其中1286kikjkikjbaabaa3473kikjkikjbaabaa5688kikjkikjbaabaa78109kikjkikjbaabaa910413kikjkikjbaabaa11121518kikjkikjbaabaa（ib表示巡检点22到各个巡检点的最短时间）因为工作时间8小时左右即工作量相差在10分钟内都属于正常，由此，对N进行修正，取N的平均值为9，由上，得到最终目标函数：82626i22111min(1)9nkikjijikkijZaattTa..st26262211470()(1)9480kikjijikijaatta(1,2,......kn（第k个人从巡检点i到巡检点j所花工作时间之和在7时50分钟到8小时之间即第k个人工作量为470分钟至480分钟，以保障每个工人工作量在8小时左右）14801nkikiaT（一班中所有工人在i处的巡检次数之和=8小时内第i处需要巡检的次数,避免在8小时内第i处巡检次数不够而导致不能正常运行）(),1,2,......26kiijijattTij(1,2,......kn（第k个人在第i处巡检点的巡检耗时+从第i处到第j处巡检点之间路程所用时间=第j处的周期，避免时间浪费或不够）[10]262626261111(+)()10kikjijiksiksjijiijijaattaatt分钟(,1,2,......ksnks且（第k个人工作量与第k+s个人工作量相差范围小于等于10分钟，以确保每名工人在上班8小时内工作量的平衡）6.1.2模型求解利用LINGO软件编程[5](见附件2）对上述模型进行计算，其根据运行结果得出要完成该任务需要5个工人，具体巡检情况见图6-1：图6-1工人到各巡检点巡检情况图（注释：1：表示工人到巡检点巡检；0：表示工人没有到该巡检点巡检）通过图6-1可清楚知道每个工人到各个巡检点的巡检情况，并制定巡检时间表及路线图。假设两次检测的时间间隔的误差在正负2分钟以内包括2分钟，划分工作区域（按巡检站1234567891011121314151617181920212223242526第一人11010000000000000011110000第二人00101111100001001000001110第三人00100101100001000000001100第四人00000000001010010100000000第五人000000000101001000000000019照路径最短即时间用得最少进行划分：利用lingo软件运行可得，程序见附件6）[4]。在固定时间上班的情况下，进行三班倒，每个巡检工人在固定的区域里巡检，以下分别是不同班五个巡检员在相同巡检点的不同巡检时间安排，且为工作时间8小时左右中的一个循环划分的巡检时间情况和巡检路线图：第一个巡检人员巡检时间表及巡检路线图：表6-1第一个巡检人员巡检时间表巡检点一班二班三班228:00-8:0216:00-16:020:00-0:02208:04-8:0716:04-16:070:04-0:07198:09-8:1116:09-16:110:09-0:1128:14-8:1616:14-16:160:14-0:1618:18-8:2116:18-16:210:18-0:2148:26-8:2816:26-16:280:26-0:28218:29-8:3216:29-16:320:29-0:32根据表6-1第一个巡检人员巡检时间表得第一个巡检人员巡检路线图[9]（见图6-2）：图6-2第一个巡检人员巡检路线图由图6-2可知第一个巡检工人从巡检点22开始巡检，按箭头指向分别巡检了巡检点22、巡检点20、巡检点19、巡检点2、巡检点1，再返回巡检点2进行巡检，由箭头指向继续向巡检点4、巡检点21进行巡检，最后回到巡检点22下班.第二个巡检人员巡检时