2017年建模D题论文

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

2、人 员的休息时间，采用每天三班倒，每班工作8小时 左右，每班需要多少人，巡检线路如何安排，并 给出巡检人员的巡检线路和巡检时间表。,问题2： 如果巡检人员每巡检2小时左右需要休息 一次，休息时间大约是5到10分钟，在中午12时和 下午6时左右需要进餐一次，每次进餐时间为30分 钟，仍采用每天三班倒，每班需要多少人，巡检 线路如何安排，并给出巡检人员的巡检线路和巡 检时间表。,问题3： 如果采用错时上班，重新讨论问题1和问 题2，试分析错时上班是否更节省人力。,3,基本信息表（巡检总耗时67分钟）,位号,周期（分） 巡检耗时（分）,位号,周期（分） 巡检耗时（分）,XJ-0001 XJ-0002

3、 XJ-0003 XJ-0004 XJ-0005 XJ-0006 XJ-0007 XJ-0008 XJ-0009 XJ-0010 XJ-0011 XJ-0012 XJ-0013,35 50 35 35 720 35 80 35 35 120 35 35 80,3 2 3 2 2 3 2 3 4 2 3 2 5,XJ-0014 XJ-0015 XJ-0016 XJ-0017 XJ-0018 XJ-0019 XJ-0020 XJ-0021 XJ-0022 XJ-0023 XJ-0024 XJ-0025 XJ-0026,35 35 35 480 35 35 35 80 35 35 35 120 35

4、,3 2 3 2 2 2 3 3 2 3 2 2 2,4,5,1、问题分析,问题所属类型： 旅行商问题（TSP），或者是带有时间窗口的车辆路径 问题。可通过最短路算法，结合启发式得到结果。,巡检路径的设计,本二人人宝,2,固时上班,错时上班,不进餐、不休息 进餐、休息 不考虑,不进餐、不休息 进餐、休息 不考虑,6,2.巡检人员下限估算,图1,7,2.巡检人员下限估算,为估算巡检人员数量的下限，先计算旅行商问题所需 要的时间（包括路程时间和巡检耗时）其中：,路程耗时：68分钟（79-11） 检查耗时：67分钟 共 计：135分钟,由于巡视点两次巡视最小间隔时间是35分钟，即,135,4,35,

5、因此，一个班至少需要4名工人。,8,3. 问题1的求解,题目要求：每名工人均从22点开始巡视。,通过分析可知，每个班需要5名工人，故需要将26个 巡视点划分成5个区域，每个区域最多包含6个点，最少 也要有4个点，其目的是保证每个区域的工作量（巡视 时间）尽量平衡。因此，距22点较近的点可多安排一些， 而距22点较远的点则少安排一些。,具体需求安排，需要计算从22点至其余各点的最短路， 可通过Dijkstra （戴克斯特拉）算法或者LINGO程序完成。,9,22号点到各点的最短路及时间,10,将相同点较多路线合并，得到如表所示路线：,到达点,经过路径,最短时间（min),7,22-21-4-2-

6、3-5-7,10 18 9,12,22-23-24-9-25-26-15-12 22-21-4-2-3-6-14,14,2,16 22-21-4-2-3-6-10-11-13-16,19 8,17 18,22-23-24-9-25-17,22-23-24-9-25-26-15-18,18,19 26,22-20-19,4,22-23-24-9-25-26,10,11,通过最短路径与巡检耗时得到5条路线,注：同一颜色为一区域 路线1：蓝色；路线2：红色；路线3：橘色； 路线4：绿色；路线5：紫色,12,1,5条路线及巡检耗时分别为：,路线一：2221413614 （6个点） 巡检耗时：35min

7、,路线二：222019257 巡检耗时：35min,（5个点）,路线三：22232492526 （6个点） 巡检耗时：35min 路线四：22178101215 （5个点） 巡检耗时：35min,路线五：2218161311 巡检耗时：31min,（4个点）,13,也可以这样划分5条路线：,14,相应的5条路线及巡检耗时分别为：, 第1组：22、20、19、2、4和21点； （6个点）,巡视周期29min； 第2组：23、24、9、8、17和25点； （6个点） 巡视周期32min； 第3组：1、3、6、14、5和7点； （6个点） 巡视周期32min； 第4组：26、15、18和12点； （

8、4个点） 巡视周期28min； 第5组：11、13、16和10点； （4个点） 巡视周期25min。,15,问题1的结论：,班次,上班时间,下班时间,巡检人员数,第一班次 第二班次 第三班次,8:00 16:00 0:00,16:00 0:00 8:00,5 5 5,固定上班每班需要5人，一天共需15人。,16,第1组巡视时间表,17,4. 问题2的求解,4.1 休息时间,可通过减少巡检周期大于35min的巡检点巡检次数得到， 若线路中无大于35min周期的巡检点或压缩时间太少， 可将线路分段并增加巡检人员。,4.2 进餐时间,可以通过调整各班次上下班时间，使得各班次进餐时由下 一班次顶替。

9、如：第一班巡检人员11：00下班进餐，则第 二班次在11：00上班。进餐时间安排可适当放宽在11时至13 时之间和17时至19时之间。,18,固时进餐休息各班次上下班时间及巡检人员数,班次,上班时间 下班时间 巡检人员数,第一班次 第二班次 第三班次,3:00 11:00 19:00,11:00 19:00 3:00,6 6 6,19,4.3 问题2的另解,排班方法如下：, 问题1中原排班时间不变；, 进餐时间安排在11时至13时之间和17时至19时之间； 进餐时间为35分钟（最小巡视周期）； 进餐时由第6名（机动）工人完成巡视工作； 第6名（机动）工人进餐时间可灵活安排在替班前后。,以第2组

10、为例：23、24、9、8、17和25点；,（6个点）巡视周期32min.,20,4.3. 问题2的另解,第2组巡视时间表（黄色部分为进餐时间）,21,4.3. 问题2的另解,第6名工人（机动）巡视时间表,接替顺序： 21354 接替时段： 10:5413:57 17:1020:15,22,问题2的结论：,班次,上班时间,下班时间,巡检人员数,第一班次 第二班次 第三班次,8:00 16:00 0:00,16:00 0:00 8:00,5 5 5,固定上班每班需要5人，考虑休息进餐时间， 需增加一名机动工人作为替补，一天共需16人。,23,5. 问题3的求解,问题3要求：考虑错时上班能否更省人力

11、?,5.1 不考虑休息进餐时间,由前面分析可知，人员下限为每班4人。,排班计划如下：,1）让每名工人完成1轮（26个点）巡视； 2）每名工人上班时间依次向后错35分钟； 即在前一名工人开始巡视35min之后，再 安排后一名工人巡视； 3）对巡视间隔大于35min的点，在相应点 处可休息。,24,Hamilton回路图,25,5. 问题3的求解,具体排班方法如下：,1,第1名工人在8:00开始巡视； 第2名工人在8:35开始巡视； 第3名工人在9:10开始巡视； 第4名工人在9:45开始巡视。,4,2,第1名工人在第1轮巡视后休息5分钟； 第1名工人在10:20开始第2轮巡视.,3,26,5.

12、问题3的求解,第1名工人具体巡视如下：,在8:00开始第1轮巡视；,在10:20开始第2轮的巡视；,在12:40开始第3轮的巡视；,在15:00结束第3轮的巡视；,在每轮巡视后，均休息5分钟，共计巡视420min，即7小时.,27,5. 问题3的求解,错时上班时间表,l结论：,不考虑休息进餐时间的错时上班，每班需要4人，,一天共需12人（小于固时上班15人）。,28,5. 问题3的求解,5.2 考虑休息进餐时间,排班方法如下：, 错时排班时间不变；, 进餐时间可适当放宽；, 进餐时间为35分钟（最小巡视周期）； 进餐时第5名（机动）工人开始替换完成巡视工作； 第5名（机动）工人进餐时间可灵活安排在替班前后。,29,5. 问题3的求解,5.2 考虑休息进餐时间替换表,第1人 8:00 10:20 12:40 换4 第2人 8:35 10:55 换1 13:15 第3人