2) *Network* In order to build the structure of a planar network (for example hydrographic or of roads), we do not store faces but the polar order of succession in the edges. Each edge stores the next edge turning left and the prior edge turning right. This structure is known as DCEL, Doubly Connected Edge List [5]. The algorithm to generate this topology uses the same dynamic quadtree structure to build the DCEL.

The road network often exists in 3D, although despite the existence of this possibility, most shapefiles only contain a 2D 
geometric representation. The data provider must in that case model the altitude differently, and our algorithm must be adapted to this. For example *NAVTEQ*'s Navstreets [6] uses another layer called z-levels that must be consulted to know whether a point corresponds to a node or not.

At the end of this step, we have a topological graph that is structured like the road network, but without its semantics. We will now build from it and from the database part of the shapefile a non-topological graph that models this ontology.

## E. From Static Topology To Traffic-Oriented Network 1) Traffic Oriented Graph

Our traffic model is individual-based: each vehicle will be modeled as an agent. This implies the creation of an adapted environment for them, in terms both suitable to their ontology and adapted to the geographic data we reaped. For that a graph will be built, a *transport graph* that will contain the necessary structures and values.

This first version of our models is only interested in simulating motor vehicle: pedestrians and bicycle are ignored.

The database contains the sense of travel and the traffic restrictions for each topological edge. One oriented edge is created for each sense of direction allowed for motor vehicles.

Edges and vertices of the transport graph are called elements. To each element is associated a *data container* and a vehicle transporter.

The *data* associated to an edge are for example its geometric length, its number of lanes, its speed limits etc.

The data associated to a vertex is notably the size of the container of its transporter, depending on the number and the sizes of the edges connected to him.

Transporters are non-mobile agents associated to elements. 

They handle parts of the collective behavior of the vehicles.

They will be described in more depth in the following section.

2) *Routes in the graph* Mobile agents will try to reach destinations in the graph. As we intend to simulate a realistic traffic of tens of thousand of vehicles, we want to facilitate their computing of their trajectory. To do that, we build a set of "shortest" path stored in the traffic graph.

We compute a weight on the edges that combines different parts of its data: its length, the speed it can reasonably be driven upon, its estimated width based on the number of lanes etc. to model the attractiveness of this edge. After that we compute Dijkstra's algorithms [7] from each vertex to all the others, which we store in each vertex. This data takes 
(numberOfVertices)2 bytes of data, which is important, but allows the computation of a good path by an agent in constant time, which is a good thing as hundreds of agents are generated at all time in the simulation (simulating vehicles entering the road network of the simulated urban agglomeration).

## Iii. Mobile Agents Of The Network

Our agents are mainly so far car agents, trying to go from one place to another.

## A. Strategic Behavior

Modeling in details the various detailed trajectories of car users is a research problem in itself [8]. Nonetheless we are not interested in who did what or why, but only in what are the fluxes in our network in typical scenarios. When an agent is injected in the network, a starting point and a destination are randomly chosen. 

![0_image_0.png](0_image_0.png)

This randomness is not necessarily uniform. If we suppose the agglomeration centered on its main town, like the agglomeration of Rouen that we simulated more than others, we can shape different distribution, favoring the likelihood of drawing rather a inner or an outer edge for example. Traffic between 8:00 AM and 9:00 AM for example starts mainly on the border or outside the agglomeration and ends to the same distance to the center (outer edges): we can simulate traffic that do that. When shops close in the town center, we have a traffic that is mainly outer bound, with a more important center generation: we can simulate that. We do not have to know what this car and its driver did in the morning, we don't have to simulate realistically its history, as long as we model the actual traffic fluxes right.

Once the agent knows where it is, and what its destination is, it can use the best paths stored in the traffic network to plan a trajectory. It then drives here, adapting his path through its tactical behavior, and managing its immediate surroundings through its operational behavior.

## B. Operational Behavior

The planned trajectory of an agent is a succession of edges. 

Once in an edge the agent tries to drive to its end, the next connection, where it will be able to choose the next planned edge.

When it enters an edge, the agent first chooses a lane if several are available, based on the traffic density in each, with a bias for the rightmost lane. As we have a good geometric description of the lane, the driving behavior is fairly detailed, incorporating the length of the car, its capacity/will to 