4 ms·

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

superpermutat0r 7y ago
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.
- JoeAltmaier 7y ago
  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.
_dps 7y ago
I've worked recently in this exact field (known in OR as "pickup dropoff problem with time windows" or PDPTW). As you say, all these modifications are completely standard (especially ones that minimize the worst-case "suffering" of the most-affected passenger).
- superpermutat0r 7y ago
  Saying these modifications are standard does not talk about their complexity. Here's [0] a paper where they analyze the mistake of the feasibility check that experts in the field failed to do properly. Here's [1] a paper aggregating all the timing problems that arise and their algorithmic complexity. Some of the timing problems, including the constraint of limiting the time of the passenger in the bus had O(n^2) or O(n^3) feasibility checks. That's slow. Especially slow if combined with integer linear programming or branch and cut algorithms. If your system instead minimizes the riding time by adding a cost function to a constraint, making it soft, in most cases the cost function is so ill defined that the solution no longer does what you want, can hardly minimize all the constraint to a normal solution, and you get a huge mess. There's no state of the art solution that models these constraints as soft ones. These problems being standard does not mean that they are simple. 0: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.927.5694&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.927... 1: https://w1.cirrelt.ca/~vidalt/papers/Timing-Problems-Final.pdf https://w1.cirrelt.ca/~vidalt/papers/Timing-Problems-Final.p...

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.

JoeAltmaier 7y ago
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.

_dps 7y ago

I've worked recently in this exact field (known in OR as "pickup dropoff problem with time windows" or PDPTW). As you say, all these modifications are completely standard (especially ones that minimize the worst-case "suffering" of the most-affected passenger).

superpermutat0r 7y ago
Saying these modifications are standard does not talk about their complexity. Here's [0] a paper where they analyze the mistake of the feasibility check that experts in the field failed to do properly. Here's [1] a paper aggregating all the timing problems that arise and their algorithmic complexity. Some of the timing problems, including the constraint of limiting the time of the passenger in the bus had O(n^2) or O(n^3) feasibility checks. That's slow. Especially slow if combined with integer linear programming or branch and cut algorithms. If your system instead minimizes the riding time by adding a cost function to a constraint, making it soft, in most cases the cost function is so ill defined that the solution no longer does what you want, can hardly minimize all the constraint to a normal solution, and you get a huge mess. There's no state of the art solution that models these constraints as soft ones. These problems being standard does not mean that they are simple. 0: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.927.5694&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.927... 1: https://w1.cirrelt.ca/~vidalt/papers/Timing-Problems-Final.pdf https://w1.cirrelt.ca/~vidalt/papers/Timing-Problems-Final.p...