ZipCode to ZipCode Storage
Partial answer:  Given that you need to look up ($z1, $z2):

WHERE zip1 = LEAST($z1, $z2)
  AND zip2 = GREATEST($z1, $z2)


For prep, you have only the PRIMARY KEY(zip1, zip2) and you have filled the table only with smaller zip to larger zip.  And adjusted the 1to2, etc, columns accordingly.