Poor results in simulating the python code for traffic optimization done by Volkswagen
I've been studying this project for a few months and based on Volkswagen's article and also the powerpoint about simulating the traffic optimization in leap website, I wrote a python code for two cars and three paths. But every time I run the program I get thoroughly different results. The qubo has completely the same coefficients as what is mentioned in leap and I don't know where the problem is. I appreciate it if someone can help me in anyway or introduce me someone who can help me.
I send the python file and also an example which shows the different results in attachment. I'll also attach the article and powerpoint(in pdf format)
By the way I tested it with different scaling factors but nothing changed.
https://github.com/mohsenbahremand/Traffic-optimization/blob/master/Traffic%20optimization%20code
https://www.dwavesys.com/media/erzjluvs/qubits-day-2-morning-5-vw.pdf
https://www.frontiersin.org/articles/10.3389/fict.2017.00029/full
Comments
Mohsen,
Thank you for posting your code. I am relatively new to using quantum annealing and your code was helpful in my understanding of the paper and in working with the QPU.
I am still learning, but for more consistent results, I would try to use minorminer to generate and save an embedding (or several) and use that embedding with FixedEmbeddingComposite. Then try various values for the scaling function to find the right level of scaling for the constraint penalties.
While playing around with your code this weekend (especially with the higher values of k (approx 35), I found that the results of your code were fine, not poor. What makes you think you were getting poor results?
Thank you again for posting your code. It makes it a lot easier to answer questions when you can see the specifics of the code.
Ed C.
Thank you for putting time on my question.
Actually I didn't understand completely the part about scaling factor in the paper but as far as I understood, it was claiming that it must be something about 2 or 3 and I didn't try a number like 35. My largest scaling factor was 10 and even with that, every time I got completely different results.
I will try what you said about fixed embedding and ask questions if necessary.
I appreciate you again for your help!
To understand the scaling factor, look at the traffic flow optimization problem as a constrained optimization problem. The constraint is that each car must be on exactly one route at a time. The cost to be minimized is the amount of congestion. The scaling factor is used to balance the conflicting goals of having one route per car and minimizing the congestion.
When the scaling factor is too low, the congestion goal is given priority. That is why when you used low values of k, most of the results were not valid (where each car must be on exactly one route). Since the penalty for violating that constraint was so low, the algorithm found that the best way to reduce congestion was to only schedule one car. By increasing the scaling factor to 35 (just an arbitrary number, I did not calculate it as the optimum, it is not), the algorithm penalized constraint violations more, so the result set from the QPU contained more valid solutions. The best value of k would be that which balances the goals. I missed the part in the article where they gave a way to calculate the best value of k (or lambda in the article). I'll take a look at that again.
Thank you for your answer Ed C!
I got the concept more or less but most of my problem is also about determining the value of k. According to the article the value of K for a problem with 2 cars and 3 routes must be something about 2 or 3 but in practical answers it's way larger than that and maybe that's why I can't get reasonable results.
Please sign in to leave a comment.