A system and method for providing navigation routing options to a vehicle driver, including estimated fuel consumption and fuel cost. A server collects data from a large number of road vehicles driving different routes, where the data includes road grade, average speed, stop / start and acceleration / deceleration info and vehicle specifications, and the data is collected via a telematics or other wireless system. The server also receives map data, point of interest data and real-time traffic data from their respective providers. When a driver of a road vehicle requests navigation routing from a start point to a destination, the server provides multiple routing options including not only distance and time for each routing option, but also fuel consumption and cost. The estimated fuel consumption is computed using models based on the crowd-sensed data from the other vehicles driving the routes, where the models include a physics-based model and a machine learning model.