Routing electric meter readers

Electric utility companies employ a crew of workers who periodically visit and read the electric meters of each customer in their service area. Each reader is transported by auto from a central office to the first customer on his work list. At the end of his work shift time limit the reader is free to leave the area possibly returning home or to the central office by public bus. Taking a graph that corresponds to the city network of streets meter readers must traverse each street while moving from house to house. It is possible that dead heading may be required-back tracking over a street that has already been covered. A working tour is an open path whose reading time plus deadheading time does not exceed the work limit. The problem is to find the minimum number of working tours. Stating the problem in this manner gives us an optimization problem closely related to the M-Chinese postman problem-an edge oriented routing problem. After presenting some background on this type of problem a heuristic procedure is used to solve an example from the City of Beersheva. The solution provides a 40% reduction in the number of working tours. The paper ends with a discussion of the solution, and provides conditions under which the algorithm should have practical utility.