MIT team’s school-bus algorithm could save $5M and 1M bus miles | Hacker News Reader

MIT team’s school-bus algorithm could save $5M and 1M bus miles

wsj.com

169 pointsfrostmatthew109 comments

I worked with a startup years ago that did these kinds of optimizations (for deliveries). The logistics & transportation market in the US is about a TRILLION dollars -- small optimizations can make a HUGE impact.

The challenge for practical implementations is that there are lots and lots and lots of optimization factors that are very hard to account for. Often, you don't even know what they are until you try to automate the process.

For example: preferring small buses on side streets, as the article mentions. Or, knowing about a major work project in an area (to avoid for the coming year), or specific left turns that are tough for a bus. Also, highly optimized schedules usually have (by definition) much less "slack" in the overall system, and are less resilient to real world changes and variations.

My point: in my experience, there can often be a significant gap between enthusiastic technologists (myself included) and real-world implementations.

Another example: a lot of rural areas have patches of gravel roads. It's not obvious from Google maps where the roads go from paved to gravel (and they sometimes do it in random sections).

Naively looking at a map, you'd think a roundabout route had potential to be shorter, but not realize the road was gravel.

I imagine many data sets track surface.

Surface data in OpenStreetMap is pretty incomplete, but it is easy to add to a road and is well used when present (cycle routing is a popular use of OSM and avoiding soft and uneven surfaces is handy for cycle routing).

In rural areas, school buses drive on gravel. Where I grew up, the buses were speed limited by law, so the speed on gravel is often the same as on the highway. Road surface might not matter as much as you think.

In rural areas there are a lot of minimum maintenance roads. Legally they are roads and you can drive on them all you want. However if you don't have 4 wheel drive you shouldn't drive on them, even with 4 wheel drive there are times when you won't make it. A bus should never drive on these roads, and google does not know which these roads are - as I've discovered when I had to rescue someone who blindly followed google maps.

Sure, I guess I was trying to comment specifically on gravel. You will need accurate maps for this to work, but I think that is basically a given. A human route planner will also need to have accurate maps.

A local human bus driver doesn't need the map, they know the route and the bad road areas.

In Colorado this has been mapped https://coloradogravelroads.com/

Despite gaps between technology and the real-world, there is still tremendous value to be had by technology, if you combined it with the real-world, i.e. humans.

Routing algorithms can come up with extremely efficient routes, which can serve as a starting point for the human route planner to fix (to account for real-world knowledge).

Consider the alternative where the human route planner starts from scratch.

UPS' automated routing system acts a partner with human drivers working to beat the route recommendations.

https://www.fastcompany.com/3004319/brown-down-ups-drivers-v...

You're all neglecting the biggest problem of all - the driver. All of this work is moot if Dorthy, who's been driving the same route for 40 years, will not change the route. And you can't get rid of Dorthy because there's nobody to replace her in Dinkysville, Flyoverstate.

I get the point you're making, there's always some human resistance to new systems but it's something you manage through. It's not a show stopper.

There are any number of reasons for bus drivers to have to change, from route optimization to school redistricting to, back in the old days, having to pick up all the children, not just the White children. People aren't horses. They can accept change.

The kids change, too. Not too many kids go to primary school for 40 years while living at the same place.

I modeled traffic. I sold my company and retired, years ago. People don't realize how complicated traffic really is. It's a chaotic system, of sorts. You can tease out patterns with some work.

Anyhow, to add to your point, you can model all you want - but some drunk is going to reverse the wrong way down a one way street.

One of these days, maybe I'll get around to putting my experiences into giant walls of text.

I would love to hear more

I'll see about getting some writing started. I keep getting asked to write a book.

It was a pretty wild ride. I have a Ph.D. in Applied Mathematics and actually did my research with vehicular traffic because the date was free. I actually expected to remain in academia, but was given the chance to contract with a government agency, even before I'd done my defense.

Basically, I helped take the art of traffic modeling to the computer age. I say helped because I stood on the shoulders of giants.

I'd eventually be able to hire competent programmers and a real IT staff. Eventually we'd model pedestrian traffic, in addition to vehicular traffic. We would also sell solutions that companies could implement on their own.

The recession hit. The US gov announced they were going to invest billions in highway infrastructure. This made the company quite valuable and I was given an exceptionally good offer. So, I sold it and don't regret that decision at all. I'm happily retired and find lots of things to keep me amused.

There is a whole lot more to the story but that's the gist of it. I'm the same KGIII you may have seen on Slashdot.

This is really interesting! Thanks for sharing. Is the vehicular traffic data you're referring to at the state level (i.e. do individual states report on it)? Or is it available for all states? And can anyone access it or is it only free for academic licenses?

Various States will have varied rules, but it is generally free. The Feds will also have stats for interstate routes.

In my case, the data was existent. I'd later collect data. Data is not just throughout, but even contains data from things like a reflectometer, sign frequency, and adjustments for specific locations.

The data collected is, for this sort of thing, paid for by the municipality and can be examined at your local municipality, where applicable. The specific department, and location, will vary but our reports were public information. Your department of transportation has copies, where applicable.

I didn't do much in the way of design. I modeled. This is what will happen if you do this, this is what will happen if you do that, and if you want these results you should consider doing these things. They don't always listen.

We also did modeling for things like disasters. A recent example would be the bridge collapse in Atlanta, GA. Most of the public thought it was going to be a nightmare. I actually had people argue with me and tell me I didn't know what I was talking about. No, they already have plans on file to deal with the expected congestion from just such an occurrence.

Of course, those plans are usually a bit out of date... In their defense, it's not an inexpensive process. Given the ubiquity of compute cycles, many municipalities are taking some of this in-house.

Your local planning board should be a good start, if you want to learn about your specific area.

Note: I have been out of the industry for about a decade. I am contractually barred from entering the industry again, in any capacity. I do try to keep up with the tech, but that's purely out of curiosity. It is no longer a scholarly or professional pursuit.

Also, any reports we filed are almost certainly still around. They are probably buried in a closet, however. I am not actually sure how municipalities function as well as they do. They are, almost without fail, very disorganized.

Someday, I'll tell you about The Font People. Yes, we even quantify fonts as an impact factor. However, Font People are some of the most unusual characters I've ever met - all of them.

I do miss the data collection and research. But, I haven't worn pants all day. So, it's an acceptable trade off.

Fascinating story. Thank you for sharing! How long did it take you to build this company from start to exit?

What were some of the toughest moments you experienced?

And what advice would you give to people who want to build their own companies in transportation/logistics fields? (I know - may not be exactly your area but there may be some cross-sector knowledge sharing at play here!).

I started it, unofficially, in 1991. The sale was finalized in late 2007. I started with loaned equipment from DEC, on an empty factory floor, with just myself and a fellow grad. He was a CS grad and we would later part peacefully. He never had ownership.

My toughest moments were people related. I never took any fancy business course that taught me how to manage people. I tried to micromanage and had a hard time letting go.

Eventually, we'd have three offices along the East Coast and a satellite office in the middle of the country. We had about 235 employees when i sold. What I learned was to stop trusting vendors.

I learned that I'd hired these people to do things that I could not do. If I could have dne them, I'd have not needed to hire them. Give them the tools they ask for, the room to do what they need, and clear goals.

They were different times. It was a Wild West sort of environment. It was hard enough getting engineers and programmers to wear shoes and a lot like herding cats. But, give them freedom and respect. Remember, you hired them because they were the very best you could find and they can do things you can not.

Advice? Be in the right place, at the right time, with specific skills, and in a position to take risks. Had I been unable to complete my first contract, the penalties were great enough that I'd still be paying them off - slight exaggeration.

It's pithy to say study hard and work hard, but that helps. I worked my ass off, often putting in 16 hour days. I'd continue to do this, even after being the sole custodial parent for my two kids. My ex wife is a bit of a mess. I missed a lot of their youth and they were often home with a girlfriend or a nanny.

But, find something that is missing and do it. Find something that is hard, and do it better. Right now, things look like a more intensive struggle for efficiency. How can you make transportation/logistics more efficient? How can you make it better? What services are lacking?

In my case, there weren't even many traffic engineers back then. The field, as applied by computers, was very young. The existent algorithms didn't scale or translate well to computers. I'm a horrible programmer, but I am a mathematician. I fixed that.

Similar processes applied to fleet management and to pedestrian traffic. Similar processes relate to outflow of people in buildings such as skyscrapers, shopping malls, and arenas. Even certain outdoor events need evacuation plans, for which modeling pedestrian behavior is important. Even your grocery store has probably modeled how you will move through it.

We had more work than we could do. I couldn't hire enough people and we just kept growing. I liked field work, so I tried to get as much time out in the field as I could. It also meant that I was on-site, a lot. I kinda hate dealing with government workers. They mean well, but they are tied to a dysfunctional environment.

Anyhow, soft skills matter. Be nice, polite, and an active listener. Listen for what they need, not what they are telling you they want. Be ready to try to provide both.

Sorry for the verbosity and disjointed post. I don't have words of wisdom, only my own experiences. I hate to admit it, but going to a good school probably helped a great deal initially. I went to MIT and just that was enough to open the doors. DEC literally loaned me equipment, both during grad work and to start the business. MDOT gave me loads of help and even followed my research from a fairly early point.

I'm open to continued responses, but I don't want to derail the thread too much.

Super interesting--thanks for the writeup. Keen on reading more if you do write the book!

I second that! Book or blog posts would be great :)

Great post, I appreciate contributions like these to the HN community.

  > Be in the right place, at the right time, with specific skills, and in a position to take risks.

You can't enter the industry but I can...

So where would you start looking? Or do you think the 90s was a different environment where you could solve a problem on your own. Now to improve efficiency, do you need the support/funding of an established company?

I would look at improving navigation efficiencies for self driving cars, as individual units and collectively.

Thank you very much for all the good advice. It didn't feel patronising and I admire the humble tone of your writing.

You are definitely right about being at the right place at the right time, and making sure you have the skills to do it better than others.

I have a pure software engineering degree (Masters) and been teaching myself deep learning lately. I am currently undertaking the Udacity self-driving car engineer nanodegree as as it is a great way to pick up skills in computer vision, machine learning and the automotive industry space. I am confident those skills will be valuable if I find the right opportunity.

I am curious: do you know anything about rail?

Yes. However, do I know enough to be of any assistance? Maybe. Am I an authoritative source in regards to rail transport? No.

But, if you have a question - I may know. I have done quite a bit of reading, but no academic research and no publications with regards to rail transport.

I am trying to figure out how to proceed forward with this:

http://micheleincalifornia.blogspot.com/2017/07/my-old-colle...

http://solanorail.blogspot.com

Perhaps one day while incredibly bored and procrastinating on the decision of pants or no pants, you could look it over, die laughing and send me an email. My email address is in my profile.

Thank you for replying.

Since this forum for founder/entrepreneur types, let me inject a bit of caution from my own experience with dealing with government organizations:

If you save a business organization money, they appreciate it.

If you save a government organization money, the next year the "savings" is likely to be deducted from their budget. They don't get to benefit from the savings and thus their motivations aren't what you might expect if you are used to dealing with businesses.

It makes sense but when I encountered this the first time it caught me by surprise. I mean who wouldn't want to save money, right?

The part that always blew me away about governmentese was when i realized that "budget cuts" meant the program isnt getting less money than last fiscal year, but their increase YoY has been reduced!

How else could you plan beyond one year, other than in reference to expected increases/decreases in subsequent years? Those expected increases can't be ignored in "the budget", so they are planned for and probably allocated before that fiscal year ever starts. If you reduce that increase, you absolutely cut the budget.

But to an idiot like me, the absolute amount should go down if it is a cut; not up!

So if i spent $500 eating lunch at work two years ago; $600 last year and plan/allocated $610 this year i had a "budget cut?" no. I spent more.

Thats how i think

I suppose they should be talking about budget velcoties.

Ah, the mythical budget vector.

Oh hey budget space must have an L1 norm. That's neat.

Pretty soon, we'll see the new consulting offering from McKinsey: Vector-based Budgeting. Very useful helping to mathematically quantify your various business unit's planning cycles in infinite dimensional space. You thought ZBB was cool, VBB is even cooler.

Think of the budget as a multi-year allocation. If Budget A from 2 years ago was "$500 this year, $600 next year, $700 the year after that" and now you reduce the allocation to $610, that is a budget cut from the original Budget A.

Only if the budget was reasonable in the first place. All too often they "budget" far more money than is possible and then celebrate the cuts.

This is two different things, not helped by the multiple meanings of the word budget. If the organization makes the budget (i.e. a spending plan) without confirming the funds (or knowing them through, say, a long term understanding), and don't get what they seek, of course that's not somebody else "cutting" their budget. That's just a budget you made up not being agreed to.

But this is more about having an expectation of funding at a certain level from whatever source, and knowing that that will be your "budget" (now meaning a spending _limit_), then having that amount come down. You now have a smaller limit.

Agreed. This is why we need zero-based budgeting. Force organizations to justify every dollar every year rather than just using previous years as the starting point.

That doesn't work either: you get situations like the TSA artificially backing up airport security lines to "necessitate" budget increases.

They should incentivize efficiency. In government, it would be citizen impact per employee. If you have more, you make more money, if you have less, you make less.

> citizen impact per employee.

Do you think it would actually possible to quantify this in a way that:

1. Accurately represented "reality"?

2. Couldn't/wouldn't be gamed?

Seems challenging to me.

I've never seen any metric that can't be gamed somehow.

Choosing metrics to represent practical value, rather than let them be decided by profit-seekers, that's the real trick.

I think you can probably boil impact down to several key metrics:

1) How many people are affected by the work of this agency

2) How quickly are peoples' needs handled on average

3) How pleased are people with the work of this agency

I think you could trivially measure each of those.

How pleased people are this year, or in ten years time? There are lots of ways to make users happy in the short term at the expense of long term benefits.

If the police stopped arresting people then criminals would be much more pleased with their work

Meh, there are times/places when that is a good idea.

But if you make it annual standard operating procedure, then you are paying people to create spreadsheets and documents rather than, say, do something useful.

And the money will funnel to the people who are awesome at creating spreadsheets and documents rather than the people who are good at doing useful stuff.

Effective oversight requires understanding the domain and being motivated to continually improve things.

> If you save a business organization money, they appreciate it.

Is that based on past experience?

Yes, they appreciated it so much they'll paid me money. :-)

I didn't write that original comment, but yes, my experience is that businesses are VERY happy to find ways to save money.

As they say, a marginal dollar saved "drops straight to the bottom line" (profits).

Yes it's how an expense becomes viewed as an investment with an ROI.

Actually most non-VC startup companies are heavily focused on opportunities to reduce their spending so long as it does not effect their ability to grow revenue

Interestingly in this case it seems it was the government that initiated the search for cost savings:

> In hopes of spending less this year, the school system offered $15,000 in prize money in a contest that challenged competitors to reduce the number of buses.

The way this typically works is that they were told from on high that their budget was getting cut, so they had to figure out a way to do so. Not sure if that happened here, or if these are just folks who are really interested in governing well, but that's been my experience.

Uhmm. Saving money doesn't mean they have to give it back you know. They could spend on other things like better computers for kids, more staff etc.

As I understand it (and I could be wrong), next year's budget uses last years budget as a baseline. If you spent $20K less on school books for example, you'd probably get $20K less for books next year. If instead you spent the same, but got 20% more books for the same money, that might work.

There is also this practice in organizations where money is allocated in "pots"[1]. For example, there is probably a pot for hardware/computers and a different pot for software. If you save them money on hardware, they don't automatically get to spend the savings on software.

(I thought you were unfairly down-voted so I up-voted you.)

[1] The correct term escapes me at the moment.

There is a difference between local government and state or federal government here: local governments are more likely to be perennially underfunded, rather than competing with other agencies for federal money.

Plenty of business organizations behave exactly the same way, which is one reason for sales cycles in b2b services. Departments are willing to spend money at the end of a budget period on things they otherwise wouldn't have, divisions unwilling to reduce staffing because they may not get approval to hire more people later...

Exactly right: this is a pattern of bureaucratic empire-building versus smaller/flatter organizations, not one of government versus business institutions.

That's also why third-party analysis of how government organizations spend their money is so crucial. Without such analysis, there is no check on wasteful spending.

They work for the people, after all.

It will be interesting to see how it works out in real life.

As the article notes, they've tried this before and the algorithmically generated route map didn't work well in real life. Assuming the algorithm was good, the issue was probably that it didn't incorporate significant real-life factors.

Perhaps they are getting more sophisticated though, by having the people who have been doing this work by hand review the results and make adjustments (as the article says, e.g., at first the algorithm allowed big busses on narrow streets, which apparently doesn't work well).

Speaking of the people who have been doing the route maps manually... they seem to have been doing an impressive job since the algorithm is expected to be only 4% better.

Kind of off topic but... why is no one converting school buses to electric? Seems like a perfect opportunity. Lots of space for batteries. High torque. Short runs in the morning and afternoon. Think of how many diesel school busses there are across just the USA every morning.

Likely for the same reason Tesla was really, really expensive until now and is just reasonably expensive now with model 3. The initial investment plus extra funds to build charging infrastructure is likely the reason why we cannot have it yet. Also, if you think about it, each school bus might not be driving enough miles to make up for the cost of conversion.

Ask Bluebird; they have the market cornered. My guess is they have no need to innovate, so they do not.

They have just announced electric buses last month [0]. They also have CNG and propane powered models.

[0] https://www.blue-bird.com/blue-bird/Press-Releases/Blue-Bird...

As with everything else, time and money. Most schools don't have the funds to replace their fleet of buses because of (the next big thing) and will have to do it as the old ones die off. Add to that the higher cost of electric vehicles and it doesn't look as immediately appealing.

I can't speak on behalf of everyone, but my mother has been a school bus driver for the past 20 years. I'm not so sure I would consider the runs short. She drives at least 8 hours a day, with a break in the middle. There isn't much extra space in her bus for batteries.

In addition, the lifetime of a bus isn't measured in the same way cars are. They are purchased once a decade, never retrofitted, and not every bus is replaced with that purchase. With that in mind it will probably be another 2 sales cycles before we see any.

I was thinking underneath the bus was the perfect space for battery packs. Once you remove the gas tank and exhaust etc there would be plenty of room.

You need to add a much strong suspension system as well, that implies more wheels.

I'm not saying it can't be done, just that it is harder than it looks.

Busses are typically MDT chassis that are spe-d out very lightly and even then they pretty much never run anywhere near their GVW (whereas every other commercial vehicle is near, at or over the GVW basically all the time). A box truck for hauling baked goods is about the only thing that's going to be spec'd out lighter.

An extra few thousand pounds would not be a problem for a full sized school bus.

And think of the cost. Diesel is cheap, buses stay in service for years and it takes just a few minutes to refuel. You’d need hundreds of charging stations for every school district. Instead of just a few fuel pumps. It would cost literally 10s of billions to convert all school buses for a marginal cost benefit.

School buses also have secondary uses as evacuation vehicles so relying on electric isn’t a secure option. Hurricane Katrina, for example, used hundreds of buses for evacuations and it would have been extremely difficult to charge a bunch of buses off generators.

Newer London buses are all hybrid and there are some electric as well I think?

Not sure if by "converting" you mean retrofitting old buses or replacing diesel buses with new electric buses. If it's the former definition, it's non-trivial from a safety and engineering standpoint to integrate a high-voltage, high-energy battery system into an old bus and expect to realize a decent ROI. Those old clunkers are not designed with an electric powertrain nor efficiency (i.e. they're heavy and have have drag coefficients) in mind. Furthermore, safety is paramount in most bus operations, and a lot of thought needs to go into mitigating thermal runaway or other catastrophic failure modes with systems of that voltage (100s of V) and energy (300kWh+). Depending on the existing bus system that the battery needs to be integrated into, this can be challenging and sometimes infeasible.

I say all of this more to make the argument that rather than retrofit old buses, in my opinion it makes more sense to outright replace them. Right now Proterra is the largest domestic producer of pure electric buses. They compete on most contracts with BYD in China, and New Flyer in Canada. Behind BYD and the government, the electric bus market in China has absolutely exploded over the last several years. Proterra is anticipating high growth in the U.S. market as well and just launched a new factory in LA last month [2].

[1]https://www.proterra.com [2]https://www.forbes.com/sites/alanohnsman/2017/07/26/proterra...

Seriously?

While aerodynamic teardrops are most efficient that means nothing if the up front cost is prohibitive.

Also, efficiency and a box that's strong enough to appease the "think of the children" types are very much at odds with each other.

For a bus with low mile requirements some boxes to hold batteries and a big DC motor where the engine goes would work fine.

The "scaled up golf cart" architecture works well if the route does not change and is very cheap to implement.

The upfront cost is no longer prohibitive with all-electric buses realizing savings in the form of reduced maintenance and fuel costs that exceed the initial investment discrepancy [1-2].

On your second point, a bus doesn't necessarily have to have a heavy steel frame for it to be safe. There are plenty of lighter weight (e.g. composite/carbon fiber) solutions which don't sacrifice safety.

Sure, if the mileage requirements are low then there's definitely a cost-effective retrofit solution. But if you're a company already building a full electric bus and investing a lot of R&D into the pack design anyway, then you could probably just sell battery solutions to school bus companies as another revenue stream. I'd wager, though, that the larger addressable market is customers looking for new electric buses for longer routes.

[1]http://www.columbia.edu/~ja3041/Electric%20Bus%20Analysis%20... [2]https://www.nrel.gov/docs/fy16osti/65274.pdf

I would argue that efficiency is more important in a school bus than safety.

Buses are designed for many years of service with long-lived and easy to replace parts. On the safety front they are painted yellow and have some lights. That's pretty much it. They don't even have seat belts.

It looks to me like efficiency trumps safety in this case.

It is reasonable to assume that safety is the primary concern for school buses. There are are a lot of safety standards.

"Pursuant to these requirements, federal safety regulations applicable to bus manufacturers have been developed. There are a total of 37 federal motor vehicle safety standards that apply to school buses. Many of these also apply to other types of motor vehicles, but several (among them standards 131, 220, 221, and 222) are written specifically for school buses."[1]

As for seatbelts,

"Large school buses are heavier and distribute crash forces differently than passenger cars and light trucks do. Because of these differences, bus passengers experience much less crash force than those in passenger cars, light trucks and vans."[2]

It seems that even weight[3] is a safety consideration.

[1] https://www.cga.ct.gov/2004/rpt/2004-R-0730.htm [2] https://www.nhtsa.gov/road-safety/school-buses [3] http://www.americanschoolbuscouncil.org/love-the-bus/educato...

Additionally there are different rules for school bus drivers, for example even small school busses are forbidden from turning right on red.

My guess is risk is part of the answer. They don't have a huge budget, and it could be pretty financially disastrous to them if the experiment fails. And this has worked for them for 50+ years so there's no pressing need to change it.

Also, school districts are in the business of education, not transportation, so they may not see themselves as the people who should be leading in this area. If someone else (transit agency, airport shuttle company, etc.) tries something and proves that it works long term, they may then feel comfortable following along, but as far as I know, that hasn't happened yet because by definition it takes a long time to prove that.

Where I live (not USA) the bus company uses those same buses for other purposes through the day. So recharging them fast is very important.

Unfortunately, busses in many metropolitan areas run on staggered schedules. It's why middle school starts at 7:20am while grade school starts at 8:10 in some cities.

A typical service day for a school bus can be pretty packed.

Locked article. So I am just curious - is that a different algorithm than the one with "no turning left" rule which saves money to UPS?

I was thinking that too. Surprisingly, if the image in the article is actually accurate (it might not be, it's probably just a graphic designer's illustration) then the route that was generated actually takes exclusively left hand turns.

You're curious whether MIT used a well-known algorithm and publicized it as their new invention?

Pickup and delivery optimizing algorithms have been optimizing stuff in private businesses for years.

What do you think what kinds of algorithm makes schedules for trashbin collection, newspaper delivery, sodapop machines etc.

If you aren't ondemand and there's multiple drivers there is someone who can optimize it to (almost) optimality.

This is a pickup & delivery problem and the algorithms exist and work in practice for decades.

Have you used any that are actually effective? Please share if so :)

I work within the trash collection industry and we've tried several different optimization schemes that in general don't come close to optimal efficiency. The marketing for a lot of the optimization companies would lead you to believe that they're able to unlock a lot more efficiency than they actually deliver. Our clients that have applied algorithms to optimize their routes quickly reverted to human optimization since the algorithms fail to provide any benefit and typically require tremendous effort to get started.

I would love to discover an algorithm that is able to consistently provide actually optimized collection routes without hand holding!

$120M budget to bus 30,000 children to school? Does that sound like a lot, or is it just me? That's $4,000 per child per year. At 180 school days per year, that's $22.22 per child per day!

At that rate, they could save many more millions by switching to Uber or some other ride sharing service.

This would create a crapton more traffic, if you could even satisfy the demand in the first place.

If I'd made a really bad career decision, I would have spent years working on this problem in a suburb of Cleveland. A startup I once worked for pivoted from mainframe scientific time-sharing to school bus scheduling. Fortunately I'd left by then.

Really cool (full disclosure - my advisor was Bertsimas's PhD advisor)! School bus optimization is slightly different from UPS/DHL/last mile logistics routing because you only solve the problem once or twice a semester and make small changes as and when kids change schools etc. From a business point of view there really aren't any off the shelf products that do this well plus its tough selling to school districts. Ping me if this interests you.

I am glad that people are using algorithms to increase efficiency. But, this seems to only save $5M out of a $120M budget - I was expecting and am hoping for more.

I feel like it would be an awesome project to dissect a large public institutions funding and to discuss ways that algorithms can help reduce costs without reducing the quality of service and agility of the organization.

The site would not allow me to read the full article, so I might have missed something.

If you prepend "facebook.com/l.php?u=" to a wsj link, it will let you read the full article. Like so:

http://facebook.com/l.php?u=https://www.wsj.com/articles/how...

WSJ: You cannot have your SEO marketing and social media virality cake and eat it, too.

ooh, this used to work when searching the article in Google but has since stopped. Glad this workaround exists!

> I am glad that people are using algorithms to increase efficiency. But, this seems to only save $5M out of a $120M budget - I was expecting and am hoping for more.

There is only so much efficiency you can squeeze out with an algorithm. But, think scale. This is only in Boston. What if this team offered up the algorithm to all schools and other public transit authorities in the country? Think how many miles driven (less miles = less wear and tear, less opportunity for accidents to occur) and dollars would be saved.

Want to do it as a for profit taking a cut of the savings? Cool. Want to do it as a non-profit funded by the DOE out of a grant? That'd work to. It appears there are hundreds of millions of dollars in savings to be realized out there from this, which is awesome.

For those that think that a 4% decrease (or equivalently a 5% increase) is not much, you should go ask your boss for a 5% raise and see what they think.

I think the 1m mile savings figure implies a much higher cost that's harder to quantify -- vehicle wear, accident reduction, traffic congestion, labour, etc.

Isn't it more like tell your boss you'll take a pay cut, all it will cost is hiring your personal firm as efficiency consultants for £2M ... But look 5% reduction off your portion of the wage bill.

The contest prize was $15,000, there were probably some ancillary costs related to running the event but still quite cheap.

Given the scale of the problems they are tackling, I'm quite surprised how little they are saving. $5m over $120m is only 4%. I would imagine municipalities' manual route planners wouldn't be that great.

We have found with many real-world scenarios, that at a much smaller scale we could save easily up to 40% in driving time and fuel costs. When we studied cases of 20+ vehicles and ~1000 stops, sometimes the savings were up to 60%.

In one scenario we took 8 cars off the road form a fleet of 30. [1] That's 26% compared to the article's 11.5%. Not to discount its results, dropping 75 bus routes is incredible! Imagine dropping another 75 :)

Note that since this is an NP-complete problem, the larger the size of the problem, the more constraints you add, the harder it is for any human route planner to plan routes efficiently -- so the larger the potential efficiency gains for an algorithm.

Disclaimer/plug: founder of Routific here.

[1] https://routific.com/stories/spring-hope-food-drive/

> I would imagine municipalities' manual route planners wouldn't be that great.

Depends. If the same routes have been in use for a long time, odds are they are already really optimized. Bus drivers will take the same route year after year, and make suggestions to optimize it (often times by "going off route" now and then, which is very much against the rules, but at times very much needed), and those suggestions will get rolled in next year.

5 or 10 years of incremental improvements add up.

These are all just savings numbers for simplified problems, like vehicle routing problem or simple pickup & delivery problem.

Points below properly define problem above:

* capacitated pickup and delivery with time windows (NP-hard)

* capacity of around 20-60

* every child has to stay maximum T minutes in the bus from the moment it is picked up

* each bus can work simultaneously on delivering to multiple schools (covered by standard p&d algorithms)

* additional routing/map constraints for roads/vehicle constraints - like minibus drivers being constrained to ares with different housing etc.

I'm pretty sure the third point is a tricky one, implementation and speed wise, last one too. I'm skeptical that your API could solve the problem for 600 vehicles off-the-shelf. Not to mention that pickup&delivery slows things down extremely compared to capacitated VRP. Each optimising step is a venture into heavy graph theory. Or one can use easy heuristics and fail miserably by exploring too little of constrained space.

I'm skeptical of these large savings. I've personally worked with some top logistics people that did amazing things with pencils and rulers. Trumping these methods gained savings of about 10-15%.

Not to mention the optimizing time. It is impossible (if algorithm is not heavily optimized) to search through enough space for these heavily constrained problems in short amount of time (couple of minutes) to get 60% savings. I might be too critical, but I doubt that Common Lisp algorithm can achieve those kinds of speeds.

What if a child was forgotten, how much will the replanning time impact the real world workflow. All sorts of invisible issues.

How do they arrive at only 20,000 lb carbon emissions (presumably CO2), from 1M bus miles traveled? According to the EIA, 1 gallon of diesel produces ~22.4lbs of CO2. Even assuming ridiculously optimistic MPG ratings on the buses, these numbers don't seem consistent with each other.

I think this is similar to what remix.com do, but just for Schoolar bus?

Didn't read article, but bus routes are optimized for efficiency. They're optimized for driver hours. This is what I read online... I'm not sure how true this is.

i can't access the WSJ journal... can someone link me the MIT profs involved in this work?

I'm surprised they're only pricing each mile at $5. The opportunity cost of time on the bus would be a lot more than that too.