• Home
• Our Products
• Our Services
• Company
• Contact

Home > Our Expertise > Case Studies > Automated Route Planning for Meter Reading – City of Vancouver

Other Case Studies

Automated Route Planning for Meter Reading – City of Vancouver

Our Client

City of Vancouver, Engineering Services
October to November 2007

Project Background

The City of Vancouver collects water meter readings from residences and businesses. Currently the meters are read manually by staff who visit the meter locations on foot. The walking routes used to visit meter locations are currently not optimized in any way. More efficient routes for meter reading would reduce the amount of staff resources required in each reading cycle, and thus produce cost savings. Refractions was asked to determine if it would be possible to improve the efficiency of collecting the meter readings by optimizing the routes.

Refractions' Solution

After analyzing the details of the business and researching various optimization strategies, Refractions determined that this problem could most effectively be solved by treating it as an instance of the classic Travelling Salesman Problem (TSP). Solving the Traveling Salesman Problem produces an optimal a route which visits every meter once and has a shorter length than any other possible path.

The first step in the analysis was to transform the raw meter location and address data supplied by the client into the distance-weighted network required by the TSP algorithm. This required geocoding point locations onto the linear street network, and then computing the network distance between pairs of locations. To accomplish this, the data was processed using two open-source tools, PostGIS and JUMP. PostGIS is an extension to the PostgreSQL database engine that allows storage and manipulation of spatial data. JUMP is a desktop GIS application for visualizing and processing geospatial data. Refractions maintains or contributes to both of these projects.

The powerful spatial processing capabilities of PostGIS made it possible to do all the data transformations that were needed. To compute network distances, the PGRouting package for PostgreSQL was used.

JUMP was used primarily for visualizing the datasets that existed in the PostGIS environment. It also provided the ability to compute topology from a set of line strings.

The calculated routes being visualized in the JUMP package.

To solve the core TSP problem, Refractions developed a custom solver using Genetic Algorithm technology. The solver takes as input an abstract graph representing the meters and the paths between them. Possible paths between pairs of meters are included as edges in the graph, with each edge having a weight proportional to the network distance between the meters it links. The solver finds a path through the graph that visits every meter at least once, and which has a near-minimum total path distance. To aid in tuning the application, additional tools were developed to show the results graphically and allow focusing on the most favorable solutions.

The Result

The result of the TSP solver is a route which visited every meter once and is guaranteed to have the shortest possible length. As a final step, Refractions mapped the computed route back onto the original street network map, using a custom visualization technique to clearly show the walking path.

Client Benefits

The City of Vancouver is very optimistic that the result computed by Refractions will be a significant improvement over their existing routes. They are currently field testing the optimized routes to calibrate them with what is actually possible to complete in a working day.