In 1988, operations researchers at the Southern California Gas Company (SOCAL) initiated a study to investigate the potential benefits of using optimization software to route and schedule its meter readers. SOCAL developed a set of optimization algorithms and tested them on a carefully selected sample region representing about 2.5% of the SOCAL service area.
In the SOCAL routes existing at that time, meter readers traversed every segment of the route which required service. However, when the segments were split into subsegments, many of the subsegments did not require service, because:
- The existing routes had been planned in anticipation of future growth, which had not always taken place.
- Meters on some of the subsegments had been removed due to urban renewal or reconstruction.
The problem was to cluster subsegments, or arcs, into partitions that each represented one day's work for a meter reader. The SOCAL operations researchers developed an arc-partitioning algorithm to solve the problem.
When the optimization algorithm was tested in the sample region, it resulted in fewer routes and savings on route length, overtime, and "deadhead" time. ("Deadhead time" is time spent traversing an arc, which does not require service.) Based on the initial test, SOCAL administrators projected tangible savings of about $875,000 annually. This cost-savings benefit motivated the company to implement the optimization algorithm throughout its entire service area.