A traveling route guidance device comprising: a landform acquiring part configured to acquire three-dimensional landform information about a landform around a construction machine; a current position acquiring part configured to acquire a current position of the construction machine with respect to the three-dimensional landform information; a destination acquiring part configured to acquire a destination with respect to the three-dimensional landform information; a controller configured to derive at least one traveling route from the current position to the destination for the construction machine based on the three-dimensional landform information; an output part configured to output information about the at least one traveling route derived by the controller; and a memory configured to store permissible range information representing a permissible range of a gradient determined in terms of a stability of the construction machine in advance, wherein when deriving a preparation-unrequired route which is one of the at least one traveling route which enables the construction machine to travel thereon only within the permissible range of the gradient until reaching the destination, the controller is configured to cause the output part to output information about the preparation-unrequired route, characterized in that: when deriving a preparation-required route, the controller is configured to determine a location which needs a preparation to enable the construction machine to travel only within the permissible range of the gradient until reaching the destination, the controller is configured to cause the output part to output information about the location which needs the preparation and about the traveling route, and in that: the permissible range depends on an advancing direction of a crawler of the construction machine with respect to a direction in which a degree of the gradient reaches maximum. a landform acquiring part configured to acquire three-dimensional landform information about a landform around a construction machine; a current position acquiring part configured to acquire a current position of the construction machine with respect to the three-dimensional landform information; a destination acquiring part configured to acquire a destination with respect to the three-dimensional landform information; a controller configured to derive at least one traveling route from the current position to the destination for the construction machine based on the three-dimensional landform information; an output part configured to output information about the at least one traveling route derived by the controller; and a memory configured to store permissible range information representing a permissible range of a gradient determined in terms of a stability of the construction machine in advance, wherein when deriving a preparation-unrequired route which is one of the at least one traveling route which enables the construction machine to travel thereon only within the permissible range of the gradient until reaching the destination, the controller is configured to cause the output part to output information about the preparation-unrequired route, characterized in that: when deriving a preparation-required route, the controller is configured to determine a location which needs a preparation to enable the construction machine to travel only within the permissible range of the gradient until reaching the destination, the controller is configured to cause the output part to output information about the location which needs the preparation and about the traveling route, and in that: the permissible range depends on an advancing direction of a crawler of the construction machine with respect to a direction in which a degree of the gradient reaches maximum.