An optimizer for a city traffic light scheduling.
A project for the Google HashCode competition, where the challenge is to find the best solution possible for a problem within a limited amount of time. We had 4 hours to code everything and run the optimizer to find the best solution!
The problem
A particular traffic light schedule controls, for each traffic light in the city, how much green-light time should be given to each incoming street in the intersection (every intersection has one such street light). Only one incoming street can be given a green light that allows cars to pass; cars will have to queue at the other streets.
Given a city – represented as a directed graph where nodes are intersections between streets – and a number of cars in certain positions, a traffic light schedule will obtain a certain number of points, roughly proportional to the efficiency of the schedule (minmizing the total delay of all cars arriving at their destinations), with some added technicalities defined in the official rules. The goal is to find the best schedule.
There’s a long list of details that make the problem particularly hard to code: cars queue behind other cars when waiting at intersections; they move at a certain speed; when a green light turns red, maybe not all queued cars have been allowed to pass; etc.
The full problem statement can be found on the official documentation, along with the data for the different scenarios.
Our solution
We split the problem in two:
- On the highest level is an optimizer that uses simulated annealing to approximate the global maximum. It starts with a random (valid) schedule and slightly tweaks it to improve upon it. The process goes on until convergence.
- The optimizer needs a way to test how good the given solution is, so we built a simulation of the traffic scenario, that runs the whole thing: cars, traffic lights, queues and everything. And, most importantly, it measures the time it takes for each car to reach its destination in order to compute the total score.
Other tricks we used
- A bad solution is better than no solution. The simulation took a very long time to code, which meant that we had little remaining time for the optimization process per se. So in some cases we decided to submit a random (but valid and reasonable) schedule that, even though it was not optimal, gave us some decent score.
- No time for multiprocessing, just fake it! Running the simulation turned out to be a huge bottleneck in the optimization process, sometimes taking several seconds for the large scenarios (keep in mind that the simulation needs to be run a huge amount of times in order to try many different schedules). A reasonable idea would be to implement some sort of parallel computing and try multiple simulations at once; however, that takes time to code, which we didn’t have. Our solution was to run the multiprocessing ourselves by running multiple optimizers at once, each one using a different CPU core (plus, each team member can run their own). Since the starting position is different every time, we are essentially exploring different regions of the search space.