21 ms·
MIT team’s school-bus algorithm could save $5M and 1M bus miles
- vineet 9y agoI 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.
- dublinben 9y agoIf 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-do-you-fix-a-school-bus-problem-call-mit-1502456400 http://facebook.com/l.php?u=https://www.wsj.com/articles/how...
- LeifCarrotson 9y agoWSJ: You cannot have your SEO marketing and social media virality cake and eat it, too.
- distantsounds 9y agoooh, this used to work when searching the article in Google but has since stopped. Glad this workaround exists!
- toomuchtodo 9y ago> 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.
- hervature 9y agoFor 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.
- dajohnson89 9y agoI think the 1m mile savings figure implies a much higher cost that's harder to quantify -- vehicle wear, accident reduction, traffic congestion, labour, etc.
- pbhjpbhj 9y agoIsn'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.
- bb611 9y agoThe contest prize was $15,000, there were probably some ancillary costs related to running the event but still quite cheap.
- cropsieboss 9y agoPickup 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.
- jeddawson 9y agoHave 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!
- towndrunk 9y agoKind 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.
- limaoscarjuliet 9y agoLikely 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.
- dclowd9901 9y agoAsk Bluebird; they have the market cornered. My guess is they have no need to innovate, so they do not.
- briffle 9y agoThey 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-Introduces-AllNew-Electric-School-Bus-So-104.aspx https://www.blue-bird.com/blue-bird/Press-Releases/Blue-Bird...
- jtuente 9y agoAs 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.
- jasoninprivate 9y agoI 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.
- chrisbennet 9y agoSince 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?
- losteverything 9y agoThe 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!
- oddlyaromatic 9y agoHow 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.
- losteverything 9y agoBut 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
- Govindae 9y agoI suppose they should be talking about budget velcoties.
- jmull 9y agoIt 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.
- yedpodtrzitko 9y agoLocked article. So I am just curious - is that a different algorithm than the one with "no turning left" rule which saves money to UPS?
- throwaway2016a 9y agoI 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.
- robotresearcher 9y agoYou're curious whether MIT used a well-known algorithm and publicized it as their new invention?
- payne92 9y agoI 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.
- trendia 9y agoAnother 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.
- maxerickson 9y agoI 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).
- goodcanadian 9y agoIn 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.
- bluGill 9y ago
- rce123 9y agoHow 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.
- Sir_Cmpwn 9y agoFlagged, paywalls without a workaround are not permitted on HN. https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html
- m777z 9y agoThere is a workaround posted elsewhere in the comments http://facebook.com/l.php?u=https://www.wsj.com/articles/how-do-you-fix-a-school-bus-problem-call-mit-1502456400 http://facebook.com/l.php?u=https://www.wsj.com/articles/how...
- mathattack 9y agoI'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.
- mck- 9y agoGiven 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/ https://routific.com/stories/spring-hope-food-drive/
- com2kid 9y ago> 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.
- cropsieboss 9y agoThese 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.
- omot 9y agoDidn'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.
- mightytightywty 9y ago$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.
- askvictor 9y agoThis would create a crapton more traffic, if you could even satisfy the demand in the first place.
- Animats 9y agoIf 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.
- vit05 9y agoI think this is similar to what remix.com do, but just for Schoolar bus?
- qandrew 9y agoi can't access the WSJ journal... can someone link me the MIT profs involved in this work?
- theprof 9y agoReally 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.