Other Case Studies
The SMART partnership supports improved law enforcement and biological monitoring in protected areas around the world. They came to Refractions to build a software tool to help meet their needs.
Biodiversity BC and its government and non-government partners were looking for regional-level environmental statistics. Refractions proposed a new approach to generating GIS summaries, using the power of a relational database and web tools to provide GIS analysis to users who previously had no access to it.
The City of Vancouver collects water readings from thousands of residences and businesses, but has never optimized the pedestrian routes the readers take. Refractions developed algorithms to create the most efficient routes of the correct length for readers.
Refractions provides full-service support for the British Columbia Digital Roads Atlas – systems design, maintenance, data conflation, client service, and rapid response.
Refractions converted a legacy habitat modelling system based on ArcView 3.X to ArcGIS 9.2, and automated the workflow to provide faster turnaround time for model runs.
The British Columbia Ministry of Forests needed a tool to conflate multiple roads databases into a single working layer. Refractions delivered the algorithms and a user interface based on the uDig platform.
Refractions developed an ArcMap extension to automate the calculation of standard reports joining a massive shape-file archive with a large Oracle database.
UN FAO needed a data collection tool that could run disconnected and didn't have a per-seat licensing cost. Refractions delivered a simple tool using the uDig desktop platform.
The Open Geospatial Consortium runs regular “testbed” projects to field-test new concepts in geospatial interoperability. Refractions was a part of the OWS-3 initiative, and built a uDig-based “GeoDSS” client to provide access to several other OGC standard services, including a prototype GeoVideo service.
Rento is a free web service that makes it easy to find a place to rent in Greece. Powered by PostgreSQL and PostGIS, it provides ad listings with photographs displayed on a map. Searching is accomplished through map navigation and natural language processing, with the search engine being capable of answering complex (spatial) questions such as "flat near the University of Athens" or "loft up to 800 euros near a metro station" (in greek).
Automated Route Planning for Meter Reading – City of Vancouver
City of Vancouver, Engineering Services
October to November 2007
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.
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.
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 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.
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.