They have mental maps of landmarks, which they use as well as "compass" cues:
... experienced birds can accurately complete their memorized routes by using landmarks alone. Nevertheless, we also find that route following is often consistently offset in the expected compass direction, faithfully reproducing the shape of the track, but in parallel.
--Pigeons combine compass and landmark guidance in familiar route navigation
Landmarks are more important than compass cues in general, and pigeons develop their own landmark maps:
we show that homing pigeons (Columba livia) not only come to rely on highly stereotyped yet surprisingly inefficient routes within the local area but are attracted directly back to their individually preferred routes even when released from novel sites off-route. This precise route loyalty demonstrates a reliance on familiar landmarks throughout the flight, which was unexpected under current models of avian navigation.
--Familiar route loyalty implies visual pilotage in the homing pigeon
That means that different birds do use different routes:
Here, we demonstrate that birds develop highly stereotyped yet individually distinctive routes over the landscape, which remain substantially inefficient.
--Homing pigeons develop local route stereotypy
In fact the same bird might use different routes over time as it learns new landmarks:
a wide intraindividual variability was observed in repeated tosses at the same site; some pigeons remained faithful to the first route, whereas other birds tried successive new routes which, in most cases, were significantly shorter than previous ones. This result indicates that pigeons try, and are actually able, to improve their performance in subsequent releases from the same site.
--Pigeon homing: The influence of topographical features in successive releases at the same site
