Quantum paths finding algorithm

The aim of this work is to design a hybrid quantum-classical algorithm to solve an optimization problem in the traffic flow domain. The basic idea is to spread vehicles on different paths in order to make the traffic as fluent as possible, while also minimizing the exposure to air pollution along the path. The problem is represented as Quadratic Unconstrained Binary Optimization (QUBO), that is a combinatorial optimization problem, frequently used for computer science applications. Such QUBO formulation can be mapped on a Quantum Annealer, a special machine that performs Adiabatic quantum computation. The problem is thus formulated: Given two distinct points in a city, a defined number of paths are selected among a set generated by Open Street Maps APIs. These paths are selected using a classical greedy algorithm, that results in a compromise between computational time and quality of the solution. At this point a basic QUBO matrix is built starting from the description in the foundational paper for this domain (Volkswagen and D-Wave, 2017). Generated matrixes are perturbed in two parts: •??The former part takes in consideration the coexistence time of two or more cars on the same street segment. For each car it is also considered the departure time. To simplify the problem a constant velocity is considered for all cars. •??The latter part performs a pollution evaluation as malus of the optimization. One is applied to each path to take in consideration the cost of pollution level all along the way and another for each path couples that consider the pollution cost only for common street segments. The formulated problem is solved on a D-wave quantum annealer and QPU parameters are properly tuned to ensure a good and appreciable solution.