建模D題論文課件

2017D題*建模D題論文2017D題巡檢線路的排班某化工廠有26個點需要進行巡檢以保證正常生產，各個點的巡檢周期、巡檢耗時、兩點之間的連通關系及行走所需時間在附件中給出。每個點每次巡檢需要一名工人，巡檢工人的巡檢起始地點在巡檢調度中心（XJ0022），工人可以按固定時間上班，也可以錯時上班，在調度中心得到巡檢任務后開始巡檢?，F(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線，使得所有點都能按要求完成巡檢，并且耗費的人力資源盡可能少，同時還應考慮每名工人在一時間段內（如一周或一月等）的工作量盡量平衡。建模D題論文2017D題巡檢線路的排班問題1：

如果采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢時間表。問題2：

如果巡檢人員每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘，在中午12時和下午6時左右需要進餐一次，每次進餐時間為30分鐘，仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢時間表。問題3：

如果采用錯時上班，重新討論問題1和問題2，試分析錯時上班是否更節(jié)省人力。建模D題論文基本信息表（巡檢總耗時67分鐘）位號周期（分）巡檢耗時（分）位號周期（分）巡檢耗時（分）XJ-0001XJ-0002XJ-0003XJ-0004XJ-0005XJ-0006XJ-0007XJ-0008XJ-0009XJ-0010XJ-0011XJ-0012XJ-001335503535720358035351203535803232232342325XJ-0014XJ-0015XJ-0016XJ-0017XJ-0018XJ-0019XJ-0020XJ-0021XJ-0022XJ-0023XJ-0024XJ-0025XJ-002635353548035353580353535120353232223323222建模D題論文建模D題論文1、問題分析問題所屬類型：旅行商問題（TSP），或者是帶有時間窗口的車輛路徑問題?？赏ㄟ^最短路算法，結合啟發(fā)式得到結果。巡檢路徑的設計本二人人寶2固時上班錯時上班不進餐、不休息

進餐、休息不考慮不進餐、不休息

進餐、休息不考慮建模D題論文2.巡檢人員下限估算圖1建模D題論文2.巡檢人員下限估算為估算巡檢人員數(shù)量的下限，先計算旅行商問題所需要的時間（包括路程時間和巡檢耗時）其中：路程耗時：68分鐘（79-11）檢查耗時：67分鐘共計：135分鐘由于巡視點兩次巡視最小間隔時間是35分鐘，即135

≈435因此，一個班至少需要4名工人。建模D題論文3.問題1的求解題目要求：每名工人均從22點開始巡視。通過分析可知，每個班需要5名工人，故需要將26個巡視點劃分成5個區(qū)域，每個區(qū)域最多包含6個點，最少也要有4個點，其目的是保證每個區(qū)域的工作量（巡視時間）盡量平衡。因此，距22點較近的點可多安排一些，而距22點較遠的點則少安排一些。具體需求安排，需要計算從22點至其余各點的最短路，可通過Dijkstra（戴克斯特拉）算法或者LINGO程序完成。建模D題論文22號點到各點的最短路及時間建模D題論文將相同點較多路線合并，得到如表所示路線：到達點經過路徑最短時間（min)722-21-4-2-3-5-7101891222-23-24-9-25-26-15-1222-21-4-2-3-6-1414216

22-21-4-2-3-6-10-11-13-16198171822-23-24-9-25-1722-23-24-9-25-26-15-1818192622-20-19422-23-24-9-25-2610建模D題論文通過最短路徑與巡檢耗時得到5條路線注：同一顏色為一區(qū)域路線1：藍色；路線2：紅色；路線3：橘色；路線4：綠色；路線5：紫色1建模D題論文5條路線及巡檢耗時分別為：路線一：22→21→4→1→3→6→14（6個點）巡檢耗時：35min路線二：22→20→19→2→5→7巡檢耗時：35min（5個點）路線三：22→23→24→9→25→26

（6個點）巡檢耗時：35min路線四：22→17→8→10→12→15

（5個點）巡檢耗時：35min路線五：22→18→16→13→11巡檢耗時：31min

（4個點）建模D題論文也可以這樣劃分5條路線：建模D題論文相應的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。????建模D題論文問題1的結論：班次上班時間下班時間巡檢人員數(shù)第一班次第二班次第三班次8:0016:000:0016:000:008:00555固定上班每班需要5人，一天共需15人。建模D題論文第1組巡視時間表建模D題論文4.問題2的求解4.1休息時間可通過減少巡檢周期大于35min的巡檢點巡檢次數(shù)得到，若線路中無大于35min周期的巡檢點或壓縮時間太少，可將線路分段并增加巡檢人員。4.2進餐時間可以通過調整各班次上下班時間，使得各班次進餐時由下一班次頂替。如：第一班巡檢人員11：00下班進餐，則第二班次在11：00上班。進餐時間安排可適當放寬在11時至13時之間和17時至19時之間。建模D題論文固時進餐休息各班次上下班時間及巡檢人員數(shù)班次上班時間

下班時間

巡檢人員數(shù)第一班次第二班次第三班次3:0011:0019:0011:0019:003:00666建模D題論文4.3問題2的另解排班方法如下：?

問題1中原排班時間不變；?

進餐時間安排在11時至13時之間和17時至19時之間；?

進餐時間為35分鐘（最小巡視周期）；?

進餐時由第6名（機動）工人完成巡視工作；?

第6名（機動）工人進餐時間可靈活安排在替班前后。以第2組為例：23、24、9、8、17和25點；（6個點）巡視周期32min.建模D題論文4.3.問題2的另解第2組巡視時間表（黃色部分為進餐時間）建模D題論文4.3.問題2的另解第6名工人（機動）巡視時間表接替順序：2→1→3→5→4接替時段：10:54~13:5717:10~20:15建模D題論文問題2的結論：班次上班時間下班時間巡檢人員數(shù)第一班次第二班次第三班次8:0016:000:0016:000:008:00555固定上班每班需要5人，考慮休息進餐時間，需增加一名機動工人作為替補，一天共需16人。建模D題論文5.問題3的求解問題3要求：考慮錯時上班能否更省人力??5.1不考慮休息進餐時間由前面分析可知，人員下限為每班4人。排班計劃如下：1）讓每名工人完成1輪（26個點）巡視；2）每名工人上班時間依次向后錯35分鐘；即在前一名工人開始巡視35min之后，再安排后一名工人巡視；3）對巡視間隔大于35min的點，在相應點處可休息。建模D題論文Hamilton回路圖建模D題論文5.問題3的求解具體排班方法如下：1第1名工人在8:00開始巡視；第2名工人在8:35開始巡視；第3名工人在9:10開始巡視；第4名工人在9:45開始巡視。42第1名工人在第1輪巡視后休息5分鐘；第1名工人在10:20開始第2輪巡視.3建模D題論文5.問題3的求解第1名工人具體巡視如下：在8:00開始第1輪巡視；在10:20開始第2輪的巡視；在12:40開始第3輪的巡視；在15:00結束第3輪的巡視；在每輪巡視后，均休息5分鐘，共計巡視420min，即7小時.建模D題論文5.問題3的求解錯時上班時間表l結論：不考慮休息進餐時間的錯時上班，每班需要4人，一天共需12人（小于固時上班15人）。建模D題論文5.問題3的求解5.2考慮休息進餐時間排班方法如下：?

錯時排班時間不變；?

進餐時間可適當放寬；?

進餐時間為35分鐘（最小巡視周期）；?

進餐時第5名（機動）工人開始替換完成巡視工作；?

第5名（機動）工人進餐時間可靈活安排在替班前后。建模D題論文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人