ishaym

The edges between the trips mean that one trip can be performed after the other on the same vehicle. The costs on these edges represent the distance of the idle trip - if they are far away - it would be more expensive. The depot pull outs are connected to the earlier trips,and depot pull ins to the later trips. The cost of these edges also represents the distance of the depot from this trip.

Which one? I'd be glad to explain

Right you are :) See my reply later on this thread (ishay from optibus)

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.

Hi, I am actually an algorithm dev at Optibus, so I can provide a few insights. 1) Naturally, mass transit operators optimize for highest payoff - so they would try to use the least number of buses, least number of drivers' work hours, least deadheads etc. However, the government rightfully enforces both driver work regulations (enough rest, coffee breaks etc) and highly penalize them for service unreliability - each city is different, but in general - if a bus is late for more than X minutes\doesn't show up, the operator will get a heavy fine. Also - if consumer satisfaction is low, this operator will not get to operate the city's buses again, so they try to keep them reasonably high. 2) for these reasons, service reliability (or dependability) is animportant factor. in general - schedulers should have a few reserve vehicles and drivers, so that in case of a delayed bus - they can replace it with their reserve. Here, at Optibus, we have started a pilot where after looking at historical data, we use AI to predict which trips are likely to be delayed. and by how much. With our predictions we first warn the operator that the estimate for this trip is questionable, and more importantly, build the schedule accordingly - give more time spread between these trips and the next scheduleued trip on this vehicle, so that this delay will not affect subsequeent trips and cause a cascade of delays. This way - we make the schedule more robust. so far it looks promising