A travel route guide device includes a travel route calculation unit configured to calculate a travel route based on current position information, destination information, a remaining amount of power of an electric vehicle, and information on a remaining power amount recovery facility. The travel route guide device further includes a region division unit configured to divide a region including the travel route into a plurality of local regions. The travel route guide device further includes a constraint condition determination unit configured to determine, for each local region, a constraint condition for a monitoring variable. The travel route guide device further includes a recalculation determination unit configured to monitor the monitoring variable, and request the travel route calculation unit to calculate the travel route in response to a determination that a value of the monitoring variable deviates from an upper limit defined by the constraint condition.