This is a great article - it's a set of really clear explanations of several complicated topics, and kudos to the author for bringing it all together so well. It reminds me of the research we conducted at Ultra PRT when building the Heathrow Pod (a driverless taxi system) [1] and evaluating much larger networks on campuses and in cities.
One aspect I didn't see in the analysis is the effect of a passenger's willingness to rideshare on the effectiveness of the algorithms - we found it can have a pretty dramatic effect on system efficiency[2], especially when operating near capacity (as you'd expect). Does anyone who's used this system have any experience of this? What happens if passengers refuse to share or request a different ride?
Unlike UberPool or Lyft Carpool, TransLoc OnDemand rides are serviced by transit agencies, most of which use shuttles or even full-size buses. There's no choice to share or not share a ride.
As another Ultra alumnus, I also enjoyed reading this article. It's great to see algorithms like this making a real difference in transit, instead of just being simulated.
It was a somewhat different problem, but FWIW I had more success with the Cross Entropy Method than with Simulated Annealing [1,2]. Maybe one for future research :)
Transloc's app is the most thoroughly unpleasant piece of software I've ever had the displeasure of keeping on my iPhone for more than 5 minutes. Sadly, when it was raining outside and the shuttles only came every half hour, I didn't have much of a choice.
Arrival data was usually missing (despite shuttles in operation) and when present, usually wrong. A given intersection would typically have 7 or 8 different tiny touch targets on it representing the different lines and systems that stop there, and you have to select the right one. No way to do that except to iterate through them all. The maximum allowed zoom level was not nearly enough to do this in a reasonable way on an iPhone 4S, certainly not in the freezing rain.
The was a list of routes you could check and uncheck to add and remove them from the map. This list was enormous, and the 3 shuttle lines that 99% of users cared about 95% of the time were buried deep within it. There was no attempt to remove visual clutter if you had other lines enabled that were not operating. Lines on the map were color-coded, but it was really not clear how to match them to route names. There was also no way to do point-to-point directions or even plot a pin on the map, so you had to zoom in on street names and manually pan around to find your destination and see what the appropriate line was, then take a guess at the directionality of the lines to see where it made sense to get that shuttle. I would usually flip over to Google Maps to plot a pin, then try to match it up visually when I switched back to Transloc.
I could go on and on. Do not let these people convince you they are a hip progressive tech company. They make an enterprisey piece of shit for captive audiences and it wouldn't even be hard to do far, far better by taking even a handful of cues from what Google Maps was doing with public transit directions years prior.
I wonder the author considered using Integer Linear Programming. For me it tends to be a go-to way to solve problems like this, but often have issues when the modelled problems become harder than I thought and processing times will be .. months?
You end up with a very similar situation as you do without integer linear programming - an enormous search space. In the papers I've read on VRP that provide a linear programming formulation (2), they then fall back to approximate methods for actually doing the work.
ILP is not the same as brute forcing it, branch and bound and cut will quickly weed out a lot of that search space. And a good solver should find approximate solutions quickly.
The question is whether good solutions are found 1) as quickly as with the simulated annealing approach 2) as good as that approach 3) whether the formulation is maybe simpler.
I don't know of any, I learned that in school. But I'm currently working on writing one. If you're interested, I'd be interested in some feedback whether it's understandable.
Would love to hear more about your thought processes before you posted the question on StackOverflow. Felt like the instant solution rushed the ending of the article a bit, but otherwise really enjoyed it.
I first implemented a recursive solution using memoization. But the linear PAVA algorithm is faster. Not sure what else I was thinking about at the time, this was 7 months ago.
One aspect I didn't see in the analysis is the effect of a passenger's willingness to rideshare on the effectiveness of the algorithms - we found it can have a pretty dramatic effect on system efficiency[2], especially when operating near capacity (as you'd expect). Does anyone who's used this system have any experience of this? What happens if passengers refuse to share or request a different ride?
[1] http://www.ultraglobalprt.com
[2] https://www.researchgate.net/publication/31589946_Ride_Shari...