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

一、優(yōu)化問題的求解

此優(yōu)化問題包含兩個方面:①對頂點進行分組;②在組中求最佳抄表回路。由于此問題屬于NP－h(huán)ard問題，所以只能尋求一種較合理的劃分準則，經(jīng)過初步劃分后，求出各部分的近似最佳抄表回路的權(quán)，再進一步進行調(diào)整，使得各部分滿足均衡性條件(3)。此優(yōu)化問題的求解過程具體分為3步，具體如下。Step1:采用一定的分區(qū)原則，將加權(quán)圖分成n個區(qū)。Step2:按區(qū)尋找最小生成樹，并在其基礎上求解最短回路。Step3:求出每條回路的長度，代入均衡度函數(shù)，如果滿足條件則終止;否則按調(diào)整原則將區(qū)域進行調(diào)整，返回Step2。1)分組原則首先，以O點為起點，采用Kruskal方法，得到一個基于整個加權(quán)圖的最小生成樹，將其分解，以得到n個子圖，使得分解結(jié)果盡量均衡。由于在最小生成樹上，邊權(quán)(相鄰兩頂點之間的距離)接近，可略認為均衡是指各子圖包含的頂點數(shù)接近。綜上所述有以下分區(qū)原則:①分解點為O點，或盡可能接近O點;②分解所得的n個子圖所包含的頂點數(shù)盡可能相等;③盡量使每一個子圖為連通圖;④盡量使每一個子圖中與點O的最短路上的點在該子圖內(nèi)。盡量使各子圖的點在子圖內(nèi)部形成環(huán)路。(2)調(diào)整原則該研究采用邊界調(diào)整法，其主要目標是在邊界對各區(qū)域進行調(diào)整，以提高各組的均衡程度。具體調(diào)整步驟為:①為增強相鄰區(qū)域的可調(diào)整性，規(guī)定首先對相鄰邊界點較多的兩個區(qū)域進行調(diào)整;②優(yōu)先對均衡度最小的區(qū)域和均衡度最大的區(qū)域之間進行調(diào)整，若這兩個區(qū)域之間的相鄰點相對較少，則對每個區(qū)域逐級進行調(diào)整。

二、應用實例

以天津市自來水集團有限公司營銷抄表管理為例，集團公司下屬多個營銷分公司，管轄范圍內(nèi)貿(mào)易結(jié)算地表總具數(shù)約為7．5萬具，需入戶抄收的戶表總具數(shù)約為160多萬具，抄收路線的不均衡勢必給企業(yè)的工作效率和經(jīng)濟效益帶來一定的影響，各營銷分公司可根據(jù)自己所轄范圍的地理特點和表位分布建立適合自己的優(yōu)化路線抄表數(shù)學模型。管轄范圍內(nèi)地表或樓房小區(qū)分布示意。以其中一個營銷分公司為例，將該營銷分公司所在的地理位置看做中的S點，圍繞這個中心點分別按地表抄收管理和戶表抄收管理建立兩個管理模型:一是把各營銷分公司管轄范圍內(nèi)在裝分布的地表看的各個頂點，邊上的數(shù)字代表地表營銷員抄收的距離;二是把各營銷分公司管轄范圍內(nèi)戶表所在的樓房小區(qū)看做的各個頂點，邊上的數(shù)字代表地表戶表營銷員抄收的距離。共有3個抄表員，。以點S為起點，采用Kruskal方法，得到一個基于整個抄表線路的最小生成樹?？梢钥闯觯瑥腟點出發(fā)到其他點共有6條干枝，它們的名稱分別為:①、②、③、④、⑤、⑥。根據(jù)實際經(jīng)驗，在分組時應遵循以下原則。原則一:盡量使同一干枝上及其分枝上的點分在同一組。原則二:應將相鄰干枝上的點分在同一組。原則三:盡量將長的干枝與短的干枝分在同一組。由上述分組原則，找到一種分組形式，即{①、②}，{③、④}，{⑤、⑥}。其近似解。由于該分組的均衡度α0=w(C2)－w(C3)w(C2)=80．63－41．8380．63=48．12%，故該分組的均衡性很差，為改善均衡性，將第Ⅱ組中的頂點38，2，3，39和4劃歸第Ⅲ組，重新分組后的近似最優(yōu)解，各組的近似最優(yōu)抄表線路見圖4。由于該分組的均衡度α0=w(C2)－w(C3)w(C2)=68．8－65．168．8=5．38%，故該組的均衡性很好。3名抄表員路程、抄表數(shù)目相差不大，因此該抄表路線設計是合理的。

三、結(jié)論

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

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