Insertion Based Ants for Vehicle Routing

Problems with Backhauls and Time Windows

Marc Reimann, Karl Doerner, and Richard F. Hartl

Institute of Management Science, University of Vienna

Brünnerstrasse 72, A-1210 Vienna, Austria
{marc.reimann, karl.doerner, richard.hartl}@univie.ac.at
http://www.bwl.univie.ac.at/bwl/prod/index.html

Abstract. In this paper we present and analyze the application of an

Ant System to the Vehicle Routing Problem with Backhauls and Time
Windows (VRPBTW). At the core of the algorithm we use an Insertion
procedure to construct solutions. We provide results on the learning and
runtime behavior of the algorithm as well as a comparison with a custom
made heuristic for the problem.

1 Introduction
Since their invention in the early 1990s by Colorni et al. (see e.g. [1]), Ant
Systems have received increasing attention by researchers, leading to a wide
range of applications such as the Graph Coloring Problem ([2]), the Quadratic
Assignment Problem (e.g. [3]), the Travelling Salesman Problem (e.g. [4], [5]), the
Vehicle Routing Problem ([6], [7]) and the Vehicle Routing Problem with Time
Windows ([8]). Recently, a convergence proof for a generalized Ant System has
been developed by Gutjahr ([9]).
The Ant System approach is based on the behavior of real ants searching
for food. Real ants communicate with each other using an aromatic essence
called pheromone, which they leave on the paths they traverse. In the absence
of pheromone trails ants more or less perform a random walk. However, as soon
as they sense a pheromone trail on a path in their vicinity, they are likely to
follow that path, thus reinforcing this trail. More specifically, if ants at some
point sense more than one pheromone trail, they will choose one of these trails
with a probability related to the strenghts of the existing trails. This idea has
first been applied to the TSP, where an ant located in a city chooses the next
city according to the strength of the artificial trails
This leads to a construction process that resembles the Nearest Neighbor
heuristic, which makes sense for the TSP. However, most of the applications
of Ant Systems to other problems, also used this constructive mechanism. In
order to be able to do so, the problem at hand had to be transformed into a
TSP first. By doing so, structural characteristics of the problem, may disappear,
thus leading to poor solutions. Moreover, for many of the problems solved with
Ant Systems so far, problem specific constructive algorithms exist that exploit
these structural characteristics. For example, for the classic VRP without side

M. Dorigo et al. (Eds.): ANTS 2002, LNCS 2463, pp. 135–148, 2002.
c Springer-Verlag Berlin Heidelberg 2002


136 M. Reimann, K. Doerner, and R.F. Hartl

constraints, we have shown in ([7]) that the incorporation of a powerful problem

specific heuristic algorithm significantly improves the performance and makes
the Ant System competitive to other state-of-the-art methods, such as Tabu
Search.
Building on these results, in this paper we propose an Ant System, where
the constructive heuristic is a sophisticated Insertion algorithm. We apply our
approach to the Vehicle Routing Problem with Backhauls and Time Windows
(VRPBTW), a problem with high practical relevance. We present some prelimi-
nary results, that suggest the potential of our approach. To our best knowledge,
we are not aware of existing works that deal with the application of an Ant
System to the VRPBTW. The same applies to the incorporation of an Insertion
algorithm within Ant Systems. These two points constitute the main contribu-
tion of our paper. While revising this paper we became aware of work done by
Le Louarn et al. ([10]). In their paper, the authors use their GENI heuristic (pro-
posed earlier in [11]) at the core of an ACO algorithm and show the potential of
this approach for the TSP.
In the next section we describe the VRPBTW and review the existing lit-
erature. Section 3 deals with the Ant System algorithm, and the details of the
incorporation of the Insertion algorithm. The numerical analysis in Section 4
focuses on the learning behavior of the Ant System, the effects of backhauls and
the general performance of our Ant System when compared with a custom-made
heuristic for the problem. Finally, we conclude in Section 5 with a summary of
the paper and an outlook on future research.

2 Vehicle Routing Problems with Backhauls and Time

Windows

Efficient distribution of goods is a main issue in most supply chains. The trans-
portation process between members of the chain can be modeled as a Vehicle
Routing Problem with Backhauls and Time Windows (VRPBTW). For example,
the distribution of mineral water from a producer to a retailer (linehauls) may
be coupled with the distribution of empty recyclable bottles from the retailer to
the producer (backhauls). Both linehauls and backhauls may be constrained by
possible service times at the producer and the retailers.
More formally, the VRPBTW involves the design of a set of pickup and
delivery routes, originating and terminating at a depot, which services a set of
customers. Each customer must be supplied exactly once by one vehicle route
during her service time interval. The total demand of any route must not exceed
the vehicle capacity. The total length of any route must not exceed a pre-specified
bound. Additionally, it is required that, on each route, all linehauls have to be
performed before all backhauls. The intuition for that is, that rearranging goods
en route is costly and inefficient. The objective is to minimize the fleet size, and
given a fleet size, to minimize operating costs. This problem is a generalization
of the VRP, which is known to be NP-hard (cf. [12]), such that exact methods
like Branch&Bound work only for relatively small problems in reasonable time.
 Insertion Based Ants for Vehicle Routing Problems 137

While the VRP has received much attention from researchers in the last four
decades (for surveys see [13]), the more constrained variants have only recently
attracted scientific attention. The Vehicle Routing Problem with Time Windows
(VRPTW) has been studied extensively in the last decade; for a recent overview
of metaheuristic approaches see (e.g. [14]). The same applies for the Vehicle
Routing Problem with Backhauls (VRPB, see e.g. [15]).
The VRPBTW, which combines the issues addressed separately in the works
cited above, has received only very little attention. Gelinas et al.([16]) have ex-
tended a Branch&Bound algorithm developed for the VRPTW to cope with
backhauling. They proposed a set of benchmark sets based on instances pro-
posed earlier for the VRPTW, and solved problems with up to 100 customers to
optimality. Their objective was to minimize travel times only. Simple construc-
tion and improvement algorithms have been proposed by Thangiah et al. ([17]),
while Duhamel et al.([18]) have proposed a Tabu Search algorithm to tackle the
problem. While the approach of Thangiah et al.’s considered the same objective
as we do in this study, namely to minimize fleet sizes first, and then to min-
imize travel times as a second goal, Duhamel et al. consider the minimization
of schedule times (which in addition to travel times include service times and
waiting times) as the second goal.

3 Ant System Algorithms for the VRPBTW

In this section we describe our Ant System algorithm and particularly focus
on the constructive heuristic used, as the basic structure of our Ant System
algorithm is identical to the one proposed in Bullnheimer et al.([6]) and used in
Reimann et al.([7]). The Ant System algorithm mainly consists of the iteration
of three steps:

– Generation of solutions by ants according to private and pheromone infor-

mation
– Application of a local search to the ants’ solutions
– Update of the pheromone information

The implementation of these three steps is described below.

3.1 Generation of Solutions

As stated above, the incorporation of the Insertion algorithm as the solution
generation technique within the Ant System is the main contribution of this
paper. So far, in most Ant Systems solutions have been built using a Nearest
Neighbor heuristic (see e.g. [6]). In Reimann et al. ([7]) we have shown for the
VRP the merit of incorporating a powerful problem specific algorithm. How-
ever, the Savings algorithm used there does not perform very well for problems
with time windows and/or backhauls such that we rather use a different con-
structive heuristic. The Insertion algorithm used in our current approach for the
VRPBTW is derived from the I1 insertion algorithm proposed by Solomon ([19])
138 M. Reimann, K. Doerner, and R.F. Hartl

for the VRPTW. Solomon tested many different route construction algorithms
and found that the I1 heuristic provided the best results.
This algorithm works as follows: Routes are constructed one by one. First,
a seed customer is selected for the current route, that is, only this customer is
served by the route. Sequentially other customers are inserted into this route
until no more insertions are feasible with respect to time window, capacity or
tour length constraints. At this point, another route is initialized with a seed
customer and the insertion procedure is repeated with the remaining unrouted
customers. The whole algorithm stops when all customers are assigned to routes.
In the above mentioned procedure two types of decisions have to be
taken. First, a seed customer has to be determined for each route, second
the attractiveness of inserting a customer into the route has to be calculated.
These decisions are based on the following criteria, where we will refer to the
attractiveness of a customer i as ηi :

Route initialization:

ηi = d0i ∀i ∈ Nu ,

where d0i denotes the distance between the depot and customer i and Nu
denotes the set of unrouted customers. This route initialization prefers seed
customers that are far from the depot.

Customer insertion:

ηi = max{0, maxj∈Rli [α · d0i − β · (dji + disj − djsj ) − (1 − β) · (bisj − bsj )]}

∀i ∈ Nu ,

where sj is the customer visited immediately after customer j in the current

solution, bisj is the actual arrival time at customer sj , if i is inserted between
customers j and sj , while bsj is the arrival time at customer sj before the
insertion of customer i and Rli denotes the set of customers assigned to the
current tour after which customer i could feasibly be inserted. Thus, this rule
not only considers the detour that occurs if customer i is inserted but also the
delay in service at the customer sj to be served immediately after i. These
two effects are weighted with the parameter β and compared with customer i s
distance to the depot, which is weighted with the parameter α. A customer being
located far from the depot, that causes little detour and little delay is more likely
to be chosen than a customer close to the depot and causing detour or delay.
Given these values, the procedure for each unrouted customer determines the
best feasible insertion position. Afterwards, given these values ηi , customer i∗ is
chosen such that ηi∗ ≥ ηi ∀i ∈ Nu .
Note that, for each customer we have to check the feasibility of inserting it
at any position in the current tour. While this is in principle quite tedious, in
particular if tours contain a large number of customers, it can be done quite
efficiently. Following Solomon we calculate for each position in the current tour
 Insertion Based Ants for Vehicle Routing Problems 139

the maximum possible delay at that position, that will ensure feasibility of the
subour starting at that position. This calculation of the maximum possible delay
has to be performed after each change to the current tour. However, by doing
so, we then only have to check if the insertion of a customer at a certain position
causes less delay than the maximum possible delay, in which case the insertion
is feasible. 1
To account for the fact that we have to deal with backhauls, we augment
these attractiveness values in the following way:

ηi =max {0,
maxj∈Rli [α · d0i − β · (dji + disj − djsj ) − (1 − β) · (bisj − bsj ) + γ · typei ]}
∀i ∈ Nu ,

where typei is a binary indicator variable denoting whether customer i is a

linehaul (typei = 0) or a backhaul customer (typei = 1). The intuition is that
we want to discriminate between linehaul and backhaul customers in some way.
In order to use the algorithm described above within the framework of our
Ant System we need to adapt it to allow for a probabilistic choice in each
decision step. This is done in the following way. First, the attractiveness for
inserting each unrouted customer at its best insertion on the current tour is
calculated according to the following function:

ηi = max {0,
τji +τisj
maxj∈Rli [(α·d0i −β·(dji +disj −djsj )−(1−β)·(bisj −bsj )+γ·typei )· 2·τjsj ]}

∀i ∈ Nu ,

where τji denotes the pheromone concentration on the arc connecting locations
(customers or depot) j and i. The pheromone concentration τji contains informa-
tion about how good visiting two customers i and j immediately after each other
was in previous iterations. The way we use the pheromone emphasizes the effect
of giving up an arc (the arc between customers j and sj in the example above)
and adding two other arcs (the arcs between customers j and i and customers i
τji +τis
and sj in the example above). In particular, the term 2·τjs j is larger than 1,
j
if the average pheromone value of the arcs to be added exceeds the pheromone
value of the arc to be deleted. Note, that the same pheromone utilization is done
for route initialization, thus augmenting the attractiveness of initializing a route
with an unrouted customer i by the search-historic information.
Then, we apply a roulette wheel selection to all unrouted customers with
positive attractiveness values ηi . The decision rule used can be written as

1
This procedure and the two rules for route initialization and customer insertion have
been proposed by Solomon ([19]) for the VRPTW.
140 M. Reimann, K. Doerner, and R.F. Hartl

3 3

5 4 5
4
2 2

6 6
1 0 1 0

7 7

Fig. 1. An example of the application of the Swap operator


 ηi
 h|η >0 ηh if ηi > 0

h
Pi = (1)


0 otherwise.
The chosen customer i is then inserted into the current route at its best feasible
insertion position.

3.2 Local Search

After an ant has constructed its solution, we apply a local search algorithm to
improve the solution quality. In particular, we apply Swap and Move operators to
the solution. The Swap operator, aims at improving the solution by exchanging
a customer i with a customer j. This operator is a special case of the 4-opt
operator, where the four arcs deleted are in pairs adjacent. An example of the
application of this operator is given in Figure 1, where customers 3 and 4 are
exchanged.
The Move operator tries to eject a customer i from its current position and
insert it at another position. It is a special case of the 3-opt operator, where two
of the three arcs deleted are adjacent. This operator is exemplified in Figure 2,
where customer 5 is moved from one route to another.
Both operators have been proposed by Osman ([20]). We apply these oper-
ators until no more improvements are possible. More specifically, we first apply

4 4
3 3

2 2
5 5
6 6
1 0 1 0
7 7

Fig. 2. An example of the application of the Move operator

 Insertion Based Ants for Vehicle Routing Problems 141

Move and then Swap operators. Note, that we do not accept infeasible solutions.
While Osman ([20]) proposed a more general version of these operators, where
λ adjacent customers can be moved or swapped, we restrict our local search to
the case where λ = 1. The reason for this is, that the operators were proposed
for the classic VRP without time window and backhauling constraints. Given
these additional constraints, most possible operations with λ > 1 lead to infea-
sible solutions. Thus, the additional computation effort to perform these more
complex operations, will in general not be justified.

3.3 Pheromone Update

After all ants have constructed their solutions, the pheromone trails are updated
on the basis of the solutions found by the ants. According to the rank based
scheme proposed in ([5]) and ([6]), the pheromone update is as follows
p
 µ ∗
τij := ρτij + ∆τij + σ∆τij (2)
µ=1

where 0 ≤ ρ ≤ 1 is the trail persistance and σ = p + 1 is the number of elitists.

Using this scheme two kinds of trails are laid. First, the best solution found
during the process is updated as if σ ants had traversed it. The amount of
∗
pheromone laid by these elitists is ∆τij = 1/L∗ , where L∗ is the objective value
of the best solution found so far. Second, the p best ants of the iteration are
allowed to lay pheromone on the arcs they traversed. The quantity laid by these
ants depends on their rank µ as well as their solution quality Lµ , such that the
µ
µ-th best ant lays ∆τij = (p − µ + 1)/Lµ . Arcs belonging to neither of those
solutions just lose pheromone at the rate (1 − ρ), which constitutes the trail
evaporation.

4 Numerical Analysis

In this section we turn to the numerical analysis of our proposed approach. First
we will describe the benchmark problem instances. After providing details about
the parameter settings, we evaluate the influence of the pheromone information.
Finally, we compare the results of our Ant System with those of Thangiah et al.’s
heuristic algorithms. All our comparisons will be on the basis of the objective to
first minimize fleet sizes and then minimize travel times as a second goal.
This objective was established by minimization of the following objective
function:

L = 10000 · F S + T T, (3)
where L denotes the total costs of a solution, F S denotes the fleet size found,
and T T corresponds to the total travel time (or distance). The parameter 10000
was chosen to ensure that a solution that saves a vehicle always outperforms a
solution with a higher fleet size.
142 M. Reimann, K. Doerner, and R.F. Hartl

4.1 The Benchmark Problem Instances

The benchmark problem instances we used for our numerical tests were devel-
oped by Gelinas et al. ([16]). They used the first five problems of the r1 instances,
namely r101 to r105, originally proposed by Solomon ([19]) for the vehicle rout-
ing problem with time windows (VRPTW). Each of these problems consists of
100 customers to be serviced from a central depot. The customers are located
randomly around the depot. Service has to take place within a short time hori-
zon (230 time units), and vehicle capacities are fairly loose when compared with
the time window requirements at the customers. These time window require-
ments are varying in the data sets. The average time window length in the five
instances are given in Table 1.

Table 1. Average length of the time windows

Instance r101 r102 r103 r104 r105

Avg. Length of TW 10.0 57.4 103.0 148.3 30.0

Given these data sets Gelinas et al. randomly chose 10%, 30% and 50% of the
customers to be backhaul customers with unchanged quantities, thus creating
15 different 100 customer instances.

4.2 Parameter Settings

Our aim is to use standard approaches and standard parameter settings as much
as possible in order to demonstrate the benefit of intelligent combination of these
approaches. However, we also performed parameter tests in order to find good
combinations of these parameters for our problem. It turned out, that most of
the parameters should be in the range documented in the literature.
More specifically, we analyzed the three parameters of the insertion algorithm
in the ranges α ∈ {0, 0.1, ..., 2}, β ∈ {0, 0.1, ..., 1} and γ ∈ {0, 1, ..., 20} on the
instances described above. From this analysis we obtained the following values:
α = 1, β = 1 and γ = 13.
Note, that the parameter γ = 13 leads to a discrimination between linehaul
and backhaul customers in favor of the backhaul customers. While this seems
counterintuitive, it can be explained in the following way. Given the parameters
α and β, the attractiveness values can become negative. However, negative at-
tractiveness values prevent insertion. Thus, feasible solutions may be prohibited
and this will generally lead to larger fleet sizes. This effect is reduced by the pa-
rameter γ, leading to tighter packed vehicles and smaller fleet sizes at the cost of
 Insertion Based Ants for Vehicle Routing Problems 143

increased travel times. To balance this trade-off, we chose to make the backhaul
customers more attractive as they represent the minority of customers.2
Let n be the problem size, i.e. the number of customers to be served, then
the Ant System parameters were: m =
n/2 ants, ρ = 0.95 and p = 4 elitists.
These parameters were not extensively tested, as our experience suggests that
the rank based Ant System is quite robust. However, the number of ants was
reduced to m =
n/2 to be able to run more iterations.
For each instance we performed 10 runs of 2.5 minutes each. All runs were
performed on a Pentium 3 with 900MHz. The code was implemented in C.

4.3 Evaluation of Pheromone Influence

In this section we will analyze whether our approach features pheromone learning
or not. As we diverge from the standard constructive approach used in Ant
Systems for Vehicle Routing, we have to check whether the utilization of the
pheromone trails helps or hinders the constructive process of the ants. To do
this, we compare the proposed Ant System with a stochastic implementation of
the underlying algorithm, where no pheromone is used.

Table 2. Influence of the pheromone on the solution quality

Time 10% BH 30% BH 50% BH

in ASinsert StochInsert ASinsert StochInsert ASinsert StochInsert
sec. FS TT FS TT FS TT FS TT FS TT FS TT
15 17,64 1552,0 17,62 1554,3 18,34 1617,2 18,4 1629,2 18,92 1662,2 18,92 1665,6
30 17,44 1534,4 17,54 1552,0 18,24 1605,3 18,3 1628,9 18,74 1649,7 18,88 1660,1
75 17,38 1509,1 17,38 1550,9 18,08 1583,0 18,14 1624,3 18,54 1630,9 18,84 1651,7
150 17,3 1499,2 17,3 1546,7 18,02 1565,8 18,08 1623,9 18,44 1617,6 18,74 1649,0

FS...fleet size
TT...travel times

The results are shown in Table 2. We provide averaged results for the differ-
ent backhaul densities after runtimes of 15, 30, 75 and 150 seconds. The table
confirms that the use of the pheromone trails in decision making significantly
improves solution quality. The Ant System (referred to as ASinsert) does find
better solutions than the stochastic implementation of the Insertion algorithm
(referred to as StochInsert). This can be seen from the last row of the table.
Furthermore, the table shows that the Ant System finds good solutions faster
than the stochastic Insertion algorithm. After 15 seconds the solutions of the
2
However, we plan and already started to investigate other methods to solve this
problem. One idea is to adjust the attractiveness values corresponding to feasible
insertions, to ensure that a certain percentage of these values is positive.
144 M. Reimann, K. Doerner, and R.F. Hartl

Ant System are already superior to those of the stochastic Insertion algorithm,
albeit the difference is small.
As more and more pheromone information is built and this matrix better
reflects the differences between good and bad solutions the Ant System clearly
outperforms the stochastic algorithm without pheromone information. This fact
is also shown in Figure 3. We chose the case with 10% backhauls, as in this
case the evolution of the fleet sizes, which are the primary goal, is similar in
both approaches. So we can compare just travel times, and the figure shows that
the Ant System at any point in time finds better solutions than the stochastic
Insertion algorithm and moreover the difference gets larger as the number of
iterations increases.

1560
1550
1540
1530
travel times

1520
1510
1500
1490
1480
1470
15 sec. 30 sec. 75 sec. 150 sec.
runtime in seconds

Fig. 3. Ant System(light columns) and stochastic Insertion algorithm performance on

problems with 10% backhauls

4.4 Comparison of Our Ant System with Existing Results

Let us now turn to the analysis of the solutions found with respect to absolute
solution quality. As stated above, there exists one paper that studies the same
objective as we do. In this paper, Thangiah et al. ([17]), propose a constructive
algorithm and a number of local search descent algorithms to tackle the problem.
In Table 3 we show in detail, that is for each instance, the results of this
approach together with the results of our Ant System and the stochastic Insertion
algorithm. Note, that Thangiah et al. propose five different algorithms and the
results in the first column of Table 3 are the best ones for each instance regardless
of the version that found the solution. For our approaches we present average
results over ten runs. In the rightmost two columns we report fleet sizes and
travel times of the best solutions we found regardless of the algorithm that found
this solution. The last row of the table reports the aggregate numbers for the
approaches. Our Ant System outperforms the Thangiah’s simple heuristics by
approximately 2% with respect to fleet sizes, and by 2.7% with respect to travel
 Insertion Based Ants for Vehicle Routing Problems 145

times. However, we also see that the simple heuristics outperform our approach
in three instances, namely r102 with 30% and 50% backhauls and r103 with 10%
backhauls. In these instances, we did not find the same fleetsize as Thangiah’s
algorithms. As these instances are spread over all possible backhaul densities
and our approach on average outperforms Thangiah’s algorithm for each density
of backhaul customers, the effect has to stem from the characteristics of the
backhaul customers.

Note that we do not compare computation times for the approaches. We

believe that a comparison of runtimes is meaningless in this case. First, the ma-
chines are very different, in particular ours are much faster. Second, a metaheuris-
tic can never be expected to be as fast as a custom-made approach. Thangiah’s
heuristics find their solutions within less than a minute, while our approach runs
for 2.5 minutes, we nevertheless believe that the results obtained by our Ant Sys-
tem justify the application and show the potential savings that can be achieved
through the use of a metaheuristic approach. Moreover, the computation time
reported for our approach refers to the total execution time of the algorithm.
Of course we find good, and even better solutions than Thangiah, earlier in the
search.

Table 3. Comparison of solution quality between our Ant System and other approaches

Thangiah StochInsert ASinsert Best solutions

best avg. avg. identified by
5 versions 10 runs 10 runs our algorithms
Instance FS TT FS TT FS TT FS TT
r101 10% BH 24 1842,3 22 1886,85 22 1841,78 22 1831,68
r101 30% BH 24 1928,6 23,3 2000,42 24 1931,73 23 1999,16
r101 50% BH 25 1937,6 24,1 1981,00 24 1949,49 24 1945,29
r102 10% BH 20 1654,1 19,5 1695,13 19,8 1636,20 19 1677,62
r102 30% BH 21 1764,3 22 1777,44 22 1759,18 22 1754,43
r102 50% BH 21 1745,7 22 1799,58 22 1784,15 22 1782,21
r103 10% BH 15 1371,6 16 1393,69 16 1352,23 16 1348,41
r103 30% BH 16 1477,6 16 1438,83 16 1395,88 16 1395,88
r103 50% BH 17 1543,2 17 1510,63 17 1477,63 17 1467,66
r104 10% BH 13 1220,3 12 1167,73 11,9 1142,17 11 1205,78
r104 30% BH 12 1303,5 12 1238,09 12 1145,77 12 1128,30
r104 50% BH 13 1346,6 12,6 1282,08 12 1232,66 12 1208,46
r105 10% BH 17 1553,4 17 1590,16 16,8 1523,54 16 1544,81
r105 30% BH 18 1706,7 17,1 1664,66 16,1 1596,23 16 1592,23
r105 50% BH 18 1657,4 18 1671,84 17,2 1644,15 17 1633,01
Sum 274 24052,9 270,6 24098,13 268,8 23412,79 265 23514,92

FS...fleet size
TT...travel times
146 M. Reimann, K. Doerner, and R.F. Hartl

Finally, we show in Figure 4 the effects of the density of backhaul customers

on both fleet sizes and travel times for our Ant System. Clearly, both fleet sizes
and travel times increase with the density of backhaul customers. Note however,
that increasing the percentage of backhaul customers further beyond 50% will
not further increase the travel times and fleet sizes. On the contrary, fleet sizes
and travel times will fall again. In the extreme case of 100% backhauls we will
have the same solution as in the other extreme case of 100% linehauls. Generally,
with a mix of 50% linehauls and 50% backhauls, there is the smallest degree of
freedom for the optimization, such that in these cases the solution quality should
be worst.

(a) (b)

Fig. 4. Effect of backhaul customer density on fleet sizes (a) and travel times (b)

5 Conclusions and Future Research

In this paper we have proposed a promising approach for the Vehicle Routing
Problem with Backhauls and Time Windows (VRPBTW). This Ant System ap-
proach is based on the well known Insertion algorithm proposed for the VRPTW
by Solomon ([19]). We have proposed an approach to use pheromone information
in the context of such an Insertion algorithm and shown that our algorithm ben-
efits from this pheromone information and outperforms a custom-made heuristic
proposed for the VRPBTW by Thangiah et al. ([17].)
Future research will deal with a more detailed analysis of the approach, and
its application to other combinatorial problems. For the VRPBTW we will an-
alyze the approach on larger instances. We also plan to incorporate swarm-like
features by equipping each ant with its own set of parameters (of the heuristic)
and adjusting these parameters in an evolutionary way during the optimization
process. Furthermore, we will embed this approach in our multi-colony Ant Sys-
tem proposed already in Doerner et al. ([21]). This approach should help us deal
better with the multiple objectives that have to be tackled in the problem.

Acknowledgments. We are grateful to two anonymous referees who provided

valuable comments that improved the presentation of the paper. This work was
supported by the Oesterreichische Nationalbank (OeNB) under grant #8630.
 Insertion Based Ants for Vehicle Routing Problems 147

References
1. Colorni, A., Dorigo, M. and Maniezzo, V.: Distributed Optimization by Ant
Colonies. In: Varela, F. and Bourgine, P. (Eds.): Proc. Europ. Conf. Artificial
Life. Elsevier, Amsterdam (1991) 134–142
2. Costa, D. and Hertz, A.: Ants can colour graphs. Journal of the Operational Re-
search Society 48(3) (1997) 295–305
3. Stützle, T. and Dorigo, M.: ACO Algorithms for the Quadratic Assignment Prob-
lem. In: Corne, D. et al. (Eds.): New Ideas in Optimization. Mc Graw-Hill, London
(1999) 33–50
4. Dorigo, M. and Gambardella, L. M.: Ant Colony System: A cooperative learning
approach to the Travelling Salesman Problem. IEEE Transactions on Evolutionary
Computation 1(1) (1997) 53–66
5. Bullnheimer, B., Hartl, R. F. and Strauss, Ch.: A new rank based version of the ant
system: a computational study. Central European Journal of Operations Research
7(1) (1999) 25–38
6. Bullnheimer, B., Hartl, R. F. and Strauss, Ch.: An improved ant system algorithm
for the vehicle routing problem. Annals of Operations Research 89 (1999) 319–328
7. Reimann, M., Stummer, M. and Doerner, K.: A Savings based Ant System for the
Vehicle Routing Problem. to appear in: Proceedings of the Genetic and Evolution-
ary Computation Conference (GECCO 2002), Morgan Kaufmann, San Francisco
(2002)
8. Gambardella, L. M., Taillard, E. and Agazzi, G.: MACS-VRPTW: A Multiple Ant
Colony System for Vehicle Routing Problems with Time Windows. In: Corne, D.
et al. (Eds.): New Ideas in Optimization. McGraw-Hill, London (1999) 63–73
9. Gutjahr, W. J.: ACO algorithms with guaranteed convergence to the optimal so-
lution. Information Processing Letters. 82 (2002) 145–153
10. Le Louarn, F. X., Gendreau, M. and Potvin, J. Y.: GENI Ants for the Travelling
Salesman Problem. CRT Research Report, Montreal (2001)
11. Gendreau, M., Hertz, A. and Laporte, G.: New Insertion and Postoptimization
Procedures for the Travelling Salesman Problem. Operations Research. 40 (1992)
1086–1094
12. Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to the
Theory of NP Completeness. W. H. Freeman & Co., New York (1979)
13. Toth, P. and Vigo, D. (Eds.): The Vehicle Routing Problem. Siam Monographs on
Discrete Mathematics and Applications, Philadelphia (2002)
14. Bräysy, O. and Gendreau, M.: Metaheuristics for the Vehicle Routing Problem
with Time Windows. Sintef Technical Report STF42 A01025 (2001)
15. Toth, P. and Vigo, D.: VRP with Backhauls. In Toth, P. and Vigo, D. (Eds.):
The Vehicle Routing Problem. Siam Monographs on Discrete Mathematics and
Applications, Philadelphia (2002) 195–224
16. Gelinas, S., Desrochers, M., Desrosiers, J. and Solomon, M. M.: A new branching
strategy for time constrained routing problems with application to backhauling.
Annals of Operations Research. 61 (1995) 91–109
17. Thangiah, S. R., Potvin, J. Y. and Sun, T.: Heuristic approaches to Vehicle Rout-
ing with Backhauls and Time Windows. Computers and Operations Research. 23
(1996) 1043–1057
18. Duhamel, C., Potvin, J. Y. and Rousseau, J. M.: A Tabu Search Heuristic for
the Vehicle Routing Problem with Backhauls and Time Windows. Transportation
Science. 31 (1997) 49–59
148 M. Reimann, K. Doerner, and R.F. Hartl

19. Solomon, M. M.: Algorithms for the Vehicle Routing and Scheduling Problems
with Time Window Constraints. Operations Research. 35 (1987) 254–265
20. Osman, I. H.: Metastrategy simulated annealing and tabu search algorithms for
the vehicle routing problem. Annals of Operations Research. 41 (1993) 421–451
21. Doerner, K. F., Hartl, R.F., and Reimann, M.: Are CompetANTS competent for
problem solving - the case of a transportation problem. POM Working Paper
01/2001 (2001)