In the vehicle routing problem with stochastic demands a vehicle has to
serve a set of customers whose exact demand is known only upon arrival
at the customer's location. The objective is to find a permutation of the customers (an a priori tour)
that minimizes the expected distance traveled by the vehicle.
Since the objective function is computationally demanding, effective
approximations of it could improve the algorithms' performance.
For the problem under study, we show that a good choice is using the length of the a priori tour as a fast approximation
of the objective, to be used in the local search of the several metaheuristics
analyzed. We also show that for the instances tested, our metaheuristics find better
solutions with respect to a known effective heuristic and with respect to solving the problem
as two related deterministic problems.
Algorithms
The metaheuristics were implemented in C++. We used the GNU compiler gcc version 2.95.4. The following files contain the source code of the implemented metaheuristics. They contain a makefile and the executable can be generated by simply typing
make. All algorithms use the same command line arguments as follows:
<algorithm> -i <instance_file> [-t <time limit in seconds per try>] [-n <number of trials>] [-s <seed for random number generator>] [-o <output_file>] [-q <vehicle capacity>] [-p <use proxy>]
Ant Colony Optimization (ACO)
Genetic Algorithm (EA)
Iterated Local Search (ILS)
Simulated Annealing (SA)
Tabu Search (TS)
Random Restart Local Search (FR)
Instances
In the literature there is no commonly used benchmark for the VRPSD, therefore we have generated our own testbed. We have tried to consider instances which are
interesting from different points of view.
First of all, the position of customers was not chosen uniformly at random, but randomly with normal distributions around two centers (so customers are grouped in two clusters). This is done in order to consider instances near to the real world situations, where customers may be located for instances in two different cities. The clusters' centers have coordinate in [0,99], and customers' coordinates are all different. We considered a total of 120 instances, of these 75 instances have 50 customers, 40 instances have 100 customers, and 5 instances have 200 customers.
The 120 instances are availabele
here.
Results are summarized in the boxplots of Fig. 2.
Each row of a boxplot shows the distribution of the quantity on the horizontal axis
obtained by each metaheuristic on all the tested instances.
The left plot of Fig. 2 reports on the horizontal axis the expected
cost of the solutions found, normalized with respect to the range of improvement found by FR.
The right plot of Fig. 2 shows the ranking of metaheuristics;
the results of all executions on the
same instance are ordered by quality of the solution (VRPSD expected cost) to determine the rank.
Figure 2:
Results over the 120 tested instances. The vertical bar of each box corresponds to the median value of the quantity on the horizontal axis;
the box spans the interval included in the 25% and 75%
quantile; the whiskers extend to the more extreme points that are no more than 1,5 times the interquartile; the circles represent points who are outside this interval.
|
Table 1:
Pairwise comparisons using Wilcoxon rank sum test. 120 instances
|
ils-tsplike |
ils-vrpsdlike |
ea-tsplike |
ea-vrpsdlike |
ts-tsplike |
ts-vrpsdlike |
fr-tsplike |
fr-vrpsdlike |
ils-vrpsdlike |
0.01924 |
- |
- |
- |
- |
- |
- |
- |
ea-tsplike |
1 |
0.70214 |
- |
- |
- |
- |
- |
- |
ea-vrpsdlike |
1.7e-05 |
0.27075 |
0.00051 |
- |
- |
- |
- |
- |
ts-tsplike |
7.1e-09 |
0.07068 |
1.5e-08 |
0.88084 |
- |
- |
- |
- |
ts-vrpsdlike |
4.4e-07 |
0.15809 |
4.3e-06 |
1 |
1 |
- |
- |
- |
fr-tsplike |
< 2e-16 |
8.0e-14 |
< 2e-16 |
1.4e-13 |
5.0e-12 |
3.4e-14 |
- |
- |
fr-vrpsdlike |
< 2e-16 |
5.9e-13 |
< 2e-16 |
3.1e-10 |
1.1e-07 |
1.8e-10 |
0.06001 |
- |
sa-tsplike |
< 2e-16 |
< 2e-16 |
< 2e-16 |
5.1e-14 |
3.6e-12 |
4.3e-14 |
0.02327 |
1.3e-05 |
sa-vrpsdlike |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
3.6e-12 |
3.4e-14 |
aco-tsplike |
< 2e-16 |
1.2e-14 |
< 2e-16 |
4.3e-14 |
1.2e-14 |
< 2e-16 |
0.00054 |
1.1e-05 |
aco-vrpsdlike |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
1.9e-08 |
6.4e-11 |
cych |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
tsp |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
cvrp |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
|
sa-tsplike |
sa-vrpsdlike |
aco-tsplike |
aco-vrpsdlike |
cych |
tsp |
ils-vrpsdlike |
- |
- |
- |
- |
- |
- |
ea-tsplike |
- |
- |
- |
- |
- |
- |
aco-tsplike |
- |
- |
- |
- |
- |
- |
ts-tsplike |
- |
- |
- |
- |
- |
- |
ts-vrpsdlike |
- |
- |
- |
- |
- |
- |
fr-tsplike |
- |
- |
- |
- |
- |
- |
fr-vrpsdlike |
- |
- |
- |
- |
- |
- |
sa-tsplike |
- |
- |
- |
- |
- |
- |
sa-vrpsdlike |
6.4e-06 |
- |
- |
- |
- |
- |
aco-tsplike |
1 |
7.5e-07 |
- |
- |
- |
- |
aco-vrpsdlike |
0.21655 |
0.01831 |
0.08072 |
- |
- |
- |
cych |
2.2e-07 |
0.21655 |
1.9e-11 |
9.5e-06 |
- |
- |
tsp |
8.7e-10 |
0.01058 |
3.4e-14 |
1.1e-07 |
0.08072 |
- |
cvrp |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
< 2e-16 |
For the interpretation of the results, one could
consider the performance of FR like a sort of minimal requirement for a metaheuristic.
In fact, FR does essentially the simple iteration of the same local search for
different starting solutions, until the available computation time is not over. Therefore, it is
reasonable to request that a good algorithm for the VRPSD perform significantly better than FR.
From Fig. 2, it seems that only ILS, EA and TS
perform significantly better than FR. This observation is
confirmed by the one-tailed paired Wilcoxon test,
confidence level 95% with Holmes corrections for multiple tests, that
we have done for each couple MH-FR (with the same type of approximation scheme).
Table 2:
Comparison of the random restart against each of the
metaheuristics. All algorithms are implemented using the VRPSDlike approximation of the cost function.
|
ils-vrpsdlike |
ea-vrpsdlike |
ts-vrpsdlike |
sa-vrpsdlike |
aco-vrpsdlike |
fr-vrpsdlike |
<1e-14 |
<1e-11 |
<1e-11 |
1 |
1 |
Table 3:
Comparison of the random restart against each of the
metaheuristics. All algorithms are implemented using the TSPlike
approximation of the cost function.
|
ils-tsplike |
ea-tsplike |
ts-tsplike |
sa-tsplike |
aco-tsplike |
fr-tsplike |
<1e-20 |
<1e-20 |
<1e-13 |
1 |
1 |
We have also verified if the TSPlike version of the metaheuristics
is significantly better than the VRPSDlike version, and the answer is positive.
Wilcoxon signed rank test with continuity correction
"All algorithms"
Data: data.all.tsp and data.all.vrpsd
V = 94779, p-value = 1.555e-08
alternative hypothesis: true mu is less than 0
Another point to note is that the cyclic heuristic performs worse than all metaheuristics.
This is an interesting results, since the cyclic heuristic was performing very well for different types of instances (customers uniformly distributed on the unit square and low
demand over capacity ratio).
The worst algorithms in our tests are the two state of the art heuristics for the TSP,
respectively CVRP; this is a point which encourages the development of
VRPSD problem-specific algorithms, and let us conclude that, for the type of tested
instances, the stochasticity of the problem is not negligible.