The APT's package cache could be made to store the version info of packages and of dependencies in preparsed form instead of strings (as now), namely, something like a union of a EVRDT structure or a parsed binary representation of set-versions.
(Then, the comparison functions from librpm which operate on such internal representations (i.e., already parsed) should be called.)
Then, I suppose, a bit more work would be done on cache generation (e.g., apt-get update), but less work in dependency resolution (e.g., during apt-get dist-upgrade).
In 0.5.15lorg2-alt65 and 0.5.15lorg2-alt68, we put some effort into making APT internally and all libapt's clients use a single comparison API as a blackbox (so that it's easy to change the algorithm only at one place in librpm). But the input data for it is ultimately stored as strings in the cache (and passed as strings between libapt and clients).