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

1、巡檢線路的排班2017年D題講評主講人：北京工業(yè)大學 薛毅 Email: 2017全國數(shù)學建模講評會云南、昆明2017年11月25日巡檢線路的排班2017年D題講評主講人：北京工業(yè)大學 薛巡檢線路的排班2017年D題講評 題目 問題分析及問題1的求解 問題2的求解 問題3的求解 閱卷情況簡述巡檢線路的排班2017年D題講評 題目 問題分析1. 題目 巡檢線路的排班題目 巡檢線路的排班 某化工廠有 26 個點需要進行巡檢以保證正常生產(chǎn)，各個點的巡檢周期、巡檢耗時、兩點之間的連通關系及行走所需時間在附件中給出。 每個點每次巡檢需要一名工人，巡檢工人的巡檢起始地點在巡檢調度中心（XJ0022），工人

2、可以按固定時間上班，也可以錯時上班，在調度中心得到巡檢任務后開始巡檢。現(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線，使得所有點都能按要求完成巡檢，并且耗費的人力資源盡可能少，同時還應考慮每名工人在一時間段內（如一周或一月等）的工作量盡量平衡。表1 Excel表中的基本信息1. 題目 巡檢線路的排班題目 巡檢線路的排班 表2 Excel表中的連通關系圖1 Excel表中的連通圖題目 巡檢線路的排班表2 Excel表中的連通關系圖1 Excel表中的連通問題1.如果采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和

3、巡檢的時間表。問題2. 如果巡檢人員每巡檢 2 小時左右需要休息一次，休息時間大約是 5 到 10 分鐘，在中午12 時和下午 6 時左右需要進餐一次，每次進餐時間為 30 分鐘，仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。題目 巡檢線路的排班問題3. 如果采用錯時上班，重新討論問題 1 和問題 2，試分析錯時上班是否更節(jié)省人力。問題1.如果采用固定上班時間，不考慮巡檢人員的休息時間，采用2.問題分析與模型建立問題分析與模型建立 這個問題說的復雜一點是旅行商問題（Traveling Salesman Problem, TSP），或者是多旅行商問題

4、（m-TSP），更嚴格的說，是車輛路徑問題（Vehicle Routing Problem, VRP），而且還是帶有時間窗口的車輛路徑問題（Vehicle Routing Problem with Time Windows, VRPTW）。 如果這樣考慮問題，這個問題將變得非常復雜。事實上，這個問題并沒有這么復雜，因為它只有26個需要巡視的點，如果每個巡視點安排一個人的話，一個班至多是26個人。當然，沒有那糟糕，如果一個人能巡視35個點的話，一個班也就是 69 個人。因此，只需要啟發(fā)式算法就可能得到問題的計算結果。2.問題分析與模型建立問題分析與模型建立 這個問題分析巡檢人員下限估計2.1 巡

5、檢人員下限估計 為估計巡檢人員數(shù)量的下限，先計算出旅行商問題所需要的時間（包括路程時間和巡檢耗時）。對于只有26個城市的旅行商問題，無論是精確計算，還是近似計算都是不困難的。 可以考慮使用LINGO程序（見1）得到精確的計算結果（見圖2），其中路程耗時68分鐘和檢查耗時67分鐘，共計135分鐘。圖2 26個點的TSP線路圖問題分析巡檢人員下限估計2.1 巡檢人員下限估計 由于巡視點兩次巡視的最小間隔時間是35分鐘，且135/35=3.86，因此，一個班至少需要4名工人。從圖2 （TSP圖形）和題目要求（從22號點開始巡視）來看，只用4名工人巡視，肯定是不夠的，應考慮增加1名工人，一個班使用5名

6、工人。 從上述計算過程來看，實際上，并不需要精確求解TSP，只需近似計算，估計出一個下界即可。 例如，可以采用手工計算，也可以采用某些啟發(fā)式算法，如最近領域法、最近插入法、最遠插入法、最便宜插入法、任意插入法和交換兩邊改進方法等。 如果不打算自己手工編程，可以使用現(xiàn)成的軟件，例如，R軟件中的TSP函數(shù)（見2）就可以很好地解決這些問題，提供不同的參數(shù)，選擇你喜歡的算法。問題分析巡檢人員下限估計 由于巡視點兩次巡視的最小間隔時間是35分鐘，且135 現(xiàn)知道每個班需要5名工人，所以需要將巡視點劃分成5個區(qū)域，每個區(qū)域最多包含6個點，最少也要有4個點，其目的是保證每個區(qū)域的工作量（巡視時間）盡量平衡。

7、 由于題目要求，每位工人均從22號點開始巡視，因此，距22號點較近的點則多安排一些，而距22號較遠的2.2 問題1的求解點則少安排一些。為了完成這種需求的安排，需要計算從22號點至其余各點的最短路，這項工作可用Dijkstra （戴克斯特拉）算法完成。 當然，也不需要自己編程計算，直接調用R軟件的shortest.paths()函數(shù)和get.shortest.paths()函數(shù)（見2）就可完成此問題，所繪圖形如圖3所示。問題分析 問題1的求解 現(xiàn)知道每個班需要5名工人，所以需要將巡視點劃分成5個問題分析 問題1的求解圖3 22號點至其余各點的最短路問題分析 問題1的求解圖3 22號點至其余各點

8、的最短 從圖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號點編為第五組。 每一組都找出相應TSP的結果，具體分組和相應的TSP圖形如圖4所示。 這種分組方式是為了滿足題目的要求：在規(guī)定的巡視時間間隔內完成巡視；每位工人的工作量盡量平衡，巡視時間即不能過長，也不能過短。問題分析 問題1的求解 從圖3出發(fā)，作如下嘗試，將 每一組都找出相應TS圖4 巡檢線路的分組情況，5-TSP問題分析 問題1的求解圖4 巡檢線路的分組情況，5-T

9、SP問題分析 問題1下面給出具體的巡視路線和巡視時間：第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號點）的

10、巡視，周期長度是25分鐘。問題分析 問題1的求解下面給出具體的巡視路線和巡視時間： 120分鐘）。問題分表3 第1組巡視的時間表（部分）問題分析 問題1的求解表3 第1組巡視的時間表（部分）問題分析 問題1的表4 第2組巡視的時間表（部分）問題分析 問題1的求解表4 第2組巡視的時間表（部分）問題分析 問題1的表5 第3組巡視的時間表（部分）問題分析 問題1的求解表5 第3組巡視的時間表（部分）問題分析 問題1的表6 第4組巡視的時間表（部分）問題分析 問題1的求解表6 第4組巡視的時間表（部分）問題分析 問題1表7 第5組巡視的時間表（部分）問題分析 問題1的求解表7 第5組巡視的時間表（部

11、分）問題分析 問題13.問題2的求解問題2 休息時間3.1 休息時間 為了簡化問題，先不用考慮“每巡視2小時左右休息大約5到10分鐘”這一要求。 因為在問題1的求解過程中，5名工人在巡視過程中，多次出現(xiàn)5分鐘的空余時間，這些空余時間可作休息時間。 在問題1的討論中，每班需要5名工人，考慮兩次進餐時間（1小時），就需要增加5小時，如果再考慮進餐的銜接時間，需要增加的時間還不止5小時，所以僅依賴于原來的5名工人而擠出進餐時間幾乎是不可能的。 因此，需要增加1名工人讓他在其他工人進餐時，完成巡視工作。3.2 進餐時間3.問題2的求解問題2 休息時間3.1 休息時間 排班的方法是：原來的排班時間不變；

12、5名工人的進餐時間安排在11時至13時之間，和17時至19時之間；進餐時間為35分鐘（最小的時間間隔），進餐時的巡視工作由第6名（機動）工人完成；第6名（機動）工人的進餐時間可安排在他不替班的非工作時間。 表8至表12給出了部分排班的時間表（白班和中班），圖中的黃色部分是可用于吃飯的時間。 第6名（機動）工人的巡視時間表，以及替換組的情況如表13所示。問題2 進餐時間排班的方法是：問題2 進餐時間表8 第1組巡視的時間表（部分，包含進餐時間）問題2 進餐時間表8 第1組巡視的時間表（部分，包含進餐時間）問題2 表9 第2組巡視的時間表（部分，包含進餐時間）問題2 進餐時間表9 第2組巡視的時間

13、表（部分，包含進餐時間）問題2 表10 第3組巡視的時間表（部分，包含進餐時間）問題2 進餐時間表10 第3組巡視的時間表（部分，包含進餐時間）問題2表11 第4組巡視的時間表（部分，包含進餐時間）問題2 進餐時間表11 第4組巡視的時間表（部分，包含進餐時間）問題2 表12 第5組巡視的時間表（部分，包含進餐時間）問題2 進餐時間表12 第5組巡視的時間表（部分，包含進餐時間）問題2 表13 第6組（機動）的巡視時間表問題2 進餐時間表13 第6組（機動）的巡視時間表問題2 進餐時間4.問題3的求解4.1 上班時間 問題3是考慮錯時上班能否更省人力。 由前面的分析（巡視人員的下限和問題1）,

14、 知道人員的下限是每班4人，而固定時間上班則需要每班5人。那么，是否能省下這1個人成為問題的關鍵。 如果能省，應在哪個地方??；如果不能省，這個問題也就沒有討論的必要了。 每個點的檢查時間（共計67分鐘）肯定是不能省，因此，要省也只能省下巡視中所花的路程時間。 巡視全部點（26個點）的最短路程這恰好是一個旅行商問題，由前面的計算已知，這個時間是68分鐘。問題3 上班時間4.問題3的求解4.1 上班時間 問題3是考慮錯時上班 那么巡視全部點的最短時間是135分鐘。而題目要求，要在規(guī)定的時間間隔（最短為35分鐘）內完成各點的巡視。 這樣，只能換一種排班方法，讓每名巡視工人完成一輪（26個點）的巡視，

15、而每名工人的上班時間向后錯35分鐘，即在前一位工人開始巡視的35分鐘之后，再安排另一名工人巡視。 對于巡視間隔要求大于35分鐘的點，可以采用下面的方法處理：無論哪一個點，一律在35分鐘巡視一次，這樣肯定滿足題目的要求；在滿足巡視時間間隔要求的情況下，可以不巡視，但要在相應點處休息，休息的時間就是該點的巡視需要的時間。問題3 上班時間 那么巡視全部點的最短時間是135分鐘。而題目要求，要 因此，得到如下的排班方法：第1名工人在8:00開始巡視（上班或換班），第2名工人則在8:35開始巡視，第3名是9:10，第4名是9:45。而每位工人都走最優(yōu)的旅行商路線。 注意到，每名巡視工人的間隔時間是35分

16、鐘，4名工人的間隔時間是140分鐘，而一次26個點的旅行商問題的用時是135分鐘。 如果第1名工人在第一輪巡視后，休息5分鐘，那么他要在10:20開始第二輪的巡視，與第一輪巡視的第4名工人的巡視時間間隔正好相差35分鐘。第2名工人第二輪巡視的開始時間是10:55，與第1名工人相差35分鐘，以此類推。 由上述推導可知，4名工人足夠滿足巡視的要求，同時也達到了巡視人員要求的下界，是最優(yōu)的。問題3 上班時間 因此，得到如下的排班方法：第1名工人在8:00表14 錯時上班的時間表（部分）問題3 上班時間表14 錯時上班的時間表（部分）問題3 上班時間4.2 換班時間 由于題目要求，上班或換班的地點只能

17、是調度中心，也就是說，只能在完成一輪（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 換班時間4.2 換班時間 由于題目要求，上班或換班的地點只能是 也就是說，第一班的4

18、名工人在第二天的換班時間分別是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 換班時間 也就是說，第一班的4名工人在第二天的換班時間分別

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

20、工作由機動（第5名）工人替代完成。問題3 進餐時間4.4 進餐時間 考慮進餐時間會使排班麻煩一些。 首先 在30分鐘后，讓11:25完成第一輪巡視的第3名工人休息進餐，而第2名工人來接替他，在11:30開始工作。 之后，第3名工作完成進餐后，接替12:05開始工作的第4名工人，讓第4名工人吃午飯。 第4名工人午飯后，在12:40接替第1名工人的工作，第1名工人開始吃午飯。 第1名工人在午飯后就不工作了，需要等到下午18:30分，接替第2名工人的工作，直到這個班工作結束。在這中間也不考慮他吃晚飯的時間，因為他可以在18:30以前吃完晚飯。 此時(18:30)，第2名工人在吃晚飯，飯后(19:05

21、)他接替第3位工人的工作。 19:05，第3名工人在吃晚飯，19:40接替第4位工人的工作。問題3 進餐時間 在30分鐘后，讓11:25完成第一輪巡視的第3名工人 20:15，第4位工人開始工作，接替第5位（機動）工人的工作。而機動工人則下班休息（這時不用考慮他是否吃晚飯），因為到第二天的10:50才接替第1位工人的工作，讓第1位工人吃午飯。 這個過程較為復雜，詳細排班請見錯時上班的換班時間表, 表16顯示了Excel表中排班和換班的部分表格。表16 增加吃飯時間的排班表問題3 進餐時間 20:15，第4位工人開始工作，接替第5位（機動）工續(xù)表16-2 增加吃飯時間的排班表續(xù)表16-1 增加吃

22、飯時間的排班表問題3 進餐時間續(xù)表16-2 增加吃飯時間的排班表續(xù)表16-1 增加5.閱卷情況簡述閱卷情況 固定上班時間 本人參加了北京地區(qū)和全國的D題閱卷，下面就閱卷中遇到的問題談一談本人一點感受。5.1 固定上班時間 問題1和問題2要求：固定時間上班，并且由巡檢調度中心（22號點）開始巡檢。 在通常情況下，三班倒的工作時間分別是8:00 16:00，16:00 24:00和0:00 8:00。 這一點絕大多數(shù)的隊都注意到了，所以基本上都采用8點、下午4點和凌晨0點開始上班的模式。當然，如果你認為有必要，采用其他時間開始上班也是正確的，只要是固定時間上班就可以。5.閱卷情況簡述閱卷情況 固定

23、上班時間 本人參加 但這個固定上班時間，是每個班組的固定上班時間，不是每個人的固定上班時間。 例如，一個班有5個人 (5條巡視線路)，則要求這5個人同時上班。這也是為什么要求大家一定從22號點開始的原因，大家需要集中一下（如布置工作或其他要求）。 有很多隊理解成每名工人固定時間上班，而上班時間是不同的，這樣理解問題，巡檢工作從22號點開始就無意義了，因為可以讓22號點、23號、1號點、26號點和11號點都是從8點開始工作，而這些點開始上班的時間分別為8:00、7:59、7:52、7:50和7:45，這種方法相當于去掉從22號點開始的要求，降低了題目的難度。事實上，這種做法只需要4個人就夠了。閱

24、卷情況 固定上班時間 但這個固定上班時間，是每個班組的固定上班時間，不是每 還有一個小問題：每個班的巡檢工作是否能在8小時內結束（并不要求一定在8小時內回到22號點），這個問題基本上沒有學生討論，但它應該是問題潛在的要求，因為在交接班時，應該簡短地說明一下本班的巡檢情況。 當然，并不需要見面交流，用一下現(xiàn)代通訊工具是可以的。 題目明確要求，給出巡檢人員的巡檢線路和巡檢的時間表，但很多隊只給出巡檢線路圖，并沒有給出具體的巡檢點的時間表。 由于沒有巡檢點的排班時間表，因此無法判斷該隊的結果是否正確，是否滿足巡檢要求。本質上沒有完成題目要求，分數(shù)上也會打折扣的。5.2 巡檢線路與時間表閱卷情況 巡檢

25、時間表 還有一個小問題：每個班的巡檢工作是否能在8小時內結束5.3 休息時間與進餐時間 問題2要求：每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘。在中午12時和下午6時左右需要進餐一次，進餐時間為30分鐘。 實際上, 如果每名巡檢人員的排班時間較均勻，這里并不需要真的考慮休息時間的安排，因為在巡檢中有大量的5分鐘可以作為休息時間。 進餐時間不是固定的，否則，大家都在中午12時進餐，這樣就需要再派其他的工人來頂替進餐時的空缺，需要的人數(shù)是原來的2倍，這顯然過于浪費人力。 當進餐時間不固定時，只需要增加一名工人就夠了，這名工人的工作是接替中午和晚上需要進餐的工人，這里的重點是具體的替班

26、時間表。閱卷情況 休息與進餐時間5.3 休息時間與進餐時間 問題2要求：每巡檢2小時左5.4 錯時上班的討論 問題3是討論錯時上班是否更節(jié)省人力，如果不能更節(jié)省人力，這一問也就沒有討論的必要。有的隊，討論了半天還是不能更省人力?？梢圆孪?，該隊應該沒有完成題目的要求。 實際上，更省人力是這個問題的重點，需要分析在哪些地方可以更省人力。 巡檢時間肯定是不能省的，要省也只能是巡檢路線，盡量少走重復路線。這自然會想到旅行商問題。但我們發(fā)現(xiàn)，很多?？茖W校沒有培訓過圖論方面的相關知識。 經(jīng)過驗算,旅行商問題的解是135分鐘，巡檢點的最小間隔時間是35分鐘，因此，需要4名工人就可以能完成工作。閱卷情況 錯時上班時間5.4 錯時上班的討論 問題3是討論錯時上班是否更節(jié)省 排班方法有點像列車時刻表，每隔35分鐘發(fā)一趟車。 這種處理方法大多數(shù)隊已經(jīng)注意到了，但很多隊沒有給出具體的