The problem presented in this paper was motivated by the need for a solution to be used in a search-and-rescue application and is formulated as a dynamic traveling salesman problem in a stochastic-state network setting. This problem formulation features a full-recourse decision framework and stochastic demands that are revealed only through direct observation. This problem is defined in a stochastic-state network setting, which allows the modeling of implicitly correlated demand stochasticity. The problem is then formulated as a Markovian decision process, and, finally, a heuristic solution is provided. The heuristic solution is based on a two-stage stochastic program with recourse solved on a set of aggregated networks generated by the use of an aggregating function. Subsets of the feasible solutions obtained at each stage are fixed, and the heuristic is used iteratively to further refine the routing policy.