抄表员抄表路线的优化设计

一、优化问题的求解

此优化问题包含两个方面:①对顶点进行分组;②在组中求最佳抄表回路。由于此问题属于NP－hard问题，所以只能寻求一种较合理的划分准则，经过初步划分后，求出各部分的近似最佳抄表回路的权，再进一步进行调整，使得各部分满足均衡性条件(3)。此优化问题的求解过程具体分为3步，具体如下。Step1:采用一定的分区原则，将加权图分成n个区。Step2:按区寻找最小生成树，并在其基础上求解最短回路。Step3:求出每条回路的长度，代入均衡度函数，如果满足条件则终止;否则按调整原则将区域进行调整，返回Step2。1)分组原则首先，以O点为起点，采用Kruskal方法，得到一个基于整个加权图的最小生成树，将其分解，以得到n个子图，使得分解结果尽量均衡。由于在最小生成树上，边权(相邻两顶点之间的距离)接近，可略认为均衡是指各子图包含的顶点数接近。综上所述有以下分区原则:①分解点为O点，或尽可能接近O点;②分解所得的n个子图所包含的顶点数尽可能相等;③尽量使每一个子图为连通图;④尽量使每一个子图中与点O的最短路上的点在该子图内。尽量使各子图的点在子图内部形成环路。(2)调整原则该研究采用边界调整法，其主要目标是在边界对各区域进行调整，以提高各组的均衡程度。具体调整步骤为:①为增强相邻区域的可调整性，规定首先对相邻边界点较多的两个区域进行调整;②优先对均衡度最小的区域和均衡度最大的区域之间进行调整，若这两个区域之间的相邻点相对较少，则对每个区域逐级进行调整。

二、应用实例

以天津市自来水集团有限公司营销抄表管理为例，集团公司下属多个营销分公司，管辖范围内贸易结算地表总具数约为7．5万具，需入户抄收的户表总具数约为160多万具，抄收路线的不均衡势必给企业的工作效率和经济效益带来一定的影响，各营销分公司可根据自己所辖范围的地理特点和表位分布建立适合自己的优化路线抄表数学模型。管辖范围内地表或楼房小区分布示意。以其中一个营销分公司为例，将该营销分公司所在的地理位置看做中的S点，围绕这个中心点分别按地表抄收管理和户表抄收管理建立两个管理模型:一是把各营销分公司管辖范围内在装分布的地表看的各个顶点，边上的数字代表地表营销员抄收的距离;二是把各营销分公司管辖范围内户表所在的楼房小区看做的各个顶点，边上的数字代表地表户表营销员抄收的距离。共有3个抄表员，。以点S为起点，采用Kruskal方法，得到一个基于整个抄表线路的最小生成树。可以看出，从S点出发到其他点共有6条干枝，它们的名称分别为:①、②、③、④、⑤、⑥。根据实际经验，在分组时应遵循以下原则。原则一:尽量使同一干枝上及其分枝上的点分在同一组。原则二:应将相邻干枝上的点分在同一组。原则三:尽量将长的干枝与短的干枝分在同一组。由上述分组原则，找到一种分组形式，即{①、②}，{③、④}，{⑤、⑥}。其近似解。由于该分组的均衡度α0=w(C2)－w(C3)w(C2)=80．63－41．8380．63=48．12%，故该分组的均衡性很差，为改善均衡性，将第Ⅱ组中的顶点38，2，3，39和4划归第Ⅲ组，重新分组后的近似最优解，各组的近似最优抄表线路见图4。由于该分组的均衡度α0=w(C2)－w(C3)w(C2)=68．8－65．168．8=5．38%，故该组的均衡性很好。3名抄表员路程、抄表数目相差不大，因此该抄表路线设计是合理的。

三、结论

计算结果表明，采用城市供水系统抄表员抄表路线的优化方法能够在保证每名抄表员工作量大致相等的情况下，合理地安排抄表员的抄表线路，提高了抄表员的工作效率。

作者：刘红施银焕张清周邢欣单位：天津市自来水集团有限公司哈尔滨工业大学