A navigation system having a central device which uses a link shape compression unit to compress information of altitude changes of a road link obtained from a three-dimensional road map, and calculates a geometry parameter based on variation of energy of a vehicle travelling on the road link. An on-board terminal device estimates the vehicle's average travelling pattern by using a travel-pattern-estimation unit based on the geometry parameter calculated by the central device, a link-travelling time estimated from statistically-stored traffic information, and a link length. The on-board terminal device further calculates fuel consumption of the vehicle travelling on each road link based on the estimated travelling pattern and parameters of the vehicle by using a fuel-consumption calculation unit, and then, searches a fuel-efficient route by using the fuel consumption as a link cost. The on-board terminal device has a vehicle-type selector for selecting a type of the vehicle.