Solution Techniques

Ant Algorithms

The first ant system for the VRP was designed by [Bullnheimer et al. 1997], who considered the most elementary version of the problem: the CVRP.

For more complex versions of the VRP, [Gambardella, Taillard and Agazzi 1999] have developed a multiple ant colony system for the VRPTW (MACS-VRPTW) which is organized with a hierarchy of artificial ant colonies designed to successively optimize a multiple objective function: the first colony minimizes the number of vehicles while the second colony minimizes the traveled distances. Cooperation between colonies is performed by exchanging information through pheromone updating.

In the design of [Bullnheimer et al. 1997], there are two basic ant system phases: construction of vehicle routes and trail update. The AS algorithm is explained here.

Ant System Algorithm

After initializing the AS, the two basic steps construction of vehicle routes and trail update are repeated for a number of iterations. Concerning the initial placement of the artificial ants, it was found that the number of ants should be equal at each customer at the beginning of an iteration. The 2-opt heuristic (an exhaustive exploration of all the permutations obtainable by exchanging 2 cities) is used to shorten the vehicle routes generated by the artificial ants, and it considerably improves the solution quality. In addition to this straightforward local search, we also introduce candidate lists for the selection of customers, which are determined in the initialization phase of the algorithm. For each location $i$ we sort $j = 1, …, n$ according to increasing distances $d(i, j)$ to obtain the candidate list. The proposed AS for the CVRP can be described by the following schematic algorithm:

Initialize
For iterations do:
1. For all ants generate a new solution using Formula (1) and the candidate lists
2. Improve all vehicle routes using the 2-opt heuristic
3. Update the pheromone trails using Formula (2)

Construction of Vehicle Routes

To solve the VRP, the artificial ants construct solutions by successively choosing cities to visit, until each city has been visited. Whenever the choice of another city would lead to an unfeasible solution for reasons of vehicle capacity or total route length, the depot is chosen and a new tour is started. For the selection of a (not yet visited) city, two aspects are taken into account: how good the choice of that city was, information that is stored in the pheromone trails $τ$ associated with each arc $(i, j)$ , and how promising the choice of that city is. This latter measure of desirability, called visibility and denoted by $η$ , is the local heuristic function mentioned above.

With $set of feasible cities$ , city $j$ is selected to be visited as follows:

$Selection probability formula$ (1)

This probability distribution is biased by the parameters $α$ and $β$ that determine the relative influence of the trails and the visibility, respectively. The visibility is defined as the reciprocal of the distance, and the selection probability is then further extended by problem-specific information. There, the inclusion of savings and capacity utilization both lead to better results. On the other hand, the latter is relatively costly in terms of computation time (as it has to be calculated in each step of an iteration) and is therefore not used in this paper. Thus, we introduce the parameters f and g, and use the following parametrical saving function for the visibility: $parametrical saving function$ .

Trail Update

After an artificial ant has constructed a feasible solution, the pheromone trails are laid depending on the objective value of the solution. This update rule is as follows:

$Pheromone trail update rule$ (2)

where $ρ$ is the trail persistence (with $0 ≤ ρ ≤ 1$ ), thus the trail evaporation is given by $(1 − ρ)$ . Only if arc $(i, j)$ was used by the $μ$ -th best ant is the pheromone trail increased by a quantity $Δτ$ which is then equal to $1 / L$ , and zero otherwise (cf. second term in (2)). In addition to that, all arcs belonging to the so-far best solution (objective value $L*$ ) are emphasized as if $e$ elitist ants had used them. Thus, each elitist ant increases the trail intensity by an amount $Δτ*$ that is equal to $1 / L*$ if arc $(i, j)$ belongs to the so-far best solution, and zero otherwise (cf. third term in (2)).