Marin Lujak
email: marin.lujak@urjc.es

Stefano Giordani
email: stefano.giordani@uniroma2.it

Sascha Ossowski
email: sascha.ossowski@urjc.es

Route Guidance: Bridging System and User Optimization in Traffic Assignment

Keywords: traffic assignment, distributed optimization, distributed coordination, traffic user optimization, traffic system optimization

In this paper we study the problem of the assignment of road paths to vehicles. Due to the assumption that a low percentage of vehicles follow the routes proposed by route guidance systems (RGS) and the increase of the use of the same, the conventional RGS might shortly result obsolete.

Assuming a complete road network information at the disposal of RGSs, their proposed paths are related with user optimization which in general can be arbitrarily more costly than the system optimum. However, the user optimum is fair for the drivers of the same Origin-Destination (O-D) pair but it doesn't guarantee fairness for different O-D pairs. Contrary, the system optimum can produce unfair assignments both for the vehicles of the same as of different O-D pairs. This is the reason why, in this paper, we propose an optimization model which bridges this gap between the user and system optimum, and propose a new mathematical programming formulation based on Nash Welfare optimization which results in a good egalitarian and utilitarian welfare for all O-D pairs. To avoid the issues with the lack of robustness related with the centralized implementation, the proposed model is highly distributed. We test the solution approach through simulation and compare it with the conventional user-and system-optimization.

Introduction

In this paper we treat the problem of the assignment of road network paths to vehicles depending on the momentary traffic situation on the road network. This problem is an open issue of present route guidance systems (RGS) whose strong assumption is that a low percentage of road users follow the proposed routes such that their influence on the change of traffic is insignificant.

Drivers' self-concerned behavior, together with the assumption that the complete road network information is at the disposal of everyone, is related to the user optimization and results in Wardrop equilibrium. The latter can be arbitrarily more costly than the globally optimal traffic assignment. However, assuming that all the vehicle drivers share the same objective function, the Wardrop equilibrium solution is fair for the drivers of the same Origin-Destination (O-D) pair, i.e., the used paths for the same O-D pair have the same value for a specific objective, e.g., minimizing total travel time. At the contrary, the solution might not be fair for different O-D pairs, i.e., the ratio of travel times between any two O-D pairs in the network of the same or similar travel durations in uncongested network can be arbitrarily high.

Furthermore, due to the increase of the use of the RGSs, the assumption on a low number of users is losing its legitimacy and the RGSs might shortly result in the same or worse traveling times than in the case when the RGS proposed path is not followed; the reason is that they direct all their users of the same O-D pair to the same route(s) without considering the dynamic component of an actual number of the drivers accepting to follow those routes. The drawback of the system optimum, on the other hand, which is calculated by minimizing total network cost, is that it can produce unfair assignments both for the vehicles of the same and of different O-D pairs.

In this paper, we study approaches that balance the requirements on equity and fairness both in the assignment of vehicles of the same O-D pair to available paths, but also in the assignment of paths to different O-D pairs. By considering different social welfare and fairness aspects in path assignment, we intend to bridge the system optimization which assumes collaborative road infrastructure users and user optimization which assumes selfish users in traffic assignment. In the usage of the road network infrastructure, we assume the existence of an interest group of rational agents whose presence in the network represents the majority of the users such that the users who do not follow the proposed RGS represent insignificant influence on the road congestion behavior. We try to optimize the behavior of the group members such as to produce maximum benefit for the interest group as a whole while not damaging individual group members. Furthermore, we propose an optimization model which bridges the gap between the user and system optimum, and propose a new mathematical programming formulation based on Nash Welfare optimization which results in a good egalitarian and utilitarian welfare.

To avoid the issues with the lack of robustness related with the centralized implementation, the proposed model is based on a highly distributed decision making between the geographically distributed road network intersection agents and road users (vehicles' drivers). In this way, we avoid the necessity of a central coordinator and the road network decision making structure represents well the network topology. The result is a light, distributed, geographically localized, and open multi-agent architecture such that it can seamlessly grow and reconfigure itself based on the transport network needs. Moreover, regarding the solution approach, dynamic traffic assignment problem is a non-convex optimization problem which is at present computationally tractable only for relatively small-scale examples. This is why we apply the static traffic assignment approach.

In the proposed optimization model, we assume that every driver within the interest group has at disposal all the network information regarding the travel time from his/her origin (O) to destination (D), as well as the travel times of other O-D pairs in real time. There is an assumption also that every driver has the information on the travel times which would result if he/she did not respect the route given by the system. However, there is an important drawback of this assumption due to the high unpredictability of future network behavior and related traffic congestion.

Once a vehicle driver is a member of the proposed route guidance system, his/her behavior can significantly influence the efficiency of the system, especially if a driver doesn't respect the route recommendations of the system. The developments of sensors and their integration on the roads allow for the implementation of a monitoring technology so that the system can identify the vehicles who behave contrary to the network traffic instructions performed a priori and perform corrective actions on those vehicles. One of the open issues is how to adapt to the changes of the vehicle self-concerned behavior, when to incentivize them and when to expel them from the system. We are aware of these issues but the treatment of this topic is out of scope of this work. Thus, for simplicity but without loss of generality, we assume that the users follow the system indications possibly incentivized by specific mechanisms, for example, available in the State-of-the-Art works which we mention in the following.

The rest of the paper is organized as follows. First, in Section 2 we discuss the State of the Art models in traffic coordination, their drawbacks, and the contribution of our work. In Section 3, we formally define the treated traffic assignment problem. In Section 4, we explain the main features of our multiagent approach. The experiment setup description and results are presented in Section 5. The paper ends with the main conclusions and directions for future work in Section 6.

Related work and contribution of the paper

Multiple transportation network problem formulations and routing optimization models related with different constraints related with transportation modes, variable demand, user classes, stochasticity of travel delay, and dynamic aspects of congestion were studied and experimented in, e.g., [START_REF] Nagurney | Mathematical models of transportation and networks[END_REF][START_REF] Herty | Multicommodity flows on road networks[END_REF][START_REF] Marcotte | A strategic flow model of traffic assignment in static capacitated networks[END_REF]. Mathematical models of traffic assignment are usually based on Wardrop's principle which states that at equilibrium, flows are assigned to shortest paths with respect to current (flow-dependent) travel cost. The Wardrop equilibrium can be viewed as an instance of a Nash equilibrium in a game with a large number of players [START_REF] Correa | Wardrop equilibria[END_REF].

Evaluating the worst-case ratio of Nash equilibria to the system optimum was first proposed in [START_REF] Koutsoupias | Worst-case equilibria[END_REF]. Papadimitriou in [START_REF] Papadimitriou | Algorithms, games, and the internet[END_REF] introduces the notion of price of anarchy which measures the user optimum inefficiency in terms of total travel time, i.e. how bad is user-selfish with respect to the system-optimum solution. In [START_REF] Roughgarden | How unfair is optimal routing?[END_REF], it was shown that for the uncapacitated problem, the total travel time associated to the user optimum is at most two times the minimum travel time. This ratio falls to 4/3 for linear travel time functions. Opposedly, in [START_REF] Correa | Fast, fair, and efficient flows in networks[END_REF], Correa et al. present a family of instances with multiple sources and a single sink for which the price of anarchy is unbounded, even in networks with linear latencies. Furthermore, in [START_REF] Correa | Selfish routing in capacitated networks[END_REF], Correa et al. proved that, in the case of nondecreasing and differentiable travel time functions, the worst-case of user optimum inefficiency is independent of the network topology. Lin et al. [START_REF] Lin | Stronger bounds on braess's paradox and the maximum latency of selfish routing[END_REF] prove for two-commodity networks related with Fibonacci numbers, that both the worst-case severity of Braess's paradox and the price of anarchy for the maximum latency objective grow exponentially with the network size. This result indicates the importance of influencing and coordinating the drivers' behavior to reach higher system efficiency.

Some of the available State-of-the-Art theoretical models and methods for infrastructure resource assignment and coordination can be found in, e.g., [START_REF] Nagurney | Mathematical models of transportation and networks[END_REF][START_REF] Herty | Multicommodity flows on road networks[END_REF][START_REF] Correa | Selfish routing in capacitated networks[END_REF][START_REF] Leblanc | An efficient approach to solving the road network equilibrium traffic assignment problem[END_REF][START_REF] Rothkopf | Computationally manageable combinational auctions[END_REF]. One of the tools for mechanism design of agent systems are auctions [START_REF] Bertsekas | Network Optimization: continuous and discrete methods[END_REF]. The implementation usually requires solving a combinatorial non-linear optimization problem which is in general NP-hard and intractable for complex networks [START_REF] Even | On the complexity of time table and multicommodity flow problems[END_REF]. However, with certain relaxations, the latter can be modeled as a convex optimization problem [START_REF] Nagurney | Mathematical models of transportation and networks[END_REF][START_REF] Bertsekas | The auction algorithm for the minimum cost network flow problem[END_REF]. Computational optimization auctions are methods that are similar to the Gauss-Seidel and Jacobii methods, see, e.g., [START_REF] Palomar | A tutorial on decomposition methods for network utility maximization, Selected Areas in Communications[END_REF]. This approach is well suited for massive parallelization, whereby each node is a processor adjusting its own variables on the basis of local information communicated by adjacent processors/nodes [START_REF] Bertsekas | Network Optimization: continuous and discrete methods[END_REF].

For comparison, in the traffic management of Internet links, it is possible to substantially increase network throughput, limit link overloads, and make a network robust to resource failures by optimizing administrative weights of links [START_REF] Fortz | Internet traffic engineering by optimizing ospf weights[END_REF][START_REF] Tomaszewski | Valid inequalities for a shortest-path routing optimization problem[END_REF]. Routers can compute shortest paths to each other and thus make routing tables by using the information on the topology of the network and the administrative weights of links. If there are several shortest path links for a specific O-D pair, the traffic is split equally according to the ECMP (equal-cost multi-path) principle.

In real-world transport networks on public roads, it is difficult to implement system-optimized network models since individual objective functions are usually contrary to one another and decision makers act frequently selfishly. The issue of incentives to align local vehicle and global infrastructure objectives is an actual topic, e.g., [START_REF] Karakostas | Stackelberg strategies for selfish routing in general multicommodity networks[END_REF][START_REF] Fotakis | Efficient methods for selfish network design[END_REF][START_REF] Zhang | Competitive, cooperative and stackelberg congestion pricing for multiple regions in transportation networks[END_REF].

The tradeoff between efficiency and fairness was considered in [START_REF] Bertsimas | On the efficiency-fairness tradeoff[END_REF]. Several managerial prescriptions were developed for the selection problem based on this trade-off. In [START_REF] Jahn | System-optimal routing of traffic flows with user constraints in networks with congestion[END_REF], Jahn et al. consider the static traffic assignment problem and propose a route-guidance system model for system optimal routing of traffic flow with explicit integration of user constraints considering a fixed maximum deviation of the assigned paths costs in respect to the optimal ones. Additive constraints guarantee that user travel times of the system optimum are not so far away from user travel times obtained with the user optimum model. Simulations results show superior fairness compared to the pure system optimum. This model was further theoretically studied in [START_REF] Schulz | Efficiency and fairness of system-optimal routing with user constraints[END_REF]. A strong assumption is that the driver acceptance of paths is assumed for all the paths without considering any additional fairness issue.

Since the dynamic traffic assignment problem is at present computationally tractable only for relatively small-scale instances, e.g., [START_REF] Skutella | An introduction to network flows over time[END_REF][START_REF] Shen | System optimal dynamic traffic assignment: Properties and solution procedures in the case of a many-to-one network[END_REF], in our paper we concentrate on the (system optimal) static traffic assignment problem which is similar to operations research minimum cost flow (MCF) problem with multiple sources and sinks in a directed graph with arc-capacities. Even though there are different centralized algorithms for the MCF problem [START_REF] Ahuja | Network flows[END_REF][START_REF] Ford | Flows in networks[END_REF][START_REF] Goldberg | Finding minimum-cost circulations by canceling negative cycles[END_REF], efficient distributed and decentralized system optimization methods which will allow for an efficient usage of state-of-the-art road infrastructure sensory technology taking into account the rationality of self-concerned vehicle drivers are still scarce.

While most of the works concentrate on the scenarios with intrinsic Wardrop equilibrium (see, e.g., [START_REF] Bazzan | A review on agent-based technology for traffic and transportation[END_REF]), we propose an optimization model based on system-optimization including relevant fairness features in interaction with vehicles. Furthermore, to the best of our knowledge, all of the State-of-the-Art approaches for driver incitement to behave in line with system optimization rely on central decision maker who coordinates the road prices (see, e.g., [START_REF] Bai | Decomposition techniques for the minimum toll revenue problem[END_REF][START_REF] Bai | Relaxed toll sets for congestion pricing problems[END_REF]). The realization of such a system might not be viable due to the road network proprietary and political issues but also due to the questionable users acceptance since those methods do not actually respond to the fairness issues among different vehicles, thus treating all the drivers on the road arcs independently of the past dynamics of their network usage and fairness among O-D pairs.

Even though the idea of road network management and computation distribution is not new, to the best of our knowledge, the solutions with Quality of Solution (QoS) guarantees are lacking. In [START_REF] Hawas | A decentralized scheme for real-time route guidance in vehicular traffic networks[END_REF], a control procedure implementable in a decentralized architecture with limited network information for real-time route guidance in congested vehicular traffic networks was presented. The decentralized approach envisions a set of local controllers distributed in the network, where every controller has a limited network view based on local detectors, and thus utilizes this information to guide the within-territory vehicles to their individual destinations. The assignment procedure is driven by informed local search procedure with heuristics. However, this approach doesn't have Quality of Solution (QoS) guarantees and can be arbitrarily away from the system optimum. While in Jahn et al. [START_REF] Jahn | System-optimal routing of traffic flows with user constraints in networks with congestion[END_REF], the vehicles are seen only as flow particles, in our paper, we consider vehicles as agents bidding on their paths and keeping track of their historical assignment of paths.

In this work, we propose a distributed network traffic assignment approach and negotiation between vehicles and road infrastructure based on a market-oriented model and auctions, both with QoS guarantees. The proposed approach is complementary to distributed traffic control strategies such as coordinated traffic lights, see, e.g., [START_REF] Oliveira | Multiagent learning on traffic lights control: effects of using shared information[END_REF].

To sum up, the main contribution of our work is the distributed multiagent architecture for traffic assignment where the optimization function is based on the maximization of Nash social welfare with included path fairness and O-D envy-freeness constraints. Furthermore, vehicles are seen as active participants in path assignment tracking their path assignment dynamics and are not seen as indifferent particles of the flow as is the case in the related work.

Problem formulation and definitions

We consider a road network without traffic rules in static flow conditions where flow represents a traffic pattern at steady state. Even though this assumption is very strong, it can be made in the time windows when traffic exhibits a flow-like behavior, e.g. in rush hours. If real-time traffic information is available from the road and intersection network to individual vehicles, and the latter two can communicate and negotiate vehicle routes over the network, it becomes possible to provide vehicles with route selection based on the individual preferences (e.g., travel time, fuel consumption, or CO 2 emissions, etc.) considering global traffic optimization.

Furthermore, we assume that the vehicle demand for a specific time window is known at the beginning of the window and is expressed through a static vehicle flow. In this view, each vehicle is seen as a unit element (particle) of the total flow. This can be performed through a reservation system where each vehicle reserves its O-D pair and the relatively short time range in which it starts the travel at its origin. We assume that the variations of the O-D pair traffic demands are negligible in an observed time window.

Moreover, we assume a real-time monitoring of the vehicles behavior through infrastructure (road and intersections) cameras. Real-time traffic monitoring permits us recognizing the vehicles acceptance of the suggested route.

Starting from the above stated assumptions, let G = (N, A) be a connected digraph representing the road network where N is the set of n nodes representing intersections including origin and destination nodes and A is the set of m arcs a = (i, j), i, j ∈ N and i = j, representing uni-directional roads connecting intersection i with j. Furthermore, to simplify the notation, we assume that there is at most one arc in each direction between any pair of nodes. For every arc (i, j) ∈ A, there is an arc cost function f ij (x ij ), which without the loss of generality, we assume is proportional to an average travel time function T ij (x ij ). The latter is the travelling time that on average is experienced by a vehicle when traversing arc (i, j) ∈ A, with x ij ≥ 0 being the flow of vehicles in a unit time period on that arc, which is limited from above by the arc capacity u ij ≥ 0 being the maximum arc flow. T ij (x ij ) is in general an increasing nonlinear function because of the effects of congestion on the arc travel time. Different functions can be considered, but for simplicity and without loss of generality, we consider the average travel time function proposed for normal use by the U.S. Federal Highway Administration traffic assignment model:

T ij (x ij ) = t ij (1 + 0.15(x ij /u ij ) 4 ) [35].
We assume that there Let x k be the flow along path k ∈ P w , then the constraints among path flows and O-D demands can be stated as:

k∈P w ψ wk • x k = R w , ∀w ∈ W. (1)
Furthermore, let Φ be the [|A| * |P W |] arc-path incidence matrix. It follows that the capacity constraints for each arc a ∈ A in the network can be expressed as:

w∈W k∈P w φ a,k • x k ≤ u a , ∀a ∈ A. (2)
Formulating the above problem in terms of the paths along which passes the flow makes the flow conservation constraints at nodes unnecessary. Finally, path duration cost f k (x k , {x l } l∈L(k) ) of each path k ∈ P w , where w ∈ W is the sum of the duration costs of its arcs

f ij (x ij ), i.e., f k (x k , {x l } l∈L(k) ) = (i,j)∈k f ij (x ij
) and is strictly convex. Since the arc duration cost f ij (x ij ) is influenced by the total number of vehicles passing through the arc, path duration cost depends not only on a local path flow x k but also on flows of other paths {x l } l∈L(k) , where L(k) is the set of paths that use the same arc(s) as path k and are therefore coupled with it. Similarly, we introduce the set of O-D pairs M(w) which paths use one or more same arc(s) as O-D pair w ∈ W and are therefore coupled with it.

Social Welfares considered

The requirements on equity and fairness emerge not only in the assignment of vehicles of the same O-D pair to available paths, but also in the assignment of paths to different O-D pairs. In this paper, we study approaches that will balance those requirements in both settings.

The objective is to minimize the combination of the costs associated with the flows on the used paths such that we keep track of the related fairness considerations among the paths assigned to the vehicles of the same and different O-D pairs. We concentrate on the equity and efficiency of the allocation, and in this light observe the behavior of the utilitarian and Nash social welfare, and Pareto efficiency. In the following we explain the reasons behind this choice.

Criteria of equity include fairness and no-envy criteria. Inspired by the envy-minimization criterion introduced in [START_REF] Tadenuma | Choice-consistent resolutions of the efficiency-equity trade-off[END_REF], we introduce a normalized mean path duration cost γ w (x w , {x l } l∈M(w) ) of agent w ∈ W :

γ w (x w , {x l } l∈M(w) ) = | Pw | k∈ Pw f k • x k . ( 3
)
We use a geometric mean since it "normalizes" the paths being averaged, so that none of the paths dominates the weighting, and a given percentage change in any of the paths has the same effect on the geometric mean. In the following, to simplify the notation, we will use

C k = m f k • x k when needed.
We propose the following envy criterion for O-D agents. An allocation θ is α-envy-free, where α is a maximum tolerance factor for non-enviousness such that 0 < α ≤ 1 if:

γ w ≥ γ α w , ∀w, w ∈ W |w = w . (4)
In other words, there is no agent w that envies any other agent w for paying less than α th power of the cost paid by w .

Note that an α-envy-free allocation does not always exist for a given α > 0, but similarly to [START_REF] Tadenuma | Choice-consistent resolutions of the efficiency-equity trade-off[END_REF], allocation θ is more envy-free than allocation θ if α(θ) > α(θ ). Now, let us define the maximum latency L max (x W ) of a feasible flow x W as:

L max (x W ) = max{γ w : w ∈ W }. (5)
The maximum latency problem defined in this way consists of minimizing the cost in (5) associated to the commodity of maximum normalized mean path duration cost, ı.e., the multi-commodity flow that minimizes the maximum normalized mean path duration cost among all the O-D pairs and thus optimizes the egalitarian welfare. This approach provides a good solution when the minimum requirements of all agents should be satisfied. Unfortunately, by optimizing the system based on the worst-off performance, we deteriorate the system efficiency and thus, the utilitarian welfare. From the overall system efficiency point of view, we can use utilitarian social welfare which sums up the agents' individual utilities in a given allocation and thus gives us a measure of the overall and average benefit for the system. However, optimizing the utilitarian social welfare is not acceptable in the systems which success is based on self-concerned users' acceptance. This is because in utilitarian systems, the optimum is payed by (usually a few) worst off agents. The latter, however, might not comply with paying the price of the system optimality (see, e.g., [START_REF] Chevaleyre | Issues in multiagent resource allocation[END_REF]).

Problem formulation with utilitarian objective function

Average normalized latency of a feasible flow x W is expressed as

L avg (x W ) = 1 |W | • w∈W γ w . (6)
By minimizing average normalized latency in [START_REF] Papadimitriou | Algorithms, games, and the internet[END_REF] we approach the normalized utilitarian welfare optimization problem which results in a system optimal solution. The latter augmented with envy-freeness constraints, denoted by (P ), can be expressed as:

(P ) :

min f (x W ) = w∈W γ w (x w , {x l } l∈M(w) ) = w∈W |P w | k∈P w a∈A f a (x a ) • φ ak • x k (7) subject to: w∈W k∈P w φ ak • x k ≤ u a , ∀a ∈ A (8) γ w ≥ γ α w , ∀w, w ∈ W |w = w (9)
k∈P w

ψ wk • x k = R w , ∀w ∈ W (10)
x k ≥ 0 , ∀k ∈ P w , w ∈ W.

Capacity constraints (8) limit the total flow across all O-D pairs on each arc a ∈ A. Furthermore, ( 9) is a constraint on envy-free O-D pair paths and γ w is calculated as in (3) while constraints [START_REF] Lin | Stronger bounds on braess's paradox and the maximum latency of selfish routing[END_REF] on the fulfillment of O-D demand among path flows force the sum of path flows of each commodity w ∈ W to be equal to the commodity demand.

The objective of ( 7) is, therefore, to achieve a requested normalized vehicle path flow over arcs a ∈ A of minimum cost such that each vehicle goes through one route from its origin and terminates at the destination position with the constraints on arc flow (8), envy-freeness (9), O-D demand [START_REF] Lin | Stronger bounds on braess's paradox and the maximum latency of selfish routing[END_REF], and admissible paths in P W (11) satisfied.

Nash product and Pareto efficiency

The balance between egalitarian and utilitarian social welfare is given by the maximization of the Nash product which is the product of the agents' individual utilities. A high Nash value, when it is defined in terms of benefits, is an indication of both good utility value and a good egalitarian value, ı.e. allocation solutions with a high Nash value are both locally and globally good solutions. Furthermore, Nash product combines utilitarian and egalitarian social welfare since it reaches the maximum when the utilities realized are high and distributed equally over all the agents. However, Nash product optimization doesn't work when defined through the minimization of the overall cost since it is sufficient that only one of the agents realizes the cost close to zero for it to have the overall value close to zero. This is why we propose reciprocal values of the costs which multiplied together will result in high Nash product values.

• Nash social welfare:

max N (x W ) = w∈W 1 γ w or equivalently, max N (x W ) = - w∈W log γ w . (12)
The mathematical programming model with included envy-freeness and fairness parameters is then:

(N ) :

min z(x W ) = w∈W log γ w = w∈W log |P w | k∈ Pw a∈A f a (x a ) • φ ak x k (13)
subject to:

w∈W k∈P w φ ak • x k ≤ u a , ∀a ∈ A (14)
γ w ≥ γ α w , ∀w, w ∈ W |w = w ( 15
)
k∈P w ψ wk • x k = R w , ∀w ∈ W (16)
x k ≥ 0 , ∀k ∈ P w , w ∈ W .

Furthermore, we study also Pareto efficiency of the found solutions. The definition of Pareto efficiency is as follows. An allocation θ ∈ Θ is Pareto superior to an allocation θ ∈ Θ iff for every O-D agent w ∈ W , and for the costs f θ w (x w ) of used paths in the path assignment θ, where f θ w (x w ) = k f k (x k ), the following is satisfied: f θ w (x w ) ≤ f θ w (x w ), where x w > 0. In other words, we say that we can Pareto-improve an allocation θ if there exists another allocation θ such that in θ at least one agent is better off and nobody is worse off. Furthermore, an allocation is Pareto efficient if no Pareto improvement is possible, i.e., iff there exists no allocation θ ∈ Θ that is Pareto superior to θ. In the same light, an allocation is Pareto-inefficient if it is possible to make some agent better off without making other agents worse off. However, Pareto efficient allocations do not always exist and when they do, it makes sense for the system manager to choose a solution from the nondominated set. Generally, however, the set of nondominated solutions is too large to be presented to the system manager for the final path assignment choice. Hence, we need tools that help the decision maker focus on his preferred solutions (or alternatives).

Proposed multi-agent vehicle-infrastructure negotiation model

The route guidance multi-agent architecture is made of three different agent categories: vehicles, vehicle travel route origins, and intersection agents. No a priori global assignment information is available and the information is exchanged among the vehicles, O-D agents and intersection agents through the neighbor to neighbor communication. The vehicles exchange the information only with the closest intersection agent by the means of which they are represented in the route guidance system. In this way, we obtain a dynamic network which can dynamically recalculate vehicle routes based on the actual traffic load and vehicle demand.

To decompose the network optimization problem, the route guidance architecture is divided in two layers as shown in Figure 1. On the upper layer, Nash social welfare maximization problem with included envy-freeness and fairness constraints ( 13)-( 17) is decomposed at four levels to reach a subproblem which can be optimized individually locally by every O-D pair independently of other O-D pairs. At the upper layer, vehicle agents inform of their traveling preferences the intersection agent closest to the origin of their travel (origin agent o). Based on the total demand for each time period expressed in terms of vehicle flow per time unit, each origin agent o tries to achieve a sufficient number of shortest paths considering fairness for all its destinations d o . Those desti- nations are requested by the vehicles starting the travel on o and the paths are computed through, e.g., k-shortest path routing algorithm [START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF]. Since problem ( 13)-( 17) is not easily decomposable and O-D objective functions are dependent on each other, we use dual decomposition at four levels where each origin agent o then negotiates for each of its O-D pairs path flows, path, envy-freeness, consistency, and demand distribution dual prices. Intersection agents, on the other hand, distributively optimize arcs' prices influenced by the arcs congestion obtained through O-D paths flow requests.

Interconnected intersection "auctioneer" agents iteratively calculate arcs' shadow prices in terms of arc penalty λ minimizing the congestion effects. Lagrange multipliers are calculated through a distributed dual-decomposition based algorithm which decouples coupled objectives ( 7) and coupled constraint sets (8) that are not readily decomposable. On the other hand, each origin agent calculates shortest paths to its destinations with arcs' prices updated and given by the intersection agents, envy-freeness prices ζ, consistency dual prices ξ, and vehicle demand distribution over paths prices µ and thus decides upon the amount of vehicles to be routed on assigned paths depending on the arcs' prices. The network decomposition method used here was inspired by [START_REF] Palomar | A tutorial on decomposition methods for network utility maximization, Selected Areas in Communications[END_REF].

After the traffic assignment is made for O-D pairs on the first level of the multi-agent architecture, the latter decide, on the second level, of the vehicles' assignment to the paths based on relevant social welfare parameters that guarantee equality through an iterative auction. The negotiation through auctions at the second level is local between each origin agent and the vehicles starting their travel at that origin. The vehicle disutility is seen as a function of travel time as a ratio between some nominal and the real travel time.

In the following, we give more details on the decision making model of intersection, origin and vehicle agents.

Upper layer distributed decision making model

In this Section, we present details for the Nash welfare optimization. Since duration costs of paths k ∈ P W depend on a local vector variable x k but also on other coupled paths' flows {x l } l∈L(k) , we tackle this issue by introducing auxiliary variables and additional equality constraints, thus transferring the coupling in the objective function to coupling in the constraints, which can then be decoupled by dual decomposition and solved by introducing additional consistency pricing. We assume the presence of mutual communication among origin node agents such that they can exchange dual variable values (pricing messages).

We first introduce auxiliary variables x kl into problem ( 13)-( 17) for the coupled arguments in the cost functions and additional equality constraints to enforce consistency. The model becomes:

min x k ,x kl z(x W ) = w∈W 1 |P w | log k∈ Pw a∈A f a (x a ) • φ ak • x k (18)
subject to:

w∈W k∈P w φ ak • x k ≤ u a , ∀a ∈ A ( 19
)
γ w ≥ γ α w , ∀w, w ∈ W |w = w (20)
x kl = x l , ∀k ∈ P w , l ∈ L(k), w ∈ W (21)
k∈P w ψ wk • x k = R w , ∀w ∈ W (22)
x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k), w ∈ W,

where x k , x kl are local flow variables at path k. By exploitation of the decomposability structure we take a four-level dual decomposition approach as seen in Figure 2. At the first level, the network infrastructure agents define arcs' dual variables (arcs' prices) to handle flow arc capacity constraints. At the second level, origin node agents negotiate on the behalf of the O-D pairs originating from them, with other origin node agents regarding the assignment of envy-free paths. At the third level, the consistency subproblem is resolved within each cluster of the paths sharing one or more arcs. The computation of the main problem is distributed into |W | subproblems related to individual O-D pairs with included relaxed consistency constraints. The flow distribution constraint is relaxed for every O-D pair at the fourth level where for path k, only local variables with the first subscript index k are used. Lagrangean relaxation of problem ( 18)-( 23) at the first level is then: [START_REF] Schulz | Efficiency and fairness of system-optimal routing with user constraints[END_REF] subject to:

min x L 1 (x; λ) = w∈W log |P w | k∈ Pw a∈A f a (x a ) • φ ak x k + + a∈A λ a k∈P w φ ak • x k - a∈A λ a • u a
γ w ≥ γ α w , ∀w, w ∈ W |w = w (25)
x kl = x l , ∀k ∈ P w , l ∈ L(k), w ∈ W ( 26
)
k∈P w ψ wk • x k = R w , ∀w ∈ W (27) x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k), w ∈ W, (28)
where λ a ≥ 0 is the Lagrange multiplier (arc shadow price) associated with the capacity constraint on arcs a ∈ A.

If we let λ k = a∈A λ a φ ak be the aggregate path congestion price of those arcs used by path k ∈ Pw , and

L w 1 (x w , λ) = log |P w | k∈ Pw a∈A f a (x a ) • φ ak x k + k∈P w λ k • x k (29)
be the w th contribution to [START_REF] Schulz | Efficiency and fairness of system-optimal routing with user constraints[END_REF] which is related only with the local variables of w, then ( 24) can be rewritten as:

min x L 1 (x; λ) = w∈W L w 1 (x w , λ) - a∈A λ a • u a . ( 30
)
At the first higher level, the master problem is in charge of updating dual variable λ. This update can be done by intersection agents who solve the following dual problem:

max λ g 1 (λ) = w∈W L w 1 (x w , λ) - a∈A λ a • u a (31)
subject to:

λ ≥ 0,
where xw is the value of the vector of variables related to O-D pair w in an optimal solution of ( 24)- [START_REF] Ford | Flows in networks[END_REF]. Solving problem ( 24)-( 28) is equivalent to solving problem

min w∈W L w 1 (x w ; λ) (32)
subject to:

γ w ≥ γ α w , ∀w, w ∈ W |w = w x kl = x l , ∀k ∈ P w , l ∈ L(k), w ∈ W k∈P w ψ wk • x k = R w , ∀w ∈ W x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k), w ∈ W,
However, due to constraints ( 25) and ( 26), the latter subproblem cannot be still resolved for each w ∈ W independently of other O-D pairs w ∈ W |w = w. This is why we continue with further two levels of decomposition until reaching the stage at which every w ∈ W can resolve its local optimization subproblem individually and independently of others. Therefore, Lagrangean relaxation of problem [START_REF] Bai | Relaxed toll sets for congestion pricing problems[END_REF] at the second level is:

min x L 2 x; (λ, ζ) = w∈W L w 1 (x w , λ) + w ∈W |w =w ζ w,w • (α log γ w -log γ w ) (33
) subject to:

x kl = x l , ∀k ∈ P w , l ∈ L(k), w ∈ W k∈P w ψ wk • x k = R w , ∀w ∈ W x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k), w ∈ W,
where ζ w,w ≥ 0 is the Lagrange multiplier related with the envy-freeness constraints (4.1).

At the second higher level, the following master problem is in charge of updating dual variable ζ:

max ζ g 2 (λ, ζ) = L 2 x, (λ, ζ) (34)
subject to:

ζ ≥ 0,
where x is the optimal solution of (33) for given λ and ζ.

If we let

L w 2 (x w ; (λ, ζ)) = L w 1 (x w , λ) + log γ w • w ∈W |w =w α • ζ w ,w -ζ w,w , (35)
then problem [START_REF] Hawas | A decentralized scheme for real-time route guidance in vehicular traffic networks[END_REF] can be decomposed at the third level into the following independent subproblems, one for each O-D pair w ∈ W .

min x L w 3 x w ; (λ, ζ, ξ) = L w 2 x w ; (λ, ζ) + k∈ Pw l∈L(k) ξ kl x kl - l:k∈L(l) ξ lk x k (36)
subject to:

k∈P w ψ wk • x k = R w (37)
x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k) [START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF] where ξ kl is the consistency price between path k and its coupled paths l ∈ L(k).

At the third higher level, we have the master problem in charge of updating dual variable ξ to solve the dual problem:

max ξ g 3 (λ, ζ, ξ) = w∈W L w 3 xw ; (λ, ζ, ξ) (39)
subject to:

ξ ≥ 0,
where xw is the optimal solution for problem ( 36)-( 38) for given λ, ζ, and ξ.

Note that in subproblem ( 36)-( 38), only variables with the first subscript index k belonging to w are used. Since there is still constraint [START_REF] Chevaleyre | Issues in multiagent resource allocation[END_REF], it makes sense to further Lagrangean decompose problem ( 36)-( 38) into another master and subproblem.

Therefore and finally, Lagrangean relaxation of problem ( 36)-( 38) at the fourth level is:

min xw L w 4 x w ; (λ, ζ, ξ, µ w ) = L w 3 x w ; (λ, ζ, ξ) + µ w k∈P w ψ wk • x k -R w (40)
subject to:

x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k), (41)
where µ w ≥ 0 is the Lagrange multiplier associated with the constraint [START_REF] Chevaleyre | Issues in multiagent resource allocation[END_REF] on distribution of demanded flow R w over paths k ∈ P w where w ∈ W . The expanded version of problem (40)-(41) is:

(I) :

min x L w 4 x w ; (λ, ζ, ξ, µ w ) = 1 |P w | • log k∈|P w | a∈A f a (x a ) • φ ak x k • 1 + w ∈W |w =w α • ζ w ,w -ζ w,w + + k∈|P w | a∈A λ a φ ak • x k + l∈L(k) ξ kl x kl - l:k∈L(l) ξ lk x k + µ w • ψ wk • x k (42)
subject to:

x k , x kl ≥ 0 , ∀k ∈ P w , l ∈ L(k). (43)
Then for each O-D pair w ∈ W we can solve locally and independently for each path k ∈ Pw the following problem: min

x k ,x kl L w k 4 x k , x kl ; (λ, ζ, ξ, µ w ) = 1 |P w | • log a∈A f a (x a ) • φ ak x k • 1 + w ∈W |w =w α • ζ w ,w -ζ w,w + + a∈A λ a • φ ak • x k + l∈L(k) ξ kl x kl - l:k∈L(l) ξ lk x k + µ w • ψ wk • x k (44)
subject to:

x k , x kl ≥ 0, ∀l ∈ L(k), (45)
At the fourth higher level, we have the master problem in charge of updating dual variables µ w to solve the dual problem:

max µw g w 4 (λ, ζ, ξ, µ w ) = k∈P w L w k 4 xk , xkl ; (λ, ζ, ξ, µ w ) -µ w • R w (46)
subject to:

µ w ≥ 0 ,
where xk and xkl is the optimal solution of (44)-(45) for given λ, ζ, ξ, and µ w . Furthermore, the solution (x k , xkl ) = arg min L w k 4

x k , x kl ; (λ, ζ, ξ, µ w ) is unique due to the strict concavity of L w k the dual function g w 4 (λ, ζ, ξ, µ w ) is differentiable and the following gradient method updates can be used:

λ a (t 1 + 1) = λ a (t 1 ) -τ 1 u a - k:a∈ P k w ,w∈W xk (t 1 ) + , ∀a ∈ A, (47)
ζ w,w (t 2 +1) = ζ w,w (t 2 )-τ 2 log γ w (t 2 )-α log γ w (t 2 ) + , ∀w, w ∈ W |w = w, (48)
ξ kl (t 3 + 1) = ξ kl (t 3 ) -τ 3 x l (t 3 ) -x kl (t 3 ) + , ∀l ∈ L(k), (49)
µ w (t 4 + 1) = µ w (t 4 ) -τ 4 R w - k∈P w x k (t 4 ) + , ∀w ∈ W, (50)
where t 1 , t 2 , t 3 , t 4 are the iteration indices at the first, second, third and fourth level, respectively. Furthermore, τ 1 , τ 2 , τ 3 , τ 4 > 0 are sufficiently small positive step sizes, and [•] + denotes the projection onto the nonnegative orthant. The dual variables λ(t 1 ), ζ(t 2 ), ξ(t 3 ), and µ(t 4 ) converge to their dual optimal values as t 1 → ∞, t 2 → ∞, t 3 → ∞, and t 4 → ∞ respectively since the duality gap for [START_REF] Roughgarden | How unfair is optimal routing?[END_REF] is zero and the solution to (I) is unique. The primal variable x W will also converge to the primal optimal value xW [START_REF] Palomar | A tutorial on decomposition methods for network utility maximization, Selected Areas in Communications[END_REF].

There are four decomposition levels in the proposed architecture, and four time scales, one per each level. Convergence and stability are guaranteed if the lower level master problems are solved on a faster time scale than the higher level ones so that all the problems at a lower level have converged at each iteration of a master problem. Therefore, duration of each time period of the four levels of decomposition δt should be such that δt 1 > δt 2 > δt 3 > δt 4 . The inner minimization of every upper level is fully performed by repeatedly updating the set of the lower level variables for each update of the upper level variable (see Figure 2). The fourth level has the fastest time scale in which the agent of the origin node from which O-D pair w originates updates independently dual variable µ w . Once the master problem of the fourth level is solved for each w ∈ W , consistency dual prices can be exchanged at the third level very quickly over local communication among the agents of the origin nodes from which originate O-D pairs that are coupled together. Furthermore, on the second level, envy-freeness constraints are relaxed and compared for all O-D pairs w ∈ W . Finally the first level has the slowest time scale in which arcs' dual prices are updated by road intersection agents.

Layer Stage 1 (Primal-dual algorithm for solving problem ( 18)-( 23))

Step 1.0 Set t 1 := 0. Each intersection agent j ∈ N sets λ a (0) := 0 for each outgoing arc a ∈ A(j) of node j ∈ N , and broadcasts them.

Step 1.1 Lagrangean problem [START_REF] Bai | Relaxed toll sets for congestion pricing problems[END_REF] is solved by calling Stage 2 and waiting for the broadcasted solution vector x w (λ) issued by the agent of origin node o ∈ O from which O-D pair w originates, for each w ∈ W .

Step 1.2 Each intersection agent j solves a part of master problem (31) by updating dual variable λ a (t 1 + 1) of each outgoing arc a ∈ A(j) with the gradient iterate (47), and broadcasts them.

Step 1.3 Set t 1 := t 1 + 1 and go to Step 1.1, until satisfying termination criteria.

Step 1.4 Take x W := {x w (λ)} w∈W as the solution of problem ( 18)-( 23)).

Stage 2 (Primal-dual algorithm for solving problem (32))

Step 2.0 Set t 2 := 0. Each origin node agent o ∈ O sets ζ ww (0) := 0, for each w ∈ W originating from origin node o and w ∈ W with w = w , and broadcasts them.

Step Step

Lower layer: negotiation between vehicles and O-D agents

While in the former Sections, we were treating the allocation of paths and flows to O-D pairs on the upper level of the architecture proposed in Figure 1, in the following we study the architecture's lower level: allocation of available O-D paths to vehicles.

Each vehicle agent, v ∈ V , is described by the tuple

a = {w v , k, S v , c v } , (51)
where w v is vehicle v's origin-destination pair, k ∈ P wv is the path assigned to vehicle v, and S v is its satisfaction variable. Each vehicle objective is to minimize cost of travel c v in terms of travel time. Satisfaction S v is calculated based on the past dynamics of the path assignment as stated in the following:

S v = ν • S v (t) + (1 -ν) • S v (t -1) . ( 52
)
where ν ∈ [0, 1] is a weight given to the satisfaction in time period t. At every time period t, vehicle satisfaction S v (t) is evaluated in the following way:

S v (t) = 1 - f k (t) f sp w (t) , (53)
where f k (t) is the duration cost of the path assigned to vehicle v, and f sp w (t) is the O-D path with the minimum duration cost at time period t. Initially, satisfaction S v values are assumed nonnegative and equal for all vehicles.

In the iterative auction performed on the lower level, each vehicle bids for its lowest cost path k ∈ P wv . In complex road networks, there might be multiple optimal paths, as the paths might have similar total costs over different arcs, though computing all Pareto-optimal paths is in general N Phard. Those individual preferences are faced upon the disutilities of all the bidding vehicles and the capacity of paths assigned to its O-D pair in the iterative auction process.

The vehicle auction algorithm is initiated with a feasible solution assuming that the demands on all paths are equal to zero. The auction is performed in iterations. Origin agents assign paths to the vehicle agents optimizing the social welfare parameters. The algorithm runs in iterations until the number of unsatisfied agents is minimal. Let V w be a set of vehicles within each O-D pair w ∈ W . Then, the steps of the algorithm are as follows:

• Initially, i.e., at auction iteration h = 0, for each vehicle agent v ∈ V w , set Q(h = 0) of assignments is assumed empty and all path values v Pw,v (0) are set to zero.

During iteration h:

• each vehicle agent v receives path values v Pw,v (h -1) and assignments Q(h -1) from its origin agent.

• Each vehicle agent updates its local list of the assignments Q v (h) and path values v Pw,v (h) in the following way. To include the past satisfaction into the assignment of paths, and balance satisfaction of vehicles, we multiply v Pw,v (h) with satisfaction S v ∈ [0, 1]. In this way, vehicle past satisfaction influences the overall system path assignment.

• If vehicle agent v is unassigned, it calculates the bid value and bids for the path with the lowest cost using the following bidding and assignment procedure.

Vehicle bidding for paths

To submit a bid, each vehicle agent v unassigned in its partial assignment Q v (h):

• finds path p which offers the best possible value p v = arg min p∈Pw {c vpv pv (h)}, and calculates bid for path p v as follows:

b valpv (h) = val pvv (h)+ u v (h)-w v (h)+ = c vpv -w v (h)+ , where u v (h) = min p∈Pw {c vp -v pv (h)} and w v (h) = min p i =pv∈Pw {c vp i -val p i v (
h)} is the second best utility that is, the best value over paths other than p v . If p v is the only path in P w , then w v (h) = -inf.

• raises the value of its preferred path by the bidding increment σ v so that it is indifferent between p v and the second best path, that is, it sets

v pvv (h) to v pvv (h) + σ v (h), where σ v (h) = v pv (h) -w v (h) + .
The bidding phase is over when all the unassigned agents calculate their bid.

Path assignment to vehicles

Let V (p v )(h) ⊆ V w be the set of agents with bids pending for path p v . Origin agent o coord is responsible for the assignment of path p v .

Each agent v ∈ V (p v )(h), broadcasts its bid b vpv (h). Agent o coord receives the bids b kpv (h) of all agents k ∈ V (p v )(h), regarding p v . Following steps are performed to resolve the assignment:

• Agent o coord selects agent v pv = arg max v∈V (pv)(h) b vpv with the highest bid b vpv max = max v∈V (p)(h) b vpv .
• If b vpv max ≥ v pvv (h) + then v pvv (h) := b vpv max , the updated assignment information is broadcasted to all the agents k ∈ V (p v ) which update their sets of assignments Q v by replacing the current agent assigned to it (if any), with agent v pv .

• If b vpv max < v pvv (h) + then all bids for path p v are cleared, no reassignment or path value change is made.

If there are any unassigned agents left within V (p v ), the assignment algorithm starts again from the bidding phase within iteration h + 1. This process terminates when each agent v ∈ V w has a path assignment.

Experiment

To illustrate the functionality of our proposed route guidance system model, we test it on 10 simulated examples of connected randomly generated Delaunay graphs with 50 nodes (representing intersections and in the same time origins o ∈ O, and destinations d ∈ D) on a map sized [10 × 10], see Figures 3 and4. The simulated Delaunay graphs with distances between the nodes satisfying the Euclidean triangle inequality represent simplified road networks. The results were produced by the main program in Matlab calling for CPLEX solver for variable optimization. The graphs were created by Matlab delaunay function.

The origin-destination matrix contains demands between all 50 nodes during a (morning or after-work) rush period. Each O-D pair agent w ∈ W has as an objective the minimization of its normalized mean path duration cost γ w (x w , {x l } l∈M(w) ). Time period durations of the architecture's four levels of decomposition were chosen to be δt 1 = 15, δt 2 = 10, δt 3 = 5, and δt 4 = 1. By using a slower timescale on lower levels of subgradient updates, we avoid the running of inner subgradient until convergence before updating the outer subgradient. Maximum tolerance factor for non-enviousness α was set to 0.4. A relative duality gap threshold on each level of decomposition was set to ε = 0.05.

In the experiments, we are concerned about the dynamics of the vehicles' average travel times in respect to the user optimum, system optimum and the proposed optimization model. O-D pairs travel times are weighted by the quantity of vehicles on each O-D pair in the calculation of the average travel time.

The weight of each O-D pair is calculated in two ways: i) as the number of vehicles on that O-D pair, in respect to the total number of vehicles leaving from that origin, and ii) the number of vehicles on that O-D pair in respect to the total number of vehicles of all O-D pairs. The latter approach is used also for the total number of vehicles in each O-D pair. The calculated costs in terms of travel time are unitary, calculated per kilometer of traveled distance for each origin O.

We examine the traffic assignment solution in respect to 10 different distributions of the vehicles on approximately 2500 origin-destination pairs. Furthermore, we test the solution quality in terms of social welfare considering individual vehicle travel times and influence of minimizing the maximum travel times on the general throughput and efficiency of the network. We An initial feasible solution, needed to initialize all the implemented algorithms, has been obtained by computing the shortest path tree from each origin to all destinations. On each O-D pair shortest path, we put the entire demand. We have adopted the lexicographic strategy for each O-D request so that the origins are randomly considered.

As can be seen from Figure 5, the proposed method is better in most of the cases in respect to the user-optimized network. However, for a very few number of origins o, it gives worse results than Wardrop Equilibrium. For those origins, monetary incentives are necessary for vehicles to behave inline with the desired system performance. The gain in travelling cost of the most of the O-D pairs is much higher than the loss of the few of the O-D pairs in respect to the user-optimum so the increased system efficiency gives space for incentivizing the worst-off agents.

Regarding the computation time, both system-optimum and our proposed model show similar behavior. Average solution time on a computer with Intel Core (1.6 GHz, 3 MB) processor and 4 GB of RAM was 56 seconds.

Conclusions

In this work we studied the problem of fair and efficient traffic assignment related with real-time and vehicle acceptance constraints. We proposed a distributed multi-agent traffic model made of vehicles with RGSs, O-D, and intersection agents. Vehicles, assumed selfish, negotiate over auctions with O-D agents for route assignment, whereas O-D agents search for the shortest O-D path over auctions with intersection agents. The latter assign the routes based on the maximization of the network traffic flow considering the road capacity constraints. In most of the cases, the mean path duration cost is significantly better than in the user-optimization while still being fair. For a minimal number of origins, the result is worse than in network user optimization. For those O-D pairs, monetary incentives are necessary for vehicles to behave inline with the desired system performance.

The State-of-the art toll-pricing methods can be applied also in the proposed solution for incentivizing user acceptance of the proposed paths. However, the adaptations are necessary since we assume users in a closed preference group. Further adaptation and development of new incentive methods will be treated in the future work.

  are n O origin nodes O, and n D destination nodes D, n O , n D ≤ n. Let w represent a generic O-D pair agent and W the set of all O-D pair agents such that w ∈ W . Let R be a n O × n D matrix representing O-D demands where R od = R w entry indicates the demand of vehicles in unit time period which request to leave origin node o ∈ O to go to destination node d ∈ D. Let P w denote the set of available paths acceptable in terms of duration cost for each O-D pair w ∈ W taking into account fairness considerations. Furthermore, let P W be the set of all such paths. By acceptable in terms of duration cost, we mean the paths for O-D pair considering the upper bound in respect to the minimum duration among the paths for that O-D pair. All the path flows in PW can be gathered in the global path flow vector x W = (x 1 , . . . , x r ), where r = |P W |. Moreover, we define a feasible flow x w as a subvector of flows of paths k ∈ Pw . For describing the vehicle flows over the whole road network in terms of path flows, we introduce the [|W | * |P W |] O-D pair-path incidence matrix Ψ with rows indexed by w ∈ W and columns indexed by paths k ∈ PW .

Figure 1 :

 1 Figure 1: Proposed two-layer MAS architecture with the decision making models for each layer

Figure 2 :

 2 Figure 2: Proposed four-level dual decomposition approach.

  1 calculations are done by executing the following Stage 1 and the nested three stages. Parameters and variables: Each origin agent o ∈ O maintains the value of γ w for each O-D pair w ∈ W originating at o, and all the dual prices with the first index related with w and its paths k ∈ Pw : ζ w,w for all w ∈ W |w = w , ξ k and ξ kl where k ∈ Pw and l ∈ L(k), and µ w . On the other hand, each intersection agent j ∈ N maintains the capacities u a , duration costs f a , and dual price λ a for each outgoing arc a ∈ A(j), where A(j) is the set of outgoing arcs of node j. Initialization: set t 1 , t 2 , t 3 , t 4 = 0 and λ a (0) = 0 for all a ∈ A, ζ w,w (0) = 0 for all w, w ∈ W |w = w , ξ k (0) = 0 and ξ kl (0) = 0 for all k ∈ Pw and l ∈ L(k), and µ w = 0. For each O-D pair w ∈ W originating at o, each origin agent o ∈ O finds | Pw | shortest paths for nominal arcs costs (without traffic).

Step 2 . 4 Step 3 . 1 Step 3 . 2

 243132 Each origin node agent o ∈ O broadcasts x w (λ) := x w (λ, ζ) as the flow subvector in the solution of problem (32), for each w ∈ W originating from origin node o. Stage 3 (Primal-dual algorithm for solving problem (33)) Step 3.0 Set t 3 := 0. Each origin node agent o ∈ O sets ξ kl (0) := 0, for each path k ∈ Pw and l ∈ L(k), with w ∈ W originating from origin node o, and broadcasts them. For each w ∈ W , Lagrangean problem (36)-(38) is solved by calling Stage 4 and waiting for the broadcasted solution vector x w (λ, ζ, ξ) issued by the agent of origin node o ∈ O from which O-D pair w originates. Each origin node agent o solves a part of master problem (39) by updating dual variable ξ kl (t 3 + 1), for each path k ∈ Pw and l ∈ L(k), with w ∈ W originating from origin node o, with the gradient iterate (49), and broadcasts them.

Step 3 . 3 Step 3 . 4

 3334 Set t 3 := t 3 + 1 and go to Step 3.1, until satisfying termination criteria. Each origin node agent o ∈ O broadcasts x w (λ, ζ) := x w (λ, ζ, ξ) as the flow subvector in the solution of problem (33), for each w ∈ W originating from origin node o. Stage 4 (Primal-dual algorithm for solving problem (36)-(38)) Step 4.0 Set t 4 := 0. Each origin node agent o ∈ O sets µ w (0) := 0, for each O-D pair w ∈ W originating in origin node o, and broadcasts them.

Step 4 . 3 Step 4 . 4

 4344 Set t 4 := t 4 + 1 and go to Step 4.1, until satisfying termination criteria. Each origin node agent o ∈ O broadcasts x w (λ, ζ, ξ) := {x k (λ, ζ, ξ, µ w )} k∈ Pw as the flow subvector in the solution of problem (36)-(38), for each w ∈ W originating from origin node o.

Figure 3 :

 3 Figure 3: First example of the 10 simulated connected randomly generated Delaunay graphs with 50 nodes (intersections) on a map sized [10 × 10]

Figure 4 :

 4 Figure 4: Second example of the 10 simulated connected randomly generated Delaunay graphs with 50 nodes (intersections) on a map sized [10 × 10]

Figure 5 :

 5 Figure 5: Obtained results of mean path duration cost γ

  2.1 Lagrangean problem (33) is solved by calling Stage 3 and waiting for the broadcasted solution vector x w (λ, ζ) issued by the agent of origin node o ∈ O from which O-D pair w originates, for each w ∈ W . Each origin node agent o solves a part of master problem (34) by updating dual variable ζ ww (t 2 + 1), for each w ∈ W originating from origin node o and w ∈ W with w = w , with the gradient iterate (48), and broadcasts them. Set t 2 := t 2 + 1 and go to Step 2.1, until satisfying termination criteria.

	Step 2.2 Step 2.3

  4.1 Each origin node agent o ∈ O solves Lagrangean problem (44)-(45), for each path k ∈ P w with w ∈ W originating from origin node o, and broadcasts solution value x k (λ, ζ, ξ, µ w ). Each origin node agent o solves master problem (46) by updating dual variable µ w (t 4 + 1), for each O-D pair w ∈ W originating from origin node o, with the gradient iterate (50), and broadcasts them.

	Step 4.2

x k , x kl ; (λ, ζ, ξ, µ w ) . It follows that

Acknowledgements. The work of Marin Lujak and Sascha Ossowski has been partially supported by the Spanish Ministry of Economy and Competitiveness through the projects Agreement Technologies (grant CSD2007-0022; CONSOLIDER-INGENIO 2010), intelligent Human-Agent Societies (grant TIN2012-36586-C03-02), and Smart Delivery (grant RTC-2014-1850-4).