数学建模国赛17年d题3

1化工厂巡检路径规划与建模摘要本文主要研究化工厂巡检路径规划与排班问题。为提高巡检效率，优化资源分配，需制定科学合理的巡检路径。通过对化工厂巡检工作内容和特点分析，并制定相应的目标体系及约束条件，建立了最短路径的多目标规划模型，使用lingo和Excel求解，得到巡检人员最少的优化方案。针对问题一：以每班需巡检人员尽可能少，工作量尽可能平衡为目标，以固时上班、无休息时间、每条线路周期不超过35min、每天三班制、每班8小时左右为约束，建立多目标规划模型，用图论法求解。先考虑分区，以线路周期内包含尽可能多巡检点与最短路径为目标，将所给巡检点连通图分组，得到共5条巡检路线，最少需5名巡检人员，如路线：22-21-4-2-1-3-6-14-21（具体巡检路线见正文图6，巡检时间表见附录表1、2、3）。为使每条路线在一段时间内的总行走时间均衡，引入均衡度，越小越合理。该模型均衡度为0.35较大，为满足要求，故采用五线三班轮倒制。考虑到该模型在巡检人员每个周期的回程中浪费大量时间，所以不分区处理，利用最短路径和巡检耗时，得到将巡检点全部巡检的最少用时。用巡检一周的最少用时与35min的比值，得到最少巡检人数4名，该优化模型在固时上班条件下，第二班次巡检人员无法在指定时间到达指定点，无法形成班次循环，但可在错时上班条件下应用。针对问题二：在第一问模型基础上，新增每2小时左右巡检人员休息5-10min、在中午12时和下午6时需进餐30分钟的约束，经分析，巡检人员每2小时的休息时间，可通过减少巡检周期大于35min的巡检点巡检次数得到，若线路中无大于35min周期的巡检点或压缩时间太少，可将线路分段并增加巡检人员。最终得到共6条路线，最少需要6名巡检人员，如路线:22-21-4-2-1-2-3-6-14-21。（具体巡检路线见正文图8，巡检时间表见附录表4、5、6）为使进餐时能正常工作，给需进餐的班次增加人员，轮换进餐，维持正常巡检。经分析，将两次进餐时间段都放入同一班次的上班时间内，可最大减少人力资源浪费，且6条巡检路线中有一条可在进餐后仍在指定时间到达指定地点。因此，得到第一班次共需11人，第二、三班次分别需6人。该模型均衡度较大，所以采用三班轮倒制。针对问题三：对于问题一，在错时上班条件下，可利用问题一中建立的优化模型直接进行求解，得到巡检路线1条，共需巡检人员4人。与问题一结果比较，减少了人力资源浪费。对于问题二，在错时上班条件下，调整各班次上下班时间即可减少人力资源浪费，可得到每班次巡检人员6人，且线路不变，仍为6条巡检线路。与问题二结果比较，减少了资源浪费。关键词：多目标规划巡检路径最短路径图论法均衡度2一、问题重述某化工厂现有26个工作点需要进行巡检来保证正常生产，每个工作点的巡检周期、巡检耗时、各点之间的连通关系及行走所需时间在附件中给出。工人可以按固定时间上班，也可以错时上班，在调度中心（XJ0022）得到巡检任务后以调度中心为起点开始巡检，且每个工作点每次巡检只需一名工人。试建立模型来安排巡检人数和巡检路线，使得所有工作点都能按要求完成巡检任务，并且巡检人数尽可能少，同时每名工人在一时间段内（如一周或一月等）的工作量尽可能均衡。问题1：在每天三班倒，每班工作时间为8小时左右，且上下班时间固定，不考虑工人的休息时间等条件下，建立模型。安排巡检线路，给出工人的巡检路线和巡检时间表。问题2：在工人每工作2小时左右休息一次、休息时间5到10分钟、中午12时和下午6时进餐一次及每次进餐时间为30分钟等条件下，仍采用每天三班倒，试建立模型确定每班需要多少人及巡检路线，并给出巡检人员的巡检线路和巡检时间表。问题3：如果采用错时上班，重新讨论问题1和问题2，并分析错时上班能否使巡检人数更少。二、模型假设1.假设巡检过程中，不会出现错检、漏检。2.假设设备是由工人第一次上班时启动。3.假设设备开启时间可以忽略。4.假设行走过程中没有特殊情况耽误，能够准时到达。三、符号说明i巡检点序号j巡检路线序号jL第j条巡检路线行走总时间it第i个巡检点巡检耗时K巡检人员数T路线总耗时R时间冗余ht各路线回程行走耗时3四、问题分析化工厂生产中使用的原料、半成品和成品种类繁多，绝大部分是易燃、易爆、有毒、有腐蚀性的危险品。在生产、运输、使用中管理不当，就会发生火灾、爆炸、中毒和烧伤事故，给工作人员生命财产安全和工厂生产造成重大影响。因此，建立数学模型来解决巡检人员的巡检路线及排班问题，以保证化工生产安全是极为重要的。针对问题一：以每班需要巡检人员尽可能少与工人工作量尽可能平衡作为目标条件；以固时上班、巡检人员无休息时间、每条线路周期小于等于35min、每天三班制、每班工作8小时左右为约束条件，建立多目标规划模型。可使用图论法对该模型进行求解。而后通过分区巡检与不分区巡检的两种模型对比，得到最优模型。针对问题二：在第一问的模型基础上，新增巡检人员每2小时左右休息5-10min、在中午12时和下午6时需要进餐30分钟的约束条件，经分析，巡检人员每2小时的休息时间可以通过减少巡检周期大于35min的巡检点的次数来得到；若线路中没有大于35min周期的巡检点或压缩时间太少，可将线路分段并增加巡检人员。为使进餐时也能正常工作，给需要进餐的班次增加巡检人员，轮换进餐，维持正常巡检。针对问题三：在问题一、问题二模型的基础上，采用错时上班，并分别重新建立模型，分析错时上班是否能使巡检人员更少。对于问题一，在错时上班条件下，可利用问题一中建立的优化模型直接进行求解，对于问题二，在错时上班条件下，调整各班次上下班时间即可减少人力资源浪费。五、模型的建立及求解问题一固时上班无休息模型：5.1.1建立模型：要求巡检人数最少的巡检线路方案，只需让每个工人在其巡检点的最小周期内巡检尽可能多的工作点并原路返回第一个巡检点，下个周期再从第一个巡检点出发，就可得到巡检人数最少的巡检线路方案。寻找XJ0022到各点的最短路径：首先，引入0-1变量，设ijS表示第i个巡检点与第j个巡检点是否直接连通，即：1j=(,1,2,...,26)0ijijSij第i个巡检点与第个巡检点直接连通第个巡检点与第个巡检点不直接连通各巡检点之间的行走耗时赋权图的邻接矩阵为ijW，其中ijWP表示巡检点i到巡检点j的权值为P。建立最短路径模型如下：262611minijijijZWS426261126126126126110.t1001kjijijajjkakkbkbjjijijijSSSSsSSSWSi,j=1,2,...,n或其中，,ab分别为起始点和目标点。利用lingo程序求解（见附录程序1）得到如下表1所示的XJ0022到各点的最短路径。表1：22点到每个点的最短路径到达点经过路径最短时间（min)122-21-4-2-18222-21-4-26322-21-4-2-37422-21-43522-21-4-2-3-58622-21-4-2-3-68722-21-4-2-3-5-710822-23-24-9-25-17-89922-23-24-941022-21-4-2-3-6-10131122-21-4-2-3-6-10-11151222-23-24-9-25-26-15-12181322-21-4-2-3-6-10-11-13171422-21-4-2-3-6-1491522-23-24-9-25-26-15161622-21-4-2-3-6-10-11-13-16191722-23-24-9-25-1781822-23-24-9-25-26-15-18181922-20-1942022-20252122-21222002322-2312422-23-2422522-23-24-9-2572622-23-24-9-25-2610找出最短路径中包含巡检点较多的几条巡检路径，并用最小周期35min为各条路径的周期，然后筛选出其中总耗时T小于或等于35min的巡检路径。因为最小周期时间不能被8小时整除，所以下面每班上班时间，采用13周期制或14周期制。考虑到工作量要均衡，所以以每条巡检路线行走总时间作为工作量，建立如下模型：max()min()max()jjjLLaL其中，jL为最终确立的巡检路线行走的总时间。最后，由题意要求，假设各巡检点巡检所耗时间为it，巡检人数为K,则可得到目标规划模型如下：minK262611().35ijiijTTtstT其中，1,2,...,26,1,2,...,26ij5.1.2求解模型：假设工人第一天上班时，第一天上班时间为8：00；各巡检点设备由巡检人员开启，每班上班八小时左右以最短路径中包含巡检点较多的几条巡检路径为主要排查对象，并用最小周期35min为各条路径的周期来筛选巡检路线。下面用图论法求解该模型：路线1：鉴于最小线路周期中巡检尽可能多的点及优先考虑只连通一个点的目标。所以尝试从起始点（XJ0022）出发，不检修XJ0022依次经过XJ0021、XJ0004、XJ0002、XJ0001、XJ0003、XJ0006、XJ0014等巡检点，因为不巡检XJ0022，所以最终回到XJ0021即可。因为该路线中损耗时间为37min，而线路损耗时间要控制在35min及以下，经观察可以将XJ0002或XJ0004放在其他路线中巡检,又因为XJ0002为各条最短路径的交集点,所以选择XJ0002为线路1中不巡检的点，此时巡检线路周期刚好为35min。易知当线路周期为35min时，每班工作周期为14次。由此得到路线1的循环路线图，如下：6图1:路线1的循环路线图路线1：○22→○21→○4→□2→○1→○3→○6→○14→○21行走时间：1C=20min,□2表示只路过不巡检，从21→21循环巡检一周为35min。各巡检点具体时间算法：到达时间=前一个点离开时间+行走所耗时间离开时间=该点到达时间+巡检所耗时间路线1安排：第一天上班时间为8:00，不巡检XJ0022，直接从XJ0022到XJ0021损耗时间为2min，所以到达XJ0021的时间为8:02，然后开始巡检XJ0021，所耗时间为3min，所以离开时间为8:05,到XJ0004行走损耗时间为1min，所以到达时间为8:06，巡检损耗时间为2min，所以离开时间为8:08。以此类推，得到该路线中各点的所有到达时间及离开时间表。具体巡检时间表如下表2：表2:线路1工人到各巡检点时间巡检点序号第一次巡检时间段第二次到达时间„„第十三次到达时间第十四次到达时间XJ00218:02-8:058:37„„15:0215:37XJ00048:06-8:088:41„„15:0615:41XJ00028:11-8:118:46„„15:1115:46XJ00018:13-8:168:48„„15:1315:48XJ00038:19-8:228:54„„15:1915:54XJ00068:23-8:268:58„„15:2315:58XJ00148:27-8:309:02„„15:2716:02观察表2，发现路线1早班八小时可以工作14个周期。路线2安排：再次从起始点（XJ0022）出发，同路线1相同，不检修XJ0022时，巡检点最多，且时间刚好35min，所以不检修XJ0022，并依次经过XJ0020、XJ0019、XJ0002、XJ0003、XJ0005、XJ0007等巡检点，同样，因为不巡检XJ0022，所以最后回到XJ0020即可,除了XJ0003在线路1中已经巡检，故不再巡检只是路过，其余点全部巡检。总共损耗时间恰好也是35min。由此得到具体巡检线路图如下：7图2:路线2的循环路线图路线2：○22→○20→○19→○2→□3→○5→○7→○20行走时间：2C=24min,□3表示只路过不巡检，从20→20循环巡检一周为35min.具体巡检时间表如下：表3:线路2工人到达各巡检