From 2021 to 2023, I conducted my research master in the field of autonomous driving, IoT, and optimization. The main title was something like “Application of metaheuristics to dynamic reversible lane at city-scale with real-time rerouting”, the research encompassed quite a large field with a diverse skillset. The project was successful, and great way to explore more about meta-heuristics and urban planning.
Project description
The keyword of this research is “dynamic reversible lanes”. It means that road lanes are allowed to change there direction in order to accommodate traffic. It is similar to reversible lanes, yet the dynamic aspect means that we do not have a fixed schedule, but rather a possibility to change the direction at any time.
The project is structured in two, collaborative parts. From a bird’s-eye view the we come from any road network and an expected traffic, we then define a strategy optimization and return an organization of lanes reversion, or which direction will be each road lane at a given time. We can adapt the reversion in real-time as the traffic will undergo unexpected events.
Reversible Lanes Scheduler
The reversible lanes scheduler is the main component of this project. It takes a road network and an expected traffic as an input. Then, it will simulate the network using SUMO (Simulation of Urban MObility), and determine how long it takes for all cars to finish their route, a metric known as Total Travel Time or TTT.
Once we have the baseline data, we run a genetic algorithm, a metaheuristic or optimization algorithm, to reduce this Total Travel Time. We generate alternative road network in which lanes have reverse direction, and we mesure the new TTT. Networks with low TTT have a high chance to pass their configuration to their descendants, while others are quickly removed.
After a determined amount of cycles, the network with the lowest TTT is kept as our model. It contains the information of which lane should be reversed at which time, making it suitable for classic, static lanes reversion, and allowing human driver to exist on the network.
Limiting the Lanes Reversion and Multi-Target Optimization
On issue of the lanes scheduler is that it tries to fit the network to the traffic (even randomized), so it may reverse as many roads as possible. Drastic changes in the road network are not desirable, and we want to avoid this kind of behavior. In addition to the first metric (TTT), we create a second metric known as Lanes Reversion (LR).
The LR metric is simply the sum of lanes changes in each step, a metric known as the hamming distance. It is easy to define and does not add a high overhead, however, it is difficult to integrate it with the TTT metric as it does not change at the same rate, and does not have the same dimension.
In order to solve it, we had to normalize both metrics. It is easy for LR, but not so much for the TTT (what are the maximum/minimum travel times?). Then, a lanes reversion cost, between 0 and 1, is chosen arbitrarily, and our final metric becomes (1 – cost) * TTT + cost * LR. With a cost of 1, we reduce lanes reversion number only, while a cost of 0 focuses on TTT, ignoring LR.
On average, the resulting network runs 20% faster. Yet, the longer the scheduler runs, the less precise it becomes, making it unsuitable for fast-changing situations. This is why I create a second, real-time rerouter.
Real Time Rerouter
This second optimization block changes the cars route in real time to accommodate unexpected traffic. It does not aim to be as radical as the lanes scheduler, but rather to provide a support on top of the existing organization.
As it is meant to be fast, we cannot run a full simulation as previously. The strategy used is to first analyse the road network by running random traffic on it and find the bottlenecks. As we need to speed up calculation time, we defined a correlation between the number of cars on a road and the average speed of this cars, a relation known as the fundamental diagram of traffic flow. We keep the resulting diagram for later.
The final step is to take apply this diagram to the network. We will use a predictive analysis: we fetch the cars positions and their future route. We input that information in our previously generated diagram of traffic flow, which results in a speed estimation for all cars. As we know the length of the route of cars, we can infer the expected travel travel. Adding this information for all cars gives use a Total Travel Time, or TTT.
As a side note, computing the travel time of one car and adding to the other cars may seem to ignore the cars dynamics (cars have an impact on each other), but this is not true. When we computed our diagram of traffic flow, it was in a configuration in many cars, which means that our computation is valid on average! Of course it won’t be true with only one car on the network, but in this case their is no traffic jam, and no need for lanes reversion…
The rerouting efficiency basically improves TTT by 10% done alone, yet we have to integrate it into our lanes reversion system.
Final evaluation
With all the building blocks defined, we can make the simulation run with all the parameters. By the end of the research, the results were satisfying with 25% increase in traffic. On average, the reversible lanes scheduler proved to be efficient to reduce bottleneck, while the rerouter was useful but did not significativelly increase the traffic conditions.