Timeline for Combinatorial Optimization: Shortest distance given sets of drivers and riders
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2019 at 0:01 | vote | accept | Ricardo Jesus | ||
| Mar 16, 2019 at 0:17 | comment | added | Ricardo Jesus | Euclidean distances for a non-directed graph. Only one edge between nodes. For proper traveling distances, it would need to be a directed graph. I found that distance using roads aren't always the same going from A to B and from B to A (one-way streets, road-work, etc.) Euclidean distances seem like a good option for me (?). | |
| Mar 16, 2019 at 0:07 | history | edited | Ricardo Jesus | CC BY-SA 4.0 |
Added a possible solution i thought of as an "edit"
|
| Mar 15, 2019 at 23:46 | answer | added | D.W.♦ | timeline score: 1 | |
| Mar 15, 2019 at 21:32 | comment | added | Optidad | okay and what about distance ? Is it euclidian distance ? | |
| Mar 15, 2019 at 15:10 | comment | added | Ricardo Jesus | @Vince Participant numbers in each computation will be fairly small. Although I'm studying a general solution, given the intended scope I don't expect participant numbers (drivers and riders combined) to exceed double-digits per calculation often, if ever. The problem does seem to mirror a general TSP, but the TSP has some clear rules that my problem doesn't follow (listed in the proposed COVRP solution). I don't know how I can adapt it. I am interested in heuristic solutions. As a matter of fact, I've implemented one solution based around Voronoi Cells, but the results weren't great. | |
| Mar 15, 2019 at 10:31 | comment | added | Optidad | This problem is clearly NP complete as a global extension of TSP. Can both the number of drivers and riders be very large ? Are you interested on a heuristic solution ? | |
| Mar 15, 2019 at 6:53 | history | edited | Anton Trunov |
remove irrelevant tag
|
|
| Mar 14, 2019 at 21:42 | history | asked | Ricardo Jesus | CC BY-SA 4.0 |