2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings

arXiv:1704.01859v1 [cs.NE] 6 Apr 2017

Tackling Dynamic Vehicle Routing Problem with
Time Windows by means of Ant Colony System
Raluca Necula

Mihaela Breaban

Madalina Raschip

Faculty of Computer Science
Alexandru Ioan Cuza University
Iasi, Romania
Email: raluca.necula@info.uaic.ro

Faculty of Computer Science
Alexandru Ioan Cuza University
Iasi, Romania
Email: pmihaela@info.uaic.ro

Faculty of Computer Science
Alexandru Ioan Cuza University
Iasi, Romania
Email: mionita@info.uaic.ro

Abstract—The Dynamic Vehicle Routing Problem with Time
Windows (DVRPTW) is an extension of the well-known Vehicle
Routing Problem (VRP), which takes into account the dynamic
nature of the problem. This aspect requires the vehicle routes
to be updated in an ongoing manner as new customer requests
arrive in the system and must be incorporated into an evolving
schedule during the working day. Besides the vehicle capacity
constraint involved in the classical VRP, DVRPTW considers in
addition time windows, which are able to better capture realworld situations. Despite this, so far, few studies have focused on
tackling this problem of greater practical importance. To this end,
this study devises for the resolution of DVRPTW, an ant colony
optimization based algorithm, which resorts to a joint solution
construction mechanism, able to construct in parallel the vehicle
routes. This method is coupled with a local search procedure,
aimed to further improve the solutions built by ants, and with an
insertion heuristics, which tries to reduce the number of vehicles
used to service the available customers. The experiments indicate
that the proposed algorithm is competitive and effective, and on
DVRPTW instances with a higher dynamicity level, it is able to
yield better results compared to existing ant-based approaches.

I. I NTRODUCTION
The Vehicle Routing Problem plays a central part in capturing logistics and distribution operations, with an impact in
the economy, more prominent as the need for transportation
is increasingly growing. Thus, this class of problems has a
practical importance and has attracted a lot of research interest over the years. Recently, the technological advancements
made possible the use of mobile devices to enable the direct
communication between the clients and the drivers, such that
a driver could dynamically change his plan while executing
his route. Also, the emergence of global positioning systems
allows a dispatcher to know the current position of a driver
and communicate him in a timely manner the next customer
to visit on his route. This leads to a VRP variant known as
Dynamic Vehicle Routing Problem (DVRP), also referred to
as online or real-time VRP.
As indicated in [1], where the authors perform a review
on VRP literature, more challenging problems such as DVRP
began being studied more intensively only recently, due to
their ability to capture real-world scenarios. Possible sources
of dynamism in DVRP include: customers requests, travel time
and demands, which can be dynamically revealed for a set
of known customers. In this paper, we considered that the

dynamic nature of DVRP is given by the customers requests,
which is the most common source of dynamism, as pointed
out in [2]. Therefore, DVRP allows customers requests to be
serviced in a real-time manner, while the drivers have already
started their routes, visiting in their way other customers. Thus,
the algorithm needs to adjust the ongoing vehicle routes, such
as to take into account these dynamic customer requests, while
maintaining the feasibility of solution.
The aim of this study is to design and analyse ant colony
optimization based algorithms, that are able to achieve good
quality solutions for DVRPTW instances with a higher level of
dynamicity. To this end, we propose in this paper an ant colony
system (ACS) based algorithm, relying on a joint mechanism
for constructing the solutions, in which the vehicle and the next
customer to be added in its tour are simultaneously selected
during the transition step. Our approach is hybridized with a
local search procedure, consisting of two operators, relocate
and exchange, that are applied in an iterative manner, until
no further improvement is possible. Moreover, we integrated
in our method an insertion heuristics to better incorporate
unvisited customers in the existing tours, thus reducing the
number of vehicles needed to service all the customers.
The remainder of this paper is structured as follows. Section
II describes the static variant of the considered DVRPTW
problem. Section III presents a survey on existing literature
related to DVRPTW. In Section IV the ant colony system
optimization algorithm is summarized, as the underlying metaheuristic for our approach that will be described in Section
V. In Section VI the experimental study and the obtained
results will be presented. The paper concludes with Section
VII, which draws the final remarks and offers future research
directions.
II. T HE

VEHICLE ROUTING PROBLEM WITH TIME
WINDOWS

In this section, we describe the (static) vehicle routing
problem with time windows (VRPTW), which is the static
variant of our considered DVRPTW problem.
As in the classical VRP or capacitated VRP, VRPTW
requires to find a set of routes for each vehicle, such that
each customer, having a given demand, is visited exactly
once by a single vehicle and the total demand on the route

AUTHOR VERSION

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
does not exceed the vehicle’s capacity. The fleet of vehicles
is assumed to be homogeneous, all the vehicles are located
at a single depot, where they start and end their route, and
each vehicle has a limited capacity. Besides this, VRPTW
brings the additional constraint of time windows associated
to a customer, such that a customer i must be serviced by a
vehicle within a time interval, defined as [ei , li ], where ei is
the earliest arrival time, and li is the latest arrival time. The
service at customer i cannot start before its earliest arrival
time, and if the vehicle arrives at the customer earlier than
ei , waiting occurs. Also, the service at each customer takes
an amount of time, denoted by si , required for the pickup
and/or delivery of goods or services. In case of hard time
windows constraints, the vehicle must arrive at the customers
not later than the latest arrival time, constraint that must be
satisfied for each customer within a vehicle’s tour in order to
maintain the solution feasible. There is also the possibility of
applying penalties if the services start after the allowed time
windows, which is the case of soft time windows. The depot’s
time window induces a constraint regarding the maximum total
route time, meaning that each vehicle route must start and end
within the time window associated with the depot.
In this study, we consider hard time windows constraints
and the existence of a homogeneous fleet of vehicles, that are
located at a single depot. Also, we assume that the primary
objective of VRPTW is to minimize the number of tours (vehicles), whilst a second objective is to minimize the total traveled
distance needed to supply all customers in their required
hours. This means that the number of tours minimization
takes precedence over total distance minimization. In case of
solutions with the same number of vehicles, those solutions
of lower distance are preferred.
By its description, it can be noticed that VRPTW is
more complicated than multiple traveling salesman problem
(mTSP), problem that we have tackled in our previous studies
[3], [4] with ant colony based methods, and for which we proposed a benchmark1. Thus, mTSP can be seen as a relaxation
of VRPTW, if removing the time windows associated with the
customers, and assuming that vehicles have unlimited capacity,
which imposes no restriction on the number of customers to
be visited on a vehicle’s route.
III. R ELATED WORK
During the last decades, the VRP and his famous VRPTW
extension have been an intensive research area. Heuristic and
exact optimization approaches have been developed for the
VRPTW problem. Surveys of proposed techniques can be
found in [5], [6]. As the VRP and VRPTW problems are both
NP-hard and they generalize the traveling salesman problem
(TSP), ant-based methods were proposed for solving them. A
multi-ant colony system consisting in two colonies, one for
optimizing the number of vehicles and one for optimizing the
total travel time, was proposed for the VRPTW problem in
[7].
1 http://profs.info.uaic.ro/∼ mtsplib/

Because of the recent technological advances, the research
on dynamic routing increased. Techniques ranging from linear programming to metaheuristics were designed to address
dynamism and uncertainty. A comprehensive review of applications and approaches for dynamic vehicle routing problems
is given in [2]. A taxonomy of papers concerning DVRP
problems was developed in [8]. Also, the interested reader
is referred to [9], for a survey of hybrid artificial intelligence
algorithms, employed for solving DVRP problems.
Very few previous studies on using metaheuristics on
DVRPTW exist, that take into account both the dynamic nature
of VRP and the time windows as additional constraint. A
first such study is due to [10], which presents a tabu search
algorithm that works on the DVRPTW, but with soft time
windows. A hybrid genetic approach based on two populations
of individuals which evolve concurrently are used to minimize
the total traveled distance, and respectively, the number of
unserviced customers, total lateness at customers locations
and temporal constraint violations in [11]. A metaheuristic
algorithm is developed in [12] for tackling two variants of
DVRPTW, which consider several real-world constraints: multiple time windows, customers priorities and vehicle-customer
constraints. In [13], the DVRPTW problem is decomposed into
several static VRPTW problems, which are then solved using
an improved large neighborhood search algorithm.
To the best of our knowledge, the study from [14] is the only
ant colony based approach found in the literature, that tackles
the DVRPTW problem. To this end, the authors propose an
ACO based method, denoted as MACS-DVRPTW, by extending to the dynamical case the state-of-the-art ant algorithm
[7] developed for VRPTW. This study was continued in [15],
where MACS-DVRPTW was applied to schedule the routes of
a fleet of cars for a surveillance company. Recently, MACSDVRPTW was enhanced in [16] with two strategies for dealing
with DVRPTW problem in which customers have different
priority levels.
IV. T HE A NT COLONY

SYSTEM

Ant Colony Optimization (ACO) is a nature-inspired metaheuristic, which follows the metaphor of real ants that succeed
in finding the shortest paths between their nest and food
sources. In case of ACO, each artificial ant, referred henceforth
as ”ant”, constructs solutions in a probabilistic manner by
iteratively adding components, until a complete solution to
the problem is obtained. When building a solution, an ant is
influenced by two factors: 1) pheromone trails, updated dynamically at runtime, that reflect the gained search experience
of ants, and 2) the heuristic information, which is a static
value, dependent upon the problem.
The algorithm presented in this study is based on the Ant
Colony System (ACS) [17], which is a successor of the Ant
System (AS) [18]. AS is the first ACO algorithm proposed in
the literature, that was initially designed for solving instances
of TSP. ACS is an improvement over AS and it brings the
following changes: 1) a modified state transition rule, which
is more focused on exploitation, 2) the inclusion of a local

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
pheromone update, which reduces the amount of pheromone
on edges visited by ants, in order to increase exploration
and prevent an early stagnation of search, and 3) the global
pheromone update is performed by a single ant, generally
being the best so far ant, which produced the best solution.

AUTHOR VERSION

V. T HE ALGORITHM

INVESTIGATED FOR

DVRPTW

This section describes our approach designed for the
DVRPTW problem, which is based on the ant colony system
metaheuristic, outlined in Section IV. To tackle the dynamic
nature of the problem, we adopted in our algorithm the
time slices and nodes commitment approach from the MACSDVRPTW ant based solver, introduced in [14]. Accordingly,
a working day of twd seconds is equally split into nts time
slices, the length of a time slice (tts ) being computed as:
tts = twd /nts . Thus, the initial DVRPTW problem is divided
into nts static problems, that will be solved consecutively.
In this context, we introduce the concept of current problem
configuration, which denotes one of these static problems,
defined by the subset of available nodes (customer requests).
We will denote by S best the currently optimal solution, which
is the best feasible solution including all the available customer
requests known so far.
Our approach, referred henceforth as DVRPTW-ACS, is
composed of two parts, that will be presented in the next
subsections, and each part is running in a separate thread. The
core part of the algorithm, briefly denoted as the ”planner”,
is concerned with the time slices management and with the
dynamic nature of the problem. The other part is responsible
with the optimization task, by running the ACS based algorithm on the current problem configuration.
A. The planner
Before the beginning of the working day, an initial feasible
solution (with respect to capacity, time window and vehicle
arrival time at the depot constraints), is built using the timeoriented nearest neighbour heuristic, introduced in [19]. The
time-oriented nearest neighbour heuristic is a sequential tour
building algorithm, that takes into account both geographical
and temporal closeness of customers. This initial solution
defines the tentative tours for the vehicles, considering only a
priori nodes, known in the system from the beginning.
Initially, a vehicle starts its tour from the depot, then
iteratively adds the closest (in terms of a metric m) unvisited
customer, relative to the last customer of this tour, while
keeping feasible the tour under construction. The metric mij ,
which defines the closeness between i, the last customer on
the current emerging tour, and j, that refers to any unrouted
customer that could be visited next, is defined as:
mij = 0.4 · dij + 0.4 · Tij + 0.2 · uij

(1)

In the previous equation, dij is the distance between the
two customers, Tij means the time difference between the
beginning of service at customer j and the completion of
service at customer i, and is expressed as: Tij = bj − (bi + si ),
and uij represents the urgency of delivery to customer j,

defined as: uij = lj − (bi + si + dij ), where bj denotes
the beginning of service at customer j, being computed as:
bj = max(ej , bi + si + dij ), assuming that the vehicle travels
to the next customer j, as soon as it has finished the service
at the current customer i.
Each time when there are still remaining unrouted customers, that cannot be feasibly appended to the current tour,
a new tour, that starts from the depot, is added to incorporate
them.
The obtained solution is used to initialize the best so
far solution, S best , and to compute the value of the initial
pheromone level, τ0 , as:
τ0 = (nav · LN N )−1

(2)

where nav is the number of available nodes (customers) and
LN N denotes the total traveled distance of this solution.
When the working day begins, a timer is started which keeps
track of the current time, so that when the working day is over,
the algorithm will stop its execution. Also, the planner starts
the ant colony thread, which will perform its optimization task,
considering only the currently available customers.
Taking into account the current time, the planner repeatedly
verifies whether a new time slice began. If this is the case, the
planner checks: 1) if there are new nodes that became available
in the meantime, during the last time slice, and 2) if there
are new nodes that must be committed. If one of these two
conditions is met, the planner stops the execution of the ACS
based algorithm, since the problem definition has changed.
The next node i, after the last committed node from a tour
of the best so far solution, S best , is marked as committed if
the following condition holds: bi ≤ idxts · tts , where idxts is
the index of the current time slice, and the idxts · tts product
denotes the time when the current time slice ends. When a
node becomes committed, its location within the vehicle’s tour
cannot be changed anymore and it will be found at this position
in its tour in the final solution to be returned by the algorithm
at the end of the working day.
After committing the necessary nodes from the tours of
S best , if condition 1) holds, the list of available customer
requests is updated and the new available nodes are added in
the tours of S best by adopting the insertion technique from I1
insertion heuristic [19]. The insertion heuristic starts by computing for each unrouted node its best feasible insertion place
in the tours of S best according to a criterion (c1 ). The score of
inserting a customer u between two adjacent customers i and
j on a route, is computed as: c1 (i, u, j) = 0.1 · c11 (i, u, j) +
0.9 · c12 (i, u, j), where c11 (i, u, j) = diu + duj − dij and
c12 (i, u, j) = bju − bj , where bju denotes the new time of
beginning the service at customer j, after inserting customer
u in the route. For a given node, its best insertion position is
the one that achieves the minimum score for the c1 criterion.
Based on this, the best customer u to be inserted in the route
is selected to be the one that obtains the minimum value for c2
criterion, defined as: c2 (i, u, j) = 2.0 · d0u − c1 (i, u, j), where
d0u denotes the distance between the depot and customer u.

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
The insertion heuristic is applied in an iterated manner, until
no further feasible insertions are possible.
If there are still remaining available nodes which couldn’t
be feasibly inserted in the existing tours of S best , a new
tour is added, which starts from the depot. The unrouted
nodes will be tried to be added in this tour by following
the same construction mechanism used in the time-oriented
nearest neighbour heuristic. This process continues until all the
available customer requests are incorporated in S best , meaning
that a complete feasible solution was obtained.
After the necessary commitments were made and the new
available nodes were added in the best so far solution, the
ant colony is restarted, performing its optimization task on
the new problem configuration. The algorithm stops after twd
seconds of execution, which marks the ending of the working
day. At this point in time, the best solution obtained so far is
returned as the output of DVRPTW-ACS, indicating the final
tours to be traveled by each vehicle.

AUTHOR VERSION

B. The ACS based algorithm
Our DVRPTW-ACS approach relies on the ACS algorithm
for performing the optimization task, such that all the available
customers are visited only once, while minimizing the number
of vehicles and the total traveled distance. An ant’s solution is
composed of a set of tours, each one designating the route to be
traveled by a vehicle. As mentioned in Section II, the formulation of the considered VRPTW problem assumes a hierarchy
between these two objectives, namely the minimization of the
number of vehicles takes precedence over the minimization
of the traveled distance. This implies that a solution which
uses less vehicles will be preferred over a solution with more
vehicles, even if it has a smaller traveled distance.
Unlike the MACS-DVRPTW solver which resorts to two
colonies, ACS-VEI and ACS-TIME, each one trying to optimize a different objective, our algorithm uses one single
colony, which simultaneously optimizes the two objectives,
the number of vehicles and the total traveled distance. Consequently, MACS-DVRPTW uses two pheromone trail matrices,
one for each colony, whereas our approach involves only one
pheromone trial matrix. Besides that, DVRPTW-ACS works
only with feasible solutions, in which all the known customers
are incorporated, which is different from MACS-DVRPTW,
where the ACS-VEI colony works also with unfeasible solutions.
At the first run of the ACS based algorithm, the pheromone
trail matrix is initialized with τ0 , computed as in equation (2).
Then, at subsequent runs, when the ant colony is restarted,
τ0 is computed like in equation (2), except for the fact that
LN N is replaced with Lbest , which denotes the total distance
of the tours from S best . In addition to this, we have adopted
the pheromone preservation strategy, employed also in one of
the variants of MACS-DVRPTW, which allows that a certain
amount of pheromone from the previous run of the ant colony
to be preserved in the current execution.
In the implementation of the algorithm, we resorted to
candidate lists, as indicated in [20], when solving instances of

TSP with ACS. A candidate list of size cl contains for a given
node, the most closest cl neighbours, arranged in increasing
order according to their distance from the considered node. In
our case, all the nodes part of the DVRPTW instance will be
considered when computing the candidate list of a node. Then,
in the transition step of ACS, when an ant located in node r
has to decide the next node to move to, it will first examine
the candidate list of node r, choosing only those nodes that are
revealed. Only when all the available nodes from the candidate
list have already been visited, the search of the next customer
is extended on the rest of available nodes.
Initially, a vehicle is placed at the depot, where it starts
and ends its tour. In an iteration of the ACS based algorithm,
several ants build feasible solutions for the problem, that integrate all the available customers and do not violate any of the
VRPTW constraints: capacity, time window and vehicle arrival
time at the depot. Later on during the algorithm execution,
when the planner starts to commit nodes, the committed parts
of S best are used to initialize the ants’ solutions, being copied
at exactly the same positions. Therefore, it may result that an
ant’s solution to be comprised from the beginning of more
than one tour and use more than one vehicle. In case there are
committed nodes, the solution construction will continue from
these added portions of tours, which will be next extended by
ants during the transition step.
Unlike the MACS-DVRPTW solver, in which the tours are
constructed sequentially and filled up with customers one by
one, in our approach the tours are built simultaneously and the
vehicles compete towards extending their partially tours with
a new available customer. In addition to this, we employed a
joint mechanism for building the vehicles tours, in which the
vehicle and the customer to be added in its tour, are selected at
the same time, during the state transition rule from the standard
ACS. Both the vehicle (v) and the next customer to visit (s)
are chosen by iterating over the existing tours (vehicles) from
the set T and the candidate set C, comprised of available
customers, that have not been visited and committed yet, and
can be appended to the tour of v vehicle, while keeping the
solution feasible:
(
α
β
), if rand(0, 1) < q0
· ηrs
arg max (τrs
v∈T s∈C
(v, s) =
(3)
S,
otherwise
where r represents the ant’s current position, being the last
customer on the tour denoted by v, τrs is the pheromone trail
associated to edge rs, ηrs is the heuristic information correβ
sponding to edge rs and is computed as: ηrs
= (1/mrs )β ,
where mrs is defined as in equation (1). In addition, α and
β are parameters that reflect the importance of pheromone,
respectively heuristic information, q0 ∈ [0, 1] is a parameter
and S is a random variable selected according to the following
probability distribution:
prs =

(

α

P

0,

w∈T

β

τrs ·ηrs
P
u∈C

α ·η β
τru
ru

, if s ∈ C
otherwise

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
During the building process of an ant’s solution, when there
are remaining unrouted available customers that cannot be
feasibly added in the existing tours and the number of these
customers is less or equal to ten, we apply the same insertion
heuristic used by the planner to update S best with the new
available nodes. Its aim is to insert in the existing tours the
remaining available unvisited nodes. In this way, the insertion
heuristic is applied in order to prevent the addition of new
tours needed to incorporate these nodes, thus reducing the
number of vehicles used to service all the known customers.
After this step, if there are still remaining unvisited customers,
that are available, a new tour is added to incorporate them.
This process is repeated until the ant’s solution covers all the
available customers, meaning that a feasible complete solution
for the DVRPTW problem was obtained.
Once an ant moves from customer r to s, it updates the
pheromone level on the edge associated to it, by applying the
local pheromone update rule, as in the standard ACS:

AUTHOR VERSION

τrs = (1 − ρ) · τrs + ρ · ∆τrs

(4)

where ρ ∈ (0, 1) is a local pheromone decay parameter and
for the ∆τrs we have used the following setting, as indicated
in [17]: ∆τrs = τ0 , where τ0 is the initial pheromone level,
computed as in equation (2). The aim of the local pheromone
update is to make visited edges less desirable for subsequent
ants, enforcing diversity within the same iteration and thus
avoiding the situation in which all the ants construct very
similar tours.
After all the ants finished to construct their solution, the
best iteration ant is selected as the one that built the best
solution, either regarding the number of vehicles or the total
distance objective. Since the number of vehicles objective has
priority over the total distance objective, a solution which uses
less vehicles is always preferred over a solution with more
vehicles, even if it has a smaller total distance. The global best
ant, which corresponds to the best so far solution, is updated,
if necessary, based on the best iteration ant. Then it follows
the global pheromone update and like in the standard ACS, it
reinforces with additional pheromone the edges used by the
global best ant:
τrs = (1 − ρ) · τrs + ρ · ∆τrs

(5)

where
∆τrs =



(Lgb )−1 , if rs ∈ best so far solution
0,
otherwise

where ρ ∈ (0, 1) is the pheromone decay parameter and Lgb
denotes the total traveled distance of the best so far solution,
obtained by the global best ant.
Since it is known from the literature that combining an ACO
algorithm with a local search phase can greatly improve its
performance, we integrated in DVRPTW-ACS a local search
procedure. This method consists of two multi-route operators,
relocate and exchange [21], which modify simultaneously
two different tours. The relocate operator removes one node
from a tour and reinserts it into another tour, whilst the

exchange operator swaps the position of two nodes from
two different tours. These two operators are applied in an
iterated manner, meaning they are called repeatedly, until no
further improvement, regarding the number of vehicles or the
total distance, can be obtained. We applied the local search
procedure to the initial solution, produced by the time-oriented
nearest neighbour heuristic, and to the best solution obtained
in the current iteration (best iteration ant) of the algorithm.
According to the concept of commitment, which involves
that the position of committed nodes within a tour is fixed, the
insertion heuristic and the local search operators are applied
only to positions that do not belong to the committed parts of
a tour. In case of insertion heuristic, this means that a node
cannot be inserted in front of a node that is committed, whilst
in case of the local search procedure, the positions eligible for
relocation and exchange will start from the first uncommitted
node within a tour.
The ACS based algorithm iteratively performs its optimization task, trying to improve S best in any of the two objectives
(number of vehicles and total distance), until it is stopped by
the planner, either because new nodes became available or
because there are nodes that must be committed.
VI. E XPERIMENTS
A. Problem instances
The experimental analysis in this paper is conducted on
several DVRPTW instances, belonging to the benchmark introduced in [14]. These problem instances were constructed
starting from the Solomon’s 100 customers static VRPTW
benchmark2, that was extended to the dynamical case, by specifying a dynamicity level of X%. To this end, the Solomon’s
benchmark was enhanced with an additional attribute, namely
the available time, which conveys the time when a customer’s
request is revealed to the system. Starting with this time, the
customer request is considered to be known and will be taken
into account by the algorithm.
A dynamicity of X% means that a percentage of X%
customer requests have a non-zero available time, these being
dynamic requests which are revealed during the working day.
The a-priori nodes (customer requests), that are known from
the beginning of the algorithm execution, have their available
time equal to 0. The problem instances from the DVRPTW
benchmark have specified different values for the dynamicity
level, ranging in the interval [0%..100%], with an increment
of 10%. The instances with 0% dynamicity are static VRPTW
problems taken from the Solomon’s benchmark, whilst the
instances with 100% dynamicity are the most dynamic ones.
The DVRPTW benchmark encompasses euclidian test problems, divided in six categories: R1, R2, C1, C2, RC1 and
RC2. The test instances in R1 and R2 categories have nodes
with randomly generated coordinates, the nodes from C1 and
C2 categories are clustered, whilst in RC1 and RC2 there is
a combination of randomly generated and clustered nodes.
Test problems of type 1 have a short scheduling horizon,
2 http://web.cba.neu.edu/∼ msolomon/problems.htm

AUTHOR VERSION

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
allowing only a few nodes to be visited on a vehicle’s route.
On the other hand, problems of type 2 have a long scheduling
horizon, such that more customers can be serviced by the same
vehicle, and thus fewer vehicles are needed to visit all the
customers. From each of these six categories, we have chosen
two problem instances and for each of it we have selected
three different values for dynamicity: 10%, 50% and 100%,
resulting in a total of 36 DVRPTW instances, that were used in
our experimental study. We have chosen different dynamicity
degrees in order to analyze the impact of the dynamicity on the
quality of solutions produced by the investigated algorithms. In
each DVRPTW instance, the depot is considered to be the first
entry in the list of given customers. Also, the fleet of vehicles
is homogeneous and the travel time between two customers is
assumed to be equal with the distance between them.
The VRPTW problem instances from the Solomon’s benchmark define a time window for each node, including the depot,
namely [e0 , l0 ], which denotes the scheduling horizon. At the
same time, the specifications of the DVRPTW problem involve
a certain length of the working day, which establishes when
the algorithm will stop from its execution. To comply with
these two requirements, we scaled in our algorithm all time
related values, as it was done in the MACS-DVRPTW solver.
More precisely, for each customer request from a particular
DVRPTW instance, the values for time windows, service
time, available time and distance between two customers, are
multiplied with the sv factor, computed as: sv = twd /(l0 −e0 ).
In a similar manner, the results reported in Section VI-C for the
total traveled distance (T D) are obtained as: T D = T D/sv .
To allow the reproduction of results, the DVRPTW test
instances, used in the experimental part of this study, and the
Java source code of our DVRPTW-ACS algorithm are available
online3 .
B. Parameters setup
To allow a fair comparison of the two investigated algorithms, DVRPTW-ACS and MACS-DVRPTW, we used the same
setting of the parameters, their values being taken from [14].
For the ACS based algorithms we have set: q0 = 0.9, α = 1.0,
β = 1.0, ρ = 0.9 and the number of ants was set to 10, whilst
for the dynamic scenario we have set: twd = 100 seconds
and nts = 50. Also, we have employed in both algorithms
the pheromone preservation strategy, by specifying ρ = 0.3 in
the equation: τij = (1 − ρ) · τijold + ρ · τ0 . Besides that, the
size of the candidate list, used in our algorithm, was set to
cl = 20. For both algorithms 30 runs were carried out on a
Linux server with 6 GB RAM memory, processor Intel Core
2 Duo P9xxx (Penryn Class Core 2) at 2.5 GHz.
C. Results
To assess the performance of the proposed algorithm, we
compared it with another ACO based approach from the
literature, namely MACS-DVRPTW, described in [14]. More
precisely, among the four variants of ACO based algorithms
3 http://profs.info.uaic.ro/∼ mtsplib/vrp-extension/dvrptw/

employed for the MACS-DVRPTW solver, we have chosen
the ACS based algorithm with pheromone preservation (WPP)
and which uses no improved initial solution (IIS), constructed
before the start of the working day. We selected this variant
of algorithm, denoted as ”DVRP, 0.3 wpp, no IIS” in [14],
since according to the results the authors reported in their
study, this variant achieves overall one of the best results on
DVRPTW instances with 50% dynamicity. For performing the
comparison of the investigated approaches, we stored for each
method the best so far solution and the number of feasible
solutions, computed during the working day.
Based on the 30 best so far solutions achieved at the
end of each algorithm execution on all DVRPTW instances,
we report in Tables I to VI the average, minimum (best),
maximum (worst) and standard deviation values. These values
are computed in terms of the two objectives: number of
vehicles (abbreviated in tables as NV) and total traveled
distance (abbreviated in tables as TD).
In addition to this, we also indicate the results obtained by
two approaches after performing 30 runs on static VRPTW
instances. The static VRPTW instances correspond to the
considered DVRPTW instances, in which all the customer
requests are known beforehand and there is no node to be
revealed dynamically during the working day. The instances
from the DVRPTW benchmark were constructed such as to
still allow obtaining the optimal solution of the corresponding
static VRPTW instance. Therefore, the solutions produced for
the static instances will act as a reference point when assessing
the quality of solutions found by the investigated approaches
on dynamic instances. In this sense, we have computed the
decline in the solution quality, relative to the solution obtained for the static instance, that will allow us to analyze
how much the solution deteriorates with the increase in the
dynamicity level. The decline measure is indicated in tables
as ”increase(%)” and its value is computed for each of the two
objectives as: increasek = (minDk − minSk )/minSk · 100,
k = 1, 2, where minDk is the minimum value obtained on
the dynamic instance for the k-th objective, and minSk is the
minimum value obtained on the static instance for the k-th
objective.
In the evaluation of the two algorithms, we take into account
the hierarchy between the two objectives, meaning that we aim
with priority minimum values for the number of vehicles, then
secondly we seek for smaller total distance values. In each
table, we highlighted with boldface the best (minimum) value
from a row, except for the instances where the statistical test
did not show statistically significant differences. The end part
from the name of a DVRPTW instance reflects its associated
dynamicity, such that ”0.0” denotes static instances having 0%
dynamicity, ”0.1” is for instances with a low dynamicity of
10%, ”0.5” is for instances with 50% dynamicity, and ”1.0”
denotes instances having the maximum dynamicity of 100%.
Analyzing the best values obtained for the two objectives,
it can be stated that MACS-DVRPTW is a clear winner on
most of the static instances, except for C201-0.0 and C2020.0 instances, where our algorithm has a better average per-

AUTHOR VERSION

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
formance. Actually, on these instances, the minimum values
produced on C201-0.0 by both algorithms, and on C202-0.0 by
DVRPTW-ACS, coincide with the best known solution reported
in the literature4 . Also, on most of DVRPTW instances with
a low dynamicity of 10% and in case of a few instances
with higher dynamicity, such as R103-0.5, R104-0.5 and R1041.0, MACS-DVRPTW achieves better results than our approach
on both objectives. The advantage of our algorithm over
MACS-DVRPTW becomes apparent as the dynamicity level of
instances increases. Thus, on almost all instances of 50% and
100% dynamicity, DVRPTW-ACS manages to obtain superior
solutions with less vehicles and of lower total distance than
MACS-DVRPTW. The better performance of our algorithm
is more noticeable on C201-0.5, C202-0.5, C101-1.0, C1021.0 and C201-1.0 instances, where the values attained by
DVRPTW-ACS on both objectives are almost half the ones
obtained by MACS-DVRPTW.
The values recorded by the two approaches for the increase
measure reveal the same good performance of DVRPTWACS. More precisely, it can be noticed that the solution
quality on DVRPTW instances with higher dynamicity of
50% and 100% is not influenced so much by the increase
in the dynamicity. Besides that, on instances with clustered
nodes such as C101-0.5, C101-1.0, C201-0.5 and C201-1.0,
DVRPTW-ACS is still able to attain the same good results as
obtained for the corresponding static instances, as indicated
by the zero values for the increase measure. In contrast to
this, MACS-DVRPTW yields on most instances higher values
for the increase measure. Also on some instances with higher
dynamicity such as R201-1.0, C201-0.5, C201-1.0, C202-1.0
and RC202-1.0, the value for increase measure in terms of
the number of vehicles is greater than or equal to 100, which
shows that the decline in the solution quality is significant.
Also, compared to the average number of vehicles required
on static instances, MACS-DVRPTW uses in addition up to 2
vehicles on instances of 10% dynamicity, on instances of 50%
dynamicity it uses at most extra 6 vehicles, and on instances
of 100% dynamicity it uses at most extra 10 vehicles. On the
other hand, our approach requires on average on all DVRPTW
instances, regardless of their dynamicity level, up to 2 extra
vehicles. This aspect shows that our algorithm manages to
cope better on instances of higher dynamicity, in which fewer
customers are known in advance and more nodes are revealed
in an ongoing fashion during the working day.
Figure 1 illustrates the distribution of the results of the two
algorithms with respect to the total distance objective. Yellow boxplots correspond to the results obtained with MACSDVRPTW, and green ones to DVRPTW-ACS. The results are
grouped based on the instance category and dynamicity level.
Analyzing the boxplots, it can be noticed that our algorithm
wins on instances from C category for all the dynamicity
levels. Also, on R and RC instances with low dynamicity,
DVRPTW-ACS is surpassed. However, on the same R and
RC instances having 100% dynamicity, DVRPTW-ACS out4 https://goo.gl/YbMGJx

performs MACS-DVRPTW. Besides that, the boxplots reveal
that the variance of DVRPTW-ACS is smaller, which indicates
a more stable algorithm.
We conducted two statistical tests, the Mann-WhitneyWilcoxon nonparametric test and the Student’s t-test (we
performed 30 runs for each algorithm), to assess if these
differences in the performance of the two approaches are statistically significant or not. The results obtained for the dynamic
instances in terms of the total distance objective, indicate
statistically significant differences on all DVRPTW instances,
excepting R202-1.0, RC102-0.5 and RC203-1.0. Also when
considering the number of vehicles objective, statistically
significant differences are recorded on all dynamic instances,
except for R202-0.1 and RC102-0.5. On static instances, only
for C102-0.0 the two statistical tests do not show significant
differences, in terms of the total distance objective. For the
number of vehicles objective, the results indicate statistically
significant differences on all static instances.
Correlating the values obtained for the considered measures
by the two investigated approaches, it can be stated that our
algorithm achieves the best overall performance on both objectives. Moreover, in some cases where DVRPTW-ACS does not
have such a good performance, the obtained values are close
to the ones attained by MACS-DVRPTW. This indicates that
our approach is competitive with the MACS-DVRPTW solver,
and on higher dynamicity instances DVRPTW-ACS is able to
yield better results.
The good performance of our approach can be ascribed
to its underlying joint mechanism employed in the transition
step of the ACS based algorithm, in which the vehicles’ tours
are constructed simultaneously. This offers better chances of
covering the available unvisited customers with the existing
vehicles, without needing to resort to additional vehicles. In
contrast to this, in MACS-DVRPTW the tours are constructed
sequentially and are filled up one by one with customers.
This aspect restricts the number of choices for adding an
unrouted customer, which may lead to using more vehicles.
Besides this, DVRPTW-ACS is coupled with a powerful insertion heuristic, being among the best heuristics proposed by
Solomon for VRPTW. Our insertion procedure manages to
better incorporate unvisited available customers in the tours
of existing vehicles, by searching for each unvisited node the
best insertion position. In this way, all the unvisited nodes
have equal chances and compete for being inserted in best
position within a vehicle’s tour. In contrast to this, in MACSDVRPTW the nodes are inserted sequentially into their best
position, according to a partial order of the customers, which
are sorted in descending order based on their demand.
In terms of the computational cost, the comparison of the
number of feasible solutions obtained by the two approaches,
reveals that for most of the DVRPTW instances, MACSDVRPTW computes more feasible solution than our algorithm.
This may be attributed to the fact that DVRPTW-ACS was
implemented in Java, whilst the MACS-DVRPTW solver was
coded in C, which may induce more rapid execution times.
Also, the relocation and exchange operators from our local

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
TABLE I
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON R1
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

R103-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

R104-0.0

R103-0.1

R104-0.1

AUTHOR VERSION

R103-0.5

R104-0.5

R103-1.0

R104-1.0

MACS-DVRPTW
NV
TD
10.933
1087.923
10
1046.225
11
1148.068
0.254
23.397
10
979.076
10
944.92
10
1007.948
0
15.742
10.367
1078.205
10
1026.682
11
1135.584
0.49
21.565
0
-1.868
10
969.424
10
934.079
10
996.333
0
16.031
0
-1.147
12.367
1153.761
12
1113.695
13
1199.753
0.49
20.675
20
6.449
9.133
976.452
9
933.443
10
1013.922
0.346
24.099
-10
-1.215
14.567
1327.262
14
1279.144
15
1390.228
0.504
29.899
40
22.263
9.8
1035.714
9
955.579
10
1092.117
0.407
29.13
-10
1.128

DVRPTW-ACS
NV
TD
14
1267.525
14
1246.521
14
1287.189
0
10.78
10.8
1072.18
10
1037.729
11
1107.054
0.407
16.243
14
1272.788
14
1248.78
14
1302.275
0
14.11
0
0.181
10.533
1059.812
10
1023.262
11
1108.842
0.507
17.035
0
-1.394
14
1301.596
14
1245.081
14
1350.338
0
22.676
0
-0.116
10.567
1097.715
10
1054.123
11
1168.38
0.504
25.714
0
1.58
14
1301.524
14
1267.567
14
1355.115
0
18.167
0
1.688
10.533
1103.916
10
1054.419
11
1161.368
0.507
24.571
0
1.608

search procedure are applied multiple times, and this involves
a higher computational cost, compared to the cross exchange
operator from MACS-DVRPTW, which is called only once.
This aspect indicates that the better performance of our algorithm on DVRPTW instances with higher dynamicity is not
due to a greater number of feasible solutions that it computes.

Fig. 1. Distribution of total distance objective for dynamicity levels ranging
in {0.1, 0.5, 1}; yellow is for MACS-DVRPTW, green is for DVRPTW-ACS.
Results are reported for each of the three problem classes (C, R, RC)

TABLE II
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON R2
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

R201-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

R202-0.0

R201-0.1

R202-0.1

R201-0.5

R202-0.5

R201-1.0

R202-1.0

MACS-DVRPTW
NV
TD
3.767
977.568
3
869.717
4
1154.818
0.43
77.168
3
928.359
3
846.279
3
1019.08
0
39.238
4.9
1075.4
4
966.55
5
1143.901
0.305
43.654
33.333
11.134
3.967
949.171
3
858.555
4
1044.958
0.183
46.793
0
1.451
5.933
1262.015
5
1171.521
6
1341.553
0.254
45.987
66.667
34.701
5.133
1148.596
5
1046.799
6
1233.396
0.346
48.095
66.667
23.694
7.2
1811.948
6
1625.431
8
1995.438
0.484
86.74
100
86.892
5.433
1249.129
5
1129.508
6
1415.06
0.504
54.7
66.667
33.468

DVRPTW-ACS
NV
TD
4.7
1307.182
4
1239.081
5
1414.325
0.466
47.917
4
1209.136
4
1157.297
4
1295.792
0
27.184
4.533
1308.653
4
1218.004
5
1433.059
0.507
56.646
0
-1.701
4
1196.264
4
1163.795
4
1255.849
0
22.327
0
0.561
4
1365.705
4
1323.148
4
1433.617
0
25.78
0
6.785
4
1229.833
4
1166.377
4
1349.382
0
34.816
0
0.785
4
1394.533
4
1357.513
4
1450.423
0
23.731
0
9.558
4
1247.435
4
1195.321
4
1323.849
0
33.132
0
3.286

VII. C ONCLUSIONS
In this paper, we have proposed an ACS based algorithm
to tackle the single-objective DVRPTW problem, which considers a hierarchy among the two objectives, minimizing the
number of vehicles having priority over minimizing the traveled distance. Experiments conducted on several DVRPTW
instances with different dynamicity levels, showed that our
algorithm is efficient and competitive with another ACO
based approach from the literature. Besides that, on DVRPTW
instances with a higher dynamicity, DVRPTW-ACS was able to
achieve better results than MACS-DVRPTW, in terms of both
objectives. Also, our algorithm proved to cope better on higher
dynamicity instances, since the decline in the solution quality
is not so significant, compared to the solution obtained for
the corresponding static instances. This makes our approach
more suitable to be applied on DVRPTW instances with a
higher dynamicity, in which few customers requests are a
priori known, case more likely to occur in real-world scenarios.
Possible avenues for future work include solving this prob-

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings

TABLE III
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON C1
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

C101-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

C102-0.0

C101-0.1

C102-0.1

AUTHOR VERSION

C101-0.5

C102-0.5

C101-1.0

C102-1.0

MACS-DVRPTW
NV
TD
10
828.937
10
828.937
10
828.937
0
0
10
857.087
10
829.133
10
899.302
0
19.344
11
1003.766
11
1002.601
11
1003.904
0
0.397
10
20.95
12
974.14
12
916.369
12
1087.706
0
38.088
20
10.521
16.667
1392.599
16
1293.749
18
1629.158
0.661
68.256
60
56.073
11.633
1170.861
11
1040.89
12
1273.721
0.49
61.062
10
25.54
20.167
2016.359
19
1879.521
21
2185.256
0.461
69.944
90
126.739
16.833
1521.483
16
1457.996
17
1596.63
0.379
36.923
60
75.846

DVRPTW-ACS
NV
TD
10
828.937
10
828.937
10
828.937
0
0
10
864.627
10
834.639
10
902.735
0
19.69
10
828.937
10
828.937
10
828.937
0
0
0
0
10
845.559
10
830.814
10
890.275
0
12.499
0
-0.458
10
828.937
10
828.937
10
828.937
0
0
0
0
10
868.538
10
828.937
10
932.31
0
25.149
0
-0.683
10
828.937
10
828.937
10
828.937
0
0
0
0
10
881.348
10
872.031
10
888.646
0
5.455
0
4.48

lem from a multi-objective perspective and extending this
research to tackle dynamic rich vehicle routing problems,
that can incorporate more complex constraints and objectives,
found in real-life VRPs.
ACKNOWLEDGEMENTS
We would like to thank to the authors of MACS-DVRPTW
solver [14] for providing us their source code, that allowed us to perform the comparison with our algorithm.
This work is partly funded from the European
Union's Horizon 2020 research and innovation
programme under grant agreement No 692178.
R EFERENCES
[1] K. Braekers, K. Ramaekers, and I. V. Nieuwenhuyse, ”The vehicle
routing problem: State of the art classification and review,” Computers
& Industrial Engineering, vol. 99, pp. 300-313, 2016.
[2] V. Pillac, M. Gendreau, C. Guéret, and A. Medaglia, ”A review of
dynamic vehicle routing problems,” European Journal of Operational
Research, vol. 225(1), pp. 1-11, 2013.

TABLE IV
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON C2
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

C201-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

C202-0.0

C201-0.1

C202-0.1

C201-0.5

C202-0.5

C201-1.0

C202-1.0

MACS-DVRPTW
NV
TD
3.767
619.148
3
591.557
4
675.307
0.43
20.922
3.267
670.613
3
605.298
4
734.512
0.45
37.403
4
626.003
4
622.535
4
650.237
0
9.014
33.333
5.237
4.033
689.57
4
626.809
5
797.32
0.183
49.843
33.333
3.554
6.133
899.03
6
814.258
7
1122.569
0.346
82.495
100
37.647
5.933
878.535
5
767.05
6
1008.27
0.254
75.38
66.667
26.723
7.233
1577.455
7
1339.839
8
1831.838
0.43
116.901
133.333
126.494
6.067
948.312
6
856.878
7
1126.274
0.254
77.829
100
41.563

DVRPTW-ACS
NV
TD
3
591.557
3
591.557
3
591.557
0
0
3
600.733
3
591.557
3
634.5
0
15.079
3
591.557
3
591.557
3
591.557
0
0
0
0
3
594.185
3
591.557
3
623.531
0
7.969
0
0
3
591.557
3
591.557
3
591.557
0
0
0
0
3
606.853
3
591.557
3
636.705
0
17.391
0
0
3
591.557
3
591.557
3
591.557
0
0
0
0
3
593.19
3
591.557
3
626.741
0
6.422
0
0

[3] R. Necula, M. Breaban, and M. Raschip, ”Performance evaluation of
ant colony systems for the single-depot multiple traveling salesman
problem,” in Proceedings of the 10th International Conference on Hybrid
Artificial Intelligence Systems, vol. 9121, pp. 257-268, 2015.
[4] R. Necula, M. Breaban, and M. Raschip, ”Tackling the Bi-criteria Facet
of Multiple Traveling Salesman Problem with Ant Colony Systems,” in
Proceedings of the 2015 IEEE 27th International Conference on Tools
with Artificial Intelligence, pp. 873-880, 2015.
[5] J. F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, and F.
Soumis, ”The VRP with time windows,” in P. Toth, D. Vigo (eds.) The
Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics
and Applications, pp. 157-194, 2001.
[6] O. Bräysy, and M. Gendreau, ”Vehicle routing problem with time
windows, Part I: Route construction and local search algorithms,”
Transportation Science, vol. 39(1), pp. 104-118, 2005.
[7] L. Gambardella, E. Taillard, and G. Agazzi, ”Macs-vrptw: a multiple
ant colony system for vehicle routing problems with time windows,” in
D. Corne, M. Dorigo, F. Glover, D. Dasgupta, P. Moscato, R. Poli, KV.
Price (eds.) New ideas in optimization, ch 5, McGraw-Hill, pp. 63-76,
1999.
[8] H. N. Psaraftis, M. Wen, and C. A. Kontovas, ”Dynamic vehicle routing
problems: Three decades and counting,” Networks, vol. 67(1), pp. 3-31,
2016.
[9] V. Ilin, D. Simić, J. Tepić, G. Stojić, and N. Saulić, ”A Survey of
Hybrid Artificial Intelligence Algorithms for Dynamic Vehicle Routing

2017 IEEE Congress on Evolutionary Computation (CEC) PREPRINT; the camera ready version will be published in IEEE proceedings
TABLE V
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON RC1
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

RC101-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

RC102-0.0

RC101-0.1

RC102-0.1

AUTHOR VERSION

RC101-0.5

RC102-0.5

RC101-1.0

RC102-1.0

[10]

[11]

[12]

[13]

[14]

[15]

[16]

MACS-DVRPTW
NV
TD
13.567
1419.259
13
1353.045
14
1514.738
0.504
36.447
11.967
1316.636
11
1278.533
12
1383.166
0.183
24.018
14.9
1499.454
14
1438.998
15
1569.396
0.305
33.063
7.692
6.353
11.167
1361.773
11
1279.555
12
1460.245
0.379
46.071
0
0.08
18.733
1947.191
17
1772.705
20
2124.249
0.828
85.384
30.769
31.016
14
1566.836
13
1471.19
15
1693.733
0.587
54.201
18.182
15.069
20.867
2219.684
19
2057.832
23
2453.04
0.819
86.721
46.154
52.089
16.433
1714.181
15
1613.665
17
1778.713
0.626
44.416
36.364
26.212

DVRPTW-ACS
NV
TD
15.1
1669.585
15
1649.803
16
1705.964
0.305
14.753
13.767
1538.879
13
1501.709
14
1589.491
0.43
21.2
15.267
1698.417
15
1666.823
16
1740.601
0.45
19.908
0
1.032
13.667
1563.956
13
1514.923
14
1629.863
0.479
22.929
0
0.88
15.133
1733.718
14
1669.847
16
1781.071
0.434
28.038
-6.667
1.215
13.933
1580.218
13
1540.802
15
1651.335
0.365
28.635
0
2.603
15.1
1720.723
15
1669.856
16
1781.512
0.305
26.007
0
1.215
13.9
1602.576
13
1551.439
15
1704.936
0.481
32.527
0
3.312

Problem,” in Proceedings of the 10th International Conference on Hybrid
Artificial Intelligence Systems, vol. 9121, pp. 644-655, 2015.
M. Gendreau, F. Guertin, JY. Potvin, and E. Taillard, ”Parallel tabu
search for real-time vehicle routing and dispatching,” Transportation
Science, vol. 33(4), pp. 381-390, 1999.
G. B. Alvarenga, R. M. de Abreu Silva, and G. R. Mateus, ”A hybrid
approach for the dynamic vehicle routing problem with time windows,”
in Fifth International Conference on Hybrid Intelligent Systems, pp. 6167, 2005.
J. de Armas, and B. Melián-Batista, ”Constrained dynamic vehicle
routing problems with time windows,” Soft Computing, vol. 19(9), pp.
2481-2498, 2015.
L. Hong, ”An improved LNS algorithm for real-time vehicle routing
problem with time windows,” Computers & Operations Research, vol.
39(2), pp. 151-163, 2012.
B. van Veen, M. Emmerich, Z. Yang, T. Bäck, and J. Kok, ”Ant
colony algorithms for the dynamic vehicle routing problem with time
windows,” in Natural and Artificial Computation in Engineering and
Medical Applications, vol. 7931, Springer, pp. 1-10, 2013.
Z. Yang, J. P. van Osta, B. van Veen, R. van Krevelen, R. van Klaveren,
A. Stam, J. Kok, T. Bäck, and M. Emmerich, ”Dynamic vehicle routing
with time windows in theory and practice,” Natural Computing, pp. 1-16,
2016.
Z. Yang, M. Emmerich, and T. Bäck, ”Ant based solver for dynamic
vehicle routing problem with time windows and multiple priorities,” in

TABLE VI
T HE VALUES OBTAINED BY MACS-DVRPTW

AND DVRPTW-ACS FOR
NUMBER OF VEHICLES AND TOTAL DISTANCE OBJECTIVES ON RC2
INSTANCES WITH 0%, 10%, 50% AND 100% DYNAMICITY

instance

measure

RC202-0.0

average
min
max
stdev
average
min
max
stdev
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)
average
min
max
stdev
increase(%)

RC203-0.0

RC202-0.1

RC203-0.1

RC202-0.5

RC203-0.5

RC202-1.0

RC203-1.0

[17]
[18]
[19]
[20]
[21]

MACS-DVRPTW
NV
TD
3
1004.369
3
893.646
3
1134.003
0
51.035
3
900.178
3
822.186
3
975.809
0
35.982
4
1044.917
4
952.876
4
1139.719
0
48.588
33
6.628
3
899.799
3
814.817
3
997.529
0
39.368
0
-0.896
4.833
1261.691
4
1146.6
5
1438.765
0.379
71.85
33.333
28.306
4.333
1123.38
4
1016.05
5
1235.297
0.479
50.062
33.333
23.579
6.7
1688.338
6
1460.384
7
1825.705
0.466
76.98
100
63.419
5.8
1231.181
5
1139.477
6
1334.584
0.407
41.599
66.667
38.591

DVRPTW-ACS
NV
TD
4
1301.551
4
1245.37
4
1366.973
0
32.926
4
1046.39
4
1011.552
4
1112.606
0
24.857
4
1291.909
4
1234.551
4
1343.794
0
29.813
0
-0.869
3.967
1076.276
3
1019.385
4
1216.303
0.183
41.685
-25
0.774
4
1340.959
4
1246.376
4
1440.575
0
47.483
0
0.081
3.1
1247.353
3
1122.897
4
1392.911
0.305
67.217
-25
11.007
3.967
1364.969
3
1277.912
4
1544.412
0.183
60.915
-25
2.613
3.067
1243.447
3
1097.193
4
1345.215
0.254
60.904
-25
8.466

2015 IEEE congress on evolutionary computation (CEC), pp. 2813-2819,
2015.
M. Dorigo, and L. M. Gambardella, ”Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE
Transactions on Evolutionary Computation, vol. 1(1), pp. 53-66, 1997.
M. Dorigo, V. Maniezzo, and A. Colorni, ”The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on
Systems, Man, and Cybernetics, Part B, vol. 26(1), pp. 29-41, 1996.
M. Solomon, ”Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35(2),
pp. 254-265, 1987.
L. M. Gambardella, and M. Dorigo, ”Solving symmetric and asymmetric
TSPs by ant colonies,” in Proceedings of the 1996 IEEE International
Conference on Evolutionary Computation, pp. 622-627, 1996.
M. W. P. Savelsbergh, ”The vehicle routing problem with time windows:
minimizing route duration,” Informs Journal on Computing, vol. 4(2),
pp. 146-154, 1992.

