Problem-Specific State Space Partitioning for Dynamic Vehicle Routing Problems

In many dynamic vehicle routing applications, anticipation of the future is essential for efficient
and effective decision making. In order to incorporate possible future events into current decision
making, it is necessary to evaluate every decision’s impact to the overall objective. This is typically
achieved by an evaluation of the post-decision state. For dynamic vehicle routing problems
(DVRP), the size of the state space can be infinitely large. Therefore, states are often aggregated to
enable an evaluation. In many cases, the aggregated state space has to be partitioned and values are
assigned to partitions, i.e., sets of single states. The partitioning has a major impact on the solution
quality. This paper presents a generic approach that exploits information about the problem
characteristics for a problem-specific state space (PSP). The proposed approach is evaluated for a
DVRP with one vehicle and stochastic customer requests (DVRPSR). Results show that the solution
quality can be increased significantly by a problem-specific partitioning and that anticipatory
decision making can be achieved efficiently.