ORC IAP Seminar 2018 - Arthur Delarue and Sebastien Martin

Hi,

everyone. If you're just coming in, welcome to the Operations Research Center's 2018 IAP seminar on Operations Research for Social Good. It is, again, my pleasure to welcome our second, this time, pair of speakers, two for the price of one. Sebastian Martin and Arthur Delarue are PhD students at the Operations Research Center. Their work that they are about to tell you about on analytics for public policy

in

partnership with the Boston Public Schools on school bus optimization and routing is very exciting. It was recently written up in the Wall Street Journal, so check that out if you want to see the pop version of what they're about to share with you today. They asked me not to embarrass them, so I'll just end by pointing out that they are intelligent, gifted, and handsome people. So, please join me in heartily welcoming Sebastian and Arthur.

Thank

you, Phil. So, eight months on a school bus. So, this talk will be a little special because we basically have two parts. The first part is about an exciting OR project with formulation, how we solve it, and the second part is about what happens after you solve the problem or you actually think you solve the problem, the implementation part. So, this is joint work with Arthur and Professor Dimitri Bertsimas, who could not be here today.

So,

first, let's talk about Boston Public Schools. Boston Public Schools is actually one of the oldest public school districts in the country. Actually, one of its schools, Boston Latin Schools, is the actual oldest public schools in the United States and still one of the best ones. So, more than 50,000 students, more than 100 schools, and it's a very inclusive district with a lot of students with disabilities and economically disadvantaged students.

So,

you can see a map of all the schools right there. It's basically all Boston except Brooklyn and Cambridge.

So,

we are going to focus a little more on school transportation. So, what are these school buses that you can see in the morning, in the afternoon, almost everywhere? Transporting children from their home to their schools. Why do we need them? Because, in particular in Boston, a lot of children are going to schools that are far away from their home. For a lot of different reasons. For example, if you have special needs, typically your school will be far away from home. And, your parents cannot have the time to spend one hour in the morning, one hour in the afternoon to transport you to school. And, the city helps with this.

Also, for example, if you have a wheelchair, you need some special vehicles for transportation. And, school buses were used, actually, in the 70s for desegregation in Boston. So, basically, the idea is that using school buses could allow you to transport children further away from their neighborhoods. So, to have a little more diversity in the city. And, this is something that Bostonians remember a lot. And, that makes the problem of school transportation really important in the eyes of Bostonians.

So, there

is a problem with school transportation. And, the main problem is the budget, the blue curve here. You can see that in the last five years, it increased something like 5% every year. While the actual enrollment, like the number of students transported in the buses, decreased. So, it's around 50% of the students that are transported. So, why did it increase like this? For a lot of reasons. First, like the costs are just increasing, the cost of the buses, more congestion in the city. And, in general, it's also a very complicated problem to solve with students that go to school very far away from their homes. So, they cannot re-share the buses with other people.

We have a lot of buses transporting only one or two students. And, this is a problem because now the budget is around $22 per student per day

in

Boston. And, this budget is taken from the school budget. So, from more teachers, more staff for the school nurses. And, this is why if we can help a little bit with this, making this system a little more efficient, it's important for the district.

So,

Boston decided to organize a challenge, a hackathon, last spring, in order to see if they could get some new creative ideas from the community, and a lot of universities and companies participated to this challenge. And, Arthur, Professor Bertsimas and I decided to participate. And Arthur is going to present, right now, how we formulated the problem and how we tried to solve it.

So,

thank you, Sebastian. So, first here, I'm going to try to explain what school transportation means in a way that we OR people can understand. And then, I'll try to describe the solution that we came up with. So,

in

Boston, when you think about routing students to school, you start with home addresses. So, you know where the students live.

And,

you start with corner stops. Corner stops are places in the city where it's safe for the school bus to stop and for children to congregate. So, these are typically intersections, hence the name corner stops. And, you don't have too many of them, but you do have fairly high coverage of the entire city.

And,

then,

what

you're going to do is these students are going to walk to a corner stop in the vicinity of their home

every

morning to pick up the school bus. And, they will be dropped off at that stop every afternoon.

So,

you notice that there's a yellow house here that was not assigned to a stop.

And,

that's because about 6,000 students in Boston are so-called door-to-door pickups, which means they need to be picked up at their home. And the reason for that is usually medical, and it could be anything from the fact that the student is in a wheelchair to the fact that the student has some form of autism that requires that they be picked up at their home.

So,

once the students have been assigned to stops, which in the case of door-to-door students is their own home, what we can do

is we

can connect these stops

so

that a bus can go and sort of visit the stops in order

and

pick up the students and drive them off to school.

So

far, very simple idea. You sort of cluster the students into stops and then you connect the stops.

And,

this is what Boston, their transportation division does every year when the new students' files come in.

So,

there's a number of constraints associated with this. So, for example, students can't ride on the bus for longer than an hour. There's different types of buses with different capacities. You've got small buses. You've got big buses. You have buses that have wheelchair lifts

for

students that are in wheelchairs. So, this is the, and importantly, the school buses can only pick up students for one school at a time. Because the schools are typically not that close to each other. So, in the interest of efficiency and also in the interest of students not getting lost, the bus will keep all students from one school on the bus at a time, and then it will drop them off at the school.

So, the

thing that's important to notice is that we are interested in routing not just for one school, but at the scale of the entire system.

And

so, there's a number of parameters that you need to take into account.

So,

each school might have several routes, and a route is just an order, a selection of stops in order. And there are several schools in different parts of the city. And what you need to do once you've sort of built routes is you need to assign buses to serve these routes. So, the buses sleep in a yard at night,

and

you can assign buses to serve each of the routes. Now, each new school bus has a fairly high fixed cost associated with it. You can think of it as the cost of buying the school bus.

And

so, one of the things that Boston cares a lot about, and school districts care a lot about in general, is reducing the overall number of buses. Because if you can do that, you can handle your costs more efficiently.

So

one of the things that Boston does is that the schools in Boston don't all start at the same time.

So

in this example, you have two schools that start at 730 and one that starts at 830.

And

so what that means is that, for example, this bus here, instead of coming from the yard, could actually come from this school here.

And

in that case, you actually save a bus. Now you only have three buses in this solution. Now the start times are different across the schools. But they were chosen a long time ago, and they can be somewhat arbitrary. So it's a possibility that by switching the start times, so for example, let's make this school start at 830 and this one start at 730.

So

clearly, we need to add this route back because it can't be shared across two schools that start at the same time.

time, but

now

we

can have, instead of having this bus come from the yard,

it

can come from this school. And this bus here can actually come from this school.

So

by adjusting bell times for schools, you can actually gain even more efficiency.

So

this is sort of the routing problem at the scale of the district. And let me recap. So

you

start with bus stop assignment for all students except the ones that have door-to-door pickups. Then you collect the stops for a single school together in one or more routes. And then you can sort of string together routes for different schools in a way that reuses buses. And if you want to gain even more efficiency, you can actually adjust the bell times.

So

there's also a large number of constraints to consider. So students can't walk too far to get to the stop. You can't put too many students at the same corner stop, like you can't put 200 students at the intersection of two streets. You need to take into account the fact that there are several bus types. They don't have the same number of seats. Not all of them can handle wheelchair students.

You

need to make sure that you leave enough time for the students to get on. You have to make sure that the students don't spend too much time on the bus.

You

need to make sure that they have enough time to get off the bus. And this is something that we won't talk about too much, but you have to keep in mind that the students are at school and then you have to take them back home.

And

because not all the schools have the same day lengths and just the same traffic patterns are not the same, you actually need to re-solve the problem for the afternoon.

So

we'll focus on the morning, but keep in the back of your mind that you need to solve this problem twice actually.

So

in the literature, it's, so okay, you would think you can just take this problem and formulate it as a big optimization problem. And it turns out that if you do that, it's very hard to solve problems at the scale at which we care about. So in the literature, a lot of these problems are solved either alone or with the problem that's adjoining. So you could have like solve these two together or maybe just this one.

And

so what we're going to do is we're going to sort of follow this natural decomposition of the problem in elaborating a solution for it.

So

let's start with stop assignment.

So

stop assignment is the very simple first step of the process. So you have your students and you have some possible corner stop locations and you want to assign the students to the stops.

Now

when you assign students to stops, there's two things you care about.

You

don't want the students to walk too much.

And

you also don't want to have too many stops. So the second one is a little bit, it's a, the idea is

we

would like to create a stop assignment that will make it easier later on

to

route the system, to connect the stops. And if you have fewer stops, you have fewer connections to make. So the problem is easier.

So we

have two objectives. To minimize the number of stops and to minimize the total walking distance.

And

so that's why these trade-offs are apparent at every stop. So for example, this house here, you could have, oops, could have been assigned

to

this stop, but in order to minimize the overall number of stops that was assigned to this one, even though it's slightly further away. And we can formulate this problem at the scale of the entire district as an integer optimization problem. And it's, it solves very efficiently because most of the decisions are sort of local. So this is step one. So at this point, we've assigned all the students that need to be assigned to a corner stop.

So

step two

is

connecting those stops. And we're going to split step two, which is the, how to, to route the stops for a single school into two sub steps.

The

first one is route generation. And the idea is because there's a large number of constraints, just

from

capacity in terms of space on the bus and in terms of time, just generating feasible solutions is not trivial.

And

so what we care about is actually generating a large number of feasible solutions and exploring the feasible space

before

we can start optimizing on it. So, we want to look at a lot of routes that could make sense for this particular school.

So,

for example, we could look at a route like this one, or something like this, or like this, or something like this, but we would never want to consider a route that's not optimized. Because here, you could easily see that there's a lot of wasted driving. And you also wouldn't want to consider routes that are infeasible, obviously. And this one might be infeasible because it's too long. It exceeds the one hour constraint. And to sort of explore the feasible space in this way, we have some randomized greedy insertion heuristics that sort of can create thousands of routes in seconds.

So

now, once we have these routes,

we

want to combine them.

So

we have our school, it has stops, and we want to make it so that each stop is assigned to exactly one route,

and

the routes are, together, optimal. So the thing is, we again have two objectives in this case.

We

care about minimizing the total number of buses. So we care about having fewer buses serving that school. And we also care about not having students spend too much time on the bus.

So these

are

our

two objectives. And what we're going to do is we're going to use the feasible routes that we've generated. And we're going to use integer optimization to combine them. And that's why I'm saying it's inspired by column generation, because we don't actually do column generation. But it's the same spirit where you have an integer optimization routine that selects from among the feasible routes. Yes?

So

there's about 125 public schools. There's 30,000 routed students. The largest school has hundreds of stops.

The

smallest school has like one stop.

So

the minutes time here is for the largest school.

So

the idea is we generate a lot of feasible routes and we use integer optimization to recombine them. And you can even do this in an iterative way where you generate routes and then use optimization to recombine them and then generate more routes and keep recombining until you converge. So the thing that's interesting is that because we have two objectives, which are the number of buses and the total time spent on the bus,

we

actually have a range of possible solutions for each individual school.

And

so this is going to be important because

right

now we're minimizing the number of buses at the scale of a single school.

But

what's optimal for one school might not be optimal for the entire system. So if you minimize the number of buses for each school individually and then you try to reuse buses across these different schools, you might get something that's not optimal or even not all that efficient.

So

keep in mind the idea that we can generate several solutions for each school, several solutions with different parameters, some of which will have more buses, some of which will have fewer buses.

And

keep this idea in mind as we move to multi-school optimization. So this is sort of the name of the game. This is where the savings come in.

And

it's where, so you remember, we want to connect buses so that they will serve several schools in sequence. Let's do a quick example. So let's say we have one school that starts at 7.30 and another school that starts at 7.30 with a very simple routing solution.

So

we have buses coming from the yard to serve those routes.

Now

consider a school that starts at 8.30 and it has two stops.

One

possible way we could route this school is we could have these two orange routes here, one for each stop. Another way would be this black route which has both stops in the same route.

So

we would consider several options for each school in this way.

And

then we would look at the different ways that these options can be connected with the rest of the system. So for example here I can just assign a bus from the yard

or

I can have the bus come from another school or I could have the bus come from two schools and serve the two different routes. And this can actually be modeled as an integer optimization problem. I think you're starting to see the theme here. And because it has sort of a network flow structure, even though it has over a million integer variables, it solves with Gurobi in about three hours, 30 minutes if you really push Gurobi. So

what

are our results? So on the right you see a simulation of school buses serving their morning routes in Boston. So you see them leaving the yard and driving around.

So

the

number

of buses that you can get from using this optimization approach is over a hundred less than what they used in the past. So last year BPS needed 650 school buses to serve all their routes. And with this optimization approach that we project that they would have needed 520. Now interestingly the amount of time spent on the bus and the amount of time spent walking to the stop is actually very similar with the optimization and without the optimization. Which means that the burden on families is zero effectively. And because we're using optimization, we don't need much time to compute.

You basically, you use a somewhat powerful computer for a few hours instead of a team of 10 people for over a month.

So

that's sort of the routing part.

But

remember there was a fourth step which was bell time assignment. We can actually adjust the bell times

in

a way that will make it even easier to connect buses from school to school and eventually lead to savings for the district. So

let's

just a quick refresher example. Let's say we have a school that starts at 730 and another one that starts at 830.

If

we want to have a single bus serving both of those schools,

well

there's a lot of driving from the school to the stop.

And

if instead we switched the bell times of the schools,

we

would actually be able to route the bus much more efficiently.

So there's

one problem. When you start messing with the start times of the school,

you're

not only messing with the students who ride the bus. You are affecting every student that goes to that school

and

their family.

So

the externalities are huge. And that means that we don't only care about transportation anymore. And our objective is very complicated and not even well defined.

And

that's where the engagement from Professor Johnson's talk would come in.

So,

because we are facing a problem that's much more abstract and much more difficult to define, well we need to step a little bit, we need to step one level higher than routing optimization.

So, what

we're going to do

is

we're going to say, okay,

for

each school,

at

each time, there's a particular cost

of

assigning that time to that school. And that's, you could think of it as each school's preference for a particular time. And in addition, for each pair of schools and each pair of times, there's a cost of assigning school s to time t and school s prime to time t prime.

And

this cost, because it correlates every pair of schools, is very powerful and it can allow us to take into account routing correlations. So, for example, we can say, well, it's very favorable to put school s at 7.30 and school s prime at 8.30 because it allows us to reuse a lot of buses.

So

this formulation is very general. And importantly, it allows us to sort of abstract away our routing optimization part, which is very important because, if you remember, it takes about three hours to solve the problem.

So

if it's going to take you three hours to solve the routing problem for one set of bell times, how can you expect to optimize over bell times efficiently? So we abstract it away. And when you have this kind of cost structure, the problem becomes a quadratic assignment problem. And so what we're saying is, as long as the objective can be represented as the objective of a quadratic assignment problem, our formulation can handle it. And the quadratic assignment problem is not very tractably solvable. But we can use some local improvement heuristics based on using optimization. And it solves in about 20 minutes to a reasonable solution.

So

because we abstracted away

the

routing engine, we don't have a number of buses directly anymore. So what we're going to do is we use our quadratic assignment formulation to optimize for bell times.

And

then we use our routing engine, given the bell times, to give us the number of buses that it would have gotten. So what we get is that if we, so remember, when we just used optimization on the routing alone, we saved about 100 buses. When you, in addition, optimize the start times to get maximum routing efficiency, you save another 100 buses. And the routing time goes up from about three hours to about a day because there are some parameters that need to be tuned. And

the

important thing is that because we have a very general formulation, we can actually explore a lot of trade-offs. So this is one example. But in this case, we have the number of buses on the y-axis. And this happiness can be thought of as the satisfaction with bell times. And it's because our costs are very general,

we

can represent, it can represent almost anything as long as it's something about how much the school likes or doesn't like a particular time.

So

what you see is that

if

you don't give families exactly what they want, you don't give them their first choice, you can actually get very efficient solutions in terms of routing. And as you give schools the bell times that they might like more for scheduling reasons, then you have to pay more and more buses. And just this point here, which appeared out of order, is the current, so the solution before sort of the optimization approach. So about 650 buses, and this is how people are satisfied. So the point is, the edge of optimization is somewhere here. It's depending on how much you want to satisfy, how much you want to cut budgets versus how much you want to satisfy school preferences.

Thank

you. So at this point, with this solution, we were happy to actually win this challenge. And Boston was particularly very interested in the implementation of our method, because, like, right now we are talking about this number of bus that might seem very abstract. But we are really talking about something like

$5

million per year by just reorganizing the buses that goes to pay for more teachers, staff, nurses in the schools. And if we were to change the bell times, we can go up to something like $20 million per year that would be poured into the schools.

So,

at this point, we're, like, end of June 2017, and the school is about to start in September, right? So, to talk about implementation, let me go over the organization of Boston Public Schools quickly, because it will be useful later. So, you have this school committee that is appointed by the mayor, and that elects a superintendent that oversees all the school's activities and that represent the schools. And then you have several departments, operations, with the COO, who was our main contact at Boston Public Schools, so really a great person. And then you have different sub-departments, and then there is this transportation. And this is the team Arthur was talking about.

Like, this team of people that were building the solution manually, but they do actually a lot of other things. They reply to the phone every day to the parents wondering where the buses are, they deal with the buses union, the bus driver union. They correct the solutions every day, students are, like, their address are changing or something like this. So, they have a very important role, and this is the team that we are trying to help here.

So,

at this point, the team always tests the bus routes every year before the first day of school in August, which only for the students to start going to school in early September.

So,

this only leaves us two weeks,

at

this point, to implement the solution. But, you know, we gave them the solution, so the solution is here, it's supposed to work, it's great, and it should be implemented, right? So, like, these are all the constraints that Arthur was talking about, all the things that we managed to solve, basically.

And,

at this point, our contacts are Boston, came to us, and we're like, oh, and by the way, the challenge was a little simplified, so there are a few more constraints, because, like, in practice, things are a little more complicated. Like, for example, you need to input everything manually into their system, thousands of routes, months of work. You need to update the route daily, because, yeah, you don't compute it once, actually, students move during the year. And then, a lot of other things, like, we actually need to route adults within the buses, because some children need supervisors. Actually, most buses don't leave the yard on time, which can basically kill a solution.

Routes are too narrow, so big buses, yeah, actually, all our big buses were using all the narrow routes of Boston, and we don't have a list of what routes are narrow or not, so by looking at Google Maps. And then, hey, students have extra constraints, they need to be with their siblings, we didn't know who their siblings were. Schools, and some schools released their kids always late, which has a snowball effect on the solution. So, basically, our solution was breaking everything. And, at this point, Boston came to us and was like, oh, you told us that optimization, like, really allowed you to take into account all these extra constraints very easily, so here you go.

So, yeah, we made them think that optimization was basically black magic, which was very useful in some cases, and not useful at all in other cases. So, at this point, we needed to find a solution. And the main thing here is the first point, because if we cannot give them the solution, it's the end, right? Like, we would have to wait one more year in order to implement the system. So, what we decided to do is actually spend the two entire weeks to build some sort of an interface that would allow a lot of people to be able to visualize our solution and basically input it manually into their system. Because Arthur and I were not enough to just do this on our own.

So, we had to learn how to build some sort of a website. Here, you can see several schools.

So,

this school has a lot of steps, and we have to route all of this. Then, they could explore all the possible routes and click on the routes. And, at this point, you would have the schedule of the bus with the different times so that they could input it in their system. OK. So, at this point,

we

had something to give them the solution, but now we needed people. So, we basically recruited everyone. And, everyone spent a full week just entering all the information. And, I can tell you that they remember this week. Like, even the CEO of Boston actually had to learn how to use the software.

And, at

this point, we were allowed to, we were able to give them our solution. But, there is still a problem. All the other constraints. Our solution was basically not implementable. So, what do we do at this point? And, we don't have any more time. So, the idea that we came up with was to actually build a lot of slack in the solution. So, you can see the solution is significantly worse than the previous one, but still a lot better than before. It still saves around five millions a year. But, basically, what we did is put so much slack in the system that it was easier to modify by hand.

Because, when you have something very optimized, you cannot change something without breaking everything, all the constraints, basically. So, with this, this actually allowed the team, the transportation team to take our imperfect solution and implement all the things that they were used to do in the last decades. And, that we could not have done it in this very restricted time. And, in the end, you always need these people. Because, there are always things that you cannot foresee and solve with an algorithm.

So,

at this point,

we

were very happy. And, Boston decided to publicize this thing. And, we were in the month of August. And, everybody started to know that Boston had had this partnership with MIT. And, again, we were very happy. But, we started wondering, like, the first day is going to come. And, people are looking, you know. And, then, we started to realize that 25,000 students is actually a lot of students. And, that everything was in this code in our computer. And, yeah. So, we were waiting this first week. And, so, the first week happened. And, yeah. So, this is what happened. So, the main problem is that all the buses were late. A lot worse than anything that happened in any previous year.

And,

we had absolutely no idea why. All the tests were good. The code was good. I mean, maybe. And, we spent our time thinking. Boston was thinking. Any idea. No idea. And, then, one week later, by magic again. Like, the bus system just solved itself. And, Boston is now convinced that optimization is black magic. Because, actually, we just, yeah. We don't, we have still no idea exactly what happened. We think that bus drivers were not really used to these new routes. Because, there were lots of significant changes. And, also, the transportation team. And, maybe, like, the whole system. And, yeah. We had, also, a very interesting week at this point. So, okay. But, in the end, it worked.

And, we managed to save some money. And, also, save money in all the subsequent years. So, at this point, Boston was really interested to try this thing with bell times that Arthur was talking about. So, bell times. These are the current bell times in Boston public schools. So, in blue, you have all the bell times in the morning. So, when schools start of the public schools. And, in orange, you have the private and charter schools. We cannot modify the orange ones. And, you have the same, the time when the school closed in the afternoon. All right. And,

you

can see that, oops. Okay. And, you can see that, actually, these are not the same distributions. Because, the school day lengths change from school to school. Okay. So,

one

thing we can notice immediately is that we have three peaks right there. So, these are what we call tiers. In order to optimize, to have bell times that would help a little bit the buses and the school transportation, Boston decided to implement a tier system, which means that, basically, one third of the schools at 7.30, another third at 8.30, and another third at 9.30. It's not really a third, but it's a third of the students, not the schools. And, this allows bus to be reused. Like, a bus can save up to three schools in the morning. And, this drive transportation costs lower, which is very important, because they are already extremely high.

So, we were saying that, just optimizing this, we can save a lot of buses. A hundred more. Something like 20 million per year. But, yeah. But, this is not really the main thing that we want to do at all.

Why?

Because, as Arthur was saying, parents care a lot about this. And, not only parents. A lot of things in the city depend on these school start times. Not only the transportation costs. Transportation costs are great, because you can pay for more teachers and staff, but there are also lots of other things. So, Boston spent a whole year, and even more than that, just having lots of meetings with the community surveys. And, this is one of the surveys for the parents and the staff of the school, asking them what bell times they would like. And, they could rank them from one to the worst possible, to seven the best possible for them. All right? And, these are the average.

So, what you can see here is, first, everybody tends to prefer the same things, from 8 to 8.30. And, hates the extreme bell times. But, also, that even our best bell times are around four. Four out of seven, in average. And, this is a sign that's something that is actually true in practice. In each school, you have parents that want absolutely every bell time. And, I think, for any school, it's not possible to move their bell time without having around 30% of the parents, minimum, that are very unhappy. Okay? So, no matter what you do, you will have people that are extremely unhappy,

which

really makes the problem a lot more complex.

So,

at this point, but, yeah, these are what the parents want. But, there are also lots of other things. And, like, this is a quick list. So, you have, like, yeah. So, I was saying parents, some parents prefer later, some parents prefer earlier. The staff is also very important. It's their life. Like, the bell times, it's very important for them. Also, there's teenager health, younger children, special education children, that would be very,

very,

it's hard for them to change their schedule. MBTA, when you change the bell times, all the students that are using the T to go to school will, can reperture the traffic, actually. And, that's a problem. Athletics, safety issues, some schools are fighting. If you put the bell times too close, you're

going

to have a lot of problems. Boston traffic, and so reinvesting money, and doing something that is fair and equitable. So, all these things, you cannot, this is multi-objective optimization. It's basically impossible to satisfy all of these objectives. And, some of them are really hard to formulate in an objective way. Boston has this problem that is very hard to hear from all the schools and all the parents. Like, some schools are louder than others, basically. And, Boston Public Schools is trying to do something that is best for all schools.

So,

at this point, after one year of lots of meetings with the community, it was decided that five things that

were

quite objective should be optimized to decide what the new bell times should be. One thing that is very important here is this teenager's health. Actually, there is a lot of medical studies that show that for teenagers, if you start very early, which is actually the case all around the country in a lot of districts, you have really an increase in problems, in mental health problems, including an increase in suicide rates, in depression. And, this is really something that needs to be solved and that a lot of districts are looking into. And, this was actually one of the first things, the first reason why Boston wanted to change its bell times. Then,

if

possible, save some money and reinvest it because Boston believes that you can have more impact on children with more teachers than with more buses.

Oops. And then,

two things. Younger children should not finish too late because they are

typically

less awake in the afternoon. So, it's kind of the opposite of the teenagers. And, trying to do something that doesn't change too many things for special education students, which is very important for Boston. And, all of this being fair and equitable. Fair and equitable is very important because, right now, the law that was in Boston for the last 30 years was saying that each school should switch their bell time every five years in order to be fair. Because, you saw that some bell times were really bad for the parents. But, we need to have all these bell times in order to have a transportation system that works. And, so, this rotation idea was actually

never

really implemented. Because, every time you want to change something like this, it can be really hard for the parents to do this. And, they protest a lot. It's very hard politically to make the change. And, so, across the years, typically schools that were a little louder than others

tend

to have bell times that were a little better. It's not always the case. But, it's really something that happened and Boston was really concerned over the equity of the current system and trying to make something a little more fair.

All

right. So, what happened is that the school committee decided to actually vote this in December 6th. So, after. And, this. So, these are exactly the five points that I just showed. And, this could have never happened without having an optimization engine behind. Because, what are these things? These things are basically describing cost functions.

If

you cannot optimize some things, it's useless to just describe cost functions. Because, you cannot prove that you actually followed these rules. And, only an algorithm can kind of prove that this is actually optimal for the rules that needs to be followed. And, let me give you a quick overview of what the changes look like. So, it's really abstract, like, because there are so many schools and so many particular examples. But, this is basically the main idea. This is the current system. The current system is all high schools extremely early, which is one of the main problems. Like, having a math class that starts at 7.15.

And, all elementary schools that are more numerous are across the spectrum of bell times.

In

practice, over the years, it looks a little bit more like this. Typically, you can see in the statistics that schools with higher income students tend to have later times that their parents prefer. Because, parents with younger kids really don't like their kids leaving home at 6 a.m. to catch the bus. And, schools with lower income students tend to be a little earlier, which is really something that needed to be solved. So, what is the algorithm doing at this point? The algorithm, the main objective, is to put the high schools later, right? In order to do this, you have to put some elementary schools earlier, just to make the transport station system work.

Or else, there is nobody early and the transportation costs are exploding.

So,

and actually doing this in a fair way here, so that the algorithm is blind to the particular, the specificities of each school, and makes its decisions just based on what is best for everyone. Yes?

Perfect. So,

at this point, these are the numbers describing a little bit like the current solution and the new solution that was proposed by the algorithm. So, you can see that we basically removed all the schools, the high schools that were early, and only 6% of them are early in the new solutions. And, elementary schools are typically now earlier, so we have more earlier, but before, for example, if you were black or Hispanic students, you had three times more chance to have an early time than white or Asian students, and we tried to correct this.

So,

what happened then? What happened? We had new bell times, and the district was ready to change them in 2018. Actually, these bell times were also saving a lot of money in transportation costs that the district promised would be entirely put into the schools and, in particular, paying for teachers and nurses.

So,

let's look at what happened in this other very interesting month of December. So, first, the Boston School Committee approved the start times.

And

people are starting to realize, oh, that's a big change. Most of the schools are changing in average by more than one hour. This really changed a lot the routine of every family. Like, sometimes you have to wake up two hours earlier or send your kids in the bus very early or in the opposite very late. And some parents decided that it was actually not doable for them, that they really wanted to have their voice heard. And even if there were lots of surveys before, like, now that the change was happening, a lot of people were a lot more concerned. And started to have their voices heard. But some other people also saw the stats and that the system was worth the change.

With the days, parents started to organize a lot more, typically, especially in some districts. And to draw a lot of political attention and put a lot of pressure on the mayor of Boston, especially with

this

petition with more than 8,000 signatures. And, yeah, parents really felt attacked in their day-to-day lives. They couldn't understand why this obscure algorithm was deciding what they should,

how

they should leave. Because this was basically affecting almost every family in Boston. And

the

mayor decided to actually push this by one year. So to give more time for exchanges with the communities, trying to understand exactly what went wrong. This doesn't change the stats. But I think it needed more communication both ways. It needed more communication for us sharing the number, explaining why this solution was better. And also, I'm sure we missed a lot of things from what the parents were thinking in all these community meetings. Maybe you always need more of them. Basically, community engagement is very important. And people started to realize that, yeah, it was not the algorithm fault. But also, some people had lost something. In particular, all the adolescents of Boston.

So,

I mean, this is basically what we were seeing, right? We were seeing our solution with our stats that look good, a great model. And this is exactly what we were discussing in the last talk. Because what were the people seeing? This was a meme that was posted on Facebook by one of the parents. And, yeah, this is

how

people really see optimization and algorithm taking care of their kids, you know? And, like, just breaking this barrier between the two worlds requires a tremendous amount of effort that, with our background in operations research, we were not expecting to have to do these things. Even if Boston did most of the work, we really learned a lot of things from this. And we are really ready in the next year to

try

to find ways to communicate a lot with the parents and decide what is the best thing that should be done for the start times. And we still think that there are some things that should be corrected. We will also keep working with the school buses to try to improve the system a little better. And we have this very exciting new project where we are starting to talk with Massachusetts to route all their homeless children from their shelters to their schools. And it's a very complicated routing problem because each kind of district does it separately. and we want to try to do it as a whole system.

So,

thank you so much. And, again, I think, like, the main takeaway here was that this communication part is extremely important and that there are lots to be learned

in

both directions. and that's just teaching people a bit about optimization, about statistics, and also accepting that when you have a model, you don't have the truth and you have to listen more and more and more to fine-tune what you know about the system is also very important. Thank you.

...formulations for routing problems with time windows and then using local search. Because then you could have combined route generation, single-school optimization, multi-school optimization.

So, one of the main reason, one of our main constraints was time, at the time. Like, this project started in the mid-spring, then we had two months and we also had to implement a lot of things with visualization. So, basically, we had one shot and one to choose. And in the end, we went this way. I really think it's a very interesting, actually, our first idea was, yeah, to

deal

with everything at the same time. We couldn't find a way quickly that was convincing to us, but I'm sure there is a way. And, yeah, that would be, that's one of the things we want to make better for the next year.

I think

it's strange to mention that you have to update this daily. So, is it updatable daily?

So, it's the original operator that

we

built

to

make sure that these changes, that these changes can be made.

I

think, so the changes come in daily and I think they're contractually obligated to make them weekly.

I

just had a question concerning the houses for people with special needs. Can those serve as...

There was actually something that Boston thought about doing. It was one of our first comments to them for this. It's actually very complicated because imagine you're one of these families. You have, all of the second, 30 kids in front of your house.

And,

like, special education kids, it can be complicated for them sometimes, like, in some cases, to interact with a lot of people. So, this sort of situation can be complicated. So, right now, Boston decided not to do this. So, only

one

student per door-to-door stop and not using them as corner stops.

Yeah? Did

you try to update the past routing again, like, after a couple of months that you had more time to solve for a better problem?

So,

we didn't do this through the optimization but we did work with the transportation team of Boston because that's their... I mean, they've... Some of them have been doing this for 30 years where they do manual updates.

So,

we let them handle the bulk of that

as

we were focusing on the bell times.

And,

yes, as an extension to that, are there seasonal patterns? Obviously, traffic might be worse during the winter, put more cars around the road, stuff like that, that you would have taken inspiration or... So,

that's

a very good point. The algorithm, right now, takes into account the patterns during the day. This is very important because congestion is in Boston at some time of the afternoon are horrendous. But, patterns across... Like, seasonal patterns, they do not take it into account because basically Bostonians understand that when there is snow, things are perturbed, right? And parents

basically...

Buses are late, but everybody accepts this and are used to it. And, as a consequence, it goes fine. So, the answer is no. It's not taken into account. It would be something that is possible. The problem is, when you change the routes, these kids are young and, you know, you don't want to change the routes so many times in a year. You want to have something as static as possible.

So... So, it's like, low-income students and high-income students

have... 45% of them have early patterns. So, it's an exactly equal percentage of them. So, is that like a hard, like a constraint that you put into the optimization? Or, did it just naturally turn out? Based on their income, like maybe they are... Their houses are located in parts of the city. So, there might naturally be a difference in the percentage of them when they are picked up by the bus. So, why are they, like, exactly equal? So, is that a constraint?

So,

we didn't need to put this in as a constraint. The fact that the algorithm is blind to income was enough to ensure this, but we did have to put a couple of extra constraints to ensure that you don't have one part of the city, like one geographic location of the city, that has like all schools at 730 or something. So, we did have a couple of constraints like this, but they were... It was a second order effect. Most of it just came from the algorithm being blind to things that shouldn't matter, like income.

Like,

if some districts are more expensive because they are located near a good school, then like actually their pick up time would be closer to the bell time frame. So, that would be later. So, is that the bell time?

So,

that's true. I think,

in

general, it tends to average out. So, the first order effect is the bell time, and the pick up time is the second order effect, because remember, there's a significant constraint on how long the students can spend on the bus. And also, in practice, you saw the average time on the bus is like 25 minutes. So, I think if you get the metric on the bell time right, you have most of the story there. But you're right that using pick up time is more accurate. There's probably a parent in Boston that thinks like that, and there's probably a parent that thinks,

I

don't want my student on the bus for more than 10 minutes.

Yes? So,

actually building on a couple of the prior questions here, I was remembering, so, 10 years ago, our little MIT shuttle bus service, we put a little GPS in those bands, so that you can log in and see, you know, where the bus is when it's cold outside. Do you stand outside? Do you stand in the hallway? And the public relation piece of this that you're struggling with, so one of the nice things about fleet management overall is the visibility. So, one of the great successes of Uber was the fact that you can not only talk to the dispatcher, but you can actually see how far that car is from you so that you can make and plan and address some of these concerns.

And I just wondered, I mean, it wouldn't be hard to RTLS enable what you're doing. I mean, you know, just use the cell phones or the drivers or whatever to add a real-time component. And I wonder whether that wouldn't help to address some of the public, you know, in other words, the benefit to the parent is now they can see where their kid is. Now, in addition to that, you can do route optimization, which maybe that has some, you know, unanticipated. But every fleet management application, you're looking at real-time and rerouting based on traffic conditions.

And there's, I mean, there's no reason you couldn't do that as well unless maybe that, you know, you cited some reasons that the changes might not be popular. But at a minimum, the visibility, you would think, could be, you know, a real plus.

Yeah, so that's a very good point. Actually, all the buses right now are tracked by GPS. And parents have an app, an application to basically check when the bus is about to come, because sometimes buses are late. And the only thing is the bail time part of the project was in the end not very correlated with the transport. Transportation was just the constraints that forced us to have schools all over the bail times. But in practice, parents that were unhappy, a lot of them were transporting their kids themselves to schools without buses. Most high schoolers are going on their own to their schools using the MBTA.

So for this part, we didn't find a way so that the application and the real-time components really helped the understanding. It was more a question of what should be the priorities of the city. If you help the teenagers, then parents of elementary school students will be unhappy. And the opposite also, too. So it's more like solving these sort of problems.

Great, and thank you very well

for

that. I'm sure that those are the ones I want to be doing, will you rather have to wait a second? I will laugh.

Let's have these fingers.

We'll be right

there once

some part.

Thank

you very much for leaving hockey and thank you very much for your support when yououre first