One City Saved $5M by Routing School Buses with an Algorithm
routefifty.com
routefifty.com
My greatest frustration is that they complain about black box algorithms when in fact it is a perfectly clear, ambiguity-free optimization function.
https://www.google.com/amp/s/www.wired.com/story/joi-ito-ai-...
Big changes that impact tens or hundreds of thousands of people need to be staged out to minimize impact. The Big Bang approach doesn’t work for problems like this — i bet a few thousand people would lose jobs over these schedule changes.
Sure, when you introduce an approach that suddenly creates considerable inconvenience for some population of parents, sure they complain (no one likes having to drop off kids at ~ vaguely recalling ~ 10 am and pick at 5 pm, sheesh, it was something terrible). Some large portion of working people are fairly dependent their children having ordinary school schedules. Maybe these were relatively better off parents in the public school system - where the actually wealthy use private schools (I know Boston well enough to attest to this). So the algorithm failed to "optimize for those they could effectively screw" but hey, would it be too much to ask to just give all schools a sane schedule? Maybe pony up that extra money, give up the need to optimize everything, keep the tail of bus optimization from wagging the dog of school scheduling?
That’s a significant change in wake up time. Yeah, I’m not keen on that. It’s a non-starter.
Those early hours exist. Someone has to take them (without doubling the bus fleet size). And it's better for the students if they have the early hours in elementary and not in high school.
But fine, if this change is somehow egregious compared to other ones, give a 5 year warning.
The schedule benefits their kids, with a net zero change in the convenience of starting hours. What a shortsighted way to complain.
This is not how to build concensus for your argument.
I recently moved due to concerns outside my control, and the school time changed from 8:30am to 7:15am for my 6-year-old. This is manageable, but not a minor change at all. These types of changes are very significant for everyone in the region.
Sure, I'm not trying to convince the population being affected with that. Here's how I would say it:
"Your kids are going through 12 years of education. This change to the entire system will make it easier for them to learn, and to be smarter adults with better focusing habits. For some people the hours are tougher right now, I'm sorry, but it's not like those hours came out of nowhere. Your students were going to have school at those hours eventually. We've only changed which years."
It's not about how hard the change is. It's that a few years of early school starts are inevitable, so it's a fair trade.
Also what if your family has both teenagers and preteens? In my family we drove, so the schedule was based on when my parents had to go to work. I’d often arrive at school when the library opened or just before, which is a good hour before when classes started. Then again, my school experience wasn’t in the US, and schools started 8:30am / 8:45am consistently across the city.
"When I was a kid" preteens and teenagers were expected to be able to get to the bus stop on their own; But maybe that's just because both of my parents worked and left before the bus came.
Many of these systems start optimizing some simple criteria and work fairly well. But with additional constraints they fall apart.
Even companies that manage their own fleets for their own needs would like different things to purely optimizing distance/duration. They might want to balance the workload across all of their drivers, separate the drivers so they drive in a particular area, undefined start or end of the driving job.
In the case above, something could have definitely be done, if the algorithm was efficient enough.
Well, routing school buses is already less than trivial. You have pickup & delivery. So there's a precedence constraint to orders. Child won't be kept for hours in the bus, so the bus has to make several trips to school. Limiting the time between delivery of the child and the pickup is already less than trivial.
Just to know if route is feasible (all constraints satisfied) given a list of child pickups, child dropoffs and time limit between pickup and dropoff is nontrivial and can mess up the optimization.
Adding school shifts to the equation, minimizing number of vehicles and a bunch of other constraints might make the optimization just too slow or too constrained for an algorithm that was working incredible without all those constraints.
And 'optimization' solutions result in 1hour+ rides to a school just down the road, as the bus winds about the countryside scavenging the few remaining students. The longer the trip gets, the more that find another way, the emptier the bus, the longer the trip to try to fill it again.
We drove our kids to school for most of their school careers, even though three busses went by our house every day.
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...
Joi Ito wrote on this https://joi.ito.com/weblog/2018/12/05/what-the-boston-school... :
“In very polite email, they told me that I didn’t have the whole story.
Kade and I met later that month with Arthur, Sebastien, and their adviser, MIT professor Dimitris Bertsimas. One of the first things they showed us was a photo of the parents who had protested against the schedules devised by the algorithm. Nearly all of them were white. The majority of families in the Boston school system are not white. White families represent only about 15 percent the public school population in the city. Clearly something was off.”
“Optimizing the algorithm for greater “equity" also meant many of the planned changes were "biased" against families with privilege. My view is that the fact that an algorithm was making decisions also upset people. And the families who were happy with the new schedule probably didn’t pay as much attention. The families who were upset marched on City Hall in an effort to overturn the planned changes.”
I mean maybe but measuring that by the skin color of those protesting is... not a good method. Of course people marching on City Hall or showing up at schoolboard meetings are going to be the disproportionately privileged, they're the people who have the time for that sort of thing. But even there I'm a bit skeptical, take a look at this:
>Parent Antonia Rodriguez after a fiery address. She says of her and fellow parents, “We don’t have careers; we have jobs!... We’re laborers!” And that makes it hard to handle early starts and early dismissals.
or this video just below:
https://twitter.com/jmlarkin/status/941104843137064960
which gets to the main root of the opposition which was drastically earlier start and end times for elementary school students, two hours earlier in some cases.
>But for those who can’t stagger working hours — specifically single parents or families who don’t have any wiggle room on working hours — kids often see themselves to bus stops in the morning, then wait an hour or so after school, alone, until parents return. I see it every day.
>Under the new start times, and therefore early end times, these kids will be spending up to four hours home alone every day.
>Let’s not sugarcoat: After-school care is for financially advantaged families. Costs vary, but for two children at the YMCA in West Roxbury, after-school care from 3:25 p.m. until 6 p.m. is more than $700 per month (the cost would naturally go up with the extension of hours needed), plus the yearly membership cost of the YMCA (currently $90 per family).
...
>And for what? So Boston Public School can save a little in transportation expenses. And while they save, families will find themselves in increasingly precarious financial straits.
https://www.wbur.org/cognoscenti/2017/12/12/boston-public-sc...
Or this analysis from the Boston NAACP, the Lawyers’ Committee for Civil Rights and Economic Justice, and the East Boston Ecumenical Community Council:
>This ignores the fact that parents of color are disproportionately in lower-wage jobs, and are less likely to have the flexibility needed to build their schedules around a school day that ends at 1:15 or 1:55, let alone pay for any resulting need in after school care
https://www.boston.com/news/education/2017/12/16/naacp-lette...
---
Now it's clear that BPS used the MIT students here as a tool, a coating of algorithmic sophistication over a plan they already had, but it strikes me a bit poorly to see those students using 'actually we did everything right, it's just rich parents who stopped us' as a scapegoat.
Something about the presence of a metric and an algorithm causes our brains to switch off.
In the UK some schools run their own bus things (in the same way that Goolge, Facebook et al do in San Francisco), but most of the other schools just get by with the public buses.
There is often some coordination to make sure buses stop at/very near schools, and they may send extra ones at certain times - e.g. there were often several buses parked up and waiting empty at my school so they could be filled at the end of the school day, but any member of the public was then able to get onboard once it was on its usual route after that, and if you were late getting out (e.g. detention/sports etc) you'd just wait at the stop outside the school for the usual bus on its usual route to come by.
What do the US school buses and their drivers do for the rest of the day and on weekends? Just sit idle?
Also, it seems to be mostly in rural areas. Some drivers keep the buses at home during the school year. And, these are large, full size buses. If you live in a medium sized or large city, it's probably different.
I got a ticket for an improper lane change and the judge asked if I had a CDL which seemed to imply it would have been revoked.
It's the same deal as the tech shuttles: in places where public transit is good (NYC, Chicago, Boston) the tech companies don't run shuttles because there's no need.
> What do the US school buses and their drivers do for the rest of the day and on weekends? Just sit idle?
Yes. The drivers typically work a "split shift" with time off in the middle of the day, and the buses sit empty both then and on weekends.
Good article on long school bus rides: https://www.mprnews.org/story/2010/10/04/long-bus-ride-cook-...
Kindergarten is just half a day in many places, so the middle of the day would be another 3 hours to shift those around.
There were also many field trips, sporting events, and other miscellaneous calls for transport throughout the day and into the evenings, as well as some weekends.
Much of all of this would vary quite a bit depending on a particular town’s location, population needs, layout, etc. but I just wanted to say that although it’s a relatively chill job and there is indeed often a lot of downtime, it’s not like bus drivers universally work 1 hr in the morning, 1 hr in the afternoon, and then just bum around all day.
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.
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.
Often times these are part-time positions. Set block of hours twice a day. Drivers can take on additional duties or other jobs. The buses themselves are either owned by a transportation company that can also hire them out on weekends or making additional money on field trips / sports transportation.
My kids are fortunate enough to be able to walk to their school - there are sidewalks and it's only a half mile away, but many other students have a longer walk, no sidewalks, or other impediments that leads them to prefer a bus. Kids could take public transit, but typically this is not a great solution in most places, and it doesn't deliver you to a school directly. The latter factor helps with truancy, security, and a number of other things. There's a cost to it, but it is a norm.
It would be straightforward for a school district to agree to change the policy or reduce bus service for cost reasons if public transit and things like walking, biking were preferred options. These are typically the norm for private schools.
Here, due to decreased enrollment and building closures, they pick up students at their front door.
The drivers are mostly paid for just the hours they are driving, the buses sit idle except for things like out of town athletic events (where they transport the participants).
It's actually a thing because our public transport is so poor. Plus there are special laws for school buses to protect children. When a school bus picks up a child it is illegal to pass it on either side of the road.
However in some places students do take public transportation. For example here is the pricing for school districts to use SEPTA, which is the public transportation in and around Philadelphia
It's not really an example of a functioning public transport system; it certainly works, but only in a very limited and specific context and without any flexibility. If a kid misses the bus either in the morning or after school (which can happen often), they're going to be waiting for a ride home from a family member. After-school programs required the same. And if you're in a rural community? The bus rides are longer, and you're waking up even earlier. But for a lot of suburban communities, there's no real alternative. If they have a bus system, it's probably for commuters and goes from specified stops (often from large "Park and Ride" lots) to the nearest city.
In that sense, there often isn't a public bus to put kids on in much of the US. Assuming, of course, that parents would be willing to do so. Back in 2008, a writer wrote about letting her 9-year-old ride the bus and subway to school alone.[0] There was a ton of public outcry, and she was labeled "America's worst mom" and suggested it was equivalent to child abuse. But that's a different issue altogether.
0. http://nysun.com/opinion/why-i-let-my-9-year-old-ride-subway...
For people who can afford alternatives, riding public transit is something you do as an adventurous young adult, and maybe get turned off of even then (sexual harassment, aggressive panhandling, long delays and breakdowns). In the culture I grew up in, sending your 7 year old to navigate that unsupervised every day is bonkers.
[0] https://www.nbcmiami.com/news/local/Bus-Driver-Detour-Fort-L...
I remember walking to school in elementary school, later taking the bike for 20 min or public transportation. I don't live in a particularly dense area.
Is Boston too sparsely populated to have schools in walking or biking distance?
Seems that we accept distances of 1-2 km for elementary school walks. (0.6 to 1.2 miles)
1) Americans just in general tend to drive their kids to school dues to fear of child abductions and related ever-present paranoia.
2) Boston's transportation system is broken on just about every levels. The street organization is irrational, derived haphazardly from ad-hoc pre-auto paths. The public transit system was also built in an ad-hoc and is at level where full transit lines stop for days at a time. So all that's left is driving, though Boston drivers have a terrible reputation too!
3) Boston's weather is also miserable - the place is at just latitude so that wet, 30 degree weather prevails in winter, giving freezing rain, frozen rain, slush and all manner of nastiness. Plus horrible hot, humid summers. So you have to avoid walking a lot.
4) Boston experienced court-order busing to end segregation in the 1970s, so it's often true that students aren't in schools closest to them geographically.
When I visited I found transport to be very european compared to other US cities I have visited.
I live about an hour outside of Boston and have to go in for a few days later this week and I'll be taking public transit.
Which in a way, is a self-fulfilling prophecy. Solutions implemented in the rest of the world will not work in the US because most people don't believe they will, or that the US is not capable of radical change (that is, radical change not driven by an individual or a corporate desire for profit)
I'm from the American Midwest and I'm currently in Northern Europe. The difference is huge. The density issue of American suburbs is real, and the phenomenon is relatively rare globally. Go check out Google Earth. How do you not see it?
The weather is also more extreme in most places of the US than Europe. When Europeans tell people in Wisconsin to "just take an electric scooter to the metro station" they understandably laugh it off as ridiculous.
It definitely created a mindset of really wanting to get home (or just staying there in the first place) if any amount of snow was forecast. Of course, it doesn't help that traffic is pretty bad even in nominal conditions. Every few years you still end up with a 6 hour commute home situation for many people.
I bet that the activity in Boston when it is "shut down" due to weather is still busier than an average day in Bangor or Buffalo.
Source: masshole who has has lived in places with harsher climates
For comparison, Munich, Germany is 48.1351° N, Barcelona, Spain is 41.3851° N
Famously(?) New York is at the same latitude that Naples, they definitely don't have the same climate.
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...
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.
With that said, those are latitudes, not longitudes.
Someone once told be a simple way to remember the difference. Longitude and latitude was first used be Greeks to travel the Mediterranean ocean (not sure if that is true, but helps with remembering); The Mediterranean ocean is long from East to West, so moving in the long direction changes the longitude.
Chicago is comparable to Rome yet Rome rarely sees snow or the very cold windy weather Chicago is known for. You’re ignoring the whole jet stream.
Is it true that in some places this paranoia has gotten so far that you’ll get reported to child services if you let your kids walk to school?
> 3) Boston's weather is also miserable - the place is at just latitude so that wet, 30 degree weather prevails in winter, giving freezing rain, frozen rain, slush and all manner of nastiness. Plus horrible hot, humid summers. So you have to avoid walking a lot.
In Slovenia, same latitude as Montreal, I walked to school and back every day for 16 years. Yes even college.
What’s the problem with walking a kilometer or two in ... weather? Sometimes it rains, sometimes it snows, slush in spring, hot in summer ... so what? Just dress appropriately.
I have fond memories of early spring where you walk to school in a winter jacket and back from school in a t-shirt jacket in hand.
Where I grew up in New Jersey I lived 2 miles (3.2 KM) from school and I was considered close to the school. Those who lived within a 10-20 minute walk would walk. Many of us who lived further away would rely on the bus.
Edit: And this was for elementary and middle school (up to age 13). From ages 14-18 everyone was significantly further away.
https://en.wikipedia.org/wiki/List_of_United_States_cities_b...
I don't know because I know very little about schools outside the US. My best guess would be that they vary everywhere and this isn't US specific.
> Assuming you were in a city rather than a rural area
Before I was born and when I was younger there were quite a few farms, but I didn't grow up with them. So I suppose it used to be rural and now is a suburb (in-between rural and a city). My town has about ~30k people.
There are a lot of sprawling cities (and I _think_ Boston may be one of those) where it would also be greater distances to walk to a school. ..so I'm not sure being a city is correlated to short walking distances to school.
Not really. There have been cases of this (well, with young children walking with older siblings to a neighborhood playground), but they are rare and sensationalized.
Isn't thus true of any European city?
This is really just an upper middle class thing.
>The street organization is irrational, derived haphazardly from ad-hoc pre-auto paths. The public transit system was also built in an ad-hoc and is at level where full transit lines stop for days at a time. So all that's left is driving, though Boston drivers have a terrible reputation too!
The smallest streets are haphazard. The big stuff was all planned out to make the overall system function well, got 80% done then some special interests kicked money to the right politicians and they stopped progress at 85%. Ditto for the subway. Every couple decades they come up with a grand plan to make it not suck then special interests compromise it out of existence. Boston drivers are fine once you've been there long enough to understand the unwritten rules. If you're naive and think you can follow the letter of the law you will have a bad time.
>Boston's weather is also miserable - the place is at just latitude so that wet, 30 degree weather prevails in winter, giving freezing rain, frozen rain, slush and all manner of nastiness. Plus horrible hot, humid summers. So you have to avoid walking a lot.
The weather is fine. Kids are much more tolerant of weather extremes than their white collar parents (the ones who dominate the debate over this kind of thing) who's days are spent in three different climate controlled boxes (house/apartment, car, office). If you do it every day it's really not a big deal.
While if I had stayed and lived in michigan, I would have been 1km walk from elementary, middle, and high school. With a university 5km away.
It all depends on the US city and state and how that community developed/organized.
Boston is reasonably dense, but it's also defacto segregated, with parts of the city having different racial and class makeup. If we went back to neighborhood schools that people walked to that would mean effectively resegregating the schools.
See: https://en.wikipedia.org/wiki/Boston_desegregation_busing_cr...
Does that also apply to privileged families ? (I assume those would send children to private schools, avoiding such a system).
Yes, and not just Boston: https://en.wikipedia.org/wiki/Desegregation_busing
> Does that also apply to privileged families?
Sometimes. Other times places close the schools in poor/non-white areas.
Our state places elementary schools so young kids don't have to cross a major street, when possible.
More background:
https://www.media.mit.edu/articles/what-the-boston-school-bu...
Is there an expression of remorse anywhere in the article? I didn't see it. Suggestions for how things could be done better are all well and good. But I don't think I'm unreasonable in expecting some contrition from someone who participated in a screw up this gargantuan.
The field has been explored, and a number of solutions have existed for at least ~25 years.
What's impressive in this article, instead, is the amount of savings; $5M is not small change.
There may be three ways to get from one neighborhood to another, and the locals know that one is faster, safer, or both at certain times of day.
I have this argument with a couple of friends who don't understand why I use different routes at different times of day and specifically why I don't use their route, when they've never been in that part of town during rush hour.
I am getting used to checking Google Maps before going anywhere near a freeway. Just a few days ago, I noticed that traffic heading south seemed bad as I was going north to drop off my daughters. I checked Google Maps and it said that going south on the freeway was fastest. I dithered and then got on the freeway. The choke point that was there 25 minutes ago was gone and I saved a bunch of time staying off surfaced roads.
The state highway department has cameras and road reports and announcements of construction. 20 years ago, I would have been on their website. Now I don't have to. I just use Google Maps.
I'm an iPhone user and I do try to use Apple Maps more often because of privacy concerns.
But this highlights the exact problem that Andrew Yang, the Democratic Candidate is highlighting which is: what do we do with people whose jobs are lost to automation and algorithms?
His proposal of universal basic income helps these people who have lost their jobs attempt a soft landing because at least they will have some income.
I used to be against UBI but now I fully understand why we need it, because too many jobs are going to be eliminated, and what do we do with these people who have lost their jobs? They are likely older with lower skills, and retraining programs are statistically an abject failure.
And the welfare state wasn't invented by Andrew Yang: only difference is his variant assumes people who are desperate to find work and people that have absolutely no need to or intention of doing anything other than live off their savings or family wealth have exactly the same need for subsidies...
(these two should know a few things about route optimization :-)
"Another proprietary tool UPS uses to manage its fleet system is ORION (On-road Integrated Optimization and Navigation)...The cost and time savings and emission reduction based on this optimization alone is extraordinary—UPS expects to reduce delivery miles by 100 million"
[1] https://www.forbes.com/sites/bernardmarr/2018/06/15/the-bril...
Now I don't have kids, but plenty of my friends around the country do, and I'm always shocked to learn that school buses don't seem to be an option. Either they just don't exist in the district, or they require kids to cross major commercial roads to get to a stop.
The depressing thing to me is parents sort of roll their eyes when I ask, like this reasonable public amenity that everyone I grew up with relied on less than 20 years ago is the equivalent of the neighborhood milkman.
Plus you're talking about investor-subsidized transport. Sure, it would be nice to have investors subsidize school transport.
An hour window each day would be crazy! Parents plan their work schedule around being able to get kids out the door at the same time each day.
I don't know the extent to which it was capable of optimizing the schedules, but it was considered to be a pretty big deal. There was apparently a lot of hand-coded logic for dealing with things like one-way streets and not wanting bus stops on busy streets.
Or read another way: "Running the algorithm eliminated 50 jobs due to automation".
This right here is what Yang is all about. The incredible loss of jobs due to technology.
And this is the problem. Culturally many people seem quite happy to leave high school and get a menial job. Those jobs are vanishing, just like jobs for elementary school dropouts vanished decades ago.
Society doesn't need people who are unwilling to aim higher than driving a bus for 50 years.
This doesn't mean everyone needs to have a phd -- there's plenty of jobs for trained plumbers, electricians, mechanics etc, but those all require training post high school.
Will it? I mean, it might, but I wouldn't bet on it.
They stopped paying people to drive in circles doing nothing.