One trick we used when I was in the transportation business is to pre-calculate the distances between border crossings and gas stations.
Storing the distances for all pairs is prohibitively expensive. Also, you'd need to store the path information as well. Fortunately, road networks exhibit a lot of hierarchical structure. For example, when going far away, you will almost certainly use the long-distance sub-network, i.e. highways. It is possible to exploit this in a preprocessing step that adds a linear amount of information, which is in turn used to speed up queries.
Google maps uses something called contraction hierarchies
Without knowing what they actually use, I feel comfortable to state that the industry has moved on from Contraction Hierarchies to somewhat more flexible techniques. These allow you to take traffic information and road closures, and user preferences, and whatnot into account without requiring a full re-processing of the input data with each traffic update. The state of the art is a two-step preprocessing that first decomposes the road network into cells, and then processes these cells independently. Sometimes it goes by the name of customisable route planning, sometimes it is called multi-level Dijkstra.