4 ms·

This is not a big data problem. This isn’t even a small data problem. Bus routes can be figured out with a paper and pencil in a few hours. I can’t possibly un

This is not a big data problem. This isn’t even a small data problem. Bus routes can be figured out with a paper and pencil in a few hours. I can’t possibly understand the level of incompetence required to get this wrong. Bus drivers don’t need to “practice routes”. Even if they get a turn wrong, the worst is a few minute delay.

gnu8 3y ago
You believe the traveling salesman problem for 100k students at 165 schools can be figured out with pencil and paper in a few hours?
- pavel_lishin 3y ago
  It's not a problem of getting 100k students to 165 schools. It's 165 separate problems, of getting (presumably, on average) 1k students to 1 school. That's a much more tractable problem, and if you have a large-scale map and a lot of push-pins, you can probably intuit 90% of the solution. Yes, the person you're replying to is probably under-estimating the problem, but this isn't a problem you have to rent quantum computing time to solve.
  - purpleflame1257 3y ago
    Additionally, you don't actually need the optimum, you just need a "good enough" method so that kids aren't on the bus till 10
  - JumpCrisscross 3y ago
    > It's 165 separate problems, of getting (presumably, on average) 1k students to 1 school If you have 165 * (1,000 / capacity) busses and drivers, sure.
    - pavel_lishin 3y ago
      That's a good point, I hadn't considered that! A good lesson for me, and maybe others, to not confidently offer opinions on areas where we're not even close to being subject matter experts.
  - WorldMaker 3y ago
    The problem is that the district in question has for a lot of reasons, many with good intentions, built this as a 100k separate problems. They wanted to abstract student assignment outside of geography and for the most part they have. They've lost the ability to just "push pin" the map because any way you slice it, it's now too much of a tangled spiderweb, because they don't want the map to make sense. They intentionally wanted to break map clusters and patterns. They can't rely on the map because they've built it so that they can't rely on the map. They've obviously built something that they can't scale easily, and it is a travelling salesman nightmare problem in so many of the harder ways. (They did this to themselves of course, but suggesting that they just start over with push pins on a large enough scale map ignores why they are in the problem in the first place. The map doesn't make sense. There's no way to intuit a 90% solution because there aren't patterns on the map. They didn't want patterns on the map.)
- glonq 3y ago
  I used to work in the transit industry. I can describe the problem and the solution with enough paper and a couple hours. But to actually perform route scheduling, we used a whole bunch of iron @ AWS.
- mrguyorama 3y ago
  The traveling salesmen problem is about the perfect solution, not a good one. The entire point of the traveling salesman problem in teaching is to show a problem where the human brain is really good at workable solutions, but computers cannot find solutions without cheating or checking EVERY solution. American schools have been designing bus routes well before they had computers to help them do so. Maybe it requires hiring a few more bus drivers.
sillystuff 3y ago
> Bus drivers don’t need to “practice routes”. Even if they get a turn wrong, the worst is a few minute delay. A long vehicle that does not bend in the middle has quite a few worse outcomes than a short delay. Fill it with children, and those worse outcomes can include tragedies. There are roads where the crest of the hill can result in the middle of the bus bottoming out, and the wheels at each end hanging in the air. There are roads where a downhill section levels out at such a sharp angle that the nose of the bus will embed in the pavement if you do not cut all the way across the road (into oncoming traffic; which you will NOT want to do with children on board) to reduce the angle. Some turns are simply impossible because the swing of the tail-end of the bus would e.g., take out the signage along the edge of the road. Maps will show a road that appears to continue through, but it is actually discontinuous due to e.g., a canyon; Turning around / backing a 65-80 passenger vehicle is no fun. Worse when full of screaming kids. I had a route where I had no choice but to back a bus down a four block long alley where the mirrors literally scraped on both sides in places due to a doorstep stop for a disabled child, but you always want to avoid live "skills tests". Why on earth would you intentionally add avoidable risk? All this while keeping in mind you need to maintain full awareness/control of the kids at all moments. Because, if you are distracted trying to correct an issue with your route and even something seemingly as minor as one kid stands up and falls, splitting his lip... You get to pull over and radio in to dispatch to call out the state highway patrol for a school bus accident, and wait for the officer to arrive and take the report. And, you get the points on your driving record (affecting insurance, etc.) as if this were an actual vehicle accident where you are at fault (at least in California). Source: Drove school buses my first year in college in a large California city. Quit after another driver had a real accident and the district left her to defend herself against parents' lawsuits. Almost all drivers were college students because the state provided a subsidy to the school districts to hire us. Our route making process was (this was years ago) Thomas guide map book -> left right sheet (a sheet with a column of just L/R streetname) for the route -> drive route to time/test and make corrections. One complication is that the start and end times of the route are fixed, so you must make the route work with those while accounting for traffic.

gnu8 3y ago

You believe the traveling salesman problem for 100k students at 165 schools can be figured out with pencil and paper in a few hours?

pavel_lishin 3y ago
It's not a problem of getting 100k students to 165 schools. It's 165 separate problems, of getting (presumably, on average) 1k students to 1 school. That's a much more tractable problem, and if you have a large-scale map and a lot of push-pins, you can probably intuit 90% of the solution. Yes, the person you're replying to is probably under-estimating the problem, but this isn't a problem you have to rent quantum computing time to solve.
- purpleflame1257 3y ago
  Additionally, you don't actually need the optimum, you just need a "good enough" method so that kids aren't on the bus till 10
- JumpCrisscross 3y ago
  > It's 165 separate problems, of getting (presumably, on average) 1k students to 1 school If you have 165 * (1,000 / capacity) busses and drivers, sure.
  - pavel_lishin 3y ago
    That's a good point, I hadn't considered that! A good lesson for me, and maybe others, to not confidently offer opinions on areas where we're not even close to being subject matter experts.
- WorldMaker 3y ago
  The problem is that the district in question has for a lot of reasons, many with good intentions, built this as a 100k separate problems. They wanted to abstract student assignment outside of geography and for the most part they have. They've lost the ability to just "push pin" the map because any way you slice it, it's now too much of a tangled spiderweb, because they don't want the map to make sense. They intentionally wanted to break map clusters and patterns. They can't rely on the map because they've built it so that they can't rely on the map. They've obviously built something that they can't scale easily, and it is a travelling salesman nightmare problem in so many of the harder ways. (They did this to themselves of course, but suggesting that they just start over with push pins on a large enough scale map ignores why they are in the problem in the first place. The map doesn't make sense. There's no way to intuit a 90% solution because there aren't patterns on the map. They didn't want patterns on the map.)
glonq 3y ago
I used to work in the transit industry. I can describe the problem and the solution with enough paper and a couple hours. But to actually perform route scheduling, we used a whole bunch of iron @ AWS.
mrguyorama 3y ago
The traveling salesmen problem is about the perfect solution, not a good one. The entire point of the traveling salesman problem in teaching is to show a problem where the human brain is really good at workable solutions, but computers cannot find solutions without cheating or checking EVERY solution. American schools have been designing bus routes well before they had computers to help them do so. Maybe it requires hiring a few more bus drivers.

sillystuff 3y ago

> Bus drivers don’t need to “practice routes”. Even if they get a turn wrong, the worst is a few minute delay. A long vehicle that does not bend in the middle has quite a few worse outcomes than a short delay. Fill it with children, and those worse outcomes can include tragedies. There are roads where the crest of the hill can result in the middle of the bus bottoming out, and the wheels at each end hanging in the air. There are roads where a downhill section levels out at such a sharp angle that the nose of the bus will embed in the pavement if you do not cut all the way across the road (into oncoming traffic; which you will NOT want to do with children on board) to reduce the angle. Some turns are simply impossible because the swing of the tail-end of the bus would e.g., take out the signage along the edge of the road. Maps will show a road that appears to continue through, but it is actually discontinuous due to e.g., a canyon; Turning around / backing a 65-80 passenger vehicle is no fun. Worse when full of screaming kids. I had a route where I had no choice but to back a bus down a four block long alley where the mirrors literally scraped on both sides in places due to a doorstep stop for a disabled child, but you always want to avoid live "skills tests". Why on earth would you intentionally add avoidable risk? All this while keeping in mind you need to maintain full awareness/control of the kids at all moments. Because, if you are distracted trying to correct an issue with your route and even something seemingly as minor as one kid stands up and falls, splitting his lip... You get to pull over and radio in to dispatch to call out the state highway patrol for a school bus accident, and wait for the officer to arrive and take the report. And, you get the points on your driving record (affecting insurance, etc.) as if this were an actual vehicle accident where you are at fault (at least in California). Source: Drove school buses my first year in college in a large California city. Quit after another driver had a real accident and the district left her to defend herself against parents' lawsuits. Almost all drivers were college students because the state provided a subsidy to the school districts to hire us. Our route making process was (this was years ago) Thomas guide map book -> left right sheet (a sheet with a column of just L/R streetname) for the route -> drive route to time/test and make corrections. One complication is that the start and end times of the route are fixed, so you must make the route work with those while accounting for traffic.