The ability to guide relief vehicles to safety and quickly pass through environments affected by fires is critical in fighting forest fires. In this paper, we focus on route determination in the case of forest fires, and propose a data model that supports finding paths among moving obstacles. This data model captures both static information, such as the type of the response team, the topology of the road network, and dynamic information, such as sensor information, changing availabilities of roads during disasters, and the position of the vehicle. We use a fire simulation model to calculate the fire evolution. The spread of the fire is represented as movements of obstacles that block the responders? path in the road network. To calculate safe and optimal routes avoiding obstacles, the A? algorithm is extended to consider the predicted availabilities of roads. We prove the optimality of the path calculated by our algorithm and then evaluate it in simulated scenarios. The results show that our model and algorithm are effective in planning routes that avoid one or more fire-affected areas and that the outlook for further investigation is promising.