What will be tomorrow’s big cities objectives and challenges? Most of the operational problems from the real world are inherently subject to uncertainty, requiring the decision system to compute new decisions dynamically, as random events occur. In this thesis, we aim at tackling an important growing problem in urban context: online dynamic vehicle routing. Applications of online vehicle routing in the society are manyfold, from intelligent on demand public transportation to sameday delivery services and responsive home healthcare. Given a fleet of vehicles and a set of customers, each being potentially able to request a service at any moment, the current thesis aims at answering the following question. Provided the current state at some moment of the day, which are the best vehicle actions such that the expected number of satisfied requests is maximized by the end of the operational day? How can we minimize the expected average intervention delays of our mobile units? Naturally, most of the requests remain unknown until they appear, hence being revealed online. We assume a stochastic knowledge on each operational problem we tackle, such as the probability that customer request arise at a given location and a given time of the day. By using techniques from operations research and stochastic programming, we are able to build and solve mathematical models that compute near-optimal anticipative actions, such as preventive vehicle relocations, in order to either minimize the overall expected costs or maximize the quality of service. Optimization under uncertainty is definitely not a recent issue. Thanks to evolution of both theoretical and technological tools, our ability to face the unknown constantly grows. However, most of the interesting problems remain extremely hard, if not impossible, to solve. There is still a lot of work. Generally speaking, this thesis explores some fundamentals of optimization under uncertainty. By integrating a stochastic component into the models to be optimized, we will see how it is in fact possible to create anticipation.