A transportation problem solving device for solving a transportation problem to optimize the end-to-end physical distribution consisting of a regional transportation and an inter-depot transportation, comprising a transformation section for adding a regional representative node representing a plurality of collection and delivery spots belonging to a depot to a model of inter-depot transportation, and incorporating the regional transportation between each of the plurality of collection and delivery spots belonging to the depot and the depot into a part of the model of inter-depot transportation as the inter-depot transportation between the depot and the regional representative node, an inter-depot transportation computing section for solving the transportation problem, based on a transformation model in which the regional transportation is incorporated into the inter-depot transportation, and computing a transportation plan for each delivery order in an inter-depot transportation portion, when a plurality of transport requests are input, and an output section for outputting the transportation plan computed by the inter-depot transportation computing section.