抄表員抄表路線的優化設計

導語：抄表員抄表路線的優化設計一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

一、優化問題的求解

此優化問題包含兩個方面:①對頂點進行分組;②在組中求最佳抄表回路。由于此問題屬于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名抄表員路程、抄表數目相差不大，因此該抄表路線設計是合理的。

三、結論

計算結果表明，采用城市供水系統抄表員抄表路線的優化方法能夠在保證每名抄表員工作量大致相等的情況下，合理地安排抄表員的抄表線路，提高了抄表員的工作效率。

作者：劉紅施銀煥張清周邢欣單位：天津市自來水集團有限公司哈爾濱工業大學