Vehicle Routing Problem - VRP

Problem Definition

The VRP is a well known integer programming problem which
falls into the category of NP-hard problems [LK81].
It is defined on an undirected graph G = (**V**
,**E**) where
is a vertex set and
is an edge set. The depot is represented by vertex ,
and it is from where that m identical vehicles of
capacity Q must service all the cities or customers,
represented by the set of n vertices .
We define on **E** a non-negative cost,
distance or travel time matrix between
customers
and .
Each cusomer
has non-negative demand
and drop time
(time needed to unload all goods). Let be
a partition of **V** representing the
routes of the vehicles to service all the customers. The cost of a given route
(),
where
** V** and
(0 denotes the depot), is given by:

(1) |

and the cost of the problem solution (**S**)
is:

(2) |

The VRP consists in determining a set of a maximum of **m**
routes (see Figure 1)

- of minimum total cost (see (2));
- starting and ending at the depot ;
- and such each customer is visited exactly once by exactly one vehicle;
- the total demand of any route does not exceed
**Q**; - and the total duration of any route is not larger
than a preset bound
**D**.

Figure 1. The Vehicle Routing Problem
finds the minimum cost routes (b) to serve from a depot (a) a set of customers
(points) geographically distributed |

For more information about this problem, pease click here.

The Algorithm

In [AD04] the authors solve the well-known benchmark of Christofides, Mingozzi, and Toth [CMT79] for the VRP with four different cGAs. Specifically, they study a canonical cGA (called JCell), and three cGAs hybridized with different local search methods: 2-Opt (JCell2o), 2-Opt and 1-Interchange (JCell2o1i), and 2-Opt and 2-Interchange (JCell2o2i).

Table 1. Parameterization used in JCell. |

The recombination operator used in JCell is an edge recombination operator (ERX) [WSF89], that builds an offspring by preserving edges from both parents (see Figure 2).

Figure 2. The Edge Recombination Operator
(ERX). |

The mutation operator used in the algorithm consists in applying Insertion, Swap or Inversion operations to each gene with equal probability (see Figure 3). The Insertion [Fog88] operator selects a customer and inserts it in another randomly selected place. Swap [Ban90] consists in randomly selecting two customers and exchanging them. Finally, Inversion [Holl75] reverses the visiting order of the customers between two randomly selected cut points. In all the three operators changes might occur in an intra or inter-route way.

Figure 3. The three different mutation
used. |

Results

In Table 2 we show the best results obtained with the four versions of JCell used in the paper (after 30 runs of each algorithm). Bolded figures in the table stand for the knwon best values so far.

Table 2. Best solutions found with the
4 versions of JCell. |

From Table 2 we can conclude that the results worked out
by the canonical cGA (JCell) are far
from the best known results for the tested

instances. However, just by including a local improvement
with 2-Opt (JCell2o algorithm) the total cost of the
solutions found in all the instances is greatly reduced
with respect to JCell, although no optimal solution is still found. It is by
adding the -Interchange
local optimization that we achieve really interesting results, since we can
solve all the instances to the optimum. Table 2 shows that JCell2o1i finds the
best known solution for all the instances, having a similar behavior as for
JCell2o2i (being this last only slightly less accurate for C3).

Table 3. The best JCell (JCell2o1i) vs.
other well-known heuristics |

Finally, in Table 3 JCell2o1i is compared against the best so far techniques reported in the literature. We have selected some classic algorithms, like savings [CW64], sweep [WH72], 1-petal or 2-petal [RHG93], and some newer ones like the tabu search (TS) of Rochat and Taillard (RT) [RT95], the hybrid GAs of Prins [Prin04] and Berger and Barkaoui (BB) [BB03], and also ant systems (ant system -AS- [BHS99] and SavingAnts -SA- [RDH04]). These three last techniques are known to perform very well on the VRP. As shown in Table 3, RT, Prins, and JCell2o1i outperform the other algorithms, finding the best known solution for all the studied instances.