Release Notes

This work originally appeared in the Proceedings of the 5th USPS Advanced Technology Conference, Washington, D.C. This online version differs in minor editorial changes, correction of typographical errors and addition of hypertext links. Copyright is retained by the author. This work may be freely copied for non-commercial purposes provided this copyright notice is included.

Abstract

A street lexicon search within a ZIP code area frequently must be expanded to neighboring ZIP codes, e.g. due to customer addressing errors. The computational expense of the neighboring ZIP code search is problematic in a real-time postal processing system.

We describe a parallel processing system in which the ZIP databases are allocated for maximum parallelism over a given number of processors. The simulated annealing algorithm is used to solve this mapping problem in two different ways: first, by generating a topology-preserving map of the ZIP code geography onto a toroidal array of processors, and second, by directly optimizing search time without regard to the topology of the processor array.

The algorithm can accommodate a wide range of additional objectives as might arise from variable lexicon sizes, search priorities, and customer addressing patterns. Comparisons are made with other NP-hard combinatorial optimization problems, e.g. map coloring, graph partitioning and bin packing.