Hacker News Reader

Comment by ramesh31 | Hacker News Reader

>Scheduling trips is a tricky calculation, and it all comes down to routing — you want drivers to spend as much of their shift as they can actually driving clients around, but you have to leave enough time in-between trips so the driver isn’t late for their next client. So far, the only way to do this successfully has been by using a team of human dispatchers, though the co-op is working on an automated solution using artificial intelligence.

I worry about this. Travelling salesman is a solved problem. Throwing "AI" into the mix sounds like someone was sold a bridge.

View on HN

Travelling salesman is a largely solved problem, but I'd say this problem is larger.

As soon as humans and the real world are involved, seemingly contradictory criteria need to be met.

Algorithms like A* search may not be able to capture these criteria robustly enough.

Example: a driver may be assigned the optimal route, but because they are human will not want to sit and wait for 15 minutes between several of their rides

A* is great for path finding but it's not a global panacea for all subproblems related to ridesharing

This is true, however these known criteria can be added in, thats the whole point of the heuristic in A*.

Likely one of Uber/Lyfts greatest strengths in their algos is discovering the E[X] of those heuristics. This could probably be captured from the human dispatchers as well.

This is a different problem, because the TSP is about reaching every point in the shortest distance, but in this case you can't just hit every point in any order you want. Each rider is going to want a ride at different times, and each rider is going to make their request at different times, and multiple drivers are going to be available at different times.

You are optimizing for least amount of time riders have to wait, not just for shortest distance driven.

>You are optimizing for least amount of time riders have to wait, not just for shortest distance driven.

Point being though that it's fundamentally a deterministic combinatorial problem. And they have the added benefit in this case of only worrying about prescheduled trips that need to be calculated the day before. It's not trivial, but it's an algorithmic problem that has no need for inductive output.

What is this "deterministic combinatorial problem" and "no need for inductive output" gibberish of which you speak?

AI! AI! AI!

I don't think having "drivers spend as much of their shift as they can driving clients" is the best objective function. It seems like you should want to get customers to their destinations as quickly as possible, not have cars driving around slowly to maximize client drive time.

"You have to leave enough time in-between trips so the driver isn’t late for their next client." also seems bizarre, as you should just be routing the minimal time cost set of vehicles to those awaiting rides. This seems to imply most rides are scheduled pickups?

>This seems to imply most rides are scheduled pickups?

Did you read the article? This is their entire business model right now.

It's a perfectly fine objective if you trust your drivers to meet a minimum standard of a good job. It won't work in an adversarial system like Uber where drivers are just numbers but if the drivers are also invested in the success of the platform it's fine.

Given that drivers are driving the shorted distance/time route at the speed limit, treating customers with respect, arriving on time to scheduled pickups, etc. The next thing to focus on is scheduling/filling orders such that drive time is maximised.

Maybe by AI they mean it uses big data as well like historical traffic to more accurately set the weights of the vertices.

Possibly, but today EVERY nontrivial piece of software is "AI". It's the new "synergy" for dipshits spouting nonsense.

FYI: in MBA speak, "AI" is now anything that can't be hacked together on top of airtable, outsourced, or done by someone with a GED and six months of bootcamping. If you need someone who isn't perceived as interchangeable cog labor to help build the thing then it's now called AI. Was just in a meeting where a major component for an optimizing compiler was called "the AI".

So just engineering? Isn't that predicted effect of AI adoption? :)

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Traveling Salesman is NP-Hard. Don't think it is solvable with current technology.

Surprisingly you can solve massive TSPs using heuristics. The solutions are not guaranteed to be optimal, but they can get very close to optimal without a crazy amount of computing power.

The Concorde TSP solver can apparently solve instances with 85.6k cities to optimality. Pretty amazing!

Ride share companies are surviving so it’s clear that some good enough solutions do exist.

There’s a difference between the algorithms ride shares have to use and the heuristic based solution for 85.6k cities.

The graph for ride shares is constantly changing as passengers request rides from random starting points to random destinations.

This version of TSP is much harder to solve.

Sorry but how is ride share problem a TSP problem? Rides are assigned one at a time and I do not think they would take into account future rides while doing the assignment optimization.

Not my industry, but imagining that they accept rides within a 48 hour windows from now. You’d quickly get something somewhat similar to a TSP. But given that you have lots of additional constraints (people tend to have a clear idea when they want to get from A to B) compared to the classical TSP, it might actually be easier to solve. As those constraints limit the paths you must evaluate.

True. I got derailed because the person I replied to and the replies to my comment used to TSP formulation to discuss this.

You’re right that the problem space is simply matching available drivers to riders.

Only in the worst case and large N. For practical problems, it’s solvable for tens of thousands of nodes.

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.

Being NP-hard doesn't mean it's unsolvable at all. It means it's not solvable quickly. Google maps does this millions of times per day... the number of points on the trip are few enough that you can brute force it perfectly or use a heuristic to solve it faster but less optimally. Very solvable just not optimizable algorithmicly.

My answer that you are replying to ends with “…with current technology” which contains what you said.

The technology doesn't matter unless you're going to make a far-fetched quantum computer argument. This is pure math.

Reply on news.ycombinator.com