Back
Texte intégral
Doctoral thesis

Stochastic vehicle routing : from theory to practice

    31.05.2013

183 p

Thèse de doctorat: Università della Svizzera italiana, 2013

Stochastic combinatorial optimization
Stochastic vehicle routing
Heuristics
Optimization
Computational complexity
Approximation
English In this thesis we discuss practical and theoretical aspects of various stochastic vehicle routing problems. These are combinatorial optimization problems related to the field of transportation and logistics in which input data is (partially) represented in a stochastic way. More in detail, we focus on two-stage stochastic vehicle routing problems and in particular on so-called a priori optimization problems. The results are divided into a theoretical part and a practical part. In fact, the theoretical results provide a strong motivation for the development and the usage of the methods presented in the practical part. We begin the theoretical part with a convergence result regarding vehicle routing problems with stochastic demands. This result can be used to give explanations for some phenomena related to these problems which have been reported in literature. We then continue with hardness results for stochastic vehicle routing problems on substantially stochastic instances. Here we show that several stochastic vehicle routing problems remain NP-hard even if they are restricted to instances which differ significantly from non-stochastic instances. Additionally, we give some inapproximability results for these problems restricted to substantially stochastic instances. After that, we focus on a stochastic vehicle routing problem which considers time dependencies in terms of deadlines. We show that various computational tasks related to this problem, including the evaluation of the objective function, are #P-hard even for Euclidean instances. Note that this is a very strong hardness result and it immediately implies that these computational tasks are also NP-hard. We then further investigate the objective function of this problem. Here we demonstrate that the existing approximations for this objective function are not able to guarantee any reasonable worst-case approximation ratio. Finally, we show that it is NP-hard to approximate the objective function of a slightly more general problem within any reasonable worst-case approximation ratio. In the practical part we develop and apply various methods for the optimization of stochastic vehicle routing problems. Since the theoretical results indicate that it is a great challenge to optimize these problems, we focus mainly on heuristic methods. We start with the development of strong local search algorithms for one of the most extensively studied stochastic vehicle routing problems. These algorithms use an efficient approximation of the objective function based on Monte Carlo sampling. They are then further used within different heuristics, leading to new state-of-the-art methods for this problem. We then transfer our results to a more intricate stochastic vehicle routing problem. Here we first present an approximation of the objective function using the novel method of quasi-parallel evaluation of samples. Then we again develop strong local search algorithms and use them within more complex heuristics to obtain new state-of-the-art methods. After that we change the scope towards a general framework for the optimization of stochastic vehicle routing problems based on general purpose computing on graphics processing units. Here we are exploiting the massive computational power for parallel computations offered by modern graphics processing units in the context of stochastic vehicle routing problems. More in detail, we propose to use an approximation of the objective function based on Monte Carlo sampling which can be parallelized in an extremely efficient way. The effectiveness of this framework is then demonstrated in a case study. We finish the practical part with an application of our methods to a real world stochastic vehicle routing problem. This problem is part of a project that has been initiated in 2010 by Caritas Suisse. It is still in an early stage, but with our work we were able to successfully support some of the decision processes at this stage.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1318484
Statistics
Document views: 195 File downloads:
  • 2013INFO002.pdf: 115