基于Kruskal算法巡检线路的排班

本文主要针对巡检路线的排班问题,我们建立了最少人数模型,最短路径模型,人力资源模型,运用 Kruskal 算法 得出理想的排班时间表以及巡检线路。要使得人力资源消耗量可能少,而且需要把所有的巡检点都要检查一遍,同时还要考 虑每名工人的工作量平衡,由于问题一采用的是三班倒,每班工作 8 小时的制度,中途没有休息以及吃饭的时间。根据这些 条件我们将问题分成了三个部分,首先建立最短路径模型用 0-1 变量以及 Kruskal 算法求出最小生成树,然后得到以 22 号点 为起点以及终点的最短回路路径,在路上总消耗时间为71分钟。巡查线路为:22→23→24→9→25→26→15→12→18→16→1 3→11→10→6→14→8→17→3→5→7→2→1→19→20→21→4→22然后建立最少人数模型,求出最少的巡检人员为4人,然后 根据人数将回路进行划分,得到 4 个区间段,根据人力资源模型,得出巡检时间表。