This paper presents GreenRoute, a fuel-saving vehicular navigation system whose contribution is motivated by one of the key challenges in the design of autonomic services: Namely, designing the service in a manner that reduces operating cost. GreenRoute achieves this end, in the specific context of fuel-saving vehicular navigation, by significantly improving the generalizability of fuel consumption models it learns (in order to recommend fuel-saving routes to drivers). By learning fuel consumption models that apply seamlessly across vehicles and routes, GreenRoute eliminates one of the key incremental costs unique to fuel-saving navigation: Namely, the cost of upkeep with ever-changing fuel-consumption-specific route and vehicle parameters globally. Unlike shortest or fastest routes (that depend only on map topology and traffic), minimum-fuel routes depend additionally on the vehicle engine. This makes fuel-efficient routes harder to compute in a generic fashion, compared to shortest and fastest routes. The difficulty results in two additional costs. First, more route features need to be collected (and updated) for predicting fuel consumption, such as the nature of traffic regulators. Second, fuel prediction remains specific to the individual vehicle type, which requires continual upkeep with new car types and parameters. The contribution of this paper lies in deriving and implementing a fuel consumption model that avoids both of the above two sources of cost. To measure route recommendation quality, we test the system (using 21 vehicles and over 2400 miles driven in seven US cities) by comparing fuel consumption on our routes against both Google Maps' routes and the shortest routes. Results show that, on average, our routes save 10.8% fuel compared to Google Maps' routes and save 8.4% compared to the shortest routes. This is roughly comparable to services that maintain individualized vehicle models, suggesting that our low-cost models do not come at the expense of quality reduction.