minus-squareBierLiebHabertoNo Stupid Questions@lemmy.world•Traveling Salesman is NP-Hard, yet Uber Eats delivery route optimization algorithms existlinkfedilinkarrow-up1·3 months agoTraveling salesmen being NP-hard only means that you cannot prove you have the optimal solution without checking all possible solutions. Uber doesnt care if the solution is optimal it only wants a solution that’s good enough. It does this using heuristics, checkout https://medium.com/opex-analytics/heuristic-algorithms-for-the-traveling-salesman-problem-6a53d8143584 as an example linkfedilink
Traveling salesmen being NP-hard only means that you cannot prove you have the optimal solution without checking all possible solutions. Uber doesnt care if the solution is optimal it only wants a solution that’s good enough. It does this using heuristics, checkout https://medium.com/opex-analytics/heuristic-algorithms-for-the-traveling-salesman-problem-6a53d8143584 as an example