One City Saved $5M by Routing School Buses with an Algorithm • Hacker News Board

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

#101

Post by w8rbt » Tue, Aug 13, 2019, 1:22 PM UTC

illnewsthat wrote: post #96

ikeyany wrote: post #89

Earlier quoted context omitted.

They're usually part-timers or neighborhood parents volunteering.

I have never heard of a bus driver being a volunteer position, is that something that happens near you? And, if so, is it a public school district?

This has been my experience as well. It's either retirees or stay at home moms/dads that drive the buses part time. They may not be purely volunteer (no pay), but it's definitely a part time job. Couple of hours in the morning and afternoon.

Also, it seems to be mostly in rural areas. Some drivers keep the buses at home during the school year. And, these are large, full size buses. If you live in a medium sized or large city, it's probably different.

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

#102

Post by gmadsen » Tue, Aug 13, 2019, 1:24 PM UTC

ikeyany wrote: post #89

mattlondon wrote: post #78

Interesting - so is it "a thing" in the US that the city runs a dedicated bus service for all schools/students? Quite a surprise for me considering how poor people say public transport is in general in the US? In the UK some schools run their own bus things (in the same way that Goolge, Facebook et al do in San Francisco), but most of the other schools just get by with the public buses. There is often some coordinati…

They're usually part-timers or neighborhood parents volunteering.

never heard of that. At least in California there are strict requirements and qualifications to be able to transport children on a school bus

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

#103

Post by kuschku » Tue, Aug 13, 2019, 1:25 PM UTC

lonnyk wrote: post #54

Swizec wrote: post #39

Earlier quoted context omitted.

> 1) Americans just in general tend to drive their kids to school dues to fear of child abductions and related ever-present paranoia. Is it true that in some places this paranoia has gotten so far that you’ll get reported to child services if you let your kids walk to school? > 3) Boston's weather is also miserable - the place is at just latitude so that wet, 30 degree weather prevails in winter, giving freezing rain…

> What’s the problem with walking a kilometer or two Where I grew up in New Jersey I lived 2 miles (3.2 KM) from school and I was considered close to the school. Those who lived within a 10-20 minute walk would walk. Many of us who lived further away would rely on the bus. Edit: And this was for elementary and middle school (up to age 13). From ages 14-18 everyone was significantly further away.

3.2km isn’t that much, I had from age 10 on a 4.5km way to school, and we all would just cycle there, even during storms or with snow, or in 41°C heat, all year.

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

#104

Post by Finnucane » Tue, Aug 13, 2019, 1:28 PM UTC

jefftk wrote: post #90

mattlondon wrote: post #78

Interesting - so is it "a thing" in the US that the city runs a dedicated bus service for all schools/students? Quite a surprise for me considering how poor people say public transport is in general in the US? In the UK some schools run their own bus things (in the same way that Goolge, Facebook et al do in San Francisco), but most of the other schools just get by with the public buses. There is often some coordinati…

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

In Somerville, it's hard to be more than a mile from the school. Cambridge, on the other hand, does run busses. It is true that the tech companies for the most part don't run private shuttles, MIT and Harvard do, though less for commuting than just connecting separated parts of their campuses.

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

#105

Post by superpermutat0r » Tue, Aug 13, 2019, 1:28 PM UTC

mipmap04 wrote: post #99

superpermutat0r wrote: post #62

Earlier quoted context omitted.

The thing is, all of these algorithms should be able to do well with arbitrary constraints. If it means saving less money then so be it. Many of these systems start optimizing some simple criteria and work fairly well. But with additional constraints they fall apart. Even companies that manage their own fleets for their own needs would like different things to purely optimizing distance/duration. They might want to b…

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

Undefined start or end time with a limit on driving duration is not trivial.

Well, routing school buses is already less than trivial. You have pickup & delivery. So there's a precedence constraint to orders. Child won't be kept for hours in the bus, so the bus has to make several trips to school. Limiting the time between delivery of the child and the pickup is already less than trivial.

Just to know if route is feasible (all constraints satisfied) given a list of child pickups, child dropoffs and time limit between pickup and dropoff is nontrivial and can mess up the optimization.

Adding school shifts to the equation, minimizing number of vehicles and a bunch of other constraints might make the optimization just too slow or too constrained for an algorithm that was working incredible without all those constraints.

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

#106

Post by ghaff » Tue, Aug 13, 2019, 1:29 PM UTC

Dumblydorr wrote: post #73

andrepd wrote: post #60

Earlier quoted context omitted.

>The street organization is irrational, derived haphazardly from ad-hoc pre-auto paths. Isn't thus true of any European city?

Not any, many were rebuilt after bombings in WW2. Even so, Germany is known for splendid trains, meanwhile Bostons trains are notoriously bad. My old company was off the red line and numerous employees were delayed at least once a week due to the red line sucking.

You'll find people who regularly use public transit in many European cities complaining about their transit systems too. Boston isn't great, especially in the winter. (I used to have to use it on a regular basis.) But if I'm being fair Boston isn't "notoriously bad" unless you're setting the bar at the level of a relative handful of world cities.

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

#107

Post by sailfast » Tue, Aug 13, 2019, 1:30 PM UTC

mattlondon wrote: post #78

Interesting - so is it "a thing" in the US that the city runs a dedicated bus service for all schools/students? Quite a surprise for me considering how poor people say public transport is in general in the US? In the UK some schools run their own bus things (in the same way that Goolge, Facebook et al do in San Francisco), but most of the other schools just get by with the public buses. There is often some coordinati…

Yes. Our population densities are lower, school distances are often not walkable reasonably, and schools being public they want to ensure that their students are not impeded from getting to the classroom for any factors related to logistics, income, etc.

Often times these are part-time positions. Set block of hours twice a day. Drivers can take on additional duties or other jobs. The buses themselves are either owned by a transportation company that can also hire them out on weekends or making additional money on field trips / sports transportation.

My kids are fortunate enough to be able to walk to their school - there are sidewalks and it's only a half mile away, but many other students have a longer walk, no sidewalks, or other impediments that leads them to prefer a bus. Kids could take public transit, but typically this is not a great solution in most places, and it doesn't deliver you to a school directly. The latter factor helps with truancy, security, and a number of other things. There's a cost to it, but it is a norm.

It would be straightforward for a school district to agree to change the policy or reduce bus service for cost reasons if public transit and things like walking, biking were preferred options. These are typically the norm for private schools.

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

#108

Post by GarrisonPrime » Tue, Aug 13, 2019, 1:30 PM UTC

jefftk wrote: post #90

mattlondon wrote: post #78

Interesting - so is it "a thing" in the US that the city runs a dedicated bus service for all schools/students? Quite a surprise for me considering how poor people say public transport is in general in the US? In the UK some schools run their own bus things (in the same way that Goolge, Facebook et al do in San Francisco), but most of the other schools just get by with the public buses. There is often some coordinati…

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

My father was a school bus driver. The pickup and drop off routes were often 3 hours each, as they were mandated by local law to provide service to the whole country.

Kindergarten is just half a day in many places, so the middle of the day would be another 3 hours to shift those around.

There were also many field trips, sporting events, and other miscellaneous calls for transport throughout the day and into the evenings, as well as some weekends.

Much of all of this would vary quite a bit depending on a particular town’s location, population needs, layout, etc. but I just wanted to say that although it’s a relatively chill job and there is indeed often a lot of downtime, it’s not like bus drivers universally work 1 hr in the morning, 1 hr in the afternoon, and then just bum around all day.

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

#109

Post by JoeAltmaier » Tue, Aug 13, 2019, 1:31 PM UTC

superpermutat0r wrote: post #105

mipmap04 wrote: post #99

Earlier quoted context omitted.

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

Undefined start or end time with a limit on driving duration is not trivial. Well, routing school buses is already less than trivial. You have pickup & delivery. So there's a precedence constraint to orders. Child won't be kept for hours in the bus, so the bus has to make several trips to school. Limiting the time between delivery of the child and the pickup is already less than trivial. Just to know if route is feas…

In rural Iowa (where I live and grew up) the middle-school bus and high-school bus are full the first couple of days of school, then they all start driving/getting rides to school. At the middle of the school year, maybe 12 people on a bus build for 60. That makes it complicated too.

And 'optimization' solutions result in 1hour+ rides to a school just down the road, as the bus winds about the countryside scavenging the few remaining students. The longer the trip gets, the more that find another way, the emptier the bus, the longer the trip to try to fill it again.

We drove our kids to school for most of their school careers, even though three busses went by our house every day.

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

#110

Post by ghaff » Tue, Aug 13, 2019, 1:33 PM UTC

dsfyu404ed wrote: post #85

magashna wrote: post #83

Earlier quoted context omitted.

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

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

It's probably not much of a factor any longer but, for many years after the "Blizzard of '78", everyone knew someone who had to be evacuated from Route 128 or who got stuck at work for a week. A decade or so later I remember a friend who had moved to Boston recently remarking to me that they had never seen a northern city where people were so paranoid when the first snowflake fell.

It definitely created a mindset of really wanting to get home (or just staying there in the first place) if any amount of snow was forecast. Of course, it doesn't help that traffic is pretty bad even in nominal conditions. Every few years you still end up with a 6 hour commute home situation for many people.