Capacity Based Model

Capacity Based Model#

This section is a brief documentation to the Capacity Based Model included in the Polaris project.

Model#

The model assumes that each signalized intersection can be interpreted as a node having a capacity (Dimension : cars/hour).

  • From a road point of view, it releases a certain number of car proportionate to its capacity at each time. This capacity is related to the road parameters.

  • From a car point of view, it traveled within the network : it enters a traveling area and then a queue/lane on each road

The capacity calculation is realized thanks to the Highway Capacity Manual 2010 - Chapter 18 (Signalized Intersections) - page 35 and further.

Finally, to validate this capacity based model, VisSim was used to compare the results.

Advantages#

This model is designed to calculate the average duration of vehicles in the network. It can be the average duration of a flow of vehicle having the same path within the network or the duration of a single vehicle in the network.

This model also handles the average length of a queue at an intersection for a congested network and semi-congested [To be verified with different simulations]

Because it is a non-sequential mesoscopic model, the calculation time is faster than a microscopic model and it can be parallelized (See “Next Steps” section)

Drawbacks#

In real life, intersections includes phases : red and green phases. It gives a “wave” effect : the cars are released together during green phases, then stopped together during red phases, etc. On the other hand, the model releases a certain number of vehicles at each time. Due to this fact, a direct comparison between cars in the Capacity Based Model and in real life is not possible - it cannot be the purpose of a non-microscopic model.

During a warm up time, before the network gets its stable parameters, the metrics (duration in the traffic, average length) are different (Vissim Versus Capacity Based Model at least) and are difficult to compare.

Data structure#

This section explains the data structure used to run the capacity based model. The cars travel within the network, from roads to roads, crossing signalized intersections depending on their capacity.

Picture 1 :

Cars#

The cars are described by :

  • ID (Car number)

  • Entering and exiting nodes

  • Entering time

  • Parameters : length, reaction time, maximum acceleration

Some iterators are also used to describe :

  • The time they spent to get into a queue after entering a road.

  • Their state : In/Out of a queue & Position in the queue

Roads#

The roads are described by :

  • ID

  • Starting and finishing nodes

  • Parameters : maximum speed, length, distance between cars in queues

A road is a portion of the network going from a node A to a node B. It includes three parts :

  • The individual queues. They are described in the next subsection.

  • The common queue. The common queue is a vector of car. It starts to exist once the individual queues are full. In real life, it models the fact at some point, far enough from the exit of a road, a car might block another road by its wish to turn. As refereed in Picture2, the common queue starts when one individual queue gets full

  • The traveling area. This area is composed by the cars that entered the road but do not reach the queues (Individual or Common) yet.

Queues#

The queues are described by :

  • ID

  • Maximum length before having a common queue

  • Distance between cars

  • Capacities depending on the next road (Each turning movement leads to a road, and they might be more than one turning movement, so more than one next road for each lane) Queues are part of the roads. A queue describes one or more turning movement (left, right, straight, merge, U-turn …), each of them leading to another road. These movements can be understood on the Picture 1.

Picture 2 :

Inputs#

This section introduces the way the network and the cars are imported from SQLite databases to fit the project data structure.

From the Supply SQLite Database to the C++ Network#

Among the SQLite database describing the supply, there are the following items :

  • The nodes

  • The links (Node A - Node B, description of the direction : A->B & B->A). Parameters : length, type, use, grade, speed, left and right movement, …

  • The connections. They describes how the links are connected one to the other : number of lane, type of movement, …

The parameters mentioned previously are used to assign a capacity value for each turning movement of each lane.

!!! However, as for now, some of the parameters of the capacity calculation are default value! They should be changed (See “Next Steps” section) !!!

From the Demand SQLite Database to the C++ Cars#

The SQLite database describing the demand includes all the trips in the network. Each trip describes a car and give the entering time in the system as well as the origin and destination connections (Which should be related to the connection table of the database describing the supply. This table gives the link and the direction associated to the connection mentioned above.) This information leads to an entering and exiting node.

From the C++ Car (Entering,Exiting) Node to their entire path#

As stated previously, the SQLite database describing the demand only gives the entering time, the entering node and the exiting node. Some parameters are missing such as the car length, the maximum acceleration and especially the path.

!!! A algorithm needs to be added to turn the (Entering, Exiting) node pairs into real path for each car. Shortest path algorithm (Dijkstra) can be used to find the path. !!! (See “Next Steps” section)

Simulation#

The model is based on a loop for which a simulation time and a timestep are defined. It relies on 4 main parts that are briefly described in the following subsection but a more detailed documentation can be find here : Capacity Based Model : Detailed documentation

The next subsections assume that the model is run between t and t+Δt

Add new cars#

A vector of cars has been creating while converting the SQLite demand database. All the cars are reviewed. If the entering time fits t and t+Δt, then the cars is added in the network. The cars are sorted so if the car entering time is bigger than t+Δt, the loop is broken. Also, the algorithm verifies if there is room left on the road for the entering car. If not, the entering time is postponed by Δt.

Store cars allowed to cross an intersection based on the capacity#

For each lane of each road, the model evaluates the number of cars that can cross the intersection to the next roads (The cars mey head to different direction as each lane may include several turning movement). This number of cars is based on the capacity The output is a vector of cars able to move from their position to the next one. Let’s called this vector storedCars. This vector includes the road ID and the queue ID where the cars come from.

Release cars from traveling areas to queues#

For each road, the cars in the traveling areas are reviewed to, either :

  • Reach an individual queue allowing the turning movement the car needs

  • Reach the common queue if all the individuals queues going to the following road are full (Or if the common queue is not empty - it would mean that there are cars ahead blocking the access to the individual queues)

  • Keep on moving in the traveling area if any queue has been reached (Individual or common queue) because there are still far ahead of the car

Release cars from queues to traveling areas#

For each road, the cars that may cross the intersections where are waiting are reviewed. To do so, the storedCars vector (Defined previously, two subsections above) is reviewed :

  • Only those that are willing to enter the road being analyzed are kept. A selectedCars vector is created with these cars.

  • A random sampling is made out of the selectedCars vector. (See “Next Steps”)

  • The cars enter the new road only if they meet the condition that they fit in the road (based on the length of the road). If so, they are stored in a movingCars vector. If not, they are stored in a stuckCars vector.

  • The movingCars and stuckCars vectors impact the storedCars vector : Actually, if the car has moved, the next one can move too. If the car is stucked, all the cars after this one are stuck.

Outputs#

During the simulation, at each time-step :

  • The cars store their state : In/Out of a queue & Position in the queue

  • The roads store their queue length.

Cars progression#

During the simulation, the state of the cars is stored in dedicated vectors at each timestep. Then, a post-process is able to return the speed profile base on a quick and dirty model.

  • If the car moves in the queue, the integral of its speed must be equal to the distance between the two position

  • If the car gets out of the queue, its speed increases to a maximum value, unless it does not have enough time to reach this value.

Queues length#

During the simulation, the length of the “global” queue length road is stored in a dedicated vector at each time-step. “Global” means that there might be several lanes ; only the longest one is stored)

Next steps#

Some part of this model needs to be improved in order to be as accurate as possible :

Too much default value#

There are default value in the solution that impact the simulation such as :

  • the factors of the capacity equation

  • the distance between cars in the common (road.h) and individual (queue.h) queues

  • … All the default value are mentioned in comments (// Default Value).

  1. They should be the same for every car/road/queue/… OR depend on each car/road/queue/…

  2. Most of the value were choose independently of any literature. They should be checked and and confirmed or changed

The most important default value to change is the effective green time of each intersection. It should be imported from the SQLite Database if there is any mention of the traffic light (A stop might also have a capacity somehow)

Converting (Entering, Exiting) car node into a real path#

The model is designed to goes this way :

  1. The SQLite Database is imported for cars in importCars.h and importCars.cpp - the entering and exiting nodes are stored within each car parameters

  2. In carsPath.h and carsPath.cpp, the model converts the entering and exiting nodes (of each car) to a real path depending on the network. Different models can be used to calculate this path : it can include the roads length, the number of lanes …

  3. The cars have a path to go through during the simulation. As for now, it is static (Calculated once at the beginning of the simulation) but a solution might include recalculate the path at each time step depending on the congestion of each road (Connected Vehicles?) or splitting the cars between the connected and the non connected one (Static calculation Versus Dynamic calculation of the path)

Problem : As for now, the model does not deal with the second part. The path is written manually in the car constructor (car.cpp).

Car::Car(bool _fake, int _carNumber, double _carLength, int _reacDuration, int _enterTime, double _maximumAcceleration) {
	fake = _fake;
	carNumber = _carNumber;
	carLength = _carLength;
	reacDuration = _reacDuration;
	enterTime = _enterTime;
	maximumAcceleration = _maximumAcceleration;

	progression.clear();
	reacIter = 0;
	position = 0;
	distInTA = 0;

	path.clear();
	path.push_back(83938);
	path.push_back(83939);
	path.push_back(83941);
	path.push_back(83937);
	path.push_back(83936);
	path.push_back(83935);
	path.push_back(83943);

	enterNodeA = 83938;
	enterNodeB = 83939;
	exitNode = 83943;
}

Idea : Use a shortest path algorithm (Dijkstra?) to convert the pair (entering node, exiting node) into a path that the car has to go through

Selection of the road within a road#

When a car is on a road, it has to select a lane to go through - several lanes can have the desired turning movement. This lane obviously has to go to the next node where the car is going. Sometime, there are several lanes going to the same next road. Selecting one of these roads should be done with respect to :

  • The number of other cars in the lane

  • The number of turning moving

  • … ? A model has been added but it has not been validated (queues.cpp)

int Queue::weight(int nextNode) {
	int weight;
	bool exist = false;
	for(vector<int>::iterator it = nextNodes.begin() ; it != nextNodes.end() ; it++) {	// To verify is the nextNode (Where the car is going) is part of the turning movement of this queue
		if((*it) == nextNode) {
			exist = true;
			break;
		}
	}

	if(exist && length() < maxLength)	//(exist == true) -> means that the nextNode is part of the turning movement of the present queue && length() is the length of all the vehicles in the queue
		weight = cars.size()*2 + nextNodes.size()*5; // This is the model comparing the queues. 2 and 5 are the linear coefficient affected to the number of cars and number of turning movement of the road
	else
		weight = 900000;

	return weight;
}

Parallelized the computing calculation#

Because the calculations within storage.cpp or toqueues.cpp or totravarea.cpp are not sequential (What happens at Road(i,j) is independent of what is calculated at Road(i’,j’) ), these calculations can be easily be multi-thread to parallelized the calculation part.

Cars sampling#

To check the cars entering a road, the model performs a loop through all the cars moving between t and t+Δt. This loop is sequential. In fact, the cars enter a road in a particular order. As for now, among all the cars entering a road, a random sampling algorithm choose the order. This might have an impact on the model. If so, another sampling algorithm may be choose.

!! Let’s say :

  • 2 cars are able to enter Road A from Road B (based on the capacity)

  • 3 from Road C

  • 1 from Road D

The model is designed a way it first deals with the vector (One car from Road B, One from Road C, One from Road D) and then, (One from Road B, One from Road C) and finally (One from Road C) [If the previous cars have been allowed to cross the intersection based on the road length]. So the sampling algorithm cannot sampled the cars this way : Car from (C,C,D,B,B,C). It has to be a permutation of (B,C,D) then a permutation of (B,C) then C.

It is due to the fact that a lane can have several turning movements, so it needs to check the first cars first (If the first car does not move, then the next ones neither)

SQLite Database Structure#

[About the SQLite Database] In the connection table, the ‘lanes’ or ‘to_lanes’ are sometimes referred to as “R1”, “L1”, “R2”, “L2”, … (Meaning Left or Right) but it does not mention a particular lane number. If Road R has 5 lanes, number 1 is the rightmost and number 5 is leftmost, is L1 the number 4 or 5. What about L2, R1, R2 …?? It can deeply impact the turning movements of the model