International Journal of Computers, Communications & Control
Vol. I (2006), No. 4, pp. 110-125

Ant Colony with Dynamic Local Search for the Time Scheduling of
Transport Networks

Salah Zidi, Salah Maouche, Slim Hammadi

Abstract: This article presents an ant colony optimization for the time scheduling
of public transport traffic. In fact, the assistance of a decision support system
becomes necessary for the real-time regulation of this transport networks since the
size of the search space increases exponentially with the number of vehicles and
stops. So, we propose an ant colony algorithm with dynamic local search, in the
case of unpredictable disturbance. This approach consists in applying a local search
window with increasing dimension according to the iterations. It treats the regulation
problem as an optimization and provides the regulator with relevant decisions. A
regulated timetable is proposed as solution aiming at minimizing the waiting time of
passengers. We insure the three most important criteria of regulation which are the
punctuality, the regularity and the correspondence.

Keywords: urban transportation systems, real-time scheduling, ant colony optimiza-
tion.

1 Introduction

In real time, the transport system can be affected in an unpredictable way by incidents which cause a
delay between these theoretical time schedules and the real time schedules. In these conditions, we have
re-adjust the planning (time table) made at previous time to return quickly to the theoretical schedules.
It is a real-time regulation.

Within this context we developed an algorithm of scheduling which allows us to ensure the most
important three criteria: the punctuality, the regularity of passing of vehicles by stops as well as the
correspondence between the lines of the different transport modes. It is an ant colony algorithm where
the main goal is to find in every movement between two successive stops the delay which it is necessary
to apply to concerned vehicles to optimize these three criteria of regulation.

At the beginning, our regulation algorithm encountered difficulties to escape from local optima.
In fact, the optimization problem which we have to resolve is complicated and the research space is
important. To manage these difficulties we propose the idea of the dynamic local search. It is the new
method which consists in applying a local search window with increasing dimensions according to the
iterations.

This article contains five parts. In the first, we will present the regulation problem. The second part
is a presentation of the ant colony algorithm. In the third part we will detail our algorithm of regulation
and we will also explain the simulation results of this approach in the urban transport network of Lille.
We will finish by a conclusion.

2 Real-time regulation

The planning process of a public transport company is made by establishing different timetables that
describe trips according to the lines, frequencies, transport demand, and travel times in the network.
These trips are then transformed into blocks and assigned to vehicles. A crew scheduling process finally
follows this vehicle scheduling [1]. Hence, the vehicle schedules are fixed for every timetable period.
This type of vehicle scheduling is in fact called predictive scheduling. It is based on a periodic review

Copyright c© 2006 by CCC Publications



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 111

of demand and resource availability in order to create arrival and departure times for the vehicles at the
different stops of the network.

However, in reality, travel times and transport demands are not fixed because of random external
influences that affect the traffic within the network and cause disturbances. These disturbances can
be, for example, caused by traffic jams, accidents, or strikes. Consequently, the theoretical schedules
resulting from the planning process cannot be followed exactly, which compels trips to start late and
makes customers wait longer.

Therefore, to reduce the effects of the disturbances, the theoretical schedules have to be adapted
to the real traffic conditions through regulation, or rescheduling tasks [2]. This process is then called
reactive scheduling. It consists in creating new schedules that increase the level of service by undertaking
operational decisions, such as, the injection of an extra vehicle in the network, or the deviation of the
routes of some vehicles. The real-time traffic management of an urban transport system is presented by
the figure1.

Figure 1: Process of real time management of public transport traffic

Presently, it’s a human operator, regulator, who performs these real time tasks and controls the global
network traffic by treating the information provided by the Automatic Vehicle Monitoring (AVM) system
and the vehicle drivers. The level of service can be represented by different regulation criteria such as,
the regularity, punctuality, and connection criteria. The choice of the criteria depends on the regulation
objectives obtained from the nature of the disturbances. However, the regulator is usually overloaded
with information, which complicates its decision-making task. In addition, despite the AVM system
assistance, the regulator spends more than 50% of his work time in communication with the vehicle
drivers. Hence, the regulator has to carry out difficult tasks that are often inaccessible for the human
scale especially if many disturbances occur simultaneously, which involves the assistance of a decision
support system [3].

Within this context, researchers began to think about the development of a computer system for
the regulators by using different tools such as the fuzzy logic [4], the multi-agent system [5] and an
evolutionary algorithm [6].

In our work we will apply an approach of ant colony optimization and we will introduce a new idea
of dynamic local search.



112 Salah Zidi, Salah Maouche, Slim Hammadi

3 Ant Colony Optimization (ACO)

Ant colonies are able to organize their foraging behavior in a seemingly efficient way without any
centralized control[7]. This self-organizing structure is carried out via stigmergic communication, i.e.
communication by changing the environment, in this case by laying down pheromone trails. Initially ants
have no idea of where food is in the environment, so they wander randomly, leaving a pheromone trail.
When an ant finds food it wanders back to the nest. Initially these paths will be arbitrary, but when an
ant follows a shorter path it will be able to follow that path more often within the same time period than
an ant following a longer path, so there is a positive reinforcement process whereby the shorter paths get
stronger.

A simple version of this is illustrated in figure 2, where ants have two possible routes from a nest to
a food source. If two ants set out at the same time, one taking route A and one route B, which is twice as
long, then the ant taking A will have traveled back and forth between the food source twice in the same
time that the other ant has traveled back and forth once. Therefore there will be a stronger pheromone
trail on route A compared to route B. This idea can be effectively scaled up to solving route finding
problems such as the TSP, with performance as good as or better than existing heuristics.

Figure 2: A simple ant foraging problem.

The natural ants inspired "ant colony algorithms" invented in 1992 by Marco Dorigo from Free
Brussels University, in his Ph.D. thesis [8]. In an iteration of this algorithm, n ants build n solutions
according to decisions based on heuristics criteria and on the quantity of pheromone. This quantity is
updated by examining the solutions. It is strengthened for the decisions having given better solutions and
decreased for the others. This mechanism allows to improve gradually the solutions during the iterations.

The ants colony optimization were applied to divers problems of optimization such as the salesman
traveling problem [9], the problems of robotics [10], the industrial problems [11] as well as the CARP
(Capacitated Arc Routing Problem) in [12] and the rucksack problem [13]. And there are several versions
of the ants colony algorithm such as the Ant System [14], the Min-Max Ant System [15], the ASrank
[16] and the Ant Colony System [9].

4 Rescheduling algorithm

4.1 Notation

We use even notations in the horizon of regulation.
SH : Set of stops of the regulation horizon.
V H : Set of the vehicles in the horizon of regulation.
Srk: k

th stop situated on the line r.
V li : i

th vehicle in the line l .
Veh(V li , S

m
j , S

r
k): First successor of V

l
i at traveling S

m
j to S

r
k.

almi j : Stop variable of V
l
i atS

m
j .



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 113

X lmri jk : Destination variable of V
l
i from S

m
j to S

r
k.

talmi j : Arrival time of V
l
i at S

m
j .

tdlmi j : Departure time of V
l
i from S

m
j .

Nmont lmi j : Number of persons who go aboard V
l
i in S

m
j .

Ndesclmi j : Number of persons who come down of V
l
i in the stop S

m
j .

ρ ll
′m

ii′ j : Rate of correspondence from V
l
i to V

l′
i′ in S

m
j .

µ(∆ti, Smj , S
r
k): Arriving rate of the passengers traveling between these stops during ∆ti.

Nl
′mr

i′ jk : Number of passengers in V
l′
i′ traveling from S

m
j to S

r
k.

Y ll
′m

ii′ j : Variable of correspondence from V
l
i to V

l′
i′ in the stop S

m
j (equal 1 if a correspondence is possible

and 0 otherwise).
wll

′m
ii′ j : Number of transferring persons from V

l
i to V

l′
i′ at S

m
j .

Clmi j : Load of V
l
i at its departure from S

m
j .

AT: total time of waiting of the passengers in the regulation horizon.
AT0: Initial waiting time of passengers at the different stops of the regulation horizon according to the
disturbed schedules.
T T : Total duration of transfers in the regulation horizon.
T T0: Initial transfer or connection time between the different vehicles of the regulation horizon according
to the disturbed schedules.
RT : Total duration of Roads in the regulation horizon.
RT0: Initial route time for the different vehicles of the regulation horizon according to the disturbed
schedules.

4.2 Criteria of regulation

To have a good quality of service in a transport network, several criteria must Be assured during the
off-line planning and the on-line regulation such as the safety, the regularity, and the punctuality. In the
present problem, we chose the criteria of the regularity, the punctuality and the correspondence. They
are the most important and the most used by regulators and researchers.

Regularity

This criterion expresses the preservation of the regularity of the time intervals which separate the
successive passings of vehicles. It concerns the minimization of the passenger wait in stops.

The calculation of the traveler wait in a stop Smj depends on the interval separating two successive
vehicles and the number of travelers at this stop.

We suppose that in a given period of the day, V l
′

i′ is the vehicle succeeding V
l
i in the stop S

m
j . The time

interval which separates both passages is:

∆t = tal
′m

i′ j −tdlmi j (1)
We consider the distribution of the passenger arrivals, µSmj (t), to the stop S

m
j . We can then calculate,

according to the figure 3, the passenger wait, during t. (equation 2)

attente(∆t, Smj ) =
∫ ∆t

0
µSmj (t)(∆t −t)dt (2)

The distribution of the passenger arrivals to stops is often considered as a non-stationary process [6].
Besides, if we have reduced intervals (2 to 4 minutes) or situated in the homogeneous periods, we can
consider a constant passenger flow,µSmj . Consequently, the number of persons who arrive in S

m
j during ∆t

is µSmj ×∆tand the average wait becomes:



114 Salah Zidi, Salah Maouche, Slim Hammadi

attente(∆t, Smj ) = µSmj ×
∆t 2

2
(3)

Figure 3: Distribution of the passenger arrivals to a stop

In the case of a wider interval not belonging to a homogeneous period, it can be divided into several
reduced intervals to simplify the calculation of the traveler waits, ∆t =

⋃
I=1...N ∆tI . The number of

persons arriving in Smj during ∆tI with a rate of arrival equal to µI is µI ×∆tI . Their average wait is then:

attente(∆tI , Smj ) = µI ×∆tI ×(
∆tI
2

+
N

∑
I′=I+1

∆tI′) (4)

Indeed, the averages wait of the travelers who arrived during ∆tI is ( ∆tI2 + ∑
N
I′=I+1 ∆tI′). We can so

calculate the average wait during t at the stop Smj :

attente(∆t, Smj ) =
N

∑
I=1

µI ×∆tI ×(
∆tI
2

+
N

∑
I′=I+1

∆tI′) (5)

We can now formulate, in the following equation, the total wait, at the stop Smj , of the travelers
who go to Srk during the interval ∆t which separates the successive passages of both vehicles V

l
i and

V l
′

i′ (V
l′
i′ = Veh

+(V li , S
m
j , S

r
k)).

attente(∆t, Smj , S
r
k) =

N

∑
I=1

µ(∆tI , Smj , S
r
k)×∆tI ×(

∆tI
2

+
N

∑
I′=I+1

∆tI′) (6)

The duration of the wait of all the passengers at Smj is then the sum of the waits for all the vehicles
which pass by this stop, as described below:

attente(Smj ) = ∑
V li ∈V h

(almi j × ∑
Srk>S

m
j

attente(tal
′m

i′ j −tdlmi j , Smj , Srk)) (7)

Finally, because the criterion of regularity is concerning the total wait, AT, of passengers at stops in
the regulation horizon, this AT is then formulated in equation 8 and 9 by adding the wait at the different
concerned stops.

AT = ∑
Smj ∈Sh

attente(Smj ) (8)

AT = ∑
Smj ∈Sh

∑
V li ∈V h

(almi j × ∑
Srk>S

m
j

attente(tal
′m

i′ j −tdlmi j , Smj , Srk)) (9)



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 115

Correspondence

The correspondence criterion is associated to the duration of transfers between vehicles in the dis-
rupted zone. We can suppose that the number of persons in transfer at stop Smj is proportional to the

passenger number who go to this stop with the rate ρ ll
′m

ii′ j so w
ll′m
ii′ j = ρ

ll′m
ii′ j ×Ndesclmi j .

We can deduct the total duration of transfers, TT, who is equal to a sum of the durations of the
correspondences between the various vehicles at the concerned stops of the network (equation 10).

T T = ∑
V li ∈V h

∑
V l
′

i′ ∈V h
∑

Smj ∈Sh
Y ll

′m
ii′ j ×wll

′m
ii′ j ×(tdl

′m
i′ j −talmi j ) (10)

Punctuality

The punctuality criterion deals with the route duration of the different vehicles. It is computed after
an estimation of the vehicle loads via the arrival rates of the passengers at the stops, and also the initial
real loads that are assumed known. Hence,

RT = ∑
V li ∈V h

∑
Smj ∈Sh

almi j ×Clm
′

i j′ ×(tdlmi j −tdlm
′

i j′ ) (11)

In fact, the loads are determined by the number of the alighting and boarding persons, according to
the arrival rates or to the origin destination matrix. It can be written as

Clmi j = C
lm′
i j′ −Ndesclmi j + Nmont lmi j (12)

4.3 Principle of the rescheduling algorithm

At first, we have a set of stops and routes of the disrupted zone. We add for every inter-stop (route
chosen between two successive stations) a set of fictitious arcs which don’t have a physical existence
but we consider them as delays to be applied to this road. In the figure 4, for example, we dispose of 5
arcs between every two successive stops. The first arc presents the real arc with 0 minutes of delay and
the others possess 1, 2, 3 or 4 minutes of delay witch we can consider in one of both stops or in a route
between these stops.

Figure 4: Graphic presentation of the decision arcs

The objective of the ant colony algorithm is to find the delay to be applied for every vehicle, with
the aim to finding the schedules that satisfy the different criteria then propose a regulated timetable. So,
for every vehicle ants move between stops and search the best arcs (delay) to be taken, until the arrival
terminus. An ant has to propose all the delays which it is necessary to apply between the departure and
the arrival.



116 Salah Zidi, Salah Maouche, Slim Hammadi

4.4 Objective function

The Objective Function to optimize is an aggregation of three criteria representing the total travel
time, total waiting time, and total transfer time. This aggregation relies on weight parameters repre-
senting the relative importance of the criteria according to the disturbances and the regulator objectives.
For instance, if no connection is involved in the disturbance, the weight parameter associated with the
transfer criterion would be surely null. Hence, the objective function to maximize is written as

f =
c=3

∑
c=1

αcCrc (13)

Where
Cr1 = (AT0 −AT ): for the regularity,
Cr2 = (T T0 −T T ): for the transfer (correspondence),
Cr3 = (RT0 − RT ): for the punctuality, α1, α2andα3 weight parameters for the regularity, transfer and
punctuality criteria, respectively and ∑−13αc = 1.

4.5 Generation of a new solution

From a stop s and with the probability P, an ant uses the first method witch chooses an arc i with the
probability P1 described by the equation (14). In that case we give the same probability to the k arcs (in
our case k=5) to be chosen. This choice allows us a better exploration of the research space.

P1 =
{

1
k if i ∈ Ωs
0 otherwise

(14)

With the probability 1-P, the ant uses the second method, more intelligent than the first. That is by
regard to the pheromone trail, τ(t). And it chose an arc according to the probability given by the equation
(15).

P1 =

{
[τi(t)]

∑kj=1[τ j (t)]
if i ∈ Ωs

0 otherwise
(15)

Where Ωs is a set of arcs witch have a stop s as departure.

4.6 Update of pheromone trail

By analogy with the nature, every ant leaves a quantity of pheromone on every chosen arc. We
reinforce the pheromone trail on the chosen arcs by taking into account vaporization. That is represented
by the equation (16), which includes a term of persistence ρ and a term of strengthening ∆τa, it is a
quantity added by an ant a.

τi(t + 1) = ρ τi(t) + ∑
allants

∆τa (16)

Where ∆τa = fa is the objective function of the solution proposed bay the ant a.

4.7 Algorithm structure

Every ant moves from a stop to the other, by using the method of generation of solution described
previously, and it adds this arc to its road, until the terminus stop, then the ant begins again from the
departure stop for all the vehicles of the disrupted zone. As soon as the ant chose the regulation decision
(the delay) to apply to every vehicle, we build the new regulated timetable and we calculate the three
criteria: the regularity, the punctuality and the transfer then the objective function which we compare



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 117

with those found by the previous ants and we keep the best (maximal). When all the ants treat all the
transport services we update the pheromone trail on every arc. The algorithm structure is presented by
the figure 5.

Figure 5: Ants colony Algorithm for the regulation

We stop the algorithm when the best solution found by ants is unchanged since a number of iteration
I1 or a maximum number of iteration I2 is attained.

4.8 Dynamic local search

To escape from local optima, the methaheuristic algorithms showed an important efficiency. But,
many difficulties persist for the more intricate problems and the wide research areas. We proposed in
the first algorithm, in the paragraph IV, the second solution based on research idea. According to our
early execution tests related to the second algorithm, in the paragraph V. C, we noticed that the unequal
decisions to zero (the delays to be applied) are always located in a part of the disrupted spatiotemporal
zone. So, we adopted another way based on local research, which is one of the most applied ideas with
ant colony algorithms [12] as well as other heuristics such as the genetic algorithms [17]. This idea,
which shows promising results, is based on a procedure that aims to improve the found solutions. In fact,
this idea deals with a restricted research area, where the early solutions are located. Nevertheless, we
still have the problem of bumping into local optimums areas, which leads us to poor quality solutions.
So, we used a new idea of dynamic local research.

This idea aims at restricting the research area by means of spatiotemporal windows with increasing
dimension according to the iterations. We begin the investigation in a small zone of the research space
and we look for decisions, which can be different from zero on this zone, but we apply only the zero



118 Salah Zidi, Salah Maouche, Slim Hammadi

Figure 6: Rescheduling ant colony algorithm with dynamic local search



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 119

decision delay on the rest of the research space. After some iteration, we increase the spatiotemporal
dimensions of this zone and we investigate the research space for new solutions. After that, we com-
pare the results and we continue to increase the local search zone, after some iteration, until we get a
dimension equals to the complete space.

The figure 6 shows our improved algorithm comparing to the one illustrated in figure 5. This algo-
rithm includes the research process with increase of the zone. In fact, we try to look for optimal decisions
included between s1 and s2 stations (spatial limitation), and t1 and t2 times (temporal limitation). We
affect the decision zero outside of this zone. After some iteration, we decrease a station for s1 and we
add a station for s2 to increase the spatial zone and we make same for the temporal window. Without
initializing the pheromone trails, the solutions of the first zone will be more strengthened than the others
and therefore they will have more chance to be chosen.

5 Simulation and result

We applied this work to scenarios inspired from a real transportation system existing in Lille, in the
north of France. We used an algorithm with 100 ants and two maximal number of iteration I1=10 and
I2=500 and a probability P=10%.

5.1 Scenario1

In the line 0 which has a frequency of one bus every 10 minutes. A disturbance, caused by the
vehicle V 03 , is detected at tpert=12:01am, at its departure from the stop S

0
2. The incident consists of a

traffic accident between two cars, what slows down vehicles. The delay of the disrupted vehicle at its
arrival in S03 is estimated to 5 minutes. We suppose that no correspondence is involved in the disturbance.
So, we are only interested in the criteria of regularity and punctuality. We assume that the studied horizon
is included in a homogenous period of the day. Then, we can have a constant arrival rate of passengers
at all the stations. Let µ = 2 passengers per minute.

S00 S
0
1 S

0
2 S

0
3 S

0
4 S

0
5 S

0
6 S

0
7

V 00 0 0 0 0 0 0 0 0
V 01 0 0 0 0 0 0 0 0
V 02 0 0 0 0 0 0 0 0
V 03 0 0 0 0 0 0 0 0
V 04 0 0 0 0 0 0 0 0
V 05 0 0 0 0 0 0 0 0
V 06 0 0 0 0 0 0 0 0

Example 1: α1 = α2 = 0andα3 = 1 f = 0
V 00 0 0 0 0 0 0 0 0
V 01 0 0 0 0 0 0 0 0
V 02 0 0 0 0 0 2 1 0
V 03 0 0 0 0 0 0 0 0
V 04 0 0 0 3 0 0 0 0
V 05 0 0 0 1 0 0 0 0
V 06 0 0 0 0 0 0 0 0
Example 2: α1 = 1andα2 = α3 = 0 f = 160

Table 1: Results of the monocriterion regulation



120 Salah Zidi, Salah Maouche, Slim Hammadi

The table 1 shows the delays to be applied to the vehicles of the regulation horizon. They involve
decisions proposed by our ant colony algorithm for a regulation. For the first two examples, we consider
a monocriterion regulation where we optimize only the punctuality in the first and the regularity in the
second.

In the example1, the optimal solution for the punctuality can correspond only to null decisions in all
the compartments of table. So, we had a null objective function f. In the example 2 the algorithm can
allow to delay vehicles to adjust the intervals which separate them. We notice that vehicles V 02 and V

0
4 ,

before and after the disrupted vehicle, were delayed 3 minutes and V 05 was delayed 1 minute.

Figure 7: Vehicles schedules representation for the example 2 scenario 1

The figure 7 shows the efficiency of the scheduling algorithm to insure the regularity of vehicles in
the perturbed zone.

S00 S
0
1 S

0
2 S

0
3 S

0
4 S

0
5 S

0
6 S

0
7

V 00 0 0 0 0 0 0 0 0
V 01 0 0 0 0 0 0 0 0
V 02 0 0 0 0 1 0 0 0
V 03 0 0 0 0 0 0 0 0
V 04 0 0 0 1 0 0 0 0
V 05 0 0 0 0 0 0 0 0
V 06 0 0 0 0 0 0 0 0

Exp 3: α1 = 0.9α2 = 0α3 = 0.1 f = 20.89
V 00 0 0 0 0 0 0 0 0
V 01 0 0 0 0 0 0 0 0
V 02 0 0 0 0 3 0 0 0
V 03 0 0 0 0 0 0 0 0
V 04 0 0 0 3 0 0 0 0
V 05 0 0 0 1 0 0 0 0
V 06 0 0 0 0 0 0 0 0
Exp 4: α1 = 0.98α2 = 0α3 = 0.02 f = 132.78

Table 2: Results of the multicriteria regulation

The example 3 favors the punctuality criterion, although α1 < α3. We notice a difference with the
example 2 in the number of treated decisions. Indeed, only vehicles V 02 and V

0
4 have to be delayed 1

minute and we find an objective function f = 20,89. In the example 4 the result is very similar to the



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 121

example 2. Indeed, V 02 and V
0
4 were delayed 3 minutes as in the example 2, but for the vehicle V

0
2 the

delay is applied in S04 instead of and because the passenger number in these stops is more important thus
a delay in is more interesting for the punctuality. We had f=132.78. In this first scenario the time of
execution is always between 7 and 8 seconds.

5.2 Scenario2

The disturbance is detected at tpert=12:24. It is caused by a technical problem at the tram line T,
obliging the tram V T3 to stand still 7 min at stop S

T
2 . This tram-line has a frequency of one vehicle per

10 min. The stop is situated at 10 min from a connection node, N, where a connection is planned at
12:40 with a bus from line B, which has a frequency of one bus every 20 min. However, because of the
disturbance, it would arrive at 12:43 at N, so the connection would not occur.

We assume that the studied horizon is included in a homogenous period of the day. Then, we can
have a constant arrival rate of passengers at all the stations (µ = 2). Additionally, we assume that the
connection rates between the two concerned lines are constant. Hence, we suppose that the number of
passengers in the tram arriving at the node and willing to take a bus on line is proportional to the load of
the tram with a rate of 10%. and, the connection rate from the buses to the trams is 20%.

We applied our algorithm for a first example which takes into account the regularity criterion (table
3). The best solution is obtained within 20 s with a maximal value of the objective function f=362
passengers-minute, that is a decrease of wait of 10 minutes for more than 36 passengers. We notice the
important number of decisions (delays) for the disrupted line (T) to adjust the intervals before and after
the disrupted vehicle.

Line T
ST0 S

T
1 S

T
2 S

T
3 N S

T
5 S

T
6 S

T
7 S

T
8

V T0 0 0 0 0 0 0 0 0 0
V T1 0 0 0 3 0 0 3 0 0
V T2 0 0 0 0 0 0 0 0 0
V T3 0 0 3 2 0 0 0 1 0
V T4 0 0 0 3 0 0 1 0 0
V T5 0 0 0 0 0 0 0 2 2
V T6 0 0 0 0 0 0 0 0 0

Line B
SB0 S

B
1 S

B
2 S

B
3 N S

B
5 S

B
6 S

B
7 S

B
8

V B0 0 0 0 0 0 0 0 0 0
V B1 0 0 0 0 0 0 0 0 0
V B2 0 0 0 0 0 0 0 0 0
V B3 0 0 0 0 0 0 0 0 0
V B4 0 0 0 0 0 0 0 0 0

α1 = 1α2andα3 = 0

Table 3: Results of example1 for scenario 2

The second example concerns the transfer criterion (table 4). So, the delays were applied before the
stop N and we had an objective function f=208.

The figure 8 shows the efficiency of the scheduling algorithm to insure the correspondence in the
perturbed zone.

We executed the algorithm also in other multicriteria example where α1 = 0.4, α2 = 0.58 and α3 =
0.02. We had a decrease of the decisions number (not equal to zero) because the punctuality criterion



122 Salah Zidi, Salah Maouche, Slim Hammadi

Line T
ST0 S

T
1 S

T
2 S

T
3 N S

T
5 S

T
6 S

T
7 S

T
8

V T0 0 0 0 0 0 0 0 0 0
V T1 0 0 0 0 0 0 0 0 0
V T2 0 0 0 0 0 0 0 0 0
V T3 0 0 0 3 3 0 0 0 0
V T4 0 0 0 0 0 0 0 0 0
V T5 0 3 0 3 0 0 0 0 0
V T6 0 0 0 0 0 0 0 0 0

Line B
SB0 S

B
1 S

B
2 S

B
3 N S

B
5 S

B
6 S

B
7 S

B
8

V B0 0 0 0 0 0 0 0 0 0
V B1 0 0 0 0 0 0 0 0 0
V B2 0 0 0 2 0 0 0 0 0
V B3 0 0 0 0 0 0 0 0 0
V B4 0 0 0 0 0 0 0 0 0

α1 = 0α2 = 1andα3 = 0

Table 4: Results of example 2 for scenario 2

Figure 8: Vehicles schedules representation for the example 2 scenario 2



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 123

and we had f=104.

5.3 Comparison between both rescheduling ant colony algorithms

We applied both rescheduling algorithms, without local search and with dynamic local search, for
real transport scenarios. We present in the table 5 the results of these simulations. We notice that the
algorithm with dynamic local search is faster. Its execution time is always lower than the first algorithm,
with same number of iteration. The ant colony algorithm with the dynamic local search space proposes
an important improvement of solutions with regard to the algorithm without local search.

Ant Colony Algorithm (ACA) ACA with dynamic local search
Scenario Example f Execution time (ms) f Execution time (ms)

1 1 0 7390 0 7390
2 160 7157 182 6922
3 20.89 7047 20.89 6890
4 132.78 7468 132.94 6860

2 1 192 10094 212 10000
2 526.4 10150 533.99 8290
3 394 10000 391.956 9370

3 1 362 28000 362 29000
2 208 31000 232 22800
3 104.88 28930 104.88 28060
4 114.39 28.31 115.23 26040

4 1 192 10500 192 7828
2 290 10109 310 8578
3 0 5000 0 5000
4 74.8 8700 74.8 8672

Table 5: Results of the both rescheduling ant colony algorithms

For the found optima, we notice that it is also effective. In fact, the results of the algorithm with
dynamic local search are better than the author 7 times on 15 examples. The local search allows us to
win in execution times and in search space exploitation. In fact, it is easier and faster to look for optima
in a smaller zone. This parameter time is very important for our real time problem of regulation. But also
the idea of the dynamic dimension allows us more investigation than the idea of the classic local search.

6 Conclusion

The disturbance of a transport system affects, first of all, the vehicle schedules. In this article we
presented an ant colony algorithm for the time-based regulation of a multimodal transport network, in
real-time. The results of this algorithm applied to real scenarios of transportation system existing in
Lille, showed the efficiency of our approach. The execution time is also important. Indeed our objective
consists in proposing quickly a solution before the propagation of the disturbance.

For a set of five stops, for example, for every vehicle there are 44 = 254 possible solutions. So it
is a complex problem. And we also noticed problems of convergence of our algorithm because of the
important dimension of the research space. The idea of the dynamic local search allowed us to win
in the execution times but also the improvement of the solutions without decreasing the search space
exploration and exploitation.



124 Salah Zidi, Salah Maouche, Slim Hammadi

References

[1] D. Huisman, R. Freling, and A. P. M.Wagelmans, "A dynamic approach to vehicle scheduling,"
Econometric Inst., Erasmus University, Rotterdam, The Netherlands, Rep. EI2001-17, 2001. begin
comment

[2] S. Maouche, H. Laichour, S. Hayat, "amélioration de la qualité de correspondances dans les réseaux
de transport", rapport final GRRT, avril 2001.

[3] P. Borne, B. Fayech, S. Hammadi and S. Maouche, "Decision Support System for Urban transporta-
tion networks", IEEE SMC Part C: Applications and Reviews, Special Issue on Decision Technolo-
gies in honour of Prof Madan Singh, Vol.33, No.1, pp.67-77, 2003.

[4] A. Soulhi, "Contribution de l’intelligence artificielle à l’aide à la décision dans la gestion des sys-
tèmes de transport urbain". Thèse de doctorat, université des sciences et technologies de Lille,
France, 2000.

[5] H. Laichour, " Modélisation multi-agent et aide à la décision : Application à la régulation des
correspondances dans les réseaux de transport urbain". Thèse de doctorat, université des sciences
et technologies de Lille, France, 2002.

[6] B. Fayech, "Régulation des réseaux de transport multimodal : systèmes multi-agent et algorithmes
évolutionnistes", Thèse de doctorat, université des sciences et technologies de Lille, France, 2003.

[7] J. D. Moss and C. G. Johnson, "An ant colony algorithm for multiple sequence alignment in bioin-
formatics", In David W. Pearson, Nigel C. Steele, and Rudolf F. Albrecht, editors, Artificial Neural
Networks and Genetic Algorithms, pages 182-186. Springer,April 2003.

[8] M. Dorigo,"Optimization, Learning and Natural Algorithms". Ph.D.Thesis, Politecnico di Milano,
Italy, in Italian, 1992.

[9] M. Dorigo and L. M. Gambardella, "Ant Colonies for the Traveling Salesman Problem". BioSys-
tems, 43:73-81. Also Tecnical Report TR/IRIDIA/1996-3, IRIDIA, Université Libre de Bruxelles,
1997.

[10] N. Monmarché, "Algorithme de fourmis artificielles : application à la classification et à
l’optimisation", Thèse à l’université de François Rabelais Tour, 2000.

[11] C. Gagné and W. L. Price, "Optimisation par colonie de fourmis pour un problème
d’ordonnancement industriel avec temps de réglages dépendants de la séquence". 3e Conférence
Francophone de MOdélisation et SIMulation MOSIM01, Troyes (France), 2001.

[12] P. Lacomme, C. Prins, A. Tanguy, "Optimisation par colonies de fourmis pour les tournées sur
arcs". 4e Conférence Francophone de MOdélisation et SIMulation MOSIM03, Toulouse (France),
2003.

[13] I. Alaya, C. Solnon and K. Ghédira, "Algorithme fourmi avec différentes stratégies phéromonales
pour le sac à dos multidimensionnel", MHOSI’05, Hammamet, Tunisie, 2005.

[14] 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, 26(1):2941, 1996.

[15] T. Stutzle and H. Hoos. MAX-MIN Ant system and local search for combinatorial optimization
problems. In S. Vos, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances
and Trends in Local Search Paradigms for Optimization, pages 137-154. Kluwer, Boston, 1998.



Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks 125

[16] B. Bullnheimer, R. F. Hartl, and C. Strauss. "A new rank-based version of the ant system: a com-
putational study". Technical Report POM-03/97, Institute of Management Science, University of
Vienna, Accepted for publication in the Central European Journal for Operations Research and
Economics, 1997.

[17] P. Lacomme, C. Prins and W. Ramdane-Chérif "Competitive genetic algorithms for the Capacitated
Arc Routing Problem and its extensions", in E.J.W. Boers and al. (ed.), Applications of evolutionary
computing, pp. 473-483, Lecture Notes in Computer Science 2037, Springer, 2001.

acknowledgement:
the authors want to acknowledge the support of the EU thought the FEDER grant #
OBJ2-2005/3-4.1-253PRESRGE-7820

Salah ZIDI, Salah MAOUCHE and Slim HAMMADI
Université des Sciences et Technologies de Lille and Ecole centrale de Lille

UFR I.E.E.A.
Bâtiment P2, Bureau 308 UFR I.E.E.A. Cité Scientifique 59655 Villeneuve dÁscq Cedex France

E-mail: salah.zidi@ed.univ-lille1.fr, salah.maouche@univ-lille1.fr, slim.hammadi@ec-lille.fr

Received: November 11, 2006