2017全國大學(xué)生數(shù)學(xué)建模競賽解析演示文檔
《2017全國大學(xué)生數(shù)學(xué)建模競賽解析演示文檔》由會員分享,可在線閱讀,更多相關(guān)《2017全國大學(xué)生數(shù)學(xué)建模競賽解析演示文檔(47頁珍藏版)》請在裝配圖網(wǎng)上搜索。
.,巡檢線路的排班,——2017年D題講評,主講人:北京工業(yè)大學(xué) 薛毅 Email: xueyi@bjut.edu.cn,2017全國數(shù)學(xué)建模講評會 云南、昆明 2017年11月25日,.,巡檢線路的排班——2017年D題講評,題目,問題分析及問題1的求解,問題2的求解,問題3的求解,閱卷情況簡述,.,1. 題目 —— 巡檢線路的排班,題目 —— 巡檢線路的排班,某化工廠有 26 個點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn),各個點(diǎn)的巡檢周期、巡檢耗時、兩點(diǎn)之間的連通關(guān)系及行走所需時間在附件中給出。 每個點(diǎn)每次巡檢需要一名工人,巡檢工人的巡檢起始地點(diǎn)在巡檢調(diào)度中心(XJ0022),工人可以按固定時間上班,也可以錯時上班,在調(diào)度中心得到巡檢任務(wù)后開始巡檢?,F(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線,使得所有點(diǎn)都能按要求完成巡檢,并且耗費(fèi)的人力資源盡可能少,同時還應(yīng)考慮每名工人在一時間段內(nèi)(如一周或一月等)的工作量盡量平衡。,表1 Excel表中的基本信息,.,表2 Excel表中的連通關(guān)系,圖1 Excel表中的連通圖,題目 —— 巡檢線路的排班,.,問題1.如果采用固定上班時間,不考慮巡檢人員的休息時間,采用每天三班倒,每班工作8小時左右,每班需要多少人,巡檢線路如何安排,并給出巡檢人員的巡檢線路和巡檢的時間表。,問題2. 如果巡檢人員每巡檢 2 小時左右需要休息一次,休息時間大約是 5 到 10 分鐘,在中午12 時和下午 6 時左右需要進(jìn)餐一次,每次進(jìn)餐時間為 30 分鐘,仍采用每天三班倒,每班需要多少人,巡檢線路如何安排,并給出巡檢人員的巡檢線路和巡檢的時間表。,題目 —— 巡檢線路的排班,問題3. 如果采用錯時上班,重新討論問題 1 和問題 2,試分析錯時上班是否更節(jié)省人力。,.,2.問題分析與模型建立,問題分析與模型建立,這個問題說的復(fù)雜一點(diǎn)是旅行商問題(Traveling Salesman Problem, TSP),或者是多旅行商問題(m-TSP),更嚴(yán)格的說,是車輛路徑問題(Vehicle Routing Problem, VRP),而且還是帶有時間窗口的車輛路徑問題(Vehicle Routing Problem with Time Windows, VRPTW)。,如果這樣考慮問題,這個問題將變得非常復(fù)雜。事實上,這個問題并沒有這么復(fù)雜,因為它只有26個需要巡視的點(diǎn),如果每個巡視點(diǎn)安排一個人的話,一個班至多是26個人。當(dāng)然,沒有那糟糕,如果一個人能巡視3~5個點(diǎn)的話,一個班也就是 6~9 個人。因此,只需要啟發(fā)式算法就可能得到問題的計算結(jié)果。,.,問題分析——巡檢人員下限估計,2.1 巡檢人員下限估計,為估計巡檢人員數(shù)量的下限,先計算出旅行商問題所需要的時間(包括路程時間和巡檢耗時)。對于只有26個城市的旅行商問題,無論是精確計算,還是近似計算都是不困難的。,可以考慮使用LINGO程序(見[1])得到精確的計算結(jié)果(見圖2),其中路程耗時68分鐘和檢查耗時67分鐘,共計135分鐘。,圖2 26個點(diǎn)的TSP線路圖,.,由于巡視點(diǎn)兩次巡視的最小間隔時間是35分鐘,且135/35=3.86,因此,一個班至少需要4名工人。從圖2 (TSP圖形)和題目要求(從22號點(diǎn)開始巡視)來看,只用4名工人巡視,肯定是不夠的,應(yīng)考慮增加1名工人,一個班使用5名工人。 從上述計算過程來看,實際上,并不需要精確求解TSP,只需近似計算,估計出一個下界即可。,例如,可以采用手工計算,也可以采用某些啟發(fā)式算法,如最近領(lǐng)域法、最近插入法、最遠(yuǎn)插入法、最便宜插入法、任意插入法和交換兩邊改進(jìn)方法等。 如果不打算自己手工編程,可以使用現(xiàn)成的軟件,例如,R軟件中的TSP函數(shù)(見[2])就可以很好地解決這些問題,提供不同的參數(shù),選擇你喜歡的算法。,問題分析——巡檢人員下限估計,.,現(xiàn)知道每個班需要5名工人,所以需要將巡視點(diǎn)劃分成5個區(qū)域,每個區(qū)域最多包含6個點(diǎn),最少也要有4個點(diǎn),其目的是保證每個區(qū)域的工作量(巡視時間)盡量平衡。 由于題目要求,每位工人均從22號點(diǎn)開始巡視,因此,距22號點(diǎn)較近的點(diǎn)則多安排一些,而距22號較遠(yuǎn)的,2.2 問題1的求解,點(diǎn)則少安排一些。為了完成這種需求的安排,需要計算從22號點(diǎn)至其余各點(diǎn)的最短路,這項工作可用Dijkstra (戴克斯特拉)算法完成。 當(dāng)然,也不需要自己編程計算,直接調(diào)用R軟件的shortest.paths()函數(shù)和get.shortest.paths()函數(shù)(見[2])就可完成此問題,所繪圖形如圖3所示。,問題分析 —— 問題1的求解,.,問題分析 —— 問題1的求解,圖3 22號點(diǎn)至其余各點(diǎn)的最短路,.,從圖3出發(fā),作如下嘗試,將 22、20、19、2、4和21號點(diǎn)編為第一組; 23、24、9、8、17和25號點(diǎn)編為第二組; 1、3、6、14、5和7號點(diǎn)編為第三組; 26、15、18和12號點(diǎn)編為第四組; 11、13、16和10號點(diǎn)編為第五組。,每一組都找出相應(yīng)TSP的結(jié)果,具體分組和相應(yīng)的TSP圖形如圖4所示。 這種分組方式是為了滿足題目的要求: 在規(guī)定的巡視時間間隔內(nèi)完成巡視; 每位工人的工作量盡量平衡,巡視時間即不能過長,也不能過短。,問題分析 —— 問題1的求解,.,圖4 巡檢線路的分組情況,5-TSP,問題分析 —— 問題1的求解,.,下面給出具體的巡視路線和巡視時間: 第1組(22、20、19、2、4和21號點(diǎn))的巡視周期是29分鐘,而21號點(diǎn)的周期間隔是80分鐘,可以兩個35分鐘巡視一次,所以此時巡視同期是27分鐘。 第2組(23、24、9、8、17和25號點(diǎn))的巡視,最長周期是32分鐘、最短周期28分鐘(17號點(diǎn)和25號點(diǎn)的時間間隔為分別為480分鐘和,120分鐘)。 第3組(1、3、6、14、5和7號點(diǎn))的巡視,最長周期是32分鐘,最短周期19分鐘(5號點(diǎn)和7號點(diǎn)的時間間隔分別為720分鐘和80分鐘)。 第4組(26、15、18和12號點(diǎn))的巡視,周期長度是28分鐘。 第5組(11、13、16和10號點(diǎn))的巡視,周期長度是25分鐘。,問題分析 —— 問題1的求解,.,表3 第1組巡視的時間表(部分),問題分析 —— 問題1的求解,.,表4 第2組巡視的時間表(部分),問題分析 —— 問題1的求解,.,表5 第3組巡視的時間表(部分),問題分析 —— 問題1的求解,.,表6 第4組巡視的時間表(部分),問題分析 —— 問題1的求解,.,表7 第5組巡視的時間表(部分),問題分析 —— 問題1的求解,.,3.問題2的求解,問題2 ——休息時間,3.1 休息時間,為了簡化問題,先不用考慮“每巡視2小時左右休息大約5到10分鐘”這一要求。 因為在問題1的求解過程中,5名工人在巡視過程中,多次出現(xiàn)5分鐘的空余時間,這些空余時間可作休息時間。,在問題1的討論中,每班需要5名工人,考慮兩次進(jìn)餐時間(1小時),就需要增加5小時,如果再考慮進(jìn)餐的銜接時間,需要增加的時間還不止5小時,所以僅依賴于原來的5名工人而擠出進(jìn)餐時間幾乎是不可能的。 因此,需要增加1名工人讓他在其他工人進(jìn)餐時,完成巡視工作。,3.2 進(jìn)餐時間,.,排班的方法是: 原來的排班時間不變; 5名工人的進(jìn)餐時間安排在11時至13時之間,和17時至19時之間; 進(jìn)餐時間為35分鐘(最小的時間間隔),進(jìn)餐時的巡視工作由第6名(機(jī)動)工人完成; 第6名(機(jī)動)工人的進(jìn)餐時間可安排在他不替班的非工作時間。 表8至表12給出了部分排班的時間表(白班和中班),圖中的黃色部分是可用于吃飯的時間。 第6名(機(jī)動)工人的巡視時間表,以及替換組的情況如表13所示。,問題2 —— 進(jìn)餐時間,.,表8 第1組巡視的時間表(部分,包含進(jìn)餐時間),問題2 —— 進(jìn)餐時間,.,表9 第2組巡視的時間表(部分,包含進(jìn)餐時間),問題2 —— 進(jìn)餐時間,.,表10 第3組巡視的時間表(部分,包含進(jìn)餐時間),問題2 —— 進(jìn)餐時間,.,表11 第4組巡視的時間表(部分,包含進(jìn)餐時間),問題2 —— 進(jìn)餐時間,.,表12 第5組巡視的時間表(部分,包含進(jìn)餐時間),問題2 —— 進(jìn)餐時間,.,表13 第6組(機(jī)動)的巡視時間表,問題2 —— 進(jìn)餐時間,.,4.問題3的求解,4.1 上班時間,問題3是考慮錯時上班能否更省人力。,由前面的分析(巡視人員的下限和問題1), 知道人員的下限是每班4人,而固定時間上班則需要每班5人。那么,是否能省下這1個人成為問題 的關(guān)鍵。,如果能省,應(yīng)在哪個地方省;如果不能省,這個問題也就沒有討論的必要了。 每個點(diǎn)的檢查時間(共計67分鐘)肯定是不能省,因此,要省也只能省下巡視中所花的路程時間。 巡視全部點(diǎn)(26個點(diǎn))的最短路程這恰好是一個旅行商問題,由前面的計算已知,這個時間是68分鐘。,問題3 —— 上班時間,.,那么巡視全部點(diǎn)的最短時間是135分鐘。而題目要求,要在規(guī)定的時間間隔(最短為35分鐘)內(nèi)完成各點(diǎn)的巡視。 這樣,只能換一種排班方法,讓每名巡視工人完成一輪(26個點(diǎn))的巡視,而每名工人的上班時間向后錯35分鐘,即在前一位工人開始巡視的35分鐘之后,再安排另一名工人巡視。,對于巡視間隔要求大于35分鐘的點(diǎn),可以采用下面的方法處理: 無論哪一個點(diǎn),一律在35分鐘巡視一次,這樣肯定滿足題目的要求; 在滿足巡視時間間隔要求的情況下,可以不巡視,但要在相應(yīng)點(diǎn)處休息,休息的時間就是該點(diǎn)的巡視需要的時間。,問題3 —— 上班時間,.,因此,得到如下的排班方法:第1名工人在8:00開始巡視(上班或換班),第2名工人則在8:35開始巡視,第3名是9:10,第4名是9:45。而每位工人都走最優(yōu)的旅行商路線。 注意到,每名巡視工人的間隔時間是35分鐘,4名工人的間隔時間是140分鐘,而一次26個點(diǎn)的旅行商問題的用時是135分鐘。,如果第1名工人在第一輪巡視后,休息5分鐘,那么他要在10:20開始第二輪的巡視,與第一輪巡視的第4名工人的巡視時間間隔正好相差35分鐘。第2名工人第二輪巡視的開始時間是10:55,與第1名工人相差35分鐘,以此類推。 由上述推導(dǎo)可知,4名工人足夠滿足巡視的要求,同時也達(dá)到了巡視人員要求的下界,是最優(yōu)的。,問題3 —— 上班時間,.,表14 錯時上班的時間表(部分),問題3 —— 上班時間,.,4.2 換班時間,由于題目要求,上班或換班的地點(diǎn)只能是調(diào)度中心,也就是說,只能在完成一輪(26個點(diǎn))巡視后才能換班。因此,每名工人的換班時間只能是140分鐘的整數(shù)倍,選擇合適的時間點(diǎn),工作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名工人在第二天的換班時間分別是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小時,所以這種換班方案一周重復(fù)一次。具體換班方案如表15所示。,4.3 中間休息,與問題2相同,這里不用考慮每2個小時左右休息5分鐘的問題,因為這里面有太多的休息時間。例如,一輪巡視后,可休息5分鐘。,問題3 —— 換班時間,.,表15 錯時上班的換班時間表,問題3 —— 中間休息,.,4.4 進(jìn)餐時間,考慮進(jìn)餐時間會使排班麻煩一些。 首先由于進(jìn)餐時間增加了4個小時,所以,不可能在一個班內(nèi)由4名工人完成。與問題2一樣,需要增加1名機(jī)動工人,頂替工人吃飯時的巡視。 由于題目要求,換班只能在22號點(diǎn)完成,也就是說,吃飯的換班時間也只能在22號點(diǎn)完成,也就是在完成,某一輪的巡視后,才可以考慮進(jìn)餐。 還以第一班工作時間為例,考慮進(jìn)餐時間的安排。 從8:35開始工作的第2名工人,在10:50完成第一輪的巡視,如果他不進(jìn)餐,將在10:55開始第二輪的巡視,這時,可以考慮讓他停止工作,選擇吃午飯,他的工作由機(jī)動(第5名)工人替代完成。,問題3 —— 進(jìn)餐時間,.,在30分鐘后,讓11:25完成第一輪巡視的第3名工人休息進(jìn)餐,而第2名工人來接替他,在11:30開始工作。 之后,第3名工作完成進(jìn)餐后,接替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 —— 進(jìn)餐時間,.,20:15,第4位工人開始工作,接替第5位(機(jī)動)工人的工作。而機(jī)動工人則下班休息(這時不用考慮他是否吃晚飯),因為到第二天的10:50才接替第1位工人的工作,讓第1位工人吃午飯。 這個過程較為復(fù)雜,詳細(xì)排班請見錯時上班的換班時間表, 表16顯示了Excel表中排班和換班的部分表格。,表16 增加吃飯時間的排班表,問題3 —— 進(jìn)餐時間,.,續(xù)表16-2 增加吃飯時間的排班表,續(xù)表16-1 增加吃飯時間的排班表,問題3 —— 進(jìn)餐時間,.,5.閱卷情況簡述,閱卷情況 —— 固定上班時間,本人參加了北京地區(qū)和全國的D題閱卷,下面就閱卷中遇到的問題談一談本人一點(diǎn)感受。,5.1 固定上班時間,問題1和問題2要求:固定時間上班,并且由巡檢調(diào)度中心(22號點(diǎn))開始巡檢。,在通常情況下,三班倒的工作時間分別是8:00 ——16:00,16:00 —— 24:00和0:00 ——8:00。 這一點(diǎn)絕大多數(shù)的隊都注意到了,所以基本上都采用8點(diǎn)、下午4點(diǎn)和凌晨0點(diǎn)開始上班的模式。當(dāng)然,如果你認(rèn)為有必要,采用其他時間開始上班也是正確的,只要是固定時間上班就可以。,.,但這個固定上班時間,是每個班組的固定上班時間,不是每個人的固定上班時間。 例如,一個班有5個人 (5條巡視線路),則要求這5個人同時上班。這也是為什么要求大家一定從22號點(diǎn)開始的原因,大家需要集中一下(如布置工作或其他要求)。 有很多隊理解成每名工人固定時,間上班,而上班時間是不同的,這樣理解問題,巡檢工作從22號點(diǎn)開始就無意義了,因為可以讓22號點(diǎn)、23號、1號點(diǎn)、26號點(diǎn)和11號點(diǎn)都是從8點(diǎn)開始工作,而這些點(diǎn)開始上班的時間分別為8:00、7:59、7:52、7:50和7:45,這種方法相當(dāng)于去掉從22號點(diǎn)開始的要求,降低了題目的難度。事實上,這種做法只需要4個人就夠了。,閱卷情況 —— 固定上班時間,.,還有一個小問題:每個班的巡檢工作是否能在8小時內(nèi)結(jié)束(并不要求一定在8小時內(nèi)回到22號點(diǎn)),這個問題基本上沒有學(xué)生討論,但它應(yīng)該是問題潛在的要求,因為在交接班時,應(yīng)該簡短地說明一下本班的巡檢情況。 當(dāng)然,并不需要見面交流,用一下現(xiàn)代通訊工具是可以的。,題目明確要求,給出巡檢人員的巡檢線路和巡檢的時間表,但很多隊只給出巡檢線路圖,并沒有給出具體的巡檢點(diǎn)的時間表。 由于沒有巡檢點(diǎn)的排班時間表,因此無法判斷該隊的結(jié)果是否正確,是否滿足巡檢要求。本質(zhì)上沒有完成題目要求,分?jǐn)?shù)上也會打折扣的。,5.2 巡檢線路與時間表,閱卷情況 —— 巡檢時間表,.,5.3 休息時間與進(jìn)餐時間,問題2要求:每巡檢2小時左右需要休息一次,休息時間大約是5到10分鐘。在中午12時和下午6時左右需要進(jìn)餐一次,進(jìn)餐時間為30分鐘。 實際上, 如果每名巡檢人員的排班時間較均勻,這里并不需要真的考慮休息時間的安排,因為在巡檢中有大量的5分鐘可以作為休息時間。,進(jìn)餐時間不是固定的,否則,大家都在中午12時進(jìn)餐,這樣就需要再派其他的工人來頂替進(jìn)餐時的空缺,需要的人數(shù)是原來的2倍,這顯然過于浪費(fèi)人力。 當(dāng)進(jìn)餐時間不固定時,只需要增加一名工人就夠了,這名工人的工作是接替中午和晚上需要進(jìn)餐的工人,這里的重點(diǎn)是具體的替班時間表。,閱卷情況 —— 休息與進(jìn)餐時間,.,5.4 錯時上班的討論,問題3是討論錯時上班是否更節(jié)省人力,如果不能更節(jié)省人力,這一問也就沒有討論的必要。有的隊,討論了半天還是不能更省人力。可以猜想,該隊?wèi)?yīng)該沒有完成題目的要求。 實際上,更省人力是這個問題的重點(diǎn),需要分析在哪些地方可以更省人力。,巡檢時間肯定是不能省的,要省也只能是巡檢路線,盡量少走重復(fù)路線。這自然會想到旅行商問題。但我 們發(fā)現(xiàn),很多專科學(xué)校沒有培訓(xùn)過圖論方面的相關(guān)知識。 經(jīng)過驗算,旅行商問題的解是135分鐘,巡檢點(diǎn)的最小間隔時間是35分鐘,因此,需要4名工人就可以能完成工作。,閱卷情況 —— 錯時上班時間,.,排班方法有點(diǎn)像列車時刻表,每隔35分鐘發(fā)一趟車。 這種處理方法大多數(shù)隊已經(jīng)注意到了,但很多隊沒有給出具體的時間表。也許學(xué)生已沒有足夠的答題時間了,也許根本就不知道如何計算。 問題3的難度是增加進(jìn)餐時間,大多數(shù)隊基本上都沒有給出這一問題的討論。,我們很多的隊希望給出一個“高大上”的模型,然后再用軟件求解(如LINGO),但由于“高大上”的模型過于復(fù)雜,無法求解(或求解困難),這只能再借助于手工求解。 這樣,這個模型實際上是沒有用的,不如將精力放在問題的分析上,如采用“接地氣”的啟發(fā)式算法 。,5.5 關(guān)于模型,閱卷情況 —— 錯時上班時間,.,5.6 能否更省人力,有的隊想出了更省人力的方法,例如,將進(jìn)餐時間安排在工作時間之外。例如,對于固定上班的工人來說,將三班的工作時間安排為3:30——11:30、11:30——19:30、19:30——3:30 (次日)。 第一班的工人下班后進(jìn)餐,第二班的工人上班前吃午飯下班后吃晚飯,,第三班的工人在上班前吃晚飯,這樣就不用考慮他們進(jìn)餐時,不需要另外的人員替換他們,從而更省人力。 有的隊確實是這樣做的(只是時間略有不同),對于題目要求來說,這種方法無可厚非,但在實際操作中會產(chǎn)生新的問題——是否要吃早飯。 如果能將吃早飯的問題解決,這種結(jié)果無疑是最好的。,閱卷情況 —— 更省人力,.,6.結(jié)論,這個問題看似復(fù)雜,如使用TSP模型、VRP 模型, 甚至是 m-TSP 模型或VRPTW 模型,但由于需要處理的點(diǎn)數(shù)較少,可以運(yùn)用最短路算法,結(jié)合啟發(fā)式方法得到問題的計算結(jié)果: 固定上班時間,每班需要5人,一天共需要15人; 考慮進(jìn)餐時間,增加一名機(jī)動工人作為替補(bǔ),一天需要16人; 如果采用錯時上班,每班需要4人,一天共12人; 如再考慮進(jìn)餐時間,再增加一人,每天需要13人。,.,參考文獻(xiàn),[1] 謝金星,薛毅.優(yōu)化建模與LINDO/LINGO軟件.北京: 清華大學(xué)出版社,2005.7 [2]薛毅.?dāng)?shù)學(xué)建模基于R.北京:機(jī)械工業(yè)出版社,2017.7,.,謝 謝!,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2017 全國大學(xué)生 數(shù)學(xué) 建模 競賽 解析 演示 文檔
鏈接地址:http://www.hcyjhs8.com/p-359785.html