A navigation system comprises a storage device which stores link data of each of links constituting roads on a map. As for a carpool link defined as a link allowing only a vehicle in which a plurality of persons are riding to pass through, the link data contains information indicative thereof. The navigation system searches for a recommended route from a departure place to a destination by use of the link data. If the links constituting the recommended route includes a carpool link, the navigation system receives an input of the number of person-on-board. The navigation system searches for a recommended route once again by use of the link data, from the departure place to the destination comprising the links passable with the number of person-on-board received by the receive step.