Usually, the combinatorial optimization problems are modeled in a static way. All data are known in advance, i.e., before the optimization process has started. But in practice, many problems are dynamic, and change during the time. For the Dynamic Vehicle Routing Problem (DVRP), new orders arrive when the working day plan is in progress. Thus, the routes must be reconfigured dynamically during the optimization process. The Particle Swarm Optimization has been previously used to solve continuous dynamic optimization problems, whereas only, few works were proposed for combinatorial ones. In this paper, we present an Adaptive Particle Swarm for solving the Vehicle Routing Problem with Dynamic Requests (VRPDR). The effectiveness of this approach is evaluated thanks to a well-known set of benchmarks. It is compared with different population based metaheuristics, and a single-solution based metaheuristic. Experimental results show that our approach may significantly decrease travel distances, and is adaptive with respect to dynamic environment.