Supporting material for the paper:

Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

Leonora Bianchi - Mauro Birattari - Marco Chiarandini - Max Manfrin - Monaldo Mastrolilli - Luis Paquete - Olivia Rossi-Doria - Tommaso Schiavinotto


Accepted to PPSN VIII

Abstract:

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

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.
value.120instances.jpg rank.120instances.jpg


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.