What you refer to is the fact that the computational complexity (i.e. time to finish it) of known algorithms rises exponentially with the size of the problem and exponentially is a code word for "really, really quickly". It just takes too much time to find the minimal path if your graph is big.
What I meant, however, is that the problem has been solved in practice. When you ask Google how to drive from SF to NY, it'll give pretty good answer in milliseconds. Is it an optimal answer? It might be, it might be not, but it's a very good answer. Getting slightly better answer is not worth the computational time because it won't make a difference in practice in your trip.
Similarly, a car rental company doesn't have to schedule things optimally, they just have to schedule things really good, and that's possible with much less computationally expensive algorithms. The big win is when you go from "no optimization" to "good optimization", not from "good optimization" to "perfect optimization".