New Routing Problems with possibly correlated travel times

In the literature of operational research, Vehicle Routing Problems (VRP) were and still are subject of countless studies. Under the scope of combinatorial optimization, this thesis analyses some variants of VRP both with deterministic and uncertain travel times. The deterministic problem under study is a drayage problem with characteristics con- cerning service types and requirement seldom investigated all together. The formulations proposed to model this problem are: the node-arc formulation and the Set Partitioning formu- lation. Concerning the solution methods, two heuristics and a branch-and-price approach are presented. The section dealing with uncertain and correlated travel times faces two classes of VRP with time windows using either single or joint chance constraints depending on whether missing a customers time window makes the entire route infeasible or not. From a comparison between deterministic and stochastic methods, these last represent a profitable investment to guarantee the feasibility of the solution in realistic instances.