The developments in mobile communication technologies are a strong motivation for the study of dynamic vehicle routing and scheduling problems. In particular, the planned routes can be quickly modified to account for the occurrence of new customer requests, whichmight imply diverting a vehicle away from its current destination. In this paper, a previously developed problem-solving approach for a vehicle routing problemwith dynamic requests and dynamic travel times is extended to account for more sophisticated communicationmeans between the drivers and the central dispatch office. Computational results are reported to empirically demonstrate the benefits of this extension.