Solving traffic jam with a quantum computer


20 Jun 2017 Frankfurt - During the Quantum Annealing session on Tuesday morning at ISC17, Christian Seidel from Volkswagen asked the audience whether there is a real-world problem that could be addressed with a quantum computer. Indeed there is, namely traffic flow optimisation. Everybody is familiar with traffic jam and nobody likes it. He showed the audience how you can maximize traffic flow using the D-Wave quantum annealer. The team at Volkswagen consists among others of Gabriele Compostella and Florian Neukart.

The public data set was taken from the T-Drive trajectory. Christian Seidel said that the city of Beijing has about 10.000 taxis. His team used the D-Wave calculation model, Quadratic unconstrained binary optimization (QUBO) to address the traffic flow problem. During the quantum annealing process the system evolves to the lowest energy level.

Christian Seidel and his colleagues transformed the real world problem for the quantum computer. They simplified the graph structure representing a route grid with 2 cars and 3 route options on a 2x2 grid and created binary variables.

The team then generated the cost function for each route segment. More cars on one street lead to higher costs.

The team also added constraints. They wanted to make sure that the solution would contain only one route for each car and only one binary variable per car. Otherwise the car would be on multiple routes simultaneously. They also had to exclude Qij= 0 because otherwise no car would be on the route.

The data pre-processing consisted in transforming the geo-coordinates to street segments using OSMnx, a Python package for street networks. They assigned each of the 418 cars.

The result that Christian Seidel showed was un-optimised traffic versus an non-optimised traffic flow.

The work still needs further improvements. Due to the 2,5 months project time the team treated in this test all streets equally. Obviously, this is a simplification. Additional constraints could be street capacity and residential zones.

The lessons learnt are that the D-Wave Quantum Annealer can help solving real world problems. Transforming the real world problem into a QUBO takes the most time, Christian Seidel explained. Problems larger than the chip's capacity can be solved by decomposition using a hybrid solver.

Due to the chimera graph structure of the quantum chip, it is not fully connected so qubit chains need to be created. In order to challenge the precision, the team has to find the right values for chain strengths and penalty weights.

Leslie Versweyveld