Operations ResearchPython

Python’s Traffic assignment module (All or Nothing)

WARNING: THIS CODE HAS BEEN DEPRECATED. FOR THE NEW STUFF GO TO https://github.com/aequilibrae/aequilibrae

Lately, I have been dealing a lot with traffic assignment problems of several types, but mostly All or Nothing and user equilibrium in some not so large networks. It is true that I could use something like Cube or TransCad, but I find TransCad post-processing capabilities not ideal if you want to do some non-standard analysis and Cube is even worse, as the GIS interface is very slow (the whole rendering thing is much slower than TransCad).

Ideally, I’d like to have an assignment procedure that returned me all the results in NumPy arrays, which results in a lot of firepower for data analysis and a vast array of libraries and free code to use.

Writing an assignment algorithm in pure python would be just silly, as the performance would be extremely poor, but there is a very nice tool called Cython. Basically, Cython allows you to write code in a mix of Python and C that is translated into C code and compiled to a Python library. I sounded like magic to me at first, and it sure is VERY good.

In parallel with this discovery, I also found a very good implementation of a Dijkstra algorithm inside SciPy written by Jake Vanderplas. It is true that the implementation could be improved by replacing the Fibonacci Heap with a simple Min Heap, but the difference would likely be very small.

Having Cython and the code Jake wrote (all in Cython) made things extremely easy, and I decided to share with people out there that might need it. It is important to note that the AoN library I generated is NOT DEPENDENT on Scipy, and the sparse matrix used by Jake is actually a forward start, which I just substituted by a forward star code I wrote myself.

I’m posting here two different packages:

  1. A compiled code to use with a standard installation of Python 2.7.x and NumPy 1.7.x (32bits)
  2. The source code in Cython and all the necessary files to compile the code

Both packages come with the examples I used, being a graph and a demand matrix so you know exactly what is the format I’m using (the NumPy arrays I use in the library have the exact same structure of the CSV files).

Some things you will have to take care of by yourself if you want to use it fully on an assignment:

  1. Remove the outbound centroid connectors for all links that are not the origin of the flows each time you assign one to all so you don’t have flows through centroids
  2. Make the code parallel, which is extremely easy.

The performance of the code is very good, and usually about 30% to 40% slower than TransCad for the instances I tested on, but if you take into consideration the time it takes to migrate from one platform to another to perform analysis, then you can save time by using the code. Cube has a similar performance to TransCad (all tests using multiprocessing in all software). And this one is FREE, which makes quite a difference… Right?

I also already implemented an equilibrium assignment using the traditional Frank-Wolfe and will try to make it available soon…

Again, comments are very welcome and so are questions.

11 thoughts on “Python’s Traffic assignment module (All or Nothing)

  1. !!
    I found this while looking things about Python and TransCAD, since I am currently learning Python and want to make the most of it.

    Your posts are amazing, great work!

  2. Pedro,

    Happened to find this by accident after a while I was looking for a program or code, I tried quite a while to find something for the User Equilibrium assignment, surprisingly I found nothing. As you have said I also didn’t like the idea of re-inventing wheels again. I appreciate your effort and your idea about this webpage.

    I have worked on a program using the convex combination based on Python for the UE assignment problem, however not being so positive as you said about the performance efficiency. I am totally considering your advice about Cython. I will be waiting for your next post and the UEA implementation using Frank Wolf algorithm.

  3. Dear Pedro,

    I’me very interested in reading your model in python. I would like to know if you run python from windows or Linux.

    My Best Regards,

    Edmond Alite

  4. Hi, just to say, that your All or Nothing assignment module has been of tremendous help on my masters thesis. However I need a 64bit version of it to work with my python(2.7) 64bit code but I have tried to compile the source code thus:

    I) I compiled the setup_Assignment.py file to get an AoN.c file using cython
    II)I then compiled the AoN.c with a c compiler(generated this error: fatal error: pyconfig.h: no such file or directory as pyconfig.h)

    These, were done with 64bit compilers and despite the errors, a .pyd file was produced despite the error, and that in turn generated this error when I tried to run the script:

    Buffer dtype mismatch, expected ‘ITYPE_t’ but got ‘long long’

    Please help me with the 64bit version if you have it or better still guide me on how to go about compiling the code so it works on a 64bit python. Thank you

  5. How about using Visum? It stores all the path information in a neat container and has COM methods which can be used to easily extract path data… Since it has a proper COM model, it is easy to automate using Python. No platform migration required.

  6. Dear Pedro,
    i have a problem when i am doin tha traffic assignment in aequalibrae. When i press assign it runs normaly 100% the first 3 fiels (1:Link IDs uniqueness check, 2:matrix loading finalized, 3: graph 9422 gis links, -1 directedlinks, i don;t know if this is normal) until when it gets to the fourth field all or nothing assignment which it dosent run at all and its stay to 0%.
    Any help?

  7. Dear Pedro,
    Thank you so much for sharing your work. It is such a help especially for a newbie to the programming world. I’m currently completing my undergrad in civil engineering at the University of Cape Town.
    Two things I have to ask:
    1) I’m using Python 3.5 and cannot seem to import the AoN.pyd file, are you able to explain how to do so?
    2) Could you perhaps kindly share User Equilibrium Assignment packages?

    Kind regards,

  8. Hi Pedro,

    I am using your traffic assignment module on a 13 node network which has a total of 24 links. I have a question though, does your module automatically assume bi-directional links?

    In my network there is a scenario where the shortest path between node 1 and 12 is 1 – 3- 7 – 10 – 9 – 12. Your module only assigns volumes to links 1 – 3 – 6 – 9 – 12 though (which is a longer path due to the weighting on those links).

    When I swap 10 and 9 around, making the shortest path: 1 – 3 – 7 – 9 – 10 – 12 your module then assigns the traffic to that shortest path.

    What are your thoughts on this?

    1. Andrew,
      Bi-directionality is not assumed. Please take a look at the new QGIS interface for creating Graphs and it should provide you with the necessary insight on the topic.

  9. Thank you for your coding. I am almost a beginner and have difficulty using the “AoN.pyd”.
    How can I install it?

    1. The idea is to use AequilibraE as a Python package, as I describe in one of my latest posts (The new version of AequilibraE with a Python API)

Comments are closed.