

Document downloaded from: 

 
This paper must be cited as:  

 
The final publication is available at 

 
Copyright 

http://dx.doi.org/10.1016/j.eswa.2011.04.092

http://hdl.handle.net/10251/38498

Elsevier

Braysy, O.; Martínez Molada, E.; Nagata, Y.; Soler Fernández, D. (2011). The mixed
capacitated general routing problem with turn penalties. Expert Systems with Applications.
38(10):12954-12966. doi:10.1016/j.eswa.2011.04.092.


The mixed capacitated general routing problem with

turn penalties

Olli Bräysy1, Eulalia Mart́ınez2, Yuichi Nagata3, David Soler2∗

(1) Agora Innoroad Laboratory, Agora Center, P.O.Box 35,

FI-40014 University of Jyväskylä, Finland

(2) Instituto Universitario de Matemática Pura y Aplicada. Universidad Politécnica de Valencia

Camino de Vera s/n, 46022, Valencia, Spain

(3) Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology,

4259 Nagatsuta Midori-ku Yokohama, Kanagawa 226-8502, Japan

Abstract

In this paper we deal with the Mixed Capacitated General Routing Problem

with Turn Penalties. This problem generalizes many important arc and node

routing problems, and it takes into account turn penalties and forbidden turns,

which are crucial in many real-life applications, such as mail delivery, waste

collection and street maintenance operations. Through a polynomial transfor-

mation of the considered problem into a Generalized Vehicle Routing Problem,

we suggest a new approach for solving this new problem by transforming it into

an Asymmetric Capacitated Vehicle Routing Problem. In this way, we can solve

the new problem both optimally and heuristically using existing algorithms. A

powerful memetic algorithm and a set of 336 new benchmark instances are also

∗Corresponding author: Address: Instituto Universitario de Matemática Pura y Aplicada. Univer-

sidad Politécnica de Valencia. Camino de Vera s/n, 46022, Valencia, Spain. Tel:+34 963877007-76667;

fax:+34 963877669. E-mail addresses: olli.m.p.braysy@jyu.fi (O. Bräysy), eumarti@mat.upv.es (E.

Mart́ınez), nagata@fe.dis.titech.ac.jp (Y. Nagata), dsoler@mat.upv.es (D. Soler).

1


suggested. The experimental results show that the average deviation of the sug-

gested solution method is less than 0.05 per cent with respect to optimum.

Keywords: Vehicle routing, capacitated general routing problem, turn penalties,

transformation.

1 Introduction

In many real-life vehicle routing problems it is important to consider the risk and time

associated with turns, i.e., the cost of the turn. Moreover, some turns, especially U-

turns, can be forbidden. This last implies that a vehicle route made with a classical

graph route generator may be illegal if it does not respect the traffic signals. For

example, Figure 1 shows a traffic signal located in an arterial avenue from Valencia

(Spain). It indicates that the next two left turns are forbidden and the way to dodge

them. These forbidden turns cannot be taken into account if we model the city map

with a classical graph.

Considering turn penalties and forbidden turns is particularly important in down-

town areas and for large-size vehicles. But also turn penalties are important in order

to save time in tours on foot. From Figure 2 it is easy to see that going on foot,

right turn a → b can be considered with zero cost, while turn a → c is much more
time-consuming, because it implies to cross two streets, with up to two traffic lights.

Usually the real-life vehicle routing software are based on separate modules for

shortest path calculation and vehicle route optimization. The latter is based on given

time and distance matrices, calculated typically in the beginning with the shortest

path procedure. In this context, the distance and time calculation are based on fixed

and known stopping points (usually addresses) for the vehicles and the possible turn

penalties and forbidden turns are taken into account during the shortest path calcu-

lation. However, in practice, there are several applications where the exact stopping

points are not known a priori and are part of the optimization problem, such as mail

collection and delivery, waste collection and street maintenance operations. In these

cases, including turn penalties and forbidden turns in the vehicle routing model is very

important.

2


Figure 1. Traffic signal indicating two forbidden left turns.

Figure 2. A street crossing.

So far research on extended vehicle routing models with turn penalties and forbidden

turns has been scarce. For previous research, see Benavent and Soler (1999), Clossey

et al (2001), Corberán et al (2002) and Soler et al (2008), that generalize several well-

known single vehicle routing problems to the existence of turn penalties. They provide

theoretical results about complexity and resolution and/or computational results on

these extensions. The last cited work studies the most general problem, the Mixed

General Routing Problem (MGRP) with turn penalties, that includes all the cases

studied in the previous cited papers. MGRP consists of finding a minimal cost closed

walk on the links of a mixed graph G which traverses a given subset of “required” links

and a given subset of “required” vertices.

With respect to multivehicle routing problems, early papers that considered turn

penalties focused on real-life applications and heuristic solution methods. See for exam-

ple Bodin et al (1989) and Roy and Rousseau (1989). Later, turn penalties have been

considered in the context of the Mixed Capacitated Arc Routing Problem (MCARP),

see for example Bautista and Pereira (2004) and Belenguer et al (2006). The MCARP

is an arc routing problem, in which a fleet of vehicles (with a known capacity) is based

3


on a specified vertex (the depot) and must service a subset of the links of a mixed

graph, with minimum total cost and such that the load assigned to each vehicle does

not exceed its capacity and each link is serviced by exactly one vehicle.

Bautista et al (2008) present two ant colony metaheuristics for a real urban waste

collection problem. This real problem is modeled as a particular case of the MCARP

with turn penalties, in which they only consider two kind of turns: forbidden or allowed

with zero cost. Finally, Perrier et al (2008) heuristically solve a real vehicle routing

problem in the context of snow plowing operations that also takes into account the

existence of forbidden turns.

The multivehicle extension (with capacity constraints) of the MGRP is called the

Mixed Capacitated General Routing Problem (MCGRP). Due to its complexity, there

are only few works on MCGRP, see e.g. Jansen (1993) who studied the undirected case

and Pandit and Muralidharan (1995). However, particular cases of the MCGRP, such

as the capacitated arc routing problem (CARP) and the capacitated vehicle routing

problem (CVRP) have attracted a huge amount of research.

In this paper we present a generalization of the MCGRP that considers turn penal-

ties and forbidden turns. The objective is to minimize the sum of the costs of the

traversed arcs and edges together with the penalties associated with the turns made.

We call the new problem the Mixed Capacitated General Routing Problem with Turn

Penalties (MCGRPTP).

As far as we know, this is the first time that MCGRPTP is presented in the liter-

ature. Moreover, there is no previous research on multivehicle node routing problems

with turn penalties. In this paper we also present for the first time an approach for

solving capacitated routing problems with turn penalties, through suggesting a new

polynomial transformation from the MCGRPTP to an asymmetric CVRP (ACVRP).

To be more precise, the transformation is done in two steps: we first transform the

MCGRPTP into a generalized VRP (GVRP), using a new approach suggested in this

paper. The key idea of GVRP, compared to CVRP is that in GVRP each customer has

several alternative service locations, and only one of them has to be selected for service.

For more details on GVRP, see e.g. Ghiani and Improta (2000). In the second step we

transform the GVRP into an ACVRP, using a model presented in Soler et al (2009).

4


Finally, we present a set of new benchmark problems and a very powerful memetic

algorithm for the ACVRP, based on a previous study by Nagata and Bräysy (2009).

The experimental results show an average deviation equal to 0.05% for instances with

known optimal solution and that large-size problems can be solved with the suggested

MA.

The suggested transformation makes it possible to use also any other powerful

algorithm developed for ACVRP, see e.g. Fischetti et al (1994), Vigo (1996) or the

more recent heuristic by De Franceschi et al (2006).

The remainder of this paper is organized as follows. Section 2 introduces some def-

initions and notations in order to formally define and solve the MCGRPTP. In Section

3, through two transformations, we prove that the MCGRPTP can be transformed

in polynomial time into a Generalized Vehicle Routing Problem (GVRP). It is known

(Soler et al (2009)) that the GVRP can be transformed into an ACVRP, so in Section

4 we show computational results for several sets of ACVRP benchmarks. Finally, in

Section 5 we present our conclusions.

2 Definitions and notations

First, to our aim, we formally define two known problems cited before: the Asymmetric

Capacitated Vehicle Routing Problem (ACVRP) and the Generalized Vehicle Routing

Problem (GVRP). The second one is an extension of the ACVRP, introduced by Ghiani

and Improta (2000), that can model several real-world situations and that will be the

“cornerstone” to solve our problem:

The ACVRP is defined as follows:

Let G = (V, A) be a complete digraph, V = {vi}ni=0 being its set of vertices, where
v0 is the depot vertex. Each vertex vi with i > 0 has an associated demand di > 0 and

each arc (vi, vj) ∈ A has an associated cost ci,j ≥ 0. Moreover, a fleet of k vehicles with
the same capacity W is available at the depot.

Find a set of k shortest routes, each starting and ending at the depot, such that each

vertex vi (∀ i ∈ {1, ..., n}) must be visited by one and only one vehicle and the sum of
the demands of the vertices visited by each vehicle does not exceed its capacity W .

5


As in other papers cited in the introduction, in all the capacitated routing problems

discussed here, we will consider k to be equal to the minimum number of vehicles needed

to serve all demands.

The GVRP is defined as follows:

Let G = (V, A) be a directed graph where the vertex set V is partitioned into m + 1

nonempty subsets S0, S1, ..., Sm such that S0 has only one vertex v0 (the depot), Sh

(h = 1, ..., m) represents l(h) possible locations of the same vertex which has associated

a positive demand dh, and each arc (vi, vj) ∈ A has associated a cost ci,j ≥ 0. Moreover,
a fleet of k homogeneous vehicles having the same capacity W is available at the depot.

Find a set of k shortest routes, each starting and ending at the depot, such that each

subset Sh (h = 1, ..., m) is visited exactly once and the sum of the demands of every

route does not exceed the capacity W of the vehicle.

Next, we need to show some concepts and notations that have been used in previous

works on turn penalties:

Given a mixed graph G = (V, E, A), each pair of links a = (u, v), b = (v, w) ∈ E ∪A
has an associated turn at v, based on going from a to b, denoted as [ab]. Moreover,

if a, b ∈ E, the same pair has another associated turn at v, based on going from b to
a, denoted as [ba]. Each edge e incident with v has an associated U-turn at v that, if

necessary, will be denoted by [eve]. Each link in G has associated a nonnegative cost

and each allowed turn in G has associated a nonnegative penalty.

Given a = (u, v), b = (s, t) ∈ E ∪A, a v-s feasible chain from a to b is an alternating
sequence of links and allowed turns {a1, [a1a2], a2, . . . , [ar−1ar], ar, [arb]}, where a1 = a.
The cost of a feasible chain is defined as the sum of the costs of the arcs it traverses

plus the sum of the penalties of the turns it makes. A v-s feasible chain from a to b is

closed if a = b and s 6= v.
Given a = (u, v), b = (s, t) ∈ E ∪ A, a shortest (minimum cost) v-s feasible chain

from a to b will be denoted by s.f.c.(va, sb).

Note that a feasible chain is defined such that it begins at a link and ends at a turn.

This is very important in the context of forbidden or penalized turns. In classical

routing problems, if we have to go from a vertex u to a vertex v and then to a vertex

w, we only have to connect the shortest path from u to v with the shortest path from v

6


to w. But even if these shortest paths have been constructed taking into account turn

conditions, the connection of both paths at v can give rise to an unavoidable forbidden

turn (U-turn for example). In our case, the connection between two feasible chains at

a vertex v is possible only if the first one ends at a turn [(t, v)(v, s)] and the second

one begins at the link (v, s), which avoids the existence of forbidden turns. Therefore,

we cannot use paths between vertices as in the classical way, and this increases the

difficulty of modeling how to serve demands at vertices, specially if these vertices have

undesirable turns.

With these previous concepts we can formally define the problem that we study

in this paper. The Mixed Capacitated General Routing Problem with Turn Penalties

(MCGRPTP) is defined as follows:

Let G = (V, E, A) be a mixed graph where each link (i, j) ∈ E ∪A has an associated
cost cij ≥ 0 and each turn [ab] has an associated penalty p[ab] ≥ 0 ( p[ab] = +∞ if turn
[ab] is forbidden). One of the vertices, say v0, represents the depot where there are k

vehicles of an identical capacity W > 0 and in it all the turns are allowed with zero

penalty. Let R ⊆ E ∪ A be a set of required links such that each (i, j) ∈ R has an
associated positive demand qij ≤ W , and let VR ⊆ V −{v0} be a set of required vertices
such that each v ∈ VR has an associated positive demand qv ≤ W .

Find k closed feasible chains in G, one for each vehicle, that minimize the total

cost and such that each chain passes through the depot, each demand is served by only

one vehicle and the total demand served by each vehicle does not exceed its capacity W .

Note that allowing all the turns with zero penalties at the depot is due to the

fact that in real-world situations, the depot normally represents a warehouse from

which the vehicles begin their journey and to which they return. It makes no sense

considering forbidden/penalty turns in the warehouse as the truck leaves from depot

independently of the route the truck made before. Moreover, these warehouses are

usually placed outside the cities with good road communications and of easy access.

Hereinafter and as in similar papers, each non-required edge will be replaced by two

arcs of the same cost and opposite direction; then we assume that all edges in the graph

are required (ER = E, with R = ER ∪ AR). Finally, for simplicity, we will not write

7


the middle turns of a feasible chain. For example, the feasible chain {a, [ab], b, [b, c]}
will be written as {a, b, [b, c]}.

In the particular case of the MCGRPTP in which VR = ∅, we have the MCARP with
turn penalties, and in the particular case of the MCGRPTP in which k = 1 we have the

MGRP with turn penalties. Therefore, the problem presented here generalizes both

the single vehicle and the multivehicle routing problems with turn penalties studied in

the literature.

3 Solving the MCGRPTP

To solve the MCGRPTP, we will first transform it into a GVRP, which in turn can be

transformed into an ACVRP.

3.1 Transformation of the MCGRPTP into a GVRP

Let G = (V, E, A) be a mixed graph where a MCGRPTP is defined, E ∪ AR being the
required link set and VR the required vertex set. Due to the fact that in the GVRP

the demand is at the vertices, we will transform graph G in which we have defined

the MCGRPTP into a directed graph G∗ = (V ∗, A∗) such that the vertices in G∗ are

related with the required links and required vertices in G.

To this aim, we first construct an intermediate directed graph G′ = (V ′, A′) from

G as follows:

First, each required edge is replaced in G by two opposite required arcs, both with

the edge cost and the edge demand.

Second, subset VR is partitioned into two subsets, VR1 and VR2 , such that ver-

tices containing all allowed zero-penalty turns belong to VR1 , and vertices containing

forbidden or positive-penalty turns belong to VR2 .

For each v ∈ VR1 ∪ {v0}, replace vertex v in G by two vertices ve and vl, so that
ve has only entering arcs (the arcs entering at v) and vl has only leaving arcs (the arcs

leaving from v). Add a required arc av = (v
e, vl) to G such that all turns at ve and

vl are allowed with zero penalty and the demand of this arc in G′ is the one of the

required vertex v in G (the demand corresponding to the arc from the depot vertex is

8


obviously zero). Note that traversing arc av in G
′ is then equivalent to passing through

vertex v in the original graph G.

For each v ∈ VR2 do:

- Replace vertex v in G by the same number of vertices vij as those of allowed

turns [aibj] at v, so that each of these copies has only one entering arc (ai) and

one leaving arc (bj), with its corresponding allowed turn. Note that if ai is an

entering arc at v, G′ will contain at least as many copies of the entering arc ai as

there are allowed turns involving ai at v. The same applies to the leaving arc bj

from v.

- Then, replace each vertex vij by two vertices, v
e
ij and v

l
ij, and add a “required”

arc avij = (v
e
ij, v

l
ij) between them with cost zero, such that p[aiavij ] = p[aibj ] and

p[avij bj ] = 0, i.e. the penalty that was in the turn at vij is moved to vertex v
e
ij,

and all these arcs will have the same demand, the one of the required vertex v.

Note that traversing only one of these required arcs avij in G
′ involves passing

through vertex v in G.

Note that in the last paragraph we have written required in quotes because for each

v ∈ VR2 , only one of the generated arcs must be served.
After this transformation we have a directed graph G′ = (V ′, A′) such that the

subset A′R comes from the required arcs, required edges and required vertices in G.

A′R will give rise to a partitioned set of vertices V
∗ in the graph G∗ in which we will

define the GVRP. Each arc between two of these vertices that do not form part of the

same subset, will have associated the cost of the shortest feasible chain between the

two corresponding links in G′.

From G′ we then construct the graph G∗ = (V ∗, A∗) as follows:

- For each arc av ∈ A′R with v ∈ VR1 ∪ {v0}, associate a vertex set Sv = {xav} in
G∗, with its corresponding demand in xav .

- For each v ∈ VR2 , associate a vertex set Sv in G∗ with as many vertices xavij as
arcs avij are in A

′
R, all of them with the same corresponding demand.

9


- For each arc a ∈ A′R that comes from a required arc in G, associate a vertex set
Sa in G

∗ with as many copies of a vertex xa as copies of arc a appear in G
′, all

of them with the same corresponding demand.

- For each pair of opposite required arcs e1, e2 ∈ A′R that come from a required
edge e in G, associate a vertex set Se in G

∗ with as many copies of vertices xe1

and xe2 as copies of arcs e1 and e2 respectively appear in G
′, all of them with the

same corresponding demand.

- For each pair of vertices xa, xb ∈ V ∗ with xa ∈ Si, xb ∈ Sj, i 6= j being a = (u, v)
and b = (s, t), add arcs (xa, xb) and (xb, xa) to A

∗, with the cost of the s.f.c.(va, sb)

and of the s.f.c.(tb, ua) respectively in G′ (if they exist).

- There is no arc between vertices belonging to the same Si.

Given an MCGRPTP in G, we define a GVRP in G∗ where the vertex set V ∗ is

partitioned into the following subsets: Sv for all v ∈ VR1 ∪ {v0} (hereinafter we will
denote the subset corresponding to the depot by S0 = {vD}), Sv for all v ∈ VR2 , Sa for
all a ∈ AR and Se for all e ∈ ER.

Let us see an example of the construction of the auxiliary graph G∗. Consider

the mixed graph given in Figure 3 corresponding to an MCGRPTP in which vertex 1

represents the depot, there are two vehicles both with capacity 55, and there are three

required arcs a, b and c, with demands 25, 25 and 20 respectively, a required edge e

with demand 20 and a required vertex 5 with demand 10. Then the total demand in

the graph is 100 units. Link costs and demands appear in Figure 3 with different size

(demands appear in bold and small size).

We will suppose in this graph that all U-turns are forbidden except at vertex 1 (the

depot) at which all turns are allowed with penalty zero, and in the rest of the vertices,

right turns (according to the drawing of the graph) have penalty 1, left turns have

penalty 3 except for the turn from arc b to arc (2, 1) that is considered forbidden, and

going straight ahead, as it occurs in the turn from arc a to edge e, has penalty zero.

10


Figure 3. Graph G with AR = {a, b, c}, ER = {e} and VR = {5}.

Starting from the information given by the initial graph G = (V, E, A), where

AR = {(3, 4), (4, 2), ((5, 6)}, ER = {(4, 6)}, VR = {5} and the depot is vertex 1, we
construct the intermediate graph G′ (see Figure 4):

First, we replace the required edge e = (4, 6) with demand qe = 20 by two opposite

arcs e1, e2 with the same cost 5 and the same demand 20.

Second, we replace vertex 1 by the sequence {1e, a1, 1l}, a1 with cost zero.
Finally, we transform vertex 5, which belongs to VR2 (here VR1 = ∅), into four arcs,

as many as allowed turns in it, all of them with cost zero and demand 10.

Figure 4. Intermediate graph G′.

From the intermediate graph G′ = (V ′, A′) we can already construct the directed

graph G∗ = (V ∗, A∗).

The vertex set V ∗ is given by the following partition:

11


- A subset S0 with only one vertex xD representing the depot and corresponding

to the required arc a1.

- Subsets Sa and Sb, each one with only one vertex xa and xb respectively, for the

required arcs a = (3, 4) and b = (4, 2), both with demand 25, and subset Sc with

two vertices xc1 and xc2 , both with demands 20, for the required arc c = (5, 6)

which have two copies in G′.

- Subset Se with two vertices xe1 and xe2 both with demand 20, for the required

edge e = (4, 6).

- Subset S5 with four vertices x5f h , x5f c , x5dc and x5gh all of them with demand 10,

for the required vertex 5 in VR2 .

Figure 5 shows graph G∗ in which, for simplicity, each pair of arcs (xr, xt) and

(xt, xr) with xr ∈ Si, xt ∈ Sj and i 6= j has been drawn as a line with two arrow heads,
one at each end, and the arc costs (normally different for each direction) have been

omitted.

Figure 5. Directed graph G∗ associated with G.

Theorem 1 An MCGRPTP defined in G can be transformed in polynomial time into

the corresponding GVRP defined in G∗.

12


Proof. By the construction of G′, given B = {Ti}ki=1 a set of k feasible closed
chains in G corresponding to a solution to the MCGRPTP, we can associate with B

a set B′ = {T ′i}ki=1 of k feasible closed chains in G′ such that for all i ∈ {1, . . . , k} we
have:

- T ′i traverses arc a1 (corresponding to the depot node 1 in G).

- Ti passes through a vertex v ∈ VR1 iff T ′i traverses arc av in G′.

- Ti passes through a vertex v ∈ VR2 iff T ′i traverses an arc avij .

- Ti traverses arc a ∈ AR iff T ′i traverses a copy of arc a in G′.

- Ti traverses edge e ∈ E iff T ′i traverses a copy of arc e1 or a copy of arc e2 in G′.

- T ′i has the same cost as Ti.

- Moreover, we will suppose that if Ti satisfies demand at v ∈ V1 (v ∈ V2) (a ∈ AR)
(e ∈ E), then T ′i satisfies the demand located at av (one and only one arc avij )
(one and only one copy of arc a in G′) (one and only one copy of e1 or e2 in G

′).

Summarizing, for all i ∈ {1, . . . , k} T ′i is a feasible closed chain in G′ that traverses
a1, satisfies the same demands as Ti and has the same cost as Ti.

Once we have constructed B′ from B, for each i ∈ {1, . . . , k}, from T ′i we construct
a cycle CBi in G

∗ as follows:

Suppose that T ′i satisfies, in this chronological order, the demands qj1 , qj2 , . . . , qjmi .

Then CBi is a cycle in G
∗ that visits, in this order, the sets of vertices S0, Sj1 , Sj2 , . . . ,

Sjmi , S0, and for all t ∈ {1, . . . , mi}, Ci visits only the vertex at St coming from the arc
in G′ at which demand has been satisfied by T ′i .

It is evident that the set of cycles LB = {CBi }ki=1 is a solution to the GVRP in
G∗ its cost c∗(LB) being less than or equal to c(B), this last due to the fact that the

cost of the route segment of one feasible closed chain T ′i in G
′ between two consecutive

serviced arcs (including the depot arc a1) is greater than or equal to the cost of the

shortest feasible chain in G′ between them (from the first serviced one to the second

serviced one), while the cost of the arc in CBi in G
∗ from the vertex coming from a

13


serviced arc in G′ to the vertex coming from the next serviced arc in G′ is equal to the

one of the shortest feasible chain in G′ between them.

On the other hand, let L = {Ci}ki=1 be a set of k cycles corresponding to a solution
to the GVRP in G∗. For each i ∈ {1, . . . , k}, from Ci we construct a feasible closed
chain T ′Li in G

′ as follows:

Let (xa, xb) be a generic arc of Ci, a = (u, v) and b = (w, r) being the arcs in A
′
R

from which vertices xa and xb come, respectively. Arc (xa, xb) will give rise in T
′L
i to

the s.f.c.(va, wb), and such that T ′Li assumes the demand at a (the same as the one in

xa) and b (the same as the one in xb). Note that in this way, T
′L
i has the same cost as

Ci and satisfies the same demands as Ci.

From the set B′L = {T ′Li }ki=1 of k feasible closed chains in G′, we construct now a
set BL = {T Li }ki=1 of k feasible closed chains in G as follows:

- “Contract” each sequence in T ′Li of the form (u, v
e)(ve, vl)(vl, w) with av = (v

e, vl)

if v ∈ VR1 ∪ {1} by (u, v)(v, w) in T Li .

- “Contract” each sequence in T ′Li of the form (u, v
e
ij)(v

e
ij, v

l
ij)(v

l
ij, w) with avij =

(veij, v
l
ij) if v ∈ VR2 by (u, v)(v, w) in T Li .

- If T ′Li traverses a copy of arc e1 or a copy of arc e2 in G
′, with e ∈ E, replace this

copy in T Li by edge e.

- Any other link or turn in T ′Li is replaced by itself in T
L
i .

- Demand at v ∈ V1 (v ∈ V2) (a ∈ AR) (e ∈ E) is assigned to route T Li iff T ′Li
satisfies the demand located at av (one and only one arc avij ) (one and only one

copy of arc a in G′) (one and only one copy of e1 or e2 in G
′).

It is evident that BL = {T Li }ki=1 is a solution to the MCGRPTP in G with c(BL) =
c∗(L), this last due to the fact that for all i, c(T Li ) = c

′(T ′Li ).

Let then Lopt be an optimal GVRP solution in G∗ and let BL
opt

be the MCGRPTP

solution in G obtained from Lopt as described above. For each MCGRPTP solution B

in G we have:

c(B) ≥ c∗(LB) ≥ c∗(Lopt) = c(BLopt ) (1)
Therefore, BL

opt
is an optimal MCGRPTP in G.

14


3.2 Solving the GVRP in G∗ through an ACVRP

Once we have transformed our MCGRPTP into a GVRP defined in G∗ = (V ∗, A∗),

from G∗ we construct a digraph Ĝ = (V̂ , Â) as follows:

- V̂ = V ∗.

- For each Si with i ∈ {0, 1, . . . , m} and |Si| > 1, order its vertices consecutively
in an arbitrary way {vi1, . . . , vil(i)}; then, for j = 1, . . . , l(i) − 1, define the cost of
arc (vij, v

i
j+1) ∈ Â as zero; also define the cost of arc (vil(i), vi1) as zero.

- For every vij ∈ Si and every w /∈ Si define the cost of arc (vij, w) in Â equal
to the cost in G∗ of the arc (vij+1, w) ((v

i
1, w) if j = l(i)) plus a fixed positive

large quantity M if |Si| > 1, and equal to the cost in G∗ of arc (vij, w) plus M if
|Si| = 1.

- Any other arc in Â has infinite cost.

- Assign positive demands having sum equal to di to the vertices in Si ∀ i, except
for the depot subset.

As it was proved by Soler et al (2009), the GVRP can be transformed into an

ACVRP. Following their proof, we can see that to solve the GVRP in G∗ we can solve

the ACVRP in the digraph Ĝ, and to obtain a GVRP solution from an ACVRP one, we

just have to identify each path in the ACVRP solution (vij, v
i
j+1, . . . , v

i
l(i), v

i
1, . . . , v

i
j−1, w)

w /∈ Si (w can be the depot) if j 6= 1 and |Si| > 1, or (vi1, . . . , vil(i), w) if j = 1 and
|Si| > 1, or (vij, w) if |Si| = 1 (in this last case vij can be the depot), with the arc
(vij, w) in G

∗. An optimal ACVRP solution Hopt in Ĝ, will give rise to an optimal

GVRP solution Lopt in G
∗ with cost c∗(Lopt) = ĉ(Hopt) − M (m + k).

Going on with our example, from the graph G∗ where the GVRP is defined (Figure

5) we define the ACVRP in the digraph Ĝ (see Figure 6) where, for simplicity again,

the pairs of arcs (xr, xt) and (xt, xr) with xr ∈ Si, xt ∈ Sj and i 6= j have been drawn
as lines with two arrow heads, one at each end, and the arc costs (normally different

for each direction) have been omitted. Figure 6 shows the cost zero “intraset” arcs

and the demand assigned to each vertex. For example, vertex 5, belonging to VR2 and

15


with demand 10 in G, has associated the set S5 in G
∗ with four vertices that in Ĝ have

demands 2, 2, 3 and 3, respectively.

Figure 6. Directed graph Ĝ associated with G∗.

Figure 7 shows the optimal solution H to the ACVRP in Ĝ given in Figure 6

corresponding to our example; it consists of two cycles:

- H1 = (xD, xa, xb, xD) with associated cost 7 + 7 + 22 + 3M = 36 + 3M (these arc

costs will be deduced above when explaining the solution to the MCGRPTP in G) and

the demand served by this cycle is qa + qb = 25 + 25 = 50.

- H2 = (xD, x5dc, x5gh, x5f h, x5f c, xc2 , xc1 , xe2 , xe1 , xD) with associated cost:

15 + 0 + 0 + 0 + 0 + 0 + 4 + 0 + 12 + 4M = 31 + 4M and the demand serviced by

this cycle is qc + qe + qv5 = 20 + 20 + 2 + 2 + 3 + 3 = 50. Note that the total cost

ĉ(H) = 67 + 7M = 36 + 31 + (5 + 2)M since m = 5 is the number of vertex subsets in

G∗ (the depot not included) and k = 2 is the number of cycles in the solution.

This optimal solution H in Ĝ gives rise to the optimal solution L in G∗ shown in

Figure 8, with total cost c∗(L) = ĉ(H) − 7M = 67, and that consists of two cycles:
C1 = (xD, xa, xb, xD) with cost 36 and C2 = (xD, x5dc, xc2 , xe2 , xD) with cost 31.

16


Figure 7. Optimal solution to the ACVRP in Ĝ.

Figure 8. Optimal solution to the GVRP in G∗.

Let us find the optimal solution to the MCGRPTP in G given by these cycles,

according to the proof of Theorem 1.

From C1 = (xD, xa, xb, xD) we have:

- (xD, xa) corresponds to the s.f.c.(1
la1 , 3a) in G′: (1e, 1l)(1l, 3)[(1l, 3), (3, 4)] with

cost 0+0+4+3=7 (in the addition, normal-font numbers indicate arc costs while

bold numbers indicate turn penalties). See Figure 4 to follow the chains in G′.

- (xa, xb) corresponds to the s.f.c.(4
a, 4b) in G′: (3, 4)[(3, 4), (4, 2)] with cost 4+3=7.

17


- (xb, xD) corresponds to the s.f.c.(2
b, 1e

a1 ) in G′: (4, 2)(2, 5ef h)(5
e
f h5

l
f h)(5

l
f h, 4)(4, 1

e)

[(4, 1e), (1e, 1l)] with cost 4+1+4+1+0+0+5+1+6+0=22.

Therefore, joining the chains we have the following feasible closed chain in G′

T ′1 =
{
(1e, 1l), (1l, 3), (3, 4), (4, 2), (2, 5ef h), (5

e
f h, 5

l
f h), (5

l
f h, 4), (4, 1

e), [(4, 1e), (1e, 1l)]
}

with cost 36, and assuming the demands of arcs (3, 4) and (4, 2) (a and b), with a total

demand of 50.

From T ′1, following again with the proof of Theorem 1, we construct the feasible

closed chain with the same cost as T ′1 in the original graph G,

T1 = {(1, 3), (3, 4), (4, 2), (2, 5)(5, 4), (4, 1), [(4, 1), (1, 3)]} that also assumes the de-
mands of arcs a and b (25+25).

Similarly, from C2 = (xD, x5dc, xc2 , xe2 , xD) we have:

- (xD, x5dc) corresponds to the s.f.c.(1
la1 , 5

ea5dc
dc ) in G

′:

(1e, 1l)(1l, 4)(4, 5edc)[(4, 5
e
dc), (5

e
dc, 5

l
dc)] with cost 0+0+6+3+5+1=15.

- (x5dc, xc2 ) corresponds to the s.f.c.(5
la5dc
dc , 5

lc2
dc ) in G

′: (5edc, 5
l
dc)[(5

e
dc, 5

l
dc), (5

l
dc, 6)]

with cost 0+0=0.

- (xc2 , xe2 ) corresponds to the s.f.c.(6
c2 , 6e2 ) in G′: (5ldc, 6)[(5

l
dc, 6), (6, 4)] with cost

3+1=4.

- (xe2 , xD) corresponds to the s.f.c.(4
e2 , 1e

a1
) in G′: (6, 4)(4, 1e)[(4, 1e), (1e, 1l)] with

cost 5+1+6+0=12.

Therefore, joining the chains we have the following feasible tour in G′,

T ′2 =
{
(1e, 1l), (1l, 4), (4, 5edc), (5

e
dc, 5

l
dc), (5

l
dc, 6), (6, 4), (4, 1

e), [(4, 1e), (1e, 1l)]
}

with

cost 31, and assuming the demands of arcs (5edc, 5
l
dc), (5

l
dc, 6) and (6, 4), with a total

demand of 50.

From T ′2, we construct the feasible closed chain with the same cost as T
′
2 in G,

T2 = {(1, 4)(4, 5)(5, 6)(6, 4)(4, 1)[(4, 1), (1, 4)]}, that assumes the demands of vertex
5 belonging to VR2 , of arc (5, 6) and of edge (4, 6) (10+20+20).

Figure 9 shows the optimal solution to the MCGRPTP in the original graph G: T1

with solid bold line and T2 with broken bold line.

18


Figure 9. Optimal solution to the MCGRPTP in G.

4 Computational experiments

The aim of this section is to show that the transformation presented here can be

considered as a good tool to solve MCGRPTP instances, at least heuristically due

to the complexity of the problem. That is, if there exists any competitive procedure

to solve the ACVRP, we can solve MCGRPTP instances within a reasonable running

time. To do this, we first present a powerful heuristic algorithm for the ACVRP based

on the memetic algorithm (MA) for the (symmetric) CVRP proposed by Nagata and

Bräysy (2009). MA is a population-based heuristic search approach that combines

evolutionary algorithm with local search algorithm. Although there are other heuristic

approaches for the ACVRP, as those cited in the introduction, we selected the above

mentioned MA because it is shown to be currently the most powerful heuristic method

for the CVRP, and it can be applied to the ACVRP by a straightforward extension.

Here the suggested MA has been tested on a set of 32 ACVRP instances by Pessoa et

al (2007). We have also applied the MA to a set of 126 single vehicle instances by Soler

et al (2008) because the optimal solutions are known to these instances. Finally, the

MA has been applied to a set of 336 ACVRP instances with up to 623 vertices that

come from the transformation of MCGRPTP instances.

4.1 The MA for the ACVRP

The main feature of the MA by Nagata and Bräysy (2009) is that the edge assem-

bly crossover (EAX) operator generates offspring solutions by combining edges of two

19


solutions selected as parents from the population. The generated offspring solutions

may violate the capacity constraint. In this case, a subsequent local search-based re-

pair procedure is used to restore the feasibility of the temporarily infeasible solutions.

Moreover, a simple local search is applied to the obtained feasible solutions according

to a standard MA procedure.

Note that the EAX was adapted to the ACVRP by defining it on the directed graph

whereas the original EAX for the symmetric CVRP was defined on the undirected

graph. The MA by Nagata and Bräysy minimized the total travel distance without

putting any constraint on the number of vehicles and the number of vehicle was also a

decision variable. However, according to the literature and therefore to the definition

of the ACVRP given here, in the ACVRP the travel distance must be minimized with

a given number of vehicles. So we have made a new version of the MA that minimizes

the total travel distance for a fixed number of vehicles. The suggested MA has been

implemented in C++ and has been executed on a ADM Opteron 2.4 GHz computer.

For each instance, the MA has been executed five times.

4.2 Results for the ACVRP instances

We first analyze the efficiency of the two MA versions (fixed or variable number of

vehicles) on a set of 32 ACVRP instances with known upper bounds that appear in the

work by Pessoa et al (2007), which are variants of the 8 benchmark ACVRP instances

given in http://or.ingce.unibo.it/research/cvrp-and-dcvrp. As far as we know, the work

by Pessoa et al is the most recent paper with computational results on the ACVRP.

The results for the 32 ACVRP instances without constraint on the number of vehi-

cles are presented in Table 1. The columns in the table list instance names (Instance),

the capacity of the vehicles (C), the number of vehicles and the total travel distance

of the best-known upper bound solutions (k and U B), the number of vehicles and the

total travel distance of the best result in five runs (best-k and best-d.) with our MA,

the average number of vehicles and the average total travel distance in these five runs

(ave-k and ave-d.), and the average computation time in seconds for a run (Time).

20


Table 1. Computational results on known ACVRP instances.

Instance C k Best U B Best − k Best − d Ave − k Ave − d T ime
a034-14f 150 14 4046 14 4046 14.0 4046.0 1.37

a036-18f 150 18 5296 19 5224 19.0 5224.0 1.21

a039-20f 150 20 5903 20 5903 20.0 5903.0 1.47

a045-18f 150 18 6399 19 5564 19.0 5568.0 4.59

a048-16f 150 16 4955 16 4955 16.6 4960.0 6.35

a056-17f 150 17 4998 17 4998 17.6 5020.0 8.82

a065-19f 150 19 6014 20 5862 20.0 5862.0 12.52

a071-17f 150 17 5006 17 5006 17.0 5014.0 13.86

a034-08f 250 8 2672 8 2672 8.0 2672.0 1.94

a036-10f 250 10 3338 11 3294 11.0 3294.0 1.67

a039-12f 250 12 3705 12 3705 12.0 3705.0 2.63

a045-11f 250 11 3544 11 3544 11.2 3555.6 5.41

a048-10f 250 10 3325 10 3325 10.0 3325.6 4.32

a056-10f 250 10 3263 10 3263 10.0 3263.0 7.46

a065-12f 250 12 3902 12 3902 12.0 3902.0 10.64

a071-10f 250 10 3486 10 3486 10.0 3486.6 12.73

a034-04f 500 4 1773 4 1773 4.0 1773.0 1.76

a036-05f 500 5 2110 5 2110 5.0 2110.0 1.95

a039-06f 500 6 2289 6 2289 6.0 2289.0 2.00

a045-06f 500 6 2303 6 2303 6.0 2303.0 3.41

a048-05f 500 5 2283 5 2283 5.0 2283.0 3.26

a056-05f 500 5 2165 5 2165 5.0 2165.0 4.70

a065-06f 500 6 2567 6 2567 6.0 2568.0 7.82

a071-05f 500 5 2475 5 2457 5.0 2457.0 7.62

a034-02f 1000 2 1406 2 1406 2.0 1406.0 1.31

a036-03f 1000 3 1644 3 1644 3.0 1644.0 1.13

a039-03f 1000 3 1654 3 1654 3.0 1654.0 1.17

a045-03f 1000 3 1740 3 1740 3.0 1740.0 1.97

a048-03f 1000 3 1891 3 1891 3.0 1891.0 1.69

a056-03f 1000 3 1739 3 1739 3.0 1739.0 3.23

a065-03f 1000 3 1974 3 1974 3.0 1974.0 4.17

a071-03f 1000 3 2054 3 2054 3.0 2054.0 4.24

21


We can see that in four instances out of the 32 instances the MA has improved

the best known upper bound by using one more vehicle, and in the other 28 instances

the solution given by the MA coincides with the best known solution both in the total

travel distance and in the number of vehicles.

We also have run the MA with fixing a priori the number of vehicles equal to the

one given in the best known solution (see third column in Table 1). In this case, in

all of the 32 instances the total travel distance obtained with the MA coincides with

the best known upper bound, with running time similar to the one given in Table 1.

Therefore, the table corresponding to these results has been omitted.

In Table 2 we show the results to the set of 126 single vehicle instances given by Soler

et al (2008) for which the optimal solution is known. In this table, results are averaged

over selected groups of the instances where the 126 instances are partitioned into 24

groups according to features of the instances. The columns in the table lists the number

of instances in each groups (Ins), the average number of required arcs in the subset

(ARA), the number of (required) edges in all the instances in the subset (|E|), the
average number of required vertices in the subset (ARV ), the average number of vertices

in the asymmetric TSP instances obtained from the original instances (AVAT SP ), the

average time in seconds to obtain the optimal solution with the exact procedure (AT O),

the average time in seconds to obtain the heuristic solution with the MA (AT M A),

the number of instances optimally solved with the MA in the subset (OP T ), and the

average deviation of the MA solutions in the subset (ADEV ). By deviation we mean

(U B − LB)/LB.

22


Table 2. Computational results on known single vehicle instances.

Group Ins ARA |E| ARV AVAT SP AT O AT M A OP T ADEV
1 6 51 0 6 82 14.48 5,76 6 0

2 4 84 0 8 127 65.04 11,04 4 0

3 6 108 0 8 149 392,81 16,20 6 0

4 5 125 0 12 195 348,34 27,89 4 0,00010

5 7 145 0 14 212 932,43 26,87 6 0,00050

6 6 164 0 16 248 1269,71 41,29 5 0,00025

7 5 54 0 3 86 42.65 7,53 4 0,00078

8 4 84 10 8 137 478,8 12,73 4 0

9 7 107 10 9 175 490,38 21,33 6 0,00071

10 6 126 10 11 201 819,55 29,76 1 0,00059

11 5 141 10 13 231 1273,89 41,44 4 0,00052

12 6 156 10 14 245 1037,18 50,19 5 0,00007

13 6 172 10 15 265 3211,59 61,19 2 0,00093

14 5 61 10 3 119 139,92 7,18 5 0

15 6 105 20 5 167 1464,62 21,52 3 0,00049

16 4 126 20 9 208 516,69 40,62 1 0,00141

17 6 142 20 11 240 3095,38 43,53 2 0,00142

18 4 156 20 9 236 3539,15 42,90 3 0,00089

19 3 168 20 12 236 3646,25 66,26 1 0,00130

20 4 58 20 3 129 846,88 16,77 2 0,00088

21 6 100 20 5 187 1218,35 22,66 4 0,00029

22 6 65 30 3 156 2437,78 22,63 3 0,00034

23 6 113 30 6 218 2931 37,87 1 0,00087

24 3 140 30 6 191 > 2h. 64,47 3 0

We can see from Table 2 that the results obtained with the MA are very good.

The MA was able to optimally solve 86 instances out of the 126 instances, with 0.05%

average deviation.

4.3 Solving MCGRPTP instances with the MA

We applied the MA to solve also three sets of random MCGRPTP instances with

up to 700 arcs, 160 (required) edges, 160 vertices, 225 required arcs, and 28 required

23


vertices, which are transformed into ACVRP instances with up to 623 vertices. As far

as we know, the largest ACVRP instance described in the literature until now has 300

vertices.

Next we describe the data generation procedure for each set.

The first set was generated from the 128 single vehicle instances given by Soler et

al (2008), and we obtain two MCGRPTP instance sets (one with vehicle capacity 1000

and the other with vehicle capacity 2000) as follows:

We choose the depot node as the first required vertex in the numerical

order. In this node all turns are changed to be allowed with zero cost.

Each required arc, required edge and required vertex will have a randomly

generated integer demand in range [13,120], [7,60], and [50,120] respectively.

Note that when we transform one of these MCGRPTP instances into an

ACVRP instance, if an original required vertex v has demand dv and it

gives rise to a vertex subset in the ACVRP with t vertices, let r be the

largest integer positive number such that dv = rt + c, with c ≥ 0, then
t − 1 vertices in this subset will have demand r, and the last one will have
demand r + c. These 256 generated MCGRPTP instances act as a basis for

ACVRP instances with number of vertices in the interval [61,290].

The second set contains 32 MCGRPTP instances generated from 16 of the biggest

single vehicle instances by Corberán et al (2002). Each original instance is first trans-

formed into an MGRP with turn penalties instance with the procedure explained in

Soler et al (2008) and then transformed into two MCGRPTP instances (one with ca-

pacity 1000 and the other with capacity 2000) with the procedure given above for the

first set. These 32 instances form the ACVRP instances with number of vertices in the

interval [235,406].

Finally, the third set contains 48 instances that have been obtained from 24 new

large single vehicle instances randomly generated with the same instance generator

used by Corberán et al (2002). These 48 MCGRPTP instances are transformed into

ACVRP instances with the number of vertices in the interval [382,623].

In these three sets we have used the MA version with variable number of vehicles

24


in order to obtain best upper bounds with respect to the total travel distance. The

appendix shows a table containing all data and results corresponding to each individual

MCGRPTP instances. In this table, each instance is named as Ixxy, where xx indicates

the subset to which the instance belongs and y indicates the number of the instance

inside that subset. The first 24 subsets correspond to the first set of (128) instances,

subsets 25 to 27 correspond to the second set of (16) instances and subsets 28 to 31

correspond to the third set of (24) instances. The columns in the table list the following

data: the number of vertices in the ACVRP instance obtained from the corresponding

MCGRPTP instance (|VACV RP |), the total demand in the ACVRP instance (T.D.),
and for i ∈ {1, 2}, the total travel distance of the best result in five runs obtained for a
vehicle capacity of Ci = i·1000 units (di), the number of vehicles corresponding to this
best result (Ki) and the average computing time in seconds for a run corresponding to

the capacity Ci (Timei). Note that di is the total distance in the original MCGRPTP

instance, not in the auxiliary ACVRP instance.

The MA was able to find feasible solutions for all 336 instances including the large-

size instances with up to 600 vertices, within a reasonable computation time, as re-

ported in the appendix. The computation times vary from a few seconds to more than

one hour depending on the problem size. We consider the reported computing times

reasonable, given the size and complexity of the considered ACVRP instances.

Based on these results, one can conclude that at least medium-size real-world MC-

GRPTPs can be solved by a state-of-the-art heuristic method for the ACVRP through

their transformation into an ACVRP as explained here. By the way, we have gener-

ated a large number of instances to the, until now, limited set of ACVRP benchmarck

instances. Of course these new instances will be available to any researcher interested

on them.

5 Conclusions

In this paper we have studied a generalization of the MCGRP including turn penalties

and forbidden turns. Through an intermediate transformation into a GVRP, we have

provided a procedure to transform it into an ACVRP. Then, at least from a theoretical

25


point of view, this generalization can be solved both optimally and heuristically with

existing algorithms. We have also introduced a set of new benchmark problems and

adapted a recent and powerful memetic algorithm to ACVRP. The experimental results

show an average deviation equal to 0.05% for instances with known optimal solution

and that large-size problems can be solved with the memetic algorithm.

We are convinced that research on turn penalties will increase and be of important

value in the future to reduce the gap between theoretical research and real-life appli-

cations. We hope that the theoretical and experimental results presented here can be

used in the future as ideas or tools to test the efficiency of specific procedures to solve

capacitated routing problems with turn penalties.

Acknowledgements

This work has been partially supported by the Ministerio de Educación y Ciencia of

Spain (project TIN2008-06441-C02-01).

26


Appendix

Inst. |V |-|A|-|E| |AR| |VR| |VACV RP | T.D. d1 K1 Time1 d2 K2 Time2
I11 40-110-0 44 3 61 3819 4255 4 13.11 3966 2 4.42

I12 60-140-0 56 5 75 6462 6848 5 25.63 6145 3 17.9

I13 40-90-0 36 3 46 3009 4103 4 11.04 3547 2 19.67

I14 80-170-0 68 6 92 5415 7578 6 25.15 6806 3 20.9

I15 40-90-0 36 6 54 3142 4126 4 7.56 3625 2 8.38

I16 80-170-0 68 11 118 5772 7651 6 65.18 6798 3 37.18

I21 80-200-0 80 7 107 6936 7464 7 53.7 6962 3 35.13

I22 100-220-0 88 7 121 7067 10152 8 41.1 8999 4 28.14

I23 80-200-0 80 4 95 5815 7300 6 53.97 7026 4 28.3

I24 100-220-0 88 14 158 8907 10643 9 79.62 9439 5 54.04

I31 100-260-0 104 3 112 6704 11831 7 63.81 11272 4 24.74

I32 120-260-0 104 6 127 8055 13666 11 256.67 12364 6 112.48

I33 120-290-0 116 7 147 8946 13493 9 228.25 12332 5 59.84

I34 100-260-0 104 6 136 8154 12352 9 62.52 11466 5 47.86

I35 120-260-0 104 11 147 8387 12264 9 43 11130 5 41.33

I36 120-290-0 116 14 195 10603 14253 11 248.94 12728 6 102.05

I41 140-300-0 120 8 151 9108 15107 10 93.41 13086 5 69.21

I42 140-330-0 132 12 216 10775 16681 11 320.16 15176 6 114.81

I43 140-330-0 132 6 164 10232 16542 11 139.86 15126 6 65.39

I44 140-300-0 120 20 220 11314 16130 12 214.2 13732 6 156.12

I45 140-300-0 120 14 185 9746 15101 10 204.5 13184 5 122.74

I51 160-340-0 136 8 166 10460 14698 11 156.37 13806 7 224.51

I52 160-340-0 136 19 219 8387 15947 14 284.86 13405 6 69

I53 160-340-0 136 13 191 11192 14987 12 183.21 13413 6 117.01

I54 180-380-0 152 8 183 10750 18322 11 219.97 16710 6 92.44

I55 160-370-0 148 14 218 12729 17818 13 387.24 15959 7 151.67

I56 180-380-0 152 21 250 13252 19431 14 422.96 17000 7 236.26

I57 180-380-0 152 15 217 12690 18806 13 369.88 16687 7 117.98

I61 200-420-0 168 10 210 12868 21039 13 431.41 18289 7 131.69

I62 180-400-0 160 8 193 12364 19634 13 227.68 17122 7 91.19

I63 200-420-0 168 17 289 15961 25569 16 1608.23 19197 9 348.06

I64 180-400-0 160 20 255 14227 20806 15 522.98 17808 8 214.22

I65 180-400-0 160 14 217 13445 20295 14 392.63 17340 7 180.87

I66 200-420-0 168 18 254 14903 22681 15 669.9 18661 8 235.08

I71 40-110-10 44 1 65 3612 4830 4 12.93 4528 2 11.29

I72 40-90-10 36 3 67 3501 4353 4 14.94 4151 2 16.83

I73 60-140-10 56 2 81 4290 6101 5 16.09 5808 3 16.85

I74 60-160-10 64 2 89 5011 7201 6 28.32 6859 3 30.66

I75 80-170-10 68 4 107 6462 7924 7 45.76 7248 4 31.74

I81 80-200-10 80 4 113 6703 7403 7 62.7 6993 4 30.44

I82 100-220-10 88 5 113 6824 7409 7 86.16 6993 4 34.07

I83 80-200-10 80 7 133 7279 7654 8 51.37 7034 4 47.82

I84 100-220-10 88 10 184 9826 9568 9 109.2 8820 5 47.64

27


Inst. |V |-|A|-|E| |AR| |VR| |VACV RP | T.D. d1 K1 Time1 d2 K2 Time2
I91 120-260-10 104 6 149 8587 13401 11 157.11 12181 6 78.18

I92 100-260-10 104 5 157 8386 12508 9 209.1 11584 5 81

I93 120-290-10 116 5 158 8700 12457 9 145.08 11757 5 47.07

I94 120-260-10 104 16 204 10556 12734 9 111.9 11894 5 60.81

I95 100-260-10 104 10 184 9826 13780 10 248.3 12055 5 129.32

I96 120-290-10 116 10 183 9539 12771 10 182.84 11934 5 106.03

I97 120-260-10 104 11 177 10132 12703 9 95.41 11877 5 61.5

I101 140-300-10 120 6 169 9675 14174 10 190.19 12609 5 121.77

I102 140-330-10 132 6 179 10520 16205 11 195.82 15124 6 64.7

I103 140-330-10 132 11 203 11670 16628 12 330.09 15468 6 172.42

I104 140-300-10 120 16 215 11522 15189 12 314.17 13089 6 169.71

I105 140-330-10 132 15 243 13154 17056 14 389.77 15618 7 177.68

I106 140-300-10 120 11 193 10832 14880 11 274.03 12822 6 102.74

I111 160-340-10 136 9 193 11457 16445 12 273.48 14640 6 172.66

I112 160-340-10 136 23 275 13274 17141 14 484.04 14918 7 330.28

I113 160-340-10 136 16 230 12651 16616 13 403.95 14690 7 152.03

I114 160-370-10 148 6 195 12448 18102 13 247.19 16335 7 113.22

I115 160-370-10 148 12 230 13856 19240 14 586 16446 7 323.42

I121 180-380-10 152 8 203 11981 20136 12 782.32 17250 8 397.97

I122 180-380-10 152 20 277 15076 20133 16 530.39 16547 6 406.85

I123 180-380-10 152 14 234 12662 18966 13 500.68 16671 7 211.59

I124 180-400-10 160 13 241 13650 18237 14 411.86 16348 7 265.88

I125 180-400-10 160 8 219 12867 18404 13 431.07 16303 7 169.24

I126 180-400-10 160 19 276 15023 18594 16 415.15 16647 8 308.28

I131 200-420-10 168 8 234 14073 20264 13 454.48 18009 7 153.91

I132 200-440-10 176 8 223 12780 21636 15 308.71 19289 8 140.3

I133 200-420-10 168 22 288 15931 23868 16 1173.59 19076 8 661.17

I134 200-440-10 176 21 290 15052 21369 16 557.87 18686 8 343.22

I135 200-420-10 168 15 257 14872 21877 15 689.08 18479 8 278.81

I136 200-440-10 176 15 275 15877 24410 16 790.1 20049 8 522.07

I141 60-90-20 36 1 77 3699 4084 4 20.51 3833 2 21.02

I142 60-160-20 64 5 115 5659 8403 7 52.74 7629 4 30.23

I143 60-140-20 56 5 129 6107 7284 6 64.19 6522 3 42.57

I144 80-170-20 68 5 125 6565 8181 7 82.09 7743 4 52.77

I145 80-200-20 80 1 121 6542 7986 7 58.58 7620 4 49.68

I151 100-220-20 88 4 141 8387 10444 8 195.27 9800 4 106.95

I152 120-260-20 104 4 157 8391 12665 9 102.45 11959 5 76.46

I153 120-290-20 116 3 169 10033 13550 11 156.71 12303 6 76.88

I154 100-260-20 104 3 153 8387 13614 11 189.79 12502 6 98.08

I155 120-260-20 104 7 171 9857 13125 10 299.63 12032 5 159.41

I156 120-290-20 116 6 183 9777 13596 10 257.16 12317 5 172.63

I161 140-300-20 120 6 184 10131 15037 11 133.85 13473 6 77.48

I162 140-330-20 132 6 196 10861 16840 11 304.8 14957 6 137.01

I163 140-300-20 120 11 208 11277 15554 12 239.37 13585 6 136.5

I164 140-330-20 132 11 235 12807 17620 13 497.14 15329 7 175.13

28


Inst. |V |-|A|-|E| |AR| |VR| |VACV RP | T.D. d1 K1 Time1 d2 K2 Time2
I171 160-340-20 136 16 249 13059 16078 14 418.03 14551 7 261.08

I172 160-340-20 136 6 197 11250 15202 12 251 14189 6 154.1

I173 160-370-20 148 6 214 12080 18298 13 237.53 16272 7 144.29

I174 160-340-20 136 11 224 11824 15763 12 388.2 14244 6 325.71

I175 160-370-20 148 11 245 13134 18765 14 355.11 16396 7 248.01

I176 160-370-20 148 16 288 14216 19257 15 500.41 16827 8 247.63

I181 180-380-20 152 5 212 11643 18628 12 332.17 16663 6 246.78

I182 180-380-20 152 9 230 12888 19989 13 756.61 17339 7 231.97

I183 180-400-20 160 7 229 13028 18463 14 303.72 16648 7 190.11

I184 180-400-20 160 14 267 13991 18851 15 1343.62 18193 7 914.38

I191 200-420-20 168 7 237 13896 22059 14 703.29 19778 8 802.64

I192 200-420-20 168 17 289 15961 25569.00 16 1608.23 18782 7 406.29

I193 200-420-20 168 12 267 14877 23137 15 907.11 19184 8 251.88

I201 40-110-30 44 1 105 5266 6069 6 40.75 5444 3 38.24

I202 60-140-30 56 2 123 5777 6705 6 96.64 6359 3 54.63

I203 60-160-30 64 2 129 6846 8571 7 154.47 7915 4 80.08

I204 80-170-30 68 5 144 7021 8487 8 66.81 7896 4 74.44

I211 80-200-30 80 3 149 7597 8704 8 131.29 7943 4 88.27

I212 80-200-30 80 6 163 7744 8818 8 198.14 8056 4 103.63

I213 100-260-30 104 1 192 10061 12822 11 284.98 11984 6 143.23

I214 120-260-30 104 5 183 8387 12670 10 161.83 11516 5 122.43

I215 120-290-30 116 6 199 10056 13642 11 166.43 12382 6 116.95

I216 120-290-30 116 11 233 12343 14384 13 356.58 12711 7 152.71

I221 40-90-40 36 1 117 5416 5321 6 59.06 4962 3 56.52

I222 60-140-40 56 3 147 7012 7742 8 88.71 7093 4 81.97

I223 60-160-40 64 2 149 7524 8892 8 150.32 8225 4 90.57

I224 80-170-40 68 1 149 7651 8818 8 129.22 8134 4 82.15

I225 100-220-40 88 5 214 10793 11285 11 368.81 10027 6 160.24

I226 80-200-40 80 2 165 7986 9410 8 509.77 8253 4 275.54

I231 120-260-40 104 3 207 10567 14740 11 403.89 13088 6 145.29

I232 120-290-40 116 3 207 10678 14281 11 430.29 13110 6 150.35

I233 120-290-40 116 6 221 11151 14642 12 369.99 13282 6 178.76

I234 100-260-40 104 5 208 10307 12485 9 88.39 11297 5 50.78

I235 140-300-40 120 5 216 11258 15690 12 327.21 14373 6 202.45

I236 140-300-40 120 10 242 7021 16012 13 460.42 14576 7 207.78

I241 140-330-40 132 5 231 11865 17444 12 606.84 15789 6 372.98

I242 160-340-40 136 6 241 12797 17189 13 687.33 15339 7 207.94

I243 160-370-40 148 5 249 13426 18010 14 552.3 16245 7 365.67

I244 160-340-40 136 12 271 13973 20563 14 1586.52 16225 7 904.7

I245 160-370-40 148 10 275 14247 18365 15 566.35 16602 8 239.05

I251 120-260-60 104 3 235 10952 16098 11 836.73 13467 6 287.68

I252 140-330-60 132 7 283 13898 18238 14 1108.62 15406 7 799.45

I253 160-370-60 148 6 293 14768 20488 15 1189.57 18175 8 476.2

I254 180-400-60 160 8 315 16339 21517 17 1184.31 19329 9 522.9

I256 200-420-60 168 17 361 19015 24841 20 1212.79 21615 10 1023.6

29


Inst. |V |-|A|-|E| |AR| |VR| |VACV RP | T.D. d1 K1 Time1 d2 K2 Time2
I261 100-220-80 88 2 253 10764 12723 11 643.9 11708 6 424.9

I262 120-260-80 104 3 273 12387 15312 13 529.4 14127 7 285.35

I263 140-330-80 132 2 299 14801 18469 15 1370.78 16110 8 552.23

I264 160-370-80 148 11 359 16695 22098 17 1434.42 18966 9 651.6

I265 180-400-80 160 10 361 18031 22641 19 1089.58 19829 10 793.31

I266 200-420-80 168 9 363 18409 23206 19 1685.57 20366 10 1026.85

I271 100-220-100 88 2 293 12705 12708 13 912.82 11754 7 461.76

I272 120-260-100 104 3 315 14161 15851 15 784.83 14099 8 490.66

I273 140-330-100 132 5 353 16462 18388 17 1280.67 16269 9 1086.19

I274 180-400-100 160 9 406 19041 23053 20 1927.5 20180 10 1489.17

I275 200-420-100 168 8 399 19914 29504 20 4160.04 23017 10 2203.86

I281 200-600-60 180 9 382 23593 25022 18 4449.39 20696 9 1819.96

I282 200-600-80 180 13 452 19844 26271 20 5636.98 223670 10 3160.30

I283 200-600-100 180 6 440 20324 24640 21 2681.01 21966 11 1802.93

I284 200-600-120 180 8 463 20555 26060 21 3841.40 23267 11 2136.15

I285 200-600-140 180 7 497 21577 27645 22 5756.68 24330 11 3655.87

I286 200-600-160 180 7 548 25148 25999 26 5966.49 23482 13 3879.16

I291 225-650-60 195 19 439 21355 27266 22 2306.38 23901 11 2337.94

I292 225-650-80 195 15 470 22727 29510 23 4450.06 248090 12 2900.06

I293 225-650-100 195 12 494 23987 28549 25 3187.86 25247 12 5064.86

I294 225-650-120 195 11 507 23593 31508 24 4747.81 27241 12 4546.69

I295 225-650-140 195 6 502 23593 30096 24 4434.57 26147 12 5327.40

I296 225-650-160 195 5 538 24429 30333 25 5490.39 267850 13 5215.72

I301 250-700-60 210 24 484 22346 28475 23 3718.08 247730 12 1945.99

I302 250-700-80 210 19 484 22746 32558 23 4312.41 27064 12 2631.71

I303 250-700-100 210 18 521 24925 29632 26 5427.05 25985 13 3103.63

I304 250-700-120 210 7 490 23071 30786 24 3635.21 27128 12 2674.20

I305 250-700-140 210 11 563 24875 374830 25 10734.52 297940 13 4286.82

I306 250-700-160 210 11 604 27643 34824 28 9304.83 29962 14 6554.05

I311 270-750-60 225 25 503 23948 30713 25 3003.68 29216 12 5038.99

I312 270-750-80 225 28 599 27111 32940 28 4606.29 28394 14 5215.76

I313 270-750-100 225 16 543 26907 33859 28 5026.30 29348 14 3865.43

I314 270-750-120 225 13 548 25044 30692 26 4782.07 27320 13 4545.20

I315 270-750-140 225 14 602 27722 36708 28 9063.87 306540 14 7840.02

I316 270-750-160 225 9 623 27771 39925 28 11808.50 32859 14 9424.87

References

Bautista, J., & Pereira, J. (2004). Ant Algorithms for Urban Waste Collection

Routing. Lecture Notes in Computer Science, 3172, 3020-3033.

Bautista, J., Fernández, E., & Pereira, J. (2008). Solving an Urban Waste Collec-

tion Problem Using Ants Heuristics. Computers & Operations Research, 35, 302-309.

30


Belenguer, J.M., Benavent, E., Lacomme, P., & Prins, C. (2006). Lower and Upper

Bounds for the Mixed Capacitated Arc Routing Problem. Computers & Operations

Research, 33, 3363-3383.

Benavent, E., & Soler, D. (1999). The Directed Rural Postman Problem with Turn

Penalties. Transportation Science 33, 408-418.

Bodin, L., Fagin, G., Welebny, R., & Greenberg, J. (1989). The Design of a Com-

puterized Sanitation Vehicle Routing and Scheduling for the Town of Oyster Bay, New

York. Computers & Operations Research, 16, 45-54.

Clossey, J., Laporte, G., & Soriano, P. (2001). Solving Arc Routing Problems with

Turn Penalties. Journal of the Operational Research Society, 52, 433-439.

Corberán, A., Mart́ı, R., Mart́ınez, E., & Soler, D. (2002). The Rural Postman

Problem on Mixed Graphs with Turn Penalties. Computers & Operations Research,

29, 887-903.

De Franceschi, R., Fischetti, M., & Toth, P. (2006). A New ILP-Based Refinement

Heuristic for Vehicle Routing Problems. Mathematical Programming Series B, 105,

471-499.

Fischetti, M., Toth, P., & Vigo, D. (1994). A Branch-and-Bound Algorithm for the

Capacitated Vehicle Routing Problem on Directed Graphs. Operations Research, 42,

846-859.

Ghiani, G., & Improta, G. (2000). An Efficient Transformation of the Generalized

Vehicle Routing Problem. European Journal of Operational Research, 122, 11-17.

Jansen, K. (1993). Bounds for the General Capacitated Routing Problem. Net-

works, 23, 165-173.

Nagata, Y., & Bräysy, O. (2009). Edge Assembly Based Memetic Algorithm for

the Capacitated Vehicle Routing Problem. Networks, 54, 205-215.

Pandit, R., & Muralidharan, B. (1995). A Capacitated General Routing Problem

on Mixed Networks. Computers & Operations Research, 22, 465-478.

Perrier, N., Langevin, A., & Amaya, C.V. (2008). Vehicle Routing for Urban Snow

Plowing Operations. Transportation Science, 42, 44-56.

Pessoa, A., Poggi, M., & Uchoa,E. (2007). Robust Branch-Cut-and-Price Algo-

rithms for Vehicle Routing Problems. Presented at Route 2007 (International Work-

31


shop on Vehicle Routing and Transportation), Jekyll Island, Georgia.

Roy, S., & Rousseau, J.M. (1989). The Capacitated Canadian Postman Problem.

INFOR, 27, 58-73.

Soler, D., Mart́ınez, E., & Micó, J.C. (2008). A Transformation for the Mixed

General Routing Problem with Turn Penalties. Journal of the Operational Research

Society, 59, 540-547.

Soler, D., Albiach, J., & Mart́ınez, E. (2009). A Way to Optimally Solve a Time-

Dependent Vehicle Routing Problem with Time Windows. Operations Research Letters,

37, 37-42.

Vigo, D. (1996). A Heuristic Algorithm for the Asymmetric Capacitated Vehicle

Routing Problem. European Journal of Operational Research, 89, 108-126.

32