2017年建模D题论文.ppt

《2017年建模D题论文.ppt》由会员分享，可在线阅读，更多相关《2017年建模D题论文.ppt（31页珍藏版）》请在三一办公上搜索。

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-0001XJ-0002XJ-0003XJ-0004XJ-0005XJ-

3、0006XJ-0007XJ-0008XJ-0009XJ-0010XJ-0011XJ-0012XJ-0013,3550353572035803535120353580,3232232342325,XJ-0014XJ-0015XJ-0016XJ-0017XJ-0018XJ-0019XJ-0020XJ-0021XJ-0022XJ-0023XJ-0024XJ-0025XJ-0026,3535354803535358035353512035,3232223323222,4,5,1、问题分析,问题所属类型：旅行商问题（TSP），或者是带有时间窗口的车辆路径问题。可通过最短路算法，结合启发式得到结果。,巡检

4、路径的设计,本二人人宝,2,固时上班,错时上班,不进餐、不休息 进餐、休息不考虑,不进餐、不休息 进餐、休息不考虑,6,2.巡检人员下限估算,图1,7,2.巡检人员下限估算,为估算巡检人员数量的下限，先计算旅行商问题所需要的时间（包括路程时间和巡检耗时）其中：,路程耗时：68分钟（79-11）检查耗时：67分钟共 计：135分钟,由于巡视点两次巡视最小间隔时间是35分钟，即,135,4,35,因此，一个班至少需要4名工人。,8,3.问题1的求解,题目要求：每名工人均从22点开始巡视。,通过分析可知，每个班需要5名工人，故需要将26个巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点

5、，其目的是保证每个区域的工作量（巡视时间）尽量平衡。因此，距22点较近的点可多安排一些，而距22点较远的点则少安排一些。,具体需求安排，需要计算从22点至其余各点的最短路，可通过Dijkstra（戴克斯特拉）算法或者LINGO程序完成。,9,22号点到各点的最短路及时间,10,将相同点较多路线合并，得到如表所示路线：,到达点,经过路径,最短时间（min),7,22-21-4-2-3-5-7,10189,12,22-23-24-9-25-26-15-1222-21-4-2-3-6-14,14,2,16 22-21-4-2-3-6-10-11-13-16,198,1718,22-23-24-9-2

6、5-17,22-23-24-9-25-26-15-18,18,1926,22-20-19,4,22-23-24-9-25-26,10,11,通过最短路径与巡检耗时得到5条路线,注：同一颜色为一区域路线1：蓝色；路线2：红色；路线3：橘色；路线4：绿色；路线5：紫色,12,1,5条路线及巡检耗时分别为：,路线一：2221413614（6个点）巡检耗时：35min,路线二：222019257巡检耗时：35min,（5个点）,路线三：22232492526（6个点）巡检耗时：35min路线四：22178101215（5个点）巡检耗时：35min,路线五：2218161311巡检耗时：31min,（4

7、个点）,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点；（4个点）巡视周期28min；第5组：11、13、16和10点；（4个点）巡视周期25min。,15,问题1的结论：,班次,上班时间,下班时间,巡检人员数,第一班次第二班次第三班次,8:0016:000:00,16:000:008:00,555,固定上班每班需要5人，一天共

8、需15人。,16,第1组巡视时间表,17,4.问题2的求解,4.1 休息时间,可通过减少巡检周期大于35min的巡检点巡检次数得到，若线路中无大于35min周期的巡检点或压缩时间太少，可将线路分段并增加巡检人员。,4.2 进餐时间,可以通过调整各班次上下班时间，使得各班次进餐时由下一班次顶替。如：第一班巡检人员11：00下班进餐，则第二班次在11：00上班。进餐时间安排可适当放宽在11时至13时之间和17时至19时之间。,18,固时进餐休息各班次上下班时间及巡检人员数,班次,上班时间 下班时间 巡检人员数,第一班次第二班次第三班次,3:0011:0019:00,11:0019:003:00,6

9、66,19,4.3 问题2的另解,排班方法如下：,问题1中原排班时间不变；,进餐时间安排在11时至13时之间和17时至19时之间；进餐时间为35分钟（最小巡视周期）；进餐时由第6名（机动）工人完成巡视工作；第6名（机动）工人进餐时间可灵活安排在替班前后。,以第2组为例：23、24、9、8、17和25点；,（6个点）巡视周期32min.,20,4.3.问题2的另解,第2组巡视时间表（黄色部分为进餐时间）,21,4.3.问题2的另解,第6名工人（机动）巡视时间表,接替顺序：21354接替时段：10:5413:5717:1020:15,22,问题2的结论：,班次,上班时间,下班时间,巡检人员数,第一

10、班次第二班次第三班次,8:0016:000:00,16:000:008:00,555,固定上班每班需要5人，考虑休息进餐时间，需增加一名机动工人作为替补，一天共需16人。,23,5.问题3的求解,问题3要求：考虑错时上班能否更省人力?,5.1 不考虑休息进餐时间,由前面分析可知，人员下限为每班4人。,排班计划如下：,1）让每名工人完成1轮（26个点）巡视；2）每名工人上班时间依次向后错35分钟；即在前一名工人开始巡视35min之后，再安排后一名工人巡视；3）对巡视间隔大于35min的点，在相应点处可休息。,24,Hamilton回路图,25,5.问题3的求解,具体排班方法如下：,1,第1名工人

11、在8:00开始巡视；第2名工人在8:35开始巡视；第3名工人在9:10开始巡视；第4名工人在9:45开始巡视。,4,2,第1名工人在第1轮巡视后休息5分钟；第1名工人在10:20开始第2轮巡视.,3,26,5.问题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.

12、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人 9:10 11:30 换2 13:50第4人 9:45 12:05 换3 14:25,第1人 15:00 17:20 19:40 换4第2人 15:35 17:55 换1,第3人 16:10 18:30第4人 16:45 19:05,换2换3,结论：考虑进餐时间，再增加1人机动，每天共需13人，（小于固时上班16人）.,30,5.问题3的求解,增加进餐时间部分排班表,31,