A DISTRIBUTED MULTI-CRITERIA APPROACH FOR TRAFFIC REGULATION IN PUBLIC TRANSPORTATION SYSTEMS

Abstract

Given the dynamic character of public transportation systems, it is difficult to respect accurately theoretical timetables. In real conditions, many disturbances may occur in transportation networks and cause troubles in vehicle schedules. In order to keep transportation systems as stable as possible, a real-time traffic regulation has to be performed by optimizing some regulation criteria that represent exploitation objectives. In this article, we deal with the regulation problem as a multi-criteria optimization one for which we propose a nonaggregative approach based on multi-agent systems. For a given disturbance, the approach firstly ensures an anytime generation of Pareto solutions set by using a distributed Tabu search. Then, the best compromise solution is determined through a multi-criteria evaluation process. Therefore, two multi-criteria evaluation procedures are also suggested: Plurality voting procedure and fuzzy-based procedure. In order to assess the distributed approach, an experimental study was performed on the base of real scenarios.

For economical and social reasons, the public transportation field has aroused most interest during the two last decades. In fact, the public transport demand was intensified given the rising density of population in urban areas. Hence, transportation managers have to face difficult traffic conditions in their daily activities. In order to support managers, many research works aiming to develop efficient tools have been carried out. These tools concern two different levels of decision-making: tactical level and operational level.

At the tactical level, theoretical timetables are generated on the basis of a predictive analysis of transport demand, traffic conditions, and resource availability, and under some constraints. In real-time, an adaptation of predictive schedules to real conditions has to be performed in order to overcome disturbances (traffic jams, accidents, vehicle breakdown, etc.). This operational level of decision-making is known as real-time regulation. In the regulation process, efficient operational decisions have to be undertaken by considering a number of regulation criteria that represent exploitation objectives. The complexity of this task expands when many disturbances appear simultaneously in the network and especially when regulation criteria are conflicting. Given this multi-criteria aspect of the regulation problem, we chose to designate it as a multi-criteria regulation problem (MRP).

The purpose of this article is to study the regulation problem from a multi-criteria point of view in order to improve the decision quality and to consider concurrently all the exploitation objectives. Our contribution for the MRP consists of proposing a distributed approach based on multi-agent systems. The approach deals with the regulation problem as a multi-criteria optimization and uses a nonaggregative method to solve it. It consists of generating a set of Pareto decisions for a detected disturbance, given a number of criteria to be optimized simultaneously by using a distributed Tabu search. Then, the best compromise decision is determined by considering the criteria set. In order to ensure these two steps, agents of the proposed approach cooperatively apply the concepts of Pareto optimality, nondominance, plurality voting, and fuzzy preference relations.

TRAFFIC CONTROL IN PUBLIC TRANSPORTATION SYSTEMS

Due to the significant increase of passenger flow and routes number, traffic control in public transportation networks has become more and more complex. We distinguish two scheduling problems that have received much attention in literature: predictive scheduling (or traffic planning) and reactive scheduling (or traffic regulation).

Predictive Scheduling

Predictive scheduling is defined by Harker and Ward (1991) as a periodic timetable constructed for governing arrival and departure times based on a periodic analysis of demand levels and resource availability. In fact, given the highly competitive market, each transport company has to determine the best use of infrastructure, crew, and vehicles. Hence, market characteristics are used to specify vehicles routes, itineraries, trips, service type, departure time, and interconnections between lines. The traffic planning process is generally defined by four steps (Boudali, Ben Jaâfar, and Ghédira, 2008). In the first step, vehicle routes and service frequencies are specified on the basis of an Origin-Destination (O-D) matrix estimation by considering different time periods (hours, days, months, and years). These estimations are used to determine passenger flows between locations so to enable evaluating the demand for transport services as well as the required supply.

In the second step, we find trips production. In fact, a number of trips are created given the set of vehicle routes, the required service frequencies, and route durations between stops. The resulting trips are then assigned to vehicles. So, a set of trips-vehicle are generated. In the last step, a crew allocation is performed given the available human resources.

Planning the efficient use of available resources through exploring the scheduling problems in an integrated environment, with iterative interaction between trips production and predictive allocation of other resources (vehicles and crew), is another important aspect of constructing predictive schedules.

Once theoretical schedules have been finalized formally, they are published to provide customers with the information and opportunity to plan their transportation needs in advance (Isaai and Cassaigne, 2001). In addition, these schedules are updated in the Exploitation Support System (ESS) in order to offer a permanent representation of theoretical network state.

Generally, timetable planners use distance-time graphs to represent timetables. The stations are listed along the vertical axis and are separated in proportion to their actual distance apart. The horizontal axis shows a time span. Each sloping line represents a scheduled vehicle, with the slope of the line representing the vehicle average speed (see Figure 1). The sloping lines include horizontal parts to show the stop duration of vehicles at stations.

FIGURE 1 Representation of a timetable as a distance-time graph.

The purpose of such graphs is to facilitate the communication of information between planners during and after the scheduling process and to help them in illustrating the spatial and temporal vehicle positions. The predictive scheduling process previously discussed shows the complexity of the planning task mainly in the case of multimodal networks where interconnections have to be considered. Hence, many research works have been carried out to address the related scheduling problems (route construction, vehicle scheduling, crew scheduling, etc.) (Chierici, Cordone, and Maja, 2004; Cipriani, Petrelli, and Fusco, 2006; Yan, Chi, and Tang, 2006).

Reactive Scheduling

In the real world, given the uncertain and variable transport environment, predictive schedules are often disrespected. In fact, random and complex influences related to traffic conditions, transport demand, and travel times may occur and cause disturbances that result either in a delay or in advance of vehicles schedules. Consequently, theoretical schedules that were pre-established on the basis of estimations and approximations of traffic conditions become improper to real traffic circumstances. In order to overcome these disturbances and to prevent the deterioration of service quality, an adaptation of predictive schedules to real conditions has to be performed through a reactive scheduling or regulation process. Hence, traffic management in transportation networks is not restricted to a planning step performed in an anticipated time. A traffic regulation process is performed in real-time, in order to handle the gap between predictive and real timetables. The regulation process embraces different tasks varying from disturbance analysis to decision-making. We arranged these tasks into three major phases, as shown in Figure 2: diagnosis phase, decision phase, and information phase.

FIGURE 2 Traffic regulation process.

The first step consists of detecting and analyzing the disturbance in order to determine its characteristics and its spatial and temporal horizon. This task is performed by means of ESS, which provides a global view of network traffic and compares a theoretical network state to a real one (Carlsson and Turban, 2002).

In the decision phase, potential alternatives are initially generated given the disturbance's characteristics. Then, the regulator chooses the most appropriate one that optimizes some regulation criteria and respects some constraints. The complexity of these tasks amplifies when many disturbances appear simultaneously in the network, when many entities (vehicles, conductors, stops, etc.) are involved, and mainly, if interconnections are implicated. Finally, information related to the selected decision (new schedules, change of itineraries, etc.) are published to network actors concerned with the disturbance (vehicle drivers, travelers, etc.) and are updated in the ESS.

RELATED WORK

Several research works have been proposed to deal with the regulation problem. Some of these works approached the problem using exact methods. In this context, we can cite the contribution of Adenso-Diaz, Gonzalez, and Gonzalez-Torre (1999) and Adenso-Diaz, Tuya, Cabal, and Goitia (2002) who propose a decision support system (DSS) for the rescheduling of railway services under unplanned events by applying a branch and bound algorithm for the exploration of the search space. Other works are based on heuristic approaches like the case of Missikoff (1998) who applied A∗ and hill-climbing heuristics to address the detected conflicts in the network. Moreover, metaheuristics such as genetic algorithms were used for the regulation problem. In this context, we can mention the works of Aloulou (1999) and Borne, Fayech, Hammadi, and Maouche (2003).

Knowledge-based approaches were also suggested to deal with the regulation problem. We can cite, for instance, the contribution of (2001) and the works of (2000) who propose a fuzzy knowledge-based system for railway traffic control. Balbo and Pinson (2008) suggest a dynamic modeling of disturbances that occur in a bus line. This modeling allows the synthesis, evaluation, and update of available information to help regulators in their monitoring task (, 2005). Furthermore, Ossowski et al. (2005) present a DSS for traffic management based on organizational and communicative multi-agent abstractions.

Most of these works were interested on the regulation of only one transportation line. Connection between lines is often treated separately (Laïchour, Maouche, and Mandiau, 2001). Another important feature of these works is the consideration of one or two regulation criteria that are optimized through aggregation methods (generally the weighted sum method) (Adenso-Diaz et al., 1999; Adenso-Diaz et al., 2002; Borne et al., 2003; Aloulou, 1999). Hence, the initial problem is transformed into a monocriterion one. The advantage of this aggregative approach is its leading into well-known mathematical problems which can be solved by using classical optimization methods. However, this approach relies on hard hypothesis that are not representative of reality. In fact, it assumes the entirety of the final solution (only one best solution), whereas when many criteria are considered, it is difficult to reach them at the same time. In addition, it presumes that all the solutions are exclusives, while solutions are often complementary, partial, and rarely global given the conflicting aspect of criteria. Moreover, this approach assumes the stability of the decisions set, while new ideas and new information could emerge during the problem analysis. Consequently, instead of providing a unique solution, it is more convenient to generate an efficient solution set among which the regulator could choose the most appropriate one to the current network state. In this set, each solution is not worse than the others on all criteria and is better at least on one criterion.

Another important assumption is the complete transitive comparability of decisions. In others words, aggregative approaches neglect the incomparability of decisions and ignore the intransitivity of judgments (indifference, preference, etc.). Furthermore, this approach presumes the commensurability of criteria.

THE MULTI-CRITERIA REGULATION PROBLEM

Given the feebleness of the monocriterion approach in the case of our problem, we chose to deal with the regulation problem by mainly considering its multi-criteria aspect. In fact, in our work we consider the problem as a multi-criteria optimization one without any aggregation form. For these reasons, we chose to designate it as MRP. Notice that in addition to this multi-criteria aspect, we will also take into account the following aspects: the real-time aspect of the problem, the simultaneity of disturbances, and finally the concurrent optimization of connection.

Basic Concepts

In this subsection, we provide insights into basic concepts related to multi-criteria optimization:

• –Criterion (Roy and Bouyssou, 1993): define a criterion as a function f with real values defined on potential solutions, which allows comparisons between them.

• –Multi-criteria Optimization Problem (MOP) (Collette and Siarry, 2002): Having defined a set A of feasible solutions and a consistent family F of criteria on A, the objective (in case of minimization) is to minimize: Min F(x) = [f ₁(x), f ₂(x),…, f _n (x)] such as x ∊ A and n ≥ 2 with n the number of criteria. In such a problem, the purpose is to find a good compromise of the different criteria.

• –Dominance (Collette and Siarry, 2002): Formally, the vector F(U) is said to dominate another vector F(V), denoted F(U) < F(V), if and only if f _i (U) ≤ f _i (V) ∀ i ∊ {1, 2,…, n} and f _j (U) < f _j (V) for some j ∊ {1, 2,…, n}.

• –Pareto Optimal: A solution X∗ ∊ A is said to be Pareto optimal or an efficient point for MOP (Collette and Siarry, 2002), if and only if there does not exist X ∊ A such that F(X) < F(X∗). The vector F(X∗) is then called non-dominated or noninferior.

The Problem Modeling

Before detailing and providing a mathematical formulation of the MRP, we need to introduce some notations and assumptions. Since a regulation process operates only in the presence of disturbances, it is necessary to determine its spatial horizon defined by the involved stops and vehicles (see Figure 3) and its temporal horizon, which is specified by human regulators as the required time for determining a good regulation solution.

FIGURE 3 Representation of H _s in the timetable.

Assumptions and Notations

Notice that our problem modelling relies on some assumptions that can be summarized in the following points:

	The considered public transportation network is defined by a set of lines with interconnection nodes.
	Network lines are assumed independent. In other words, vehicle exchanges between lines are not allowed even in the case of regulation.
	Turn-back points are only situated in terminus. So vehicles cannot perform half-turns online.
	Running vehicles are the only ones available in the network. So decisions of resource injections are not allowed in the regulation process.
	Incoming passengers in the network must wait until they take at least one vehicle. Hence, passengers do not leave the network without getting a vehicle.
	Passengers movements (origin-destination) are assumed known through investigations on traffic passengers and are also presumed independent of the undertaken decisions in real-time.

We denote by:

	S: the set of vehicles in the network
	V: the set of stops in the network
	H s : the spatial horizon of regulation defined by the set of involved stops S H s and vehicles V H s . So, H s  = S H s ∪ V H s
	H T : the temporal horizon of regulation
	H: the spatial-temporal horizon, H = H S ∪ H T
	: the kth stop of the line l
	: the ith vehicle of the line l
	: the arriving time of the vehicle at the stop
	: the departure time of the vehicle from the stop
	: arriving rate of passengers travelling between and
	: number of transferred person between and at with m = l or l′ and m ∊ l ∩ l′
	Trans_per: transfer duration per person at connection nodes
	: load of at its departure from
	: the rate of passengers travelling from to
	: distance crossed by between two successive stops and
	: the stop time of at
	: the route time of between and .

Decision Variables

Decision variables must specify each vehicle route, the course order for vehicles at stations, interconnections between lines, and vehicle service time. Therefore, we define three decision variables: the passage variable , the destination variable , and the connection variable .

Regulation Criteria

When disturbances occur in the network, it is necessary to notice firstly passenger impression. The most important factor to which passengers are sensitive is the total travel time. In fact, some passengers are in a rush, and others are more patient. In a complex network, passengers have to determine optimal travel by identifying lines, finding suitable connections, and estimating travel time. Moreover, travelers are more stressed when a connection is missed. Hence, passengers are sensitive to different factors related to travel time, security, travel conditions, service availability, travel complexity, and finally, to travel costs.

In order to maximize passengers’ satisfaction, regulators have to consider regulation measures that overcome disturbances by optimizing some exploitation objectives. These objectives, also called regulation criteria, are very significant in the regulation process and evenly represent regulator preferences. Here, we will focus on the following criteria: regularity, punctuality, connection, service quality, and commercial kilometers.

Regularity

This criterion is relative to the uniformity of time intervals between two successive passages of vehicles at stops. We chose to measure it through the total waiting time of passengers at the different stops. Formally, this criterion (REG) is defined by Equation (1):

with Δt the time interval between two successive passages of vehicles at the same stop, and , the expected number of arriving persons during Δt at to travel to This number is determined on the base of the rate .

Hence, optimizing regularity criterion corresponds to minimizing the total waiting time of passengers at the different stops.

Punctuality

Punctuality criterion corresponds to the respect of vehicle schedules. However, when disturbances occur, it is difficult to return immediately to theoretical schedules. So punctuality for passengers means reaching their destinations within a minimal route time. Consequently, optimizing this criterion corresponds to minimizing the total route time aboard the various vehicles according to their loads. Formally, this criterion (PUN) is defined by Equation (2):

Connection

Connection criterion is considered when connection nodes are affected by the occurred disturbances. It is associated with passengers transfer time between vehicles of different lines. So optimizing this criterion corresponds to minimizing the connection duration in the spatial horizon H _s . Formally, this criterion (CON) is defined by Equation (3):

Service Quality

This criterion is related to the waiting time of passengers who are concerned with transhipment between vehicles in case of disturbances. Transhipment duration must be minimized to maintain a considerable service quality even when transhipment decisions are selected by regulators at some stops different from connection nodes. Formally, this criterion (SQ) is expressed as follows:

With , the transhipment variable indicates if will ignore the stop .

Commercial Kilometers

This criterion represents the crossed distance in kilometers that the transportation company has to ensure. In this case, we have to minimize the gap between theoretical and real crossed kilometers for any vehicle in the spatial horizon H _S . Formally, it is expressed as follows:

Notice that punctuality, regularity, connection, and service quality are measured in terms of passengers time since durations are weighted by passenger number, whereas commercial kilometers are considered in terms of kilometers.

Operational Constraints

Different constraints that are related to the spatial-temporal network configuration have to be respected during the traffic regulation. We distinguish the following constraints:

• Consistency constraint of passage variables and destination variables : each vehicle has a unique origin point and goes to unique destination point:

• Time interval constraint: The minimal interval between two successive passages of vehicles at station is stated as follows:

  with the inferior bound of time intervals between successive passages of vehicles at stops.

• Stop time constraint: the stop time of vehicles at stations does not exceed the maximum value

• Transfer time constraint: The transfer time at connection nodes is defined within an interval [Trans _min, Trans _max], where Trans _min and Trans _min represent the inferior and superior limits, respectively, of transfer time between two vehicles and at . Formally, the constraint is expressed as follows:

• Vehicle load constraint: the total vehicle loads do not exceed a maximal capacity. Hence, the charge of each vehicle at its departure from every station must be lower than .

Regulation Decisions

Many regulation measures can be applied in transportation systems when disturbances occur. The retained regulation solution consists of a combination of different procedures that concern passengers, vehicles, destinations, conductors, and schedule (Caruso, 1997). Regulation measures rely on vehicle type and to network configuration. Several classifications of these measures have been proposed in literature (Froloff, Rizzi, and Saporito, 1989). In the present work, we propose a classification of regulation measures according to three flexibility levels (Figure 4): timetable flexibility, vehicle passages flexibility, and itinerary flexibility.

FIGURE 4 The proposed flexibility levels.

Timetable Flexibility

In this class we arrange decisions affecting vehicles departure time only. Only decisions involving delays or advances of vehicle schedules are applied. Hence, only departure time and arrival time of vehicles at stations are modified. This class is applied when vehicle services order at the different stops has to be respected; no vehicle is allowed to depart from a station earlier than that given in theoretical timetables.

Vehicle Passage Flexibility

This class is defined by decisions affecting both timetables and vehicle passages at stops. The disrespect of vehicle passages at some stops is acceptable. However, the main itinerary must be respected. These decisions are generally applied to vehicles at some stops to reach their theoretical timetables rapidly.

Itinerary Flexibility

As shown in Figure 2, the third class holds decisions that affect both timetables, vehicle passages at stops, and itinerary. These decisions are usually practical in case of vehicle breakdown in the main itinerary, or when a vehicle is much delayed and must take a shortcut to get its theoretical schedule back on line. The flexibility level is determined by the flexibility variable f defined as follows:

When f = 0, the vehicle passage order at stations as well as the main itineraries have to be respected. Only departure and arrival times of the concerned vehicles at the different stations of H _s could be modified. We denote by the variation of stop time and by , the variation of route time .

For f = 1, flexible points in the horizon H _s have to be defined in a passage flexibility table (see Table 1). The possibility of passage for the vehicle at station of H _s is specified by the variable which is defined as follows:

In addition to Table 1, flexible routes also have to be specified in an itinerary flexibility table when f = 2 (see Table 2). Flexible routes are determined on the base of a travelling graph that describes the set of shortcuts between each couple of stations (, ) in the horizon H _s . Every shortcut has a unique reference ref varying from 0 to n with 0 the reference of the main itinerary and n the identifier of the last possible shortcut. In addition, each shortcut is weighted by the corresponding distance that is proportional to its route time. The itinerary flexibility between two stops, and , is specified by the route variable with k > j:

In Table 2, we illustrate an example of itinerary flexibility in H _s . For each station, , we identify the possible routes that lead to a successive station, , by specifying their references ref. Let us notice that beyond the horizon limits defined by the starting and final points s and f, each vehicle takes its main itinerary again. Notice that Tables 1 and 2 are relative to the same spatial horizon H _s in order to get a coherent example.

TABLE 1 Example of Vehicle Passage Flexibility

Station	s	1	2	3	4	5	6	7	8	9	f
	0	0	0	1	0	1	1	0	1	1	0

TABLE 2 Example of Itinerary Flexibility

Station	s	1	2	3	4	5	6	7	8	9	f
,	((s, l), 0)	((1,2),0)	((2,3),0)	((3,4),0)	((4,5),0)	((5,6),0)	((6,7),0)	((7,8),0)	((8,9),0)	((9,f),0)	–
ref)			((2,4),1)		((4,7),1)	((5,7),2)		((7,9),2)	((8,j),1)

The MRP Complexity

Following the mathematical formulation of the MRP, we can infer some characteristics that justify the difficulty and complexity of the problem-solving. In fact, many decision variables are defined: passage variable, destination variable, connection variable, variation of stop time, and variation of route time. The first three variables are defined in the set {0, 1} and the last ones are defined within fixed intervals. So we can conclude the discrete character of decision variables. Moreover, another important characteristic of the MRP is its multi-criteria aspect. In fact, the problem is defined by many conflicting regulation criteria that have to be optimized simultaneously and a set of operational constraints that have to be respected. The nonlinearity of the problem is also justified by the presence of some nonlinear criteria and constraints.

Furthermore, given that regulation decisions correspond to new schedules for the implicated vehicles at the concerned stops, the size of the search space increases exponentially with the number of these entities. To highlight such difficulty let us assume that for a set of four vehicles and four stops, if we only deal with the decisions that concerns the passage of a vehicle at a stop or not, we have 2^4×4 ≈ 6 × 10⁴ possible solutions. Formally, the number of possible alternatives N can be expressed as follows: N =  Dec ^|v|★|s| with Dec the number of possible decisions for a vehicle at a given stop, v and s the number of involved vehicles and stops, respectively. N is also intensified when connection nodes are affected in H _s . So the size of the search space increases exponentially with the size of H _s and its flexibility levels. Besides the large search space, the problem complexity expands when many disturbances appear simultaneously in the network.

Consequently, we can conclude the following characteristics of the MRP: the combinatorial aspect, the multi-criteria aspect, the discrete search space, real-time aspect, and simultaneity of disturbances. All these characteristics show the complexity of the MRP and justify the necessity of a decision support tool for regulators.

THE DISTRIBUTED APPROACH

In order to deal with the MRP, we propose here a distributed multi-criteria approach based on multi-agent systems. In fact, we opted for multi-agent techniques to benefit from their capacities in reducing complexity of problem-solving and in dealing with problems in terms of cooperation, conflict, negotiation, and concurrence within a society of agents (Wooldridge, 2002). Our approach works with a set of current solutions that are optimized simultaneously and separately towards the nondominated set. Hence, it applies directly to the concepts of nondominance and Pareto optimality during the optimization process. Then, the best compromise solution is determined among the obtained nondominated set during an evaluation process by applying plurality voting and fuzzy preference relations. Before detailing the suggested approach and the relative processes, we will firstly introduce the multi-agent architecture of our model.

The Multi-Agent Architecture

In order to reduce the complexity of the MRP and to reach a considerable number of efficient alternatives in real-time, the problem knowledge is divided into subsets that are affected to a number of agents by coordinating their activities. Therefore, two basic types of agents are defined in our approach: decision-maker agent and criterion agent. The decision-maker agent (DM) is associated with a detected disturbance. It is responsible for the creation of criterion agents, the control of the optimization process firstly, and the supervision of the evaluation process secondly. It is also defined by its accountancies made of criterion agents and its static and dynamic knowledge. Every criterion agent i corresponds to a given regulation criterion and is defined by its accountancies made of the others criterion agents and the decision-maker agent. The different criterion agents act cooperatively during the two processes through negotiation protocols which guarantee a consensus.

The Optimization Process

The Basic Optimization Method

In this subsection, we will describe the proposed optimization method which relies on a new distributed solution construction. However, first of all we have to explain the preliminary step of this method. After analyzing the detected incident (spatial horizon H _s , flexibility level f), the DM agent estimates the disturbed timetable TT ^dist , the disturbed vehicle loads Ch _dist , as well as the disturbed values of each criterion (REG _dist , PUN _dist , CON _dist , SQ _dist , KM _dist ). Then a criterion agent is associated with each required regulation criterion. For instance, when connection nodes are involved in H _s a criterion agent is associated to connection criterion. In addition, according to flexibility level of H _s , service quality criterion (in case of vehicle passage flexibility and itinerary flexibility) and commercial kilometers criterion (in case of itinerary flexibility) could be taken into account. The creation of these agents involves their initialization with the necessary knowledge related to the disturbance and the horizon H _s .

Before starting the optimization process, the DM agent generates a set of random feasible solutions RSet by considering the disturbed state (the distributed timetable TT _dist , the distributed vehicle loads Ch _dist ). Notice that for each generated solution, the resulting timetables are computed, a new vehicle loads are estimated, a new connection order is determined, and criteria values are considered. The generated RSet is then distributed among criterion agents. Each criterion agent i receives a random solution that it considers as its starting one Sinit _i . When initializing Sinit _i , each criterion agent i determines the corresponding criterion value in order to update its tolerance threshold (REG _th , PUN _th , CON _th , SQ _th , or Km _th ) which it sends after that to the others criterion agents j. At the receipt of a threshold from agent i, each criterion agent j updates the threshold of the criterion i. Hence, at the beginning, every criterion agent i has n tolerance thresholds corresponding to the n considered regulation criteria.

During this preliminary step, the DM agent finds out efficient solutions among the generated set RSet in order to initialize the ND-set. Therefore, the DM agent applies the Pareto optimality concept by performing pairwise comparisons between solutions. Afterwards, the optimization process is launched.

Throughout the process, the current solutions are optimized simultaneously and separately by criterion agents who collaborate iteratively towards a nondominated set. In fact, the main idea of the distributed and incremental construction of efficient solutions is described formally as follows: Each criterion agent i optimizes (by minimizing or maximizing) its function f _i under constraints related to the other criteria j. Each criterion j should not be deteriorated in relation to its tolerance thresholds ε _j .

with f _i  ∊ {REG, PUN, CON, SQ, KmC} and ε _j  ∊ {REG _th , PUN _th , CON _th , SQ _th , Km _th }.

These constraints allow agents to maintain their local search in feasible solutions space and ensure the generation of compromise solutions which optimize simultaneously the different criteria by favoring the current criterion. Nevertheless, these constraints require cooperation between agents in order to adjust tolerance thresholds and to avoid conflicts. Therefore, a negotiation protocol that deals with threshold conflicts was implemented. This protocol is defined by four types of messages:

	UpDate_Threshold: it is an update request that is sent from a criterion agent i to another j in order to inform it with the new threshold ε i . This message is transmitted when a new generated solution improves the criterion i.
	UpDate_ND: this message is dispatched by a criterion agent i to the DM agent after each cycle of the optimization process in order to update the ND-set. The transmitted solution is considered by the agent i as the best generated one regarding the criterion i with respect to the current threshold constraints. The DM verifies the efficiency of the solution in relation to the ND-set that it updates if necessary.
	Request_Degradation: it corresponds to a request of threshold degradation that is sent from a criterion agent i to another agent j. This message is dispatched by i given the conflict caused by threshold value ε j . On the basis of this value, the agent j determines a new value from its historical threshold list hist_thresh j .
	Proposal_Degradation: this message is an answer to a request of threshold degradation. The new value of threshold is transmitted in this message after an exploration of the historical list hist_thresh.

At each cycle of the optimization process, each criterion agent i generates a neighborhood N _i starting from the current solution and by considering the different constraints. The best solution in N _i according to criterion i, is selected and sent to the DM agent via the message Update_ND. So, the DM agent receives iteratively new solutions from criterion agents. Each new solution is inserted into the ND-set if it is nondominated with respect to this, and solutions already in the ND-set, which thereby become dominated, if any, are removed. Hence, an incremental construction of ND-set is performed and the Pareto optimality concept is directly applied in solution selection.

Notice that when the generated neighborhood N _i corresponds to an empty set, a threshold conflict is detected. This conflict is handled by a threshold degradation request which is dispatched to the concerned agents via the message Request_Degradation. In order to identify the implicated agents, we associate to each criterion constraint a conflicting indicator ind _j . When evaluating N _i the violated constraints are identified and the corresponding indicators are updated. According to indicators value, agent i identifies the receivers of the request.

At the receipt of a degradation request, the criterion agent j determines the new threshold value from its historical list hist_thresh _i , given the conflicting threshold. The proposal of the new threshold is dispatched to criterion agent i via the message Proposal_Degradation. When all the required proposals are received, the blocked process is resumed by considering the new thresholds and by generating a new neighborhood for the last current solution.

Distributed Tabu Search

In order to implement the proposed optimization method, we opted for a dynamic neighboring search technique, Tabu Search. This metaheuristic was firstly suggested by Glover and Laguna (1997), and has received much success in combinatorial optimization for its fast and deep search and the solution quality. Besides the fundamental Tabu search, many extensions have been suggested by Glover and others authors (Glover and Laguna, 1997). The basic principle of Tabu Search is to pursue local search whenever it encounters a local optimum by allowing nonimproving moves; cycling back to previously visited solutions is prevented by the use of memories, called tabu lists that record the recent history of the search. This systematic use of memory is a key idea that can be linked to artificial intelligence concepts.

The proposed search method consists in a Distributed Tabu Search (DTS) which guarantees the distribution of the search space among n criterion agents. Each agent optimizes the corresponding criterion with respect to n − 1 criterion constraints. Hence, the proposed method operates with a set of current solutions that are optimized simultaneously and separately by the different agents in order to diversify the search space and to get closer to the Pareto frontier. The progress of the optimization process is ensured through threshold exchanges via the negotiation protocol presented in the previous section.

At the beginning, the starting solution of each criterion agent is set to a random feasible one that it received from the DM agent, and the corresponding tabu list (TL) is emptied. Notice that the TL is defined by tabus elements on the from- and to-solution in order to prevent backward moves. In order to avoid unexplored regions of the search space, we chose to alternate intensification and diversification phases during the search. The intensification phase is performed during a number of cycles by exploring promising regions: moving from a current solution to the best one in its neighborhood, and avoiding cycling by keeping in TL (managed in First-In-First-Out manner) last moves. In addition to this short-term memory, we also used a long-term memory in which we store the frequent moves during the search. This memory is exploited in the diversification phase. In fact, in this phase, we firstly clear the TL and set the most frequent moves of the run so far to be tabu. Then we choose a random solution to move to and proceed as in the search phase. Given the real-time characteristic of the MRP, the stop criterion of our algorithm is specified by the amount of CPU-time that should not exceed the temporal horizon H _T . This horizon is defined by human regulators as the required time for determining a good regulation decision.

The Evaluation Process

Given the generated ND-set during the optimization process, a human regulator has to deal with a decision problem. In fact, the regulator has to evaluate all the efficient decisions in order to select the best compromise of some regulation criteria. Therefore, we propose here two multi-criteria evaluation procedures that may be performed cooperatively by criterion agents and the DM agent. These procedures are based on different concepts, different preference relations, and diverse negotiation protocols. Notice that the evaluation process is launched by the DM agent by sending the ND-set to each criterion agent. In the following subsections, we present the basic idea of each procedure.

Plurality Voting Procedure (PVP)

This procedure relies on the “pseudo-criterion” concept introduced by Vincke (1989) and Roy and Bouyssou (1993). This concept is a preference model, which is defined by two different thresholds: preference threshold and indifference threshold for each criterion i. These thresholds may be constant or linear. Hence, each criterion agent presents three preference levels for solutions (Boudali et al., 2006; Boudali et al., 2008): strong preference, weak preference, and indifference (see Figure 5). In order to illustrate these relation preferences, we assume x and y are two efficient solutions. For every criterion i (defined by its function f _i ), the double thresholds model is the following:

FIGURE 5 Preference model of the PVP.

with p _i (f _i (y)) and q _i (f _i (y)) the preference and indifference thresholds of the criterion i, respectively. Weak preference is supposed to describe the criterion agent's hesitation between indifference and preference.

In our work, solutions are not compared to each other, but each one is only compared to the ideal id _i and anti-ideal aid _i solutions. Note that

The current voting procedure defines the indifference threshold q _i and the preference threshold p _i as follows:

with ε an adjustment parameter defined in ]0, 1[ and used to gradually increase p _i and q _i .

Therefore, the criterion agent i is indifferent between solutions x such as aid _i  ≤ f _i (x) ≤ q _i . These solutions are unsatisfied and should be deleted from the ND-set whenever the most of the criterion agents have the same indifference. Solutions y such as p _i  ≤ f _i (y) < id _i are considered the most preferred ones, while solutions w such as q _i  < f _i (w) < p _i are weakly preferred.

At each iteration of the voting procedure, every criterion agent i determines the ideal id _i and anti-ideal aid _i costs, and computes the thresholds q _i and p _i . On the basis of these parameters, the set of unsatisfied solutions USol _i  = {x ∊ ND-set | aid _i  ≤ f _i (x) ≤ q _i } is computed.

Every criterion agent i would delete this set of solutions from the ND-set. So it informs the other criterion agent j about his USol _i subset via the message InformUSol, and asks them to make their vote.

At the receipt of the InformUSol message by criterion agents j, three cases may occur:

	Case 1: ∀ x ∊ USol i such as aid j  ≤ f j (x) ≤ q j . So the criterion agent j agrees to delete x from the ND-set.
	Case 2: ∀ x ∊ USol i such as p j  ≤ f j (x) ≤ id j . Hence, the criterion agent j does not agree to delete x from ND-set.
	Case 3: ∀ x ∊ USol i such as q j  < f j (x) < p j . So the criterion agent j hesitates, the solution is weakly preferred.

So, it doesn't vote.

When all the votes are received (by means of the message Notify_Vote), the criterion agent i computes a qualification score for each solution x ∊ USol _i . This qualification score (QScore) can be defined formally, as

This score corresponds to the difference between the number of agents j voting for keeping solutions x (such that x ∊ [p _j , id _j ]) and the number of agents j voting for their deleting (such that x ∊ [aid _j , q _j ]).

Consequently, each criterion agent i communicates to the DM agent its USol _i with the associated scores through the message Inform_Score. The DM agent compares the qualification scores of solutions in USol and removes those having the minimal score from the ND-set. Hence, the removed solutions compose the first subset of the least-preferred nondominated solutions.

If the updated ND-set contains more than one solution, the DM agent communicates it to criterion agents via the message UpDate_ND, in order to start a new cycle of the voting procedure. So, every criterion agent i determines the new values of id _i and aid _j costs, then computes its q _i and its p _i thresholds. After that, the same procedure is repeated by considering these new parameters until |ND-set| ≤1. Hence, the initial ND-set is divided into distinct subsets that are classified from the most preferred subset to the least one.

Notice that we can suggest to associate weights to criteria in order to model regulator's preferences. For instance, a regulator may prefer regularity or punctuality criterion to commercial kilometer or connection to regularity, etc. So, the computed scores are modified as follows:

with w _j the weight of criterion j. Solutions with the minimal score are eliminated from ND-set iteratively during the voting procedure.

Fuzzy Voting Procedure (FVP)

This procedure is an extension of the PVP. In fact, for a better precision in solution classifying and to offer more flexibility in defining preference levels, we propose to introduce a fuzzy modelling for regulation criteria. Hence, for each criterion i, we obtain the fuzzy preference model illustrated in Figure 6.

FIGURE 6 Fuzzy preference model.

As in PVP, each criterion agent i determines the aid _i and id _i values given the ND-set. Then, it computes the indifference q _i and preference p _i thresholds. On the base of these parameters, each criterion agent i defines its votes for each solution in the ND-set. These votes are established according to their membership levels to the defined zones. Hence, for each solution x the criterion agent i defines a three-dimension vote defined as follows:

	μ GoodCi (x): corresponds to a vote in favor of the solution x with a level μ Good .
	μ MediumCi (x): designates a neutral vote for the solution x with a level μ Medium .
	μ BadCi (x): corresponds to a vote in disfavor of the solution x with a level μ Bad .

The votes of each criterion agent i for each solution x in the ND-set are communicated to the DM agent via the message Inform_Vote. In order to store all the received votes, the DM agent uses a three-dimensional matrix as follows: C ₁…C _n For each solution Sol _k in the ND-set, the DM agent computes a normalized score through a linear aggregation of the received votes. Therefore, weights have to be assigned to membership levels. Formally, this score is defined as follows:

with

Notice that weights are specified according to the importance of membership areas. In fact, the high weight is assigned to the level μ _Good , and the low weight is given to the level μ _Bad . Hence, in our case we have

Then, the DM agent eliminates solution(s) having the least score from the ND-set. Thus, the eliminated ones correspond to the least preferred nondominated solutions. As in PVA, the end of the voting procedure is detected when |ND-set| <1. Otherwise, a new cycle of the voting procedure is launched by the DM agent that sends the updated ND-Set to criterion agents via the message UpDate_ND.

Thus, we obtain a progressive classification of nondominated solutions from the most preferred ones to the least preferred ones. An advantage of this proposed approach is the qualitative (or linguistic) description that it may offer. In fact, when the cardinality of the last subset S _Pre is superior to 1, a linguistic description grid could be provided to regulator for a further decision support (see Figure 7).

FIGURE 7 Grid of linguistic description.

This grid provides a qualitative description of each solution Sol for each criterion C. It is performed through two different techniques, according to cardinality of S _Pre :

	When |S pre | ≤3: Pairwise comparisons of solutions for each criterion are performed;
	When |S Pre | > 3: Application of α-cuts (Bouchon-Meunie, 1995; Siler and Buckley, 2005) (α = 0, 4 (Medium), α = 0, 6 (Good), α = 0, 8 (Very Good)) by considering the id et aid of S Pre . Notice that an α-cut of a fuzzy set is the subset of elements having a membership degree upper than α (Siler and Buckley, 2005).

Hence, on the base of this grid the final solution is selected by a regulator according to its preferences for each criterion.

SIMULATION RESULTS

The proposed distributed approach has been assessed for the case of an urban transportation system defined by different lines and connection nodes. During this experimental study we considered different disturbance cases that may consider connection nodes and some flexibility level of the network (timetable flexibility, vehicle passage flexibility, itinerary flexibility). Thus, in these cases the number of the involved criteria is varying. In this section, we firstly present a real disturbance case in order to illustrate the solving process. Then, we present some general conclusions deduced during the experimental study.

Illustrative Example

In order to illustrate some simulation results, we present here a real disturbance case that concerns two underground lines of the transportation system.

Throughout this case study, we firstly test the suggested optimization process by implementing the Distributed Tabu Search. Then we illustrate the implementation of the proposed evaluation procedures: PVP and FVP. Figure 8 shows theoretical timetables for the two lines. Line 1 has a frequency of one vehicle per 10 minutes while line 2 has an average frequency of one vehicle per 20 minutes.

FIGURE 8 Timetables of Line 1 and Line 2.

The connection node corresponds to stops and of line 1 and line 2, respectively. At t _dist  = 12: 00, the vehicle encounters a technical problem obliging it to be delayed 7 minutes at , which is situated at 10 minutes from the connection node . At this node a connection is planned at 12:18 with the vehicle . However, because of the disturbance, would arrive at 12:19 at . Hence, the connection would not occur. We assume here a flexibility level f = 0 (timetable flexibility). We also presume that the studied horizon is included in a homogenous period of day. Then we can have a constant arrival rate of passengers at all the stations of each line. Let μ = 2 passengers per minute be that arrival rate in line 1 and μ = 1 passengers per minute in line 2. Furthermore, we suppose that the number of passengers w to be transferred from line 1 to line 2 is proportional to vehicle loads with a rate of 10%. Similarly, the transfer rate from line 2 to line 1 is 20%. In addition, we assume that theoretical vehicle loads at each stop are defined by a triangular pattern where peak are at the connection node. Notice, that all this information is stored in the ESS which provides a global view of the network state in real-time (vehicles positions, vehicles loads, transfer rate, etc.).

Step 1. The Optimization Process

Given the disturbance's characteristics, the DM agent is launched. It estimates the disturbed timetable TT _dist , the disturbed vehicle loads Ch _dist , and computes the disturbed values of each criterion (REG _dist , PUN _dist , CON _dist ). Afterwards, a criterion agent is associated to each required regulation criterion. Given the implication of the connection node and the flexibility level, the launched criterion agents are PUN agent, REG agent, and CON agent.

The DM agent generates random solutions and sends each one of them to each criterion agent. Hence criterion agents initialize their starting solutions and implement the Distributed Tabu Search during the cooperative optimization process. Thus, the different criterion agents collaborate via the negotiation protocol that guarantees thresholds exchange and conflict-solving in order to evolve the search of efficient solutions. Given the considered flexibility level, the supported decisions are only departure delay by considering the H _s . Departure delay for the implicated vehicles must not exceed 4 minutes.

In Table 3, we show an example of an ND-set containing 20 efficient solutions, which we obtained within a horizon time H _T  = 12 seconds. As we can notice in this efficient set, each solution is neither superior nor inferior to the other ones on all the criteria. In fact, every solution improves only one or two criteria simultaneously. Hence, the generated solutions correspond to diverse compromise solutions of the different criteria. Given this efficient set, the regulator cannot easily choose the best compromise in a few moments. Therefore, it is necessary to support him in classifying these solutions according to its preferences through the evaluation process.

TABLE 3 The Generated ND-Set by the Distributed Tabu Search WithinH _T  = 12 s

Solution Sol i	REG	PUNC	CON
Sol 1	25095.0	35194.0	1009.4
Sol 2	25632.0	34536.0	1019.8
Sol 3	25551.0	35284.0	885.8
Sol 4	25071.0	36022.0	885.8
Sol 5	24607.0	35898.0	1009.4
Sol 6	24725.0	36602.0	844.4
Sol 7	24213.0	36322.0	975.199
Sol 8	24914.0	37250.0	835.4
Sol 9	24069.0	36862.0	993.199
Sol 10	24618.0	38167.0	835.4
Sol 11	23943.0	37252.0	988.4
Sol 12	23821.0	37554.0	988.4
Sol 13	24958.0	38669.0	825.4
Sol 14	25679.0	34490.0	1020
Sol 15	23780.0	37766.0	988.4
Sol 16	24776.0	39057.0	825.4
Sol 17	24739.0	39417.0	825.4
Sol 18	23759.0	37839.0	988.4
Sol 19	24712.0	39574.0	825.4
Sol 20	23734.0	37927.0	1011.599

Step 2. The Evaluation Process

In this process, we implemented separately the two proposed evaluation procedure (PVP and FVP) by considering the ND-set shown in Table 3. These procedures are launched by the DM agent that sends the generated ND-set to the different criterion agents and asks them to perform the voting iteratively until |ND-set| ≤1. Here we discuss the obtained results for each procedure.

Plurality Voting Procedure

At the receipt of the ND-set, each criterion i determines its costs aid _i and id _i , and computes the thresholds p _i and q _i . Then it finds out the subset of unsatisfied solutions Usol _i . The corresponding results obtained in this first iteration are shown in Table 4. Afterwards, the determined Usol _i is transmitted to the other criterion j to establish their votes. After receiving the votes of all the criterion agent j, the agent i computes the qualification score (QScore) for each solution in Usol _i .

TABLE 4 Threshold Values at Iteration 1

	Critere-PON	Critere-REG	Critere-COR
aid i	39574.0	25679.0	1019.8
id i	34490.0	23734.0	825.4
p i	36019.4	24317.5	883.72
q i	38050.6	25095.5	961.48

Next, each criterion i sends its subset Usol _i with the corresponding scores QScore to the DM agent, which centralizes the votes and eliminates from ND-set the solutions with minimal score. At the end of this first iteration, we obtain ND-set = ND-set\{Sol ₂, Sol ₁₄} given that solutions Sol ₂ and Sol ₁₄ correspond to the least qualified. Since |ND-set| > 1, the DM agent asks the criterion agents to start up another voting iteration by considering the updated ND-set. In Table 5 we summarize the obtained results at each iteration of the PVP.

TABLE 5 The Obtained ND-Set at Each Iteration of the PVP

Iteration k	ND-set
1	ND\{Sol 2, Sol 14}
2	ND\{Sol 1}
3	ND\{Sol 3, Sol 4, Sol 5, Sol 9, Sol 11, Sol 12, Sol 13, Sol 15, Sol 16, Sol 17, Sol 18, Sol 19, Sol 20}
4	ND\{Sol 8, Sol 10}
5	{Sol 6, Sol 7}\Ø

Fuzzy Voting Procedure

As in PVP, the beginning of this procedure is detected by criterion agents at the receipt of the generated ND-set from the DM agent. So, each criterion agent determines firstly its costs, aid _i and id _i , and computes the thresholds, p _i and q _i . Then we obtain the results shown in Table 4 for this first iteration. On the basis of these results a fuzzy modelling of each criterion is performed by the corresponding criterion agent. For instance, in the case of regularity, the corresponding agent generates the fuzzy preference model shown in Figure 9.

FIGURE 9 The fuzzy preference model of regularity criterion.

Given the generated model, each criterion agent computes a three dimension vote (μ _Good , μ _Medium , μ _Bad ) for each efficient solution according to their membership level. Afterwards, all the established votes are transmitted to the DM agent which computes a global score for each solution in the ND-set Equation (20). The obtained scores in this first iteration are shown in Table 6.

TABLE 6 Solutions Scores at Iteration 1

Sol	Score	Sol	Score
Sol 1	0.267	Sol 11	0.333
Sol 2	0.266	Sol 12	0.315
Sol 3	0.425	Sol 13	0.302
Sol 4	0.431	Sol 14	0.266
Sol 5	0.333	Sol l5	0.294
Sol 6	0.414	Sol 16	0.333
Sol 7	0.388	Sol 17	0.333
Sol 8	0.379	Sol 18	0.287
Sol 9	0.333	Sol 19	0.333
Sol 10	0.333	Sol 20	0.278

According to these scores, the DM agent eliminates solutions with minimal scores from the ND-set. In this first iteration, the least preferred solutions are {Sol ₂, Sol ₁₄). So we obtain ND-set = ND-set\{Sol ₂, Sol ₁₄}. Given that |ND-set| > 1, a new voting iteration is performed by considering this new set which is sent from the DM agent to the different criterion agents. In Table 7, we summarize the obtained results at each voting iteration.

TABLE 7 The Obtained ND-Set at Each Iteration of the FVP

Iterationk	ND-set
1	ND\{Sol 2, Sol 14}
2	ND\{Sol 1}
3	ND\{Sol 13}
4	ND\{Sol 20}
5	ND\{Sol 18}
6	ND\{Sol 15}
7	ND\{Sol 5, Sol 11, Sol 12, Sol 116, Sol 17, Sol 19}
8	ND\{Sol 9}
9	ND\{Sol 8}
10	ND\{Sol 3}
11	ND\{Sol 10}
12	ND\{Sol 6}
13	ND\{Sol 4, Sol 7} = Ø

Thus, a progressive solution classification is performed by eliminating the subset of least preferred solutions at each voting cycle. Finally, the last subset corresponds to the most preferred one. This subset contains more than one solution, so a grid of linguistic description can be provided in order to present the satisfaction level of each solution for each criterion (see Figure 10).

FIGURE 10 Grille de description linguistique associée à la PVF.

This grid is established after pair-wise comparisons of solutions for each criterion given that the size of this subset is less than 3.

Experimental Study

In order to assess the performance of the suggested distributed approach, we considered different disturbance cases in which we vary the number of the considered regulation criteria.

We are firstly interested in the optimization process and studied the progression of solution numbers in terms of CPU time. Here, we provide the experimental results obtained with the Distributed Tabu Search by considering two criteria (case of timetable flexibility), three criteria (case of timetable flexibility and involved connection node), and four criteria (case of vehicle passage flexibility and involved connection node). The obtained results are shown in Figures 11-13.

FIGURE 11 ND-set generated with two criteria.

FIGURE 12 ND-set generated with three criteria.

FIGURE 13 ND-set generated with four criteria.

These figures show the anytime character of our approach. In fact, at any time of the optimization process, a set of compromise solutions is available and the regulator can choose the most suitable one according to its preferences. So, whatever the specified time horizon H _T , the approach always provides a set of efficient solutions. Notice that the value of H _T generally does not exceed 2 minutes.

Following the optimization process, we are now interested in the evaluation process by performing separately the two voting procedures, PVP and FVP. However, a parametric study of the adjustment parametric ε is firstly required. In fact, after analyzing different values in the interval [0, 1], we selected the one that gives a good compromise between time convergence and the number of solutions to be treated (ε = 0.3). In order to assess the evaluation procedures, we considered different ND-sets that were previously generated during the optimization process. Then, we proceeded by comparing PVP and FVP, according to two axes: quantitative comparison and qualitative comparison.

For the first axis, we considered the rate of eliminating solutions at each voting cycle. We noticed that for the PVP, this rate could exceed 50% of the ND-set in one voting cycle. However, with the FVP, a reduced number of solutions are eliminated at each cycle. This progressive elimination offers more precision in solution classification. Hence, the quality of each eliminated solution is more obvious in relation to those previously eliminated and the remaining ones in the ND-set. Consequently, the FVP offers a precise preference order of efficient solutions.

For the second axis, we mainly considered the temporal complexity and precision of solution qualification. Given the increasing number of eliminated solutions at each cycle of the PVP, the required cycle number is reduced. However, in the FVP with the progressive solution elimination, the cycle number is increasing. These results are illustrated in Figures 14-16, by considering 2, 3, and 4 criteria, respectively.

FIGURE 14 The evaluation process with two criteria.

FIGURE 15 The evaluation process with three criteria.

FIGURE 16 The evaluation process with four criteria.

These figures show the required time (in 10⁻³ s) by each evaluation approach (PVP and FVP) in the case of different ND-set. According to these comparisons, we noticed that with the growing size of the ND-set, the FVP is generally more time-consuming than PVP. Nevertheless, we have to notice that interactions between criterion agents in PVP (exchanges of USol and the corresponding votes) have been eliminated in FVP, since each criterion agent determines its votes for all the efficient solutions, and communicates them to the DM agent in order to compute solutions scores.

Moreover, with the grid of linguistic description provided by the FVP, the regulator is no longer faced with a decision problem even when the most preferred subset contains more than one solution. The quality of each retained solution according to each criterion is more obvious.

Following these comparisons, we cannot deduce the best procedure. In fact, each one presents some interesting advantages that are not verified in the other one.

Finally, the proposed distributed approach provides the regulator with simple immediate applicable decisions that are based on a projection in the future of the network state. Since no benchmarks are available for this type of problems, we intend to validate our approach on a real transportation system. Let us notice that the implementation of our approach was carried out by using the multi-agent platform JADE 3.1 version (SUN MICROSYSTEMS), and the SUN JAVA Development Kit (JDK) 1.5 version (Telecom Italia SpA). For the experimental study, we used a PC Intel Pentium IV @ 3.2 GHz, 512 MB of RAM memory (Intel Corporation).

CONCLUSION

In our article, we presented an interactive distributed approach to deal with the multi-criteria regulation problem. This approach provides the regulators with relevant decisions to undertake in case of disturbances. This approach relies on data supplied by the ESS that controls the global traffic of the network. The solving process of our approach includes two steps. In the first one, a multi-criteria optimization of the regulation problem is performed by means of a Distributed Tabu Search, which generates a set of compromise solutions given some regulation criteria to be optimized. In order to support a human regulator in selecting the best compromise solution according to its preference, an evaluation process is then carried out. Therefore, we suggested two possible cooperative procedures: the plurality voting procedure and the fuzzy voting procedure. An assessment of the proposed approach was performed through an experimental study. The provided results explain the applicability of the approach mainly for solving real-time and multi-criteria problems.