全國大學生數(shù)學建模競賽-D題解析

巡檢線路的排班——2021年D題講評主講人：北京工業(yè)大學薛毅Email:xueyi@2021全國數(shù)學建模講評會云南、昆明2021年11月25日整理ppt巡檢線路的排班——2021年D題講評

題目

問題分析及問題1的求解

問題2的求解

問題3的求解閱卷情況簡述整理ppt1.題目——巡檢線路的排班題目——巡檢線路的排班某化工廠有26個點需要進行巡檢以保證正常生產(chǎn)，各個點的巡檢周期、巡檢耗時、兩點之間的連通關(guān)系及行走所需時間在附件中給出。每個點每次巡檢需要一名工人，巡檢工人的巡檢起始地點在巡檢調(diào)度中心〔XJ0022〕，工人可以按固定時間上班，也可以錯時上班，在調(diào)度中心得到巡檢任務(wù)后開始巡檢?，F(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線，使得所有點都能按要求完成巡檢，并且消耗的人力資源盡可能少，同時還應(yīng)考慮每名工人在一時間段內(nèi)〔如一周或一月等〕的工作量盡量平衡。表1Excel表中的根本信息整理ppt表2

Excel表中的連通關(guān)系圖1

Excel表中的連通圖題目——巡檢線路的排班整理ppt問題1.如果采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。問題2.如果巡檢人員每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘，在中午12時和下午6時左右需要進餐一次，每次進餐時間為30分鐘，仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。題目——巡檢線路的排班問題3.如果采用錯時上班，重新討論問題1和問題2，試分析錯時上班是否更節(jié)省人力。整理ppt2.問題分析與模型建立問題分析與模型建立這個問題說的復雜一點是旅行商問題〔TravelingSalesmanProblem,TSP〕，或者是多旅行商問題〔m-TSP〕，更嚴格的說，是車輛路徑問題〔VehicleRoutingProblem,VRP〕，而且還是帶有時間窗口的車輛路徑問題〔VehicleRoutingProblemwithTimeWindows,VRPTW〕。

如果這樣考慮問題，這個問題將變得非常復雜。事實上，這個問題并沒有這么復雜，因為它只有26個需要巡視的點，如果每個巡視點安排一個人的話，一個班至多是26個人。當然，沒有那糟糕，如果一個人能巡視3～5個點的話，一個班也就是6～9個人。因此，只需要啟發(fā)式算法就可能得到問題的計算結(jié)果。整理ppt問題分析——巡檢人員下限估計2.1巡檢人員下限估計為估計巡檢人員數(shù)量的下限，先計算出旅行商問題所需要的時間〔包括路程時間和巡檢耗時〕。對于只有26個城市的旅行商問題，無論是精確計算，還是近似計算都是不困難的?？梢钥紤]使用LINGO程序〔見[1]〕得到精確的計算結(jié)果〔見圖2〕，其中路程耗時68分鐘和檢查耗時67分鐘，共計135分鐘。圖2

26個點的TSP線路圖整理ppt由于巡視點兩次巡視的最小間隔時間是35分鐘，且135/35=3.86，因此，一個班至少需要4名工人。從圖2〔TSP圖形〕和題目要求〔從22號點開始巡視〕來看，只用4名工人巡視，肯定是不夠的，應(yīng)考慮增加1名工人，一個班使用5名工人。從上述計算過程來看，實際上，并不需要精確求解TSP，只需近似計算，估計出一個下界即可。例如，可以采用手工計算，也可以采用某些啟發(fā)式算法，如最近領(lǐng)域法、最近插入法、最遠插入法、最廉價插入法、任意插入法和交換兩邊改進方法等。如果不打算自己手工編程，可以使用現(xiàn)成的軟件，例如，R軟件中的TSP函數(shù)〔見[2]〕就可以很好地解決這些問題，提供不同的參數(shù)，選擇你喜歡的算法。問題分析——巡檢人員下限估計整理ppt現(xiàn)知道每個班需要5名工人，所以需要將巡視點劃分成5個區(qū)域，每個區(qū)域最多包含6個點，最少也要有4個點，其目的是保證每個區(qū)域的工作量〔巡視時間〕盡量平衡。由于題目要求，每位工人均從22號點開始巡視，因此，距22號點較近的點那么多安排一些，而距22號較遠的2.2問題1的求解點那么少安排一些。為了完成這種需求的安排，需要計算從22號點至其余各點的最短路，這項工作可用Dijkstra〔戴克斯特拉〕算法完成。當然，也不需要自己編程計算，直接調(diào)用R軟件的shortest.paths()函數(shù)和get.shortest.paths()函數(shù)〔見[2]〕就可完成此問題，所繪圖形如圖3所示。問題分析——問題1的求解整理ppt問題分析——問題1的求解圖3

22號點至其余各點的最短路整理ppt從圖3出發(fā)，作如下嘗試，將22、20、19、2、4和21號點編為第一組；23、24、9、8、17和25號點編為第二組；1、3、6、14、5和7號點編為第三組；26、15、18和12號點編為第四組；11、13、16和10號點編為第五組。每一組都找出相應(yīng)TSP的結(jié)果，具體分組和相應(yīng)的TSP圖形如圖4所示。

這種分組方式是為了滿足題目的要求：在規(guī)定的巡視時間間隔內(nèi)完成巡視；每位工人的工作量盡量平衡，巡視時間即不能過長，也不能過短。問題分析——問題1的求解整理ppt圖4巡檢線路的分組情況，5-TSP問題分析——問題1的求解整理ppt下面給出具體的巡視路線和巡視時間：第1組〔22、20、19、2、4和21號點〕的巡視周期是29分鐘，而21號點的周期間隔是80分鐘，可以兩個35分鐘巡視一次，所以此時巡視同期是27分鐘。第2組〔23、24、9、8、17和25號點〕的巡視，最長周期是32分鐘、最短周期28分鐘〔17號點和25號點的時間間隔為分別為480分鐘和120分鐘〕。第3組〔1、3、6、14、5和7號點〕的巡視，最長周期是32分鐘，最短周期19分鐘〔5號點和7號點的時間間隔分別為720分鐘和80分鐘〕。第4組〔26、15、18和12號點〕的巡視，周期長度是28分鐘。第5組〔11、13、16和10號點〕的巡視，周期長度是25分鐘。問題分析——問題1的求解整理ppt表3第1組巡視的時間表〔局部〕問題分析——問題1的求解整理ppt表4第2組巡視的時間表〔局部〕問題分析——問題1的求解整理ppt表5第3組巡視的時間表〔局部〕問題分析——問題1的求解整理ppt表6第4組巡視的時間表〔局部〕問題分析——問題1的求解整理ppt表7第5組巡視的時間表〔局部〕問題分析——問題1的求解整理ppt3.問題2的求解問題2

——休息時間3.1休息時間為了簡化問題，先不用考慮“每巡視2小時左右休息大約5到10分鐘〞這一要求。因為在問題1的求解過程中，5名工人在巡視過程中，屢次出現(xiàn)5分鐘的空余時間，這些空余時間可作休息時間。在問題1的討論中，每班需要5名工人，考慮兩次進餐時間〔1小時〕，就需要增加5小時，如果再考慮進餐的銜接時間，需要增加的時間還不止5小時，所以僅依賴于原來的5名工人而擠出進餐時間幾乎是不可能的。因此，需要增加1名工人讓他在其他工人進餐時，完成巡視工作。3.2進餐時間整理ppt排班的方法是：原來的排班時間不變；5名工人的進餐時間安排在11時至13時之間，和17時至19時之間；進餐時間為35分鐘〔最小的時間間隔〕，進餐時的巡視工作由第6名〔機動〕工人完成；第6名〔機動〕工人的進餐時間可安排在他不替班的非工作時間。表8至表12給出了局部排班的時間表〔白班和中班〕，圖中的黃色局部是可用于吃飯的時間。第6名〔機動〕工人的巡視時間表，以及替換組的情況如表13所示。問題2

——進餐時間整理ppt表8第1組巡視的時間表〔局部，包含進餐時間〕問題2

——進餐時間整理ppt表9第2組巡視的時間表〔局部，包含進餐時間〕問題2

——進餐時間整理ppt表10第3組巡視的時間表〔局部，包含進餐時間〕問題2

——進餐時間整理ppt表11第4組巡視的時間表〔局部，包含進餐時間〕問題2

——進餐時間整理ppt表12第5組巡視的時間表〔局部，包含進餐時間〕問題2

——進餐時間整理ppt表13第6組〔機動〕的巡視時間表問題2

——進餐時間整理ppt4.問題3的求解4.1上班時間問題3是考慮錯時上班能否更省人力。由前面的分析〔巡視人員的下限和問題1〕,知道人員的下限是每班4人，而固定時間上班那么需要每班5人。那么，是否能省下這1個人成為問題的關(guān)鍵。如果能省，應(yīng)在哪個地方??；如果不能省，這個問題也就沒有討論的必要了。每個點的檢查時間〔共計67分鐘〕肯定是不能省，因此，要省也只能省下巡視中所花的路程時間。巡視全部點〔26個點〕的最短路程這恰好是一個旅行商問題，由前面的計算，這個時間是68分鐘。問題3

——上班時間整理ppt那么巡視全部點的最短時間是135分鐘。而題目要求，要在規(guī)定的時間間隔〔最短為35分鐘〕內(nèi)完成各點的巡視。這樣，只能換一種排班方法，讓每名巡視工人完成一輪〔26個點〕的巡視，而每名工人的上班時間向后錯35分鐘，即在前一位工人開始巡視的35分鐘之后，再安排另一名工人巡視。對于巡視間隔要求大于35分鐘的點，可以采用下面的方法處理：無論哪一個點，一律在35分鐘巡視一次，這樣肯定滿足題目的要求；在滿足巡視時間間隔要求的情況下，可以不巡視，但要在相應(yīng)點處休息，休息的時間就是該點的巡視需要的時間。問題3

——上班時間整理ppt因此，得到如下的排班方法：第1名工人在8:00開始巡視〔上班或換班〕，第2名工人那么在8:35開始巡視，第3名是9:10，第4名是9:45。而每位工人都走最優(yōu)的旅行商路線。注意到，每名巡視工人的間隔時間是35分鐘，4名工人的間隔時間是140分鐘，而一次26個點的旅行商問題的用時是135分鐘。如果第1名工人在第一輪巡視后，休息5分鐘，那么他要在10:20開始第二輪的巡視，與第一輪巡視的第4名工人的巡視時間間隔正好相差35分鐘。第2名工人第二輪巡視的開始時間是10:55，與第1名工人相差35分鐘，以此類推。由上述推導可知，4名工人足夠滿足巡視的要求，同時也到達了巡視人員要求的下界，是最優(yōu)的。問題3

——上班時間整理ppt表14錯時上班的時間表〔局部〕問題3

——上班時間整理ppt4.2換班時間由于題目要求，上班或換班的地點只能是調(diào)度中心，也就是說，只能在完成一輪〔26個點〕巡視后才能換班。因此，每名工人的換班時間只能是140分鐘的整數(shù)倍，選擇適宜的時間點，工作7個小時開始換班。例如，第一班工作的4名工人上班的時間分別是8:00、8:35、9:10和9:45，那么，第二班的4名工人的換班時間分別是15:00、15:35、16:10和16:45，第三班的4名工人的換班時間分別是22:00、22:35、23:10和23:45。由于每天是24小時，而換班的時間是7小時，三班下來是21小時，所以每天的換班時間比前一天提前3小時。

問題3

——換班時間整理ppt也就是說，第一班的4名工人在第二天的換班時間分別是5:00、5:35、6:10和6:45；第二班的4名工人在第二天的換班時間分別是12:00、12:35、13:10和13:45；第三班的4名工人在第二天的換班時間分別是19:00、19:35、20:10和20:45。以后的各天以此類推，每天提早3個小時換班。一周7天，有7個24小時，恰好有8個21小時，所以這種換班方案一周重復一次。具體換班方案如表15所示。4.3中間休息與問題2相同，這里不用考慮每2個小時左右休息5分鐘的問題，因為這里面有太多的休息時間。例如，一輪巡視后，可休息5分鐘。問題3

——換班時間整理ppt表15錯時上班的換班時間表問題3

——中間休息整理ppt4.4進餐時間考慮進餐時間會使排班麻煩一些。首先由于進餐時間增加了4個小時，所以，不可能在一個班內(nèi)由4名工人完成。與問題2一樣，需要增加1名機開工人，頂替工人吃飯時的巡視。由于題目要求，換班只能在22號點完成，也就是說，吃飯的換班時間也只能在22號點完成，也就是在完成某一輪的巡視后，才可以考慮進餐。還以第一班工作時間為例，考慮進餐時間的安排。從8:35開始工作的第2名工人，在10:50完成第一輪的巡視，如果他不進餐，將在10:55開始第二輪的巡視，這時，可以考慮讓他停止工作，選擇吃午飯，他的工作由機動〔第5名〕工人替代完成。問題3

——進餐時間整理ppt在30分鐘后，讓11:25完成第一輪巡視的第3名工人休息進餐，而第2名工人來接替他，在11:30開始工作。之后，第3名工作完成進餐后，接替12:05開始工作的第4名工人，讓第4名工人吃午飯。第4名工人午飯后，在12:40接替第1名工人的工作，第1名工人開始吃午飯。第1名工人在午飯后就不工作了，需要等到下午18:30分，接替第2名工人的工作，直到這個班工作結(jié)束。在這中間也不考慮他吃晚飯的時間，因為他可以在18:30以前吃完晚飯。此時(18:30)，第2名工人在吃晚飯，飯后(19:05)他接替第3位工人的工作。19:05，第3名工人在吃晚飯，19:40接替第4位工人的工作。問題3

——進餐時間整理ppt20:15，第4位工人開始工作，接替第5位〔機動〕工人的工作。而機開工人那么下班休息〔這時不用考慮他是否吃晚飯〕，因為到第二天的10:50才接替第1位工人的工作，讓第1位工人吃午飯。這個過程較為復雜，詳細排班請見錯時上班的換班時間表,表16顯示了Excel表中排班和換班的局部表格。表16增加吃飯時間的排班表問題3

——進餐時間整理ppt續(xù)表16-2增加吃飯時間的排班表續(xù)表16-1增加吃飯時間的排班表問題3

——進餐時間整理ppt5.閱卷情況簡述閱卷情況——固定上班時間本人參加了北京地區(qū)和全國的D題閱卷，下面就閱卷中遇到的問題談一談本人一點感受。5.1固定上班時間問題1和問題2要求：固定時間上班，并且由巡檢調(diào)度中心〔22號點〕開始巡檢。在通常情況下，三班倒的工作時間分別是8:00——16:00，16:00——24:00和0:00——8:00。這一點絕大多數(shù)的隊都注意到了，所以根本上都采用8點、下午4點和凌晨0點開始上班的模式。當然，如果你認為有必要，采用其他時間開始上班也是正確的，只要是固定時間上班就可以。整理ppt但這個固定上班時間，是每個班組的固定上班時間，不是每個人的固定上班時間。例如，一個班有5個人(5條巡視線路)，那么要求這5個人同時上班。這也是為什么要求大家一定從22號點開始的原因，大家需要集中一下〔如布置工作或其他要求〕。有很多隊理解成每名工人固定時間上班，而上班時間是不同的，這樣理解問題，巡檢工作從22號點開始就無意義了，因為可以讓22號點、23號、1號點、26號點和11號點都是從8點開始工作，而這些點開始上班的時間分別為8:00、7:59、7:52、7:50和7:45，這種方法相當于去掉從22號點開始的要求，降低了題目的難度。事實上，這種做法只需要4個人就夠了。閱卷情況——固定上班時間整理ppt還有一個小問題：每個班的巡檢工作是否能在8小時內(nèi)結(jié)束〔并不要求一定在8小時內(nèi)回到22號點〕，這個問題根本上沒有學生討論，但它應(yīng)該是問題潛在的要求，因為在交接班時，應(yīng)該簡短地說明一下本班的巡檢情況。當然，并不需要見面交流，用一下現(xiàn)代通訊工具是可以的。題目明確要求，給出巡檢人員的巡檢線路和巡檢的時間表，但很多隊只給出巡檢線路圖，并沒有給出具體的巡檢點的時間表。由于沒有巡檢點的排班時間表，因此無法判斷該隊的結(jié)果是否正確，是否滿足巡檢要求。本質(zhì)上沒有完成題目要求，分數(shù)上也會打折扣的。5.2巡檢線路與時間表閱卷情況——巡檢時間表整理ppt5.3休息時間與進餐時間問題2要求：每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘。在中午12時和下午6時左右需要進餐一次，進餐時間為30分鐘。實際上,如果每名巡檢人員的排班時間較均勻，這里并不需要真的考慮休息時間的安排，因為在巡檢中有大量的5分鐘可以作為休息時間。進餐時間不是固定的，否那么，大家都在中午12時進餐，這樣就需要再派其他的工人來頂替進餐時的空缺，需要的人數(shù)是原來的2倍，這顯然過于浪費人力。當進餐時間不固定時，只需要增加一名工人就夠了，這名工人的工作是接替中午和晚上需要進餐的工人，這里的重點是具體的替班時間表。閱卷情況——休息與進餐時間整理ppt5.4錯時上班的討論問題3是討論錯時上班是否更節(jié)省人力，如果不能更節(jié)省人力，這一問也就沒有討論的必要。有的隊，討論了半天還是不能更省人力。可以猜測，該隊應(yīng)該沒有完成題目的要求。實際上，更省人力是這個問題的重點，需要分析在哪些地方可以更省人力。巡檢時間肯定是不能省的，要省也只能是巡檢路線，盡量少走重復路線。這自然會想到旅行商問題。但我們發(fā)現(xiàn)，很多?？茖W校沒有培訓過圖論方面的相關(guān)知識。經(jīng)過驗算,旅行商問題的解是135分鐘，巡檢點的最小間隔時間是35分鐘，因此，需要4名工人就可以能完成工作。閱卷情況——錯時上班時間整理ppt排班方法有點像列車時刻表，每隔35分鐘發(fā)一趟車。這種處理