[ishaym]

Hi, I am an algorithm developer at optibus. So I can explain the logic of the use of heuristics in this case. We actually use MIP solvers for many of our problems, and are quite proficient with it. However, mass transit problems, especially in large cities, tend to be highly complex for CPLEX or any other solver to solve out of the box. There are billions of variables, and many global constrains which involves: vehicle types, multiple depots, fueling and charging considerations, driver unions and regulation, and hundreds of others. Simply using generic solver (though very advanced one) works well for small instances but doesn’t scale well for medium to large ones. Just fitting the model in memory is challenging. We, at Optibus, are distributing the problem using massive cloud resources and dedicated algorithms, and use a mixture of this, MIP solvers, and the heuristics discussed in the article. We wanted to keep our competitive edge, but hopefully, we may write a blog post about it in the near future.

[wenc]

Makes sense. MIPs are good for getting to rigorous optimality, but right now they have limits to their scaling (every binary variable and every inequality constraint you add increases the complexity of the problem).

Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights).

If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.