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)
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.

 

back to home