A SOLUTION TO THE VEHICLE ROUTING PROBLEM USING

TABU SEARCH

Etiene Pozzobom Lazzeris Simas

Universidade do Vale do Rio dos Sinos. Av. Unisinos,950,São Leopoldo,Brasil

Arthur Tórgo Gómez

Universidade do Vale do Rio dos Sinos. Av. Unisinos,950,São Leopoldo,Brasil

Keywords: Vehicle Routing Problem, Tabu Search.

Abstract: This paper presents a model for solving the Vehicle Routing Problem using Tabu Search. The Vehicle

Routing Problem aims to serve a set of clients by a fleet of vehicle through the creation of least-cost routes

that satisfy some constraints. In this paper, only the vehicle capacity is considered. The objective of this

model is to design least-cost routes to serve a set of clients with known demands in such a way that some

defined constraints are satisfied. An application to construct this model is proposed using Tabu Search.

Some experiments were generated and confirmed that an increase in diversification on search space politics

can generate results that are more qualified.

1 INTRODUCTION

The Vehicle Routing Problem (VRP) can be

described as a set of customers that have to be

served by a fleet of vehicles, satisfying some

constraints (Laporte, 1992; Xu and Kelly, 1996).

The Routing problems are usually deal within the

logistic context (Ho and Haugland, 2004; Xu and

Kelly, 1996). Logistic can be defined as the

provision of goods and services from a supply point

to a demand point (Bodin, Golden and Assad, 1983).

The transport is one of the most costly activities in

logistic, typically varying in one or two thirds of the

total costs (Ballou, 2001). As said by Thangiah and

Petrovic (Thangiah and Petrovic, 1997) the cost of

transportation is dependent upon the minimization of

the distance traveled by the vehicles and the number

of vehicles required for serving all the demands.

Therefore, the necessity to improve the efficiency of

this activity has great importance. The search for

transportation cost reduction, through designing a

routing model that offer more economic routes

aiming the minimization of time, distance and

associated cost (Barbarasoglu and Ozgur, 1999)

besides the number of vehicles required is a frequent

problem of the decisions making in the logistic

context (Ballou, 2001). The importance of the

routing problems is evident due to the magnitude of

the associated distribution costs. In this context, a

small percentage saved in these expenses could

result in substantial saving total (Bodin, Golden and

Assad, 1983). Section 2 presents some resolutions

methods of this problem. Section 3 is an introduction

to Tabu Search metaheuristic. Section 4 defines the

proposed model and the formulation used in this

paper is showed in section 5. The Tabu Search

implementation and the politics of neighborhood

generation are explained in section 6. Section 7

brings a description of the experiments that were

made and, in section 8, the results are shown,

followed by the final considerations of this work in

section 9.

2 THE VEHICLE ROUTING

PROBLEM

The VRP is NP-Hard (Lenstra e Rinooy Kan, 1981)

and this property makes this type of problem very

difficult to be solved by exact methods, because of

the computational costs. Since VRP is Np-Hard to

obtain good solutions in an acceptable time,

heuristics are used and this is the reason why the

Pozzobom Lazzeris Simas E. and Tórgo Gómez A. (2006).

A SOLUTION TO THE VEHICLE ROUTING PROBLEM USING TABU SEARCH.

In Proceedings of the Third International Conference on Informatics in Control, Automation and Robotics, pages 76-81

DOI: 10.5220/0001212000760081

 SciTePress

majority of researchers and scientists direct their

efforts in heuristics development (Thangiah and

Petrovik, 1997; Nelson et al, 1985; Xu and Kelly,

1996). Osman and Laporte (Osman and Laporte,

1996) define heuristic as a technique, which seeks

good solutions at a reasonable computational cost

without being able to guarantee the optimality.

Laporte et al (Laporte et al, 2000) define two main

groups of heuristics: classical heuristics, developed

mostly between 1960 and 1990, and metaheuristics.

The classical heuristics are divided in three groups:

constructor methods, two-phase methods and

improvement methods. Since 1990, the

metaheuristics have been applied to the VRP

problem. To Osman and Laporte (Osman and

Laporte, 1996) a metaheuristic is formally defined as

an iterative generation process which guides a

subordinate heuristic by combining intelligently

different concepts for exploring and exploiting the

search space in order to find efficiently near-optimal

solutions. Several metaheuristics have been

proposed to solve the VRP problem. Among these

ones, Tabu Search are considered the best

metaheuristic for VRP. To review some works with

Tabu Search and others metaheuristics some

readings are suggested (Cordeau et al, 2002;

Gendreau et al, 1999; Tarantilis et al, 2005).

3 TABU SEARCH

It’s a technique to solve optimization combinatorial

problems (Glover, 1989; Glover and Laguna, 1997),

which consists in an iterative routine to construct

neighborhoods, emphasizing the prohibition of

stopping in an optimum local. The process that Tabu

Search seeks, for the best solution, is through an

aggressive exploration choosing the best movement,

for each iteration, independently if this movement

improves or not the value of the actual solution. As

said by Viana (Viana, 1998), in Tabu Search

development, intensifications and diversification

strategies are alternated though the Tabu attribute

analysis. Diversification strategies direct the search

to new regions, aiming to reach whole search space

while intensification strategies reinforce the search

in the neighborhood of a solution historically good.

4 USED MODEL

The model used in this paper is defined in a

complete, undirected graph G=(V,A) where V=

,...v

) is a set of vertices and A=((v

):v

∈

V,i≠j) is an edge set. Vertex v

represents a depot

where a fleet of N

vehicles of homogeneous

capacity Q

is located. All remaining vertices are

customers to be served. A non-negative matrix C =

) is defined on A representing the distance

between the vertices. This problem is symmetric,

since the costs are same in both directions. A non-

negative weight d

, is associated with each vertex to

represent the customer demand at v

The routes must

be designed in such way that each customer is

visited once, only by one vehicle and every route

must start and finish at the depot (Xu and Kelly,

1996; Barbarosoglu and Ozgur, 1999). In this model,

the basic version of the problem is used, often called

the capacitated vehicle routing problem, because the

only constraint is the capacity of the vehicles (Toth

and Vigo, 2002; Laporte, 1992), which means, the

total demand of the route can’t exceed the capacity

of the vehicle.

5 MATHEMATICAL

FORMULATION

The mathematical formulation used in this paper was

based on the one described in Barbarasoglu and

Ozgur (Barbarasoglu and Ozgur, 1999):

Minimize

∑

(1)

Subject to:

∑

for all j (2)

∑

for all I (3)

0=−

∑

for all p,v (4)

d <=

⎟

⎠

⎞

⎜

⎝

⎛

∑∑

for all v (5)

∑

for all v (6)

∑

for all v (7)

A SOLUTION TO THE VEHICLE ROUTING PROBLEM USING TABU SEARCH

∈

for all i,j, and v (8)

where

are binary variables indicating if

arc(vi,vj) is traversed by vehicle v. The objective

function of distance/cost/time is expressed by eq.

(1). Constraints in eqs (2) and (3) together state that

each demand vertex is served by exactly one vehicle.

The eq. (4) guarantees that a vehicle leaves the

demand vertex as soon as it has served the vertex.

Vehicle capacity is expressed by (5) where Q

is the

capacity. Constraints (6) and (7) express that vehicle

availability can’t be exceeded. The sub tour

elimination constraints are given in eq.(8) where Z

can be defined by:

(

)

{

1: −<==

∑∑

∈∈

BjBi

for

}

2};0/{ >=⊆ BVB

6 THE TABU SEARCH

APPLICATION

The architecture proposed was based on Tabu

Search and the following modules compose it:

Initial Solution: This module generates the initial

solution, which will be used in Tabu Search

application, and it’s divided in:

a) Net Generation: This module is responsible for a

net generation. In this application, two types of nets

were created: for 50 and 75 customers and one

depot. The necessary information for net generation

(vertices, demands and coordinates) was obtained in

problems 8 and 9 from Christofides and Eilon

(Christofides and Eilon,1969). These problems

describes two nets of customers and one depot. In

problem 8 there are 50 customers and in problem 9

there are 75. In both nets, the cost of the arcs

represents the Euclidian distance between each pair

of customers. These problems are widely used for

testing purposes by several authors (Gendreau, Hertz

and Laporte, 1994; Christofides, Mingozzi and Toth

1979; Xu and Kelly,1996; Laporte et al, 2000). This

fact is very important for the evaluation of the

results obtained in this paper that are presented in

the end of this paper.

b) Route generation: This module use the net

obtained in the previous stage to generate a set of

routes for the problem. These routes are

implemented following the idea know as “The

Nearest Neighbor” (Tyagi, 1968; Cook et al, 1998).

The initial solution obtained in this module is

represented as a net that connects all vertices

representing the customers and the depot. The

objective value obtained for the problem with 50

customers was 715.04 and for the other problem was

1077.75.

Tabu Search Application Module: In this module the

Tabu Search algorithm is implemented aiming to

minimize the routes costs. The stop criterion adopted

is the maximum number of iteration without an

improvement in the value of the objective function.

The stage of neighborhood generation was

implemented with the usage of three politics to

create the movements: exchanges between routes,

routes construction and delete/insertion of routes.

The first politic implements the vertex exchange and

it was called V1. The second politic implements the

route construction and it was called V2 and third

politic which consist in performing the insertion and

the removal of vertex was called V3. From each

generated neighborhood (V1, V2, V3), a movement

that minimizes the value of the objective function is

chosen. This movement must not be Tabu, but if it is

in the Tabu List, it may be admitted when there is

the possibility of applying the aspiration criterion

function. In this paper the criterion used consists in:

if the Tabu movement value is better than the actual

solution best value then this movement is forgiven

and accepted. If the solution of the actual

neighborhood f(s

*) is the best one ever found, the

variables that keep the best solution obtained

f*(melhsol) and the Tabu List are updated. This

procedure which consists in generating a

neighborhood, choosing the movement that

minimize the objective function, evaluating if it isn’t

Tabu or if it's Tabu but can be accept with the use of

the criterion aspiration function, and optimize the

best solution (if possible) is performed to the three

politics. While the stop criterion isn’t reached, the

search is restarted attributing to the initial solution

the f* value (melhsol).

7 EXPERIMENTS DESCRIPTION

The objective function of this paper, showed in

section 5, intends to minimize the distance

associated to the arcs. The flexibility of the Tabu

Search algorithm makes possible that several

mechanisms of neighborhood generation can be

utilized aiming the diversification of the search for

good solutions. The Tabu Search allows the usage of

intensification and diversification strategies in the

search of good solutions (Glover and Laguna, 1997).

ICINCO 2006 - INTELLIGENT CONTROL SYSTEMS AND OPTIMIZATION

These strategies can be used through the learning of

the model dynamic and parameters NbMax (number

of iterations without improvement in objective

function) and Tabu List size adjustments. In this

work, searching a bigger variety of solutions, the

experiments were done using the three politics of

neighborhood generated alone or in association. Five

types of experiments had been done with different

combinations of neighborhood generation politics.

The politics used in each experiment are shown in

the Table 1.This table shows that the experiments 1,

2 and 3 aim to evaluate the solutions generated

through the isolated execution of each politic. The

experiments 4 and 5 evaluate the generated solutions

through the politic association. After V1, V2 and V3

execution, the politics V2 and V3 had presented the

best results, so they were grouped in the experiment

4. In experiment 5 the three politics were used

together to generate the neighborhood. The objective

of doing the experiments with the politics together is

to analyze if when they are used with association

they can influence themselves and produce a

different neighborhood and possibly better solutions

than when they are used isolated. For each

experiment the Tabu Search algorithm was used

with different size of Tabu List (250, 500, 750,

1000, 1500, 2000, 3000) and several NbMax values

(100, 300, 500, 700, 900). Forty experiments, of

Exp. Politcs Description of Politics

1 V1 Exchange of vertex

2 V2 Route Construction

3 V3 Removal and Insertion of

vertex

4 V2,V3 Route construction, Removal

and Insertion of vertex

5 V1,V2,V3 Exchange; Route construction;

Removal and Insertion of

vertex

each type were generated, totalizing 200

experiments for each net (50 customers and 75

customers). The experiments were made in a

machine with Window XP, AMD Atlhon processor

with 264 Mb of RAM memory.

8 RESULTS

From the experiments done it was evidenced that

with the flexibility of Tabu Search it’s possible to

obtain a great diversity of solutions that points as the

best solutions the ones obtained when the politics

were used together. When the politics were used

together, they diversified the search in the space,

because they generated more possible solutions to be

investigated in the neighborhood. The behaviors of

generated solutions in both cases have a similarity in

the solutions quality. The graphics show the cost of

the best solution obtained to each variation of

NbMax and size of Tabu List used.

Using V1 politic, the NbMax intensification allowed

finding solutions that minimize the initial solution,

independently of Tabu List size. To the 50 customer

net, using NbMax = 900 and Tabu List = 250 the

result (654.88) was close to the result obtained

(652,16) when Tabu List = 2000. To the 75 net

customer, the best result was obtained with NbMax

= 900. The politic V2 used by the experiment 2 had

a constant behavior, not flexible and not influenced

by the variation of the parameters, characterized by a

poor neighborhood and consequently keeping the

same value for all the experiments independently of

the variation in Tabu List and NbMax. This behavior

was observed in both problems. To the 75 net

customers this politic presented the best results

between the isolated politics (949.85). The

experiments that used V3, primarily kept their

constant results, presenting a significant reduction in

a second moment and then keeping it constant until

the end. To 50 customers net the reduction occurred

with NbMax = 500 and Tabu List = 500, to 75

customers net it happened with Nbmax = 750 and

Tabu List = 250. To the 50 customers net, this

politic generated the best result between the politics

that were used isolated (617.57). However, the

results generated by these three isolated politics

weren’t the best. The average solutions obtained in

each politic improved in 12% the value of the initial

solution. In experiment 4, where the politics V2 and

V3 were used together a significant reduction was

obtained for both nets. To the 50 customers net, the

best cost was 582,75 and to the 75 customers net

was 904,11. It showed that the combination of the

politics can generate greater quantities of

movements diversifying the possible solutions.

Although the behavior of these politics were not

influenced by NbMax and Tabu List size variations,

the results obtained were much better that those

obtained through the execution of isolated politics.

In the experiment 5, which was done with the three

politics together, the best solutions were found. It

was 569.39 to the 50 customers net and 888.91 to

the 75 customers net. For each NbMax value

increase, better solutions were found. In both

Table 1: Politics used in experiments.

A SOLUTION TO THE VEHICLE ROUTING PROBLEM USING TABU SEARCH

problems the best solution was obtained with NbMax

= 900. Comparing the experiments 4 and 5 it is

possible to say that the politic V1 was the

responsible for the variations of the solutions.

Although the isolated behavior of this politic was the

worst one, it is possible to conclude that the

presence of this politic, associated with the other two

politics, allowed to find the best solution for both

nets. The reason of experiments 4 and 5 good results

can be determined by the fact that the different

neighborhood generation politics, when used in

association, increase the model flexibility, providing

greater diversification and quantity of generated

neighborhood.

These results were compared with some classical

heuristics: {CW}Clark & Wright algorithm (Clarke

and Wright,1964),{DV}Desrochers and Verhoog

algorithm (Desrochers and Verhoog,1989),

{MJ}Mole and Jamenson heuristic (Mole and

Jamenson, 1976), {GM}Gillet and Miller algorithm

(Gillet and Miller,1974) and with some of the best

results of Tabu Search implementations:{PF} Pureza

and França(Pureza and França,1991), {GHL}

Gendreau, Hertz and Laporte (Gendreau, Hertz and

Laporte, 1994) and {XK}Xu and Kelly (Xu and

Kelly,1996). The results were obtained in

Gendreau, Hertz and Laporte (Gendreau, Hertz and

Laporte, 1994) and Xu and Kelly (Xu and Kelly,

1996). The best results obtained for problems 8 and

9 were generated by Tabu Search implementations.

The comparison of the results is presented in Figure

1 and Figure 2. The results obtained in these

experiments were considered satisfactory since there

is a difference of less than 10% above the others

results. The experiments show that the use of the

diversification, in the neighborhood generation,

allows an improve in the solution quality. The Tabu

Search offers resources that enhance these qualified

solutions. Observing only the papers that use Tabu

Search, it´s easy to see that the implementations

which use more memory resources and others

sophisticated neighborhood produced the best

results. So, the model development in this work, that

uses a simple neighborhood structure, didn´t reach

the best results of the others implementations.

Figure 1: Papers results used in comparison for problem 8.

Figure 2: Papers results used in comparison for problem 9.

9 FINAL CONSIDERATIONS

In this paper, it was proposed a model for solving

the Vehicle Routing Problem, which intended to

generate least-cost routes to attend a set of

customers respecting the constraints defined on the

model. Here, the only constraint considered was the

vehicle capacity. This model was implemented

through the generation of an architecture that uses

Tabu Search for solution generation. Two modules

compose this architecture: initial solution generation

module and Tabu Search module. The distance net

generation was based on the vertices, demands and

coordinates from Christofides and Eilon

(Christofides and Eilon, 1969) problems 8 and 9. To

the initial solution generation, it was applied a

modified version of the algorithm based on Nearest

Neighbor heuristic (Cook et al, 1998; Tyagi, 1968),

contemplating the vehicle capacity constraint. The

Tabu Search perform module utilized the initial

ICINCO 2006 - INTELLIGENT CONTROL SYSTEMS AND OPTIMIZATION

solution to generate a set of routes that optimize the

objective function model, through successive

neighborhood generation. The flexibility of Tabu

Search, allowed three neighborhood generations

mechanisms, intending to diversify the process of

generating routes for the model. The experiments

indicate as better results the ones where all politics

were used in association. The robustness and

flexibility of Tabu Search makes possible to

diversify and improve the process of search in space.

The usage of varied neighborhood generation

politics and the refinement of these politics,

according to the objective model, make possible to

expect that quality solutions can be found.

REFERENCES

Ballou, R.H. 2001 Gerenciamento da cadeia de

Suprimentos – Planejamento, Organização e Logística

Empresarial, 4Ed, Porto Alegre: Bookman

Barbarasogju,G., Ozgur, D. 1999. “A tabu search

algorithm for the vehicle routing problem”, Computers

& Operations Research 26, 255-270

Bodin, L.D, Golden, B.L., Assad, A.A., Ball, M.O. 1983

“Routing and Scheduling of vehicles and crews: The

State of the Art”. Computers and Operations Research

10, 69-211

Clarke, G, Wright, J.W. 1964 “Scheduling of vehicles

from a central depot to a number of delivery points”.

Operations Research 12: 568-581

Christofides, N.; Mingozzi, A.; Toth, P.1979. The Vehicle

Routing Problem.In: Christofides, Nicos.

Combinatorial Optimization UMI, 1979

Christofides, N.,Eilon, S. 1969 “An Algorithm for the

vehicle Dispatching Problem”. Operational Research

Quartely, Vol. 20, N.3

Cook,W.J, Cunningham, W.H, Pulleyblank, W.R,

Schrijver, A.1998. Combinatorial Optimization.

Willey

Cordeau, J-F., Gendreau, M., Laporte, G., Potvin, J.-Y., &

Semet, F. 2002. A guide to vehicle routing heuristics.

Journal of the Operational Research Society, 53,512-

522

Desrochers, M., Verhoog, T.W. 1989. “A Matching Based

savings Algorithm for the Vehicle Routing Problem”

Cahier du GERAD G-89-04. École des Haustes Études

Commerciales de Montréal

Gillet, B.E, Miller, L.R.1974 “A heuristic algorithm for

the vehicle dispatch problem” Operations Research 22,

240-349.

Gendreau, M.; Laporte, G., Potvin, J.-Y. XXXX

“Metaheuristics for te Vehicle Routing Problem” Les

Cashiers du GERAD

Glover,F.1989 “Tabu Search – parte 1”. ORSA Journal on

Computing v.1, n.3.

Glover,F., Laguna,M..1997 Tabu Search. Kluwer

Academic Publishers.

Ho, S.C.,Haugland, D. 2004 “A tabu search heuristic for

the vehicle routing problem with time windows and

split deliveries” Computers & Operations Research

31, 1947-1964

Laporte, G. 1992. “The Vehicle Routing Problem: An

overview of exact and approximate algorithms”.

European Journal of operational Research 59,345-458

Laporte, G., Semet, F. 1998 "Classical Heuristics for the

Vehicle Routing Problem". Les Cahiers du GERAD,

G98-54, Group for Research in Decision Analysis,

Montreal, Canada. 1998

Laporte,G., Gendreau,M., Potvin,J., Semet, F.2000

“Classical and modern heuristics for the vehicle

routing problem” Intl.Trans. in Op. Res 7,285-300

Lentra,J.K, Rinnoy K., G. 1981 “Complexity of Vehicle

Routing and Scheduling Problems” Networks 11,221-

227

Mole,R.H, Jamenson, S.R. 1976 “A sequential route-

building algorithm employing a generalized savings

criterion” Operations Research Quarterly 27,503-511

Nelson, M.D, Nygard, K.E., Griffin, J.H.,Shreve, W.E.

1985 “Implementing Techniques for the vehicle

routing problem” Computers & Operations Research

12,273-283

Osman, I; Laporte,G.1996 Metaheuristics: A bibliography.

Annals of Operations Research 63, 513-628.

Tarantilis, C.D; Ioannou, G; Prastacos, G. 2005

“Advanced vehicle routing algorithms for complex

operations management problems” Journal of Food

Engineerig, 70:455-471.

Thangiah, S.R., Petrovik, P. 1997 Introduction to Genetic

Heuristics and vehicle Routing Problems with

Complex Constraints.In: Woodruff, David, L.

Advances in Computacional and Stochastic

Optimization, Logic programming , and Heuristic

search: Interfaces in Computer Science and Operations

research. Kluwer Academic Publishers.

Toth, P., Vigo, D. 2002 “Models, relaxations and exact

approachs for the capacitated vehicle routing problem”

Discrete Applied Mathematics 123, 487-512

Tyagi, M. 1968 “A Pratical Method for the Truck

Dispatching Problem”. J. of the Operations Research

Society of Japan, 10,76-92

Viana, Valdisio. 1998 Meta-heurísticas e Programação

Paralela em Otimização Combinatória. Fortaleza:

EUFC

Xu, J., Kelly, James P. 1996 “A Network Flow-Based

Tabu Search Heuristic for the Vehicle Routing

Problem” Transportation Science 30, 379-393.

A SOLUTION TO THE VEHICLE ROUTING PROBLEM USING TABU SEARCH