Live data from Hacker News

One City Saved $5M by Routing School Buses with an Algorithm

routefifty.com

151–155 of 155 posts

Re: One City Saved $5M by Routing School Buses with an Algorithm

#151
post #150

Earlier quoted context omitted.

I’m not sure I follow. All of those additional optimizations are pretty simple problems in the OR field.

I've worked recently in this exact field (known in OR as "pickup dropoff problem with time windows" or PDPTW). As you say, all these modifications are completely standard (especially ones that minimize the worst-case "suffering" of the most-affected passenger).

Saying these modifications are standard does not talk about their complexity.

Here's [0] a paper where they analyze the mistake of the feasibility check that experts in the field failed to do properly. Here's [1] a paper aggregating all the timing problems that arise and their algorithmic complexity. Some of the timing problems, including the constraint of limiting the time of the passenger in the bus had O(n^2) or O(n^3) feasibility checks. That's slow. Especially slow if combined with integer linear programming or branch and cut algorithms.

If your system instead minimizes the riding time by adding a cost function to a constraint, making it soft, in most cases the cost function is so ill defined that the solution no longer does what you want, can hardly minimize all the constraint to a normal solution, and you get a huge mess.

There's no state of the art solution that models these constraints as soft ones.

These problems being standard does not mean that they are simple.

0: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.927...

1: https://w1.cirrelt.ca/~vidalt/papers/Timing-Problems-Final.p...

Re: One City Saved $5M by Routing School Buses with an Algorithm

#152

Earlier quoted context omitted.

Longitude in itself doesn't dictate weather. Labrador is the same longitude as London but we don't have similar climates. Köppen climate classification is probably the best indicator of where else is similar; which comes out as the same as most of northern Europe [1]. 1. https://www.weatherbase.com/weather/weather-summary.php3?s=9...

You mean latitude.

You're absolutely right (we both meant that)

Re: One City Saved $5M by Routing School Buses with an Algorithm

#153

Earlier quoted context omitted.

Boston is at 42.3601 N longitude, which is actually pretty far south-ish compared to Germany. For comparison, Munich, Germany is 48.1351° N, Barcelona, Spain is 41.3851° N

Longitude in itself doesn't dictate weather. Labrador is the same longitude as London but we don't have similar climates. Köppen climate classification is probably the best indicator of where else is similar; which comes out as the same as most of northern Europe [1]. 1. https://www.weatherbase.com/weather/weather-summary.php3?s=9...

Latitude doesn't, you're right, though the map on the site you linked shows broad-strokes correlation, and I've found it helpful if I guess imprecise in illustrating general temperature differences.

The difference in summers - cool summer vs hot summer - is a big one, and I'd suggest that it makes Boston's climate not really the same as most of northern Europe. We haven't traditionally needed air conditioning in Germany, for example, while I understand Boston and New England (the upper mid-Atlantic and New York, surely, when I lived and visited there) come to rely on it during the summer months to not just live in puddles of sweat.

Re: One City Saved $5M by Routing School Buses with an Algorithm

#154

Earlier quoted context omitted.

Snow is fine, but Boston will get 3 feet of snow, then an hour of freezing rain, and the next day it will be 45F. Winter is chaos

And that situation would literally just be business as usual in somewhere like Bangor or Buffalo. In Boston it's an excuse for half the city to call out of work and the MBTA to run trains "whenever we get around to it".

Both those towns are small fries compared to Boston. Why not compare it to the Arctic?

Re: One City Saved $5M by Routing School Buses with an Algorithm

#155
post #117
post #90

Earlier quoted context omitted.

Most US cities and towns have minimal public transit that wouldn't be anywhere near sufficient for getting kids to and from school, so they run school buses instead. In some places with good public transit, like Somerville MA where I live, the city doesn't run school buses and people walk or take general purpose public transit, but that's very unusual here. It's the same deal as the tech shuttles: in places where pub…

> in places where public transit is good (NYC, Chicago, Boston) The Boston one is a real giggle. At best, public transit in Boston is no better than the Bay Area, and on average is much worse. The real reason for not running shuttles in these locations is office size. The Bay Area offices where shuttles are run have 10-100x the employees these other locations have.

I work at Google in Cambridge, in Kendall sq. Most of my coworkers take public transit, most commonly the Red Line. If you look at https://www.mapnificent.net/boston/#11/42.3729/-71.0760/2700... you can see there's a large area within reasonable public transit commuting distance.

The tech company shuttles in the Bay Area mostly run to the South Bay, where Google etc are, and the public transit options there are minimal.

Post reply on HN