The algorithmic framework developed for improving heuristic solutions of the new version of deterministic TSP [Comput. Chem. Eng. (2004)] is extended to the stochastic case. To verify the algorithmic framework for the stochastic case, a new variant of the stochastic TSP with an optional task, in which key parameters (cost matrix) of the problem change according to an underlying Markov model, is introduced in this work as a prototypical stochastic optimization problem. The optional task is the performing of an "investigation" which improves the information for decision making at some cost. The stochastic dynamic programming is performed in the subset of the states that is obtained by simulating a set of heuristics. The proposed algorithmic framework finds the approximated optimal cost-to-go, only for the states in the subset. This reduces the computational time dramatically compared to the stochastic DP in the entire states space, without significant loss in the solution quality. The results show that the algorithmic framework also works efficiently for stochastic problems by improving the heuristic policies for making decisions for different realizations of the Markov process. (C) 2003 Elsevier Ltd. All rights reserved.