Real-world routing applications are scientifically approached in the field of stochastic dynamic vehicle routing problems (DVRPs). For many of these problems, anticipation of uncertainty is mandatory. For a dynamic decision making that anticipates uncertainty, i.e., integrates stochastic information, methods of approximate dynamic programming (ADP) have been established in many research fields, e.g., managerial finance. These methods approximate the expected future outcomes of states in an approximation process and provide these estimates to allow anticipatory decision making. The application of ADP to DVRPs is limited because the structure of DVRPs is rather complex and the vast state space impedes the approximation process. States spaces are therefore often aggregated or partitioned in an a priori manner. Since DVRPs are complex, the required knowledge about the problem structure is often not available. Important information is then neglected permanently. Both approximation process and resulting solution quality are obstructed.

In this work, we propose to partition the state space in an adaptive manner induced by the approximation process. Areas of the state space with many observations as well as areas with varying estimates of the future have to be considered in more detail. In order to focus on those areas of the state space that are “interesting”, we successively adapt the partitioning of the state space during the approximation process. We analyze the results of the proposed method for a DVRP with one vehicle and stochastic pickup requests. Results show that a problem-specific partitioning and an efficient approximation can be achieved enabling anticipatory decision making.