First generated: November 2009. Last update:July 2010
Table of Contents |
The vehicle routing problem with stochastic demands and customers (VRPSDC) requires finding the optimal route for a capacitated vehicle that delivers goods to a set of customers, where each customer has a probability of requiring being visited and has a stochastic demand. Besides the usual difficulty of finding the optimal solution in a large search space, the VRPSDC has a computationally expensive cost function. For large instances, evaluation of the cost function is a primary bottleneck for finding high quality solutions in a reasonable computation time. We tackle this issue by using an empirical estimation approach, where the solution cost is estimated by Monte Carlo simulation. Moreover, we use the recently developed state-of-the-art iterative improvement algorithm for the closely related probabilistic traveling salesman problem as an underlying local search algorithm inside metaheuristic algorithms for the VRPSDC. We present an experimental study of several estimation-based algorithms on a number of problem instances. We show that the proposed algorithms outperform the current best algorithm for the given problem. Among the estimation-based algorithms, we show that an ant colony optimization algorithm is particularly effective.
Keywords: Vehicle routing problem with stochastic demands and customers, Metaheuristics, Iterative Improvement Algorithm, Empirical Estimation
Experimental set | File |
---|---|
Tuning instances |
Clustered instances of size 1000 |
Parameter configutations |
A set of 10 parameter configurations for each algorithm on 1000 CPU seconds |
Experimental set | File |
---|---|
Instances used in Section 4.2 |
Section4.2.tar.gz |
Instances used in Section 4.3 |
Section4.3.tar.gz |
Instances used in Section 4.4 |
Section4.4.tar.gz |
The absolute values for all the results in the form of tables. In these tables, we present the final solution quality and the corresponding computational time for each probabiltiy range. Moreover, in order to test that the observed difference between the cost of the solutions reached by the considered algorithms are significant in a statistical sense, we use a t test and we present the 95% confidence interval obtained from the t-test. The results are composed in a single pdf file: