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.