Hacker News new | ask | show | jobs
by xenity7 3402 days ago
I don't think this problem is as hard as you think it is in practical terms. N is going to be relatively small given basic constraints (the number of drivers and requests that could feasibly be matched is geographically limited). The search space for a request is limited to a few hundred drivers at most, competing with what is likely an even smaller pool of requests, making even extremely inefficient brute force approaches feasible.
1 comments
projectorlochsa 3402 days ago
Yeah, problem is so simple that they have job listings for AI research engineers that should have a little bit of experience in TensorFlow, Theano, Caffe or Torch (obviously some lovely deep learning on who knows what). About a year ago they were searching for PhDs and asked for experience with combinatorial algorithms, especially travelling salesman and vehicle routing problems.
link
debatem1 3402 days ago
It's worth pointing out that Uber had their service working more than a year ago, so while the folks you mention might help take Uber to the N+1th order of optimization they are clearly not necessary to reach the Nth.

I suspect this is what the GP is getting at: reaching the levels of optimization on this problem which are required to launch the service is comparatively easy. Going from there to optimality is extremely hard, but may not be necessary from a business or end user point of view.

link
projectorlochsa 3401 days ago
N that the GP is talking about is number of vehicles and number of requests.

Yes, service can obviously work with subpar algorithms but to really succeed at pricing it as cheaply as possible it requires practically an ability to successfully predict the whole day and then optimizing on the NP-hard problem of that whole day. Maybe sampling a million day variants while routing to make a single decision (which driver should pickup the next request).

Of course brute force greedy algorithms work but they can be, on a hundred vehicle scale, 30% away from the optimum cost.

I've been downvoted to oblivion so I cannot longer keep participating in this discussion (HN will shadowban me).

link