Route search devices, methods, and programs acquire basic congestion information, the basic congestion information being congestion information for specific links. The systems, methods, and programs set a destination and search for a first travel route from a departure point to the set destination using the acquired basic congestion information. Based on the first travel route, the systems, methods, and programs determine, whether center traffic information is necessary to be acquired. Only when it is determined that the center traffic information is necessary, the systems, methods, and programs acquire the center traffic information, the center traffic information being congestion information of a link other than the specific links, and search for a second travel route from the departure point to the set destination using the acquired additional congestion information.