As international visitors to Japan increase rapidly, demand is rising for services that support travel planning so that travelers can enjoy comfortable and efficient trips. Currently, however, it is difficult for travelers to flexibly plan their itineraries according to their own requirements and objectives. Although there are websites that introduce standard routes, there are few applications that can provide efficient and personalized travel plans. To assist travelers in planning their trips, it is necessary to properly model the transportation network as a graph and utilize state-of-the-art routing algorithms to derive efficient routes. In addition, flexible route planning and fast algorithms that take into account constraints such as time, distance, and cost are essential for travelers to visit multiple tourist spots within a limited period of time. In this paper, we formulate the problem of determining a route that satisfies a traveler’s specified constraints as an optimization problem and propose a heuristic algorithm to solve it efficiently. Furthermore, we evaluate the effectiveness of the proposed method through numerical experiments and aim to demonstrate its feasibility for improving the efficiency of travel planning and the overall tourism experience.