5 ms·

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

by gnu8 3y ago

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.

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

by 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.