Timeline for Combinatorial Optimization: Shortest distance given sets of drivers and riders
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2019 at 0:01 | vote | accept | Ricardo Jesus | ||
| Mar 19, 2019 at 0:01 | comment | added | Ricardo Jesus | Thank you for the help! I've never looked into ILPs before and I was misunderstanding you at first, but I get it now! | |
| Mar 16, 2019 at 0:42 | comment | added | D.W.♦ | Zero-or-one is because you either select a participant or don't (you can't put half a rider in a car). Yes, each $x_S=1$ corresponds to one car; each car drives separately. | |
| Mar 16, 2019 at 0:42 | comment | added | D.W.♦ | @RicardoJesus, no, you'd use the ILP solver once. You'd have one variable per possible combination. There are many (overlapping) combinations: e.g., with 10 drivers and 20 riders, there would be something like $10 \times {20 \choose 5}$ combinations. You'd figure out all possible combinations in advance, generate one variable per, create a giant linear system, and feed it all to the ILP solver. The ILP solver would solve the whole thing in one go. | |
| Mar 16, 2019 at 0:38 | comment | added | Ricardo Jesus | Thank you! I have some questions if that's ok with you. Your formulation goes from car to car, and using their available seats it tries to find all combinations of passengers and calculate the shortest path for each combination, correct? I guess I would need to use this solver twice. 1 to group riders with drivers, 2 to group clusters between themselves? And sometimes the combined shortest dist is clusters traveling separately, That's where the zero-or-one variable comes in? The chosen S for each car would be one combination without the other cars, meaning they would travel separately. | |
| Mar 15, 2019 at 23:46 | history | answered | D.W.♦ | CC BY-SA 4.0 |