We consider a dynamic vehicle routing problem with time windows and stochastic customers (DS-VRPTW), such that customers may request for services as vehicles have already started their tours. To solve this problem, the goal is to provide a decision rule for choosing, at each time step, the next action to perform in light of known requests and probabilistic knowledge on requests likelihood. We introduce a new decision rule, called Global Stochastic Assessment (GSA) rule for the DS-VRPTW, and we compare it with existing decision rules, such as MSA. In particular, we show that GSA fully integrates nonanticipativity constraints so that it leads to better decisions in our stochastic context. We describe a new heuristic approach for efficiently approximating our GSA rule. We introduce a new waiting strategy. Experiments on dynamic and stochastic benchmarks, which include instances of different degrees of dynamism, show that not only our approach is competitive with state-of-the-art methods, but also enables to compute meaningful offline solutions to fully dynamic problems where absolutely no a priori customer request is provided.
 This paper reconsiders online packet scheduling in computer networks, where the goal is to minimize weighted packet loss and where the arrival distributions of packets, or approximations thereof, are available for sampling. Earlier work proposed an expectation approach, which chooses the next packet to schedule by approximating the expected loss of each decision over a set of scenarios. The expectation approach was shown to significantly outperform traditional approaches ignoring stochastic information. This paper proposes a novel stochastic approach for online packet scheduling, whose key idea is to select the next packet as the one which is scheduled first most often in the optimal solutions of the scenarios. This consensus approach is shown to outperform the expectation approach significantly whenever time constraints and the problem features limit the number of scenarios that can be solved before making a decision. More importantly perhaps, the paper shows that the consensus and expectation approaches can be integrated to combine the benefits of both approaches. These novel online stochastic optimization algorithms are generic and problem-independent, they apply to other online applications as well, and they shed new light on why existing online stochastic algorithms behave well. This paper considers online stochastic optimization problems where time constraints severely limit the number of offline optimizations which can be performed at decision time and or in between decisions. It proposes a novel approach which combines the salient features of the earlier approaches: the evaluation of every decision on all samples (expectatio0n) and the ability to avoid distributing the samples among decisions (consensus). The key idea underlying the novel algorithm is to approximate the regret of a decision d. The regret algorithm is evaluated on two fundamentally different applications: online packet scheduling in networks and online multiple vehicle routing with time windows. On both applications, it produces significant benefits over prior approaches. Recent advances in both computational power and communications technologies have created novel opportunities for research in combinatorial optimizations. Many applications in routing, scheduling, and networking raise exciting challenges, in particular in uncertainty. These applications are often online optimization problems, where the input is not known a priori, but characterized by a probabilistic model, and where decisions are made under severe time constraints. This thesis presents an online stochastic optimization framework whose goal is to maximize expected profit. It presents two algorithms, consensus and regret, designed to operate under severe time constraints. Theoretical results show that the framework and algorithms provide strong guarantees on solution quality under reasonable assumptions about the input distribution). Moreover, experimental results on a variety of applications in packet scheduling, vehicle dispatching, and vehicle routing indicate that the approach provides significant improvements in quality of service, even under severe time constraints. The framework is also shown to be robust even when the distribution itself is unknown. Finally, a large neighborhood search that hybridizes constraint programming and local search in novel ways is presented for its success in online vehicle routing problems.