> Is the main RAM usage from the graph or is the algorithm RAM intense?

The graph itself is negligible, unless you want to store lots of auxiliary data (street addresses and whatnot), but then those are already on the disk, and you don't need them in memory for this problem. The traffic data is somewhat bigger, e.g. a few hundred float64's per edge, so like 100 MB for |E| = 40k edges would be normal (no pun intended) but that's (a) just something that depends on the sizes of your distributions and not the algorithm, and (b) something that you can discard and re-generate on the fly from the continuous-time distribution parameters, at a speed cost.

The main memory usage is for storing the policy solution itself. For a discrete budget T (say, 5k steps) and |V| vertices (say, 10k) you need approximately T * |V| float64's just to store the policy solution (e.g. 200 MB). And if you want the convolutions to be done in guaranteed quasilinear time, you can pay a penalty of T * |E|, which would be e.g. 800 MB (4 roads per intersection). This is not necessarily necessary though, it just depends on the problem parameters. Sometimes naive convolution is faster too. (Actually, I just lied a bit, because for every edge you don't need a vector of size T, but a smaller vector of size (T - min_travel_time_to_destination_from_edge_source), so what I gave you is somewhat of an overestimate. But that's the general ballpark.)

For computing the path, an algorithm that doesn't need to pre-compute a policy may (or may not) use less memory, so for that problem, the policy's memory usage can be ascribed to the algorithm. However, I don't really expect the memory usage of a different algorithm for the same exact problem to be radically different. (You can of course make approximations, etc. but then it's not the same problem or necessarily the same solution.)

> I'm asking as other open source projects (like ours, see my profile) might not look in your code just because of the license. And yes, that is the tricky thing about open source: accept that other people make money with it and try to do this too ;)

(Edit: I edited this comment since I realized I initially misunderstood your licensing model.)

I think a few key difference between our projects (and therefore licensing models) are:

1. Just how much more computationally intensive this problem is compared to standard routing. For me to adopt your model of providing a paid service while making the code free for commercial use, I would not only have to spend a significant amount of time writing service APIs for this (I have other things to do than to start this business!), but I'd have to invest in quite a large cluster of servers -- 1000 CPUs per metropolitan road network seems to be the minimum for this problem to get decent query times. (Again, note that a reasonable query on a sub-portion of San Francisco takes 15 seconds, and this is already making the unrealistic assumption that traffic is constant throughout the day.) Both of those just seem unrealistic for me, so I'm just saying if someone else actually thinks such a business would be profitable and would like to take up those tasks, they can request a commercial license.

I'm not sure anyone should use this commercially, though -- see the next point.

2. I simply have not designed or even intended this project for production usage, whether paid or free... and the license is meant to emphasize that. It's for researchers, meaning it's meant to be short & easy to tweak. It's not particularly well-written code, there is no clear API at all, there are many "engineering" tricks/approximations that would need to be put in for actual real-world usage, etc... and to be honest, I actually don't want poorly-written code to go into production use! I think that is one of the things that is actually harming us in the modern era. So I would rather that anyone who wants to use the algorithm just rewrites their own code in a better way for production usage, and not even use my code. Honestly, they would probably have to understand the code well enough to be able to rewrite it in a breeze if they want to modify it enough to make it useful.

So, basically, the commercial-license clause was the "else" clause in the license. :-) Like I wrote there, I didn't necessarily think this clause should ever be hit. Chances are good that even if someone contacts me, they'll change their mind and decide it's outright easier in anything but the very-short-term for them to just write their own code based on the paper (and that this would be more profitable would just be icing on the cake). But in case for some reason they don't think that, I didn't want to leave any doors closed, so I included that option.