Re:A driver-owned alternative to Uber and Lyft is on the ver...
by domoritz on Monday July 17, 2023 @10:48PM
(#36767209)
Only in the worst case and large N. For practical problems, it’s solvable for tens of thousands of nodes.
[ Parent
| on HN ]
Re:A driver-owned alternative to Uber and Lyft is on the ver...
by Sai_ on Monday July 17, 2023 @11:06PM
(#36767322)
A cab service with unknown, frequently updated nodes where edge weights - driving distance from last drop to next pickup- can vary, would qualify as pretty bad version of TSP.
You can come up with a good enough solution but it’s not “solved”.
This “good enough” solution starts to break down whenever there is a huge concentration of drivers in a location. If this weren’t the case, ride shares wouldn’t have had to add a cancellation fee and hidden destinations from drivers.