3 ms·

>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 clie

>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.

themitigating 3y ago
Maybe by AI they mean it uses big data as well like historical traffic to more accurately set the weights of the vertices.
- ke88y 3y ago
  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".
  - ComodoHacker 3y ago
    So just engineering? Isn't that predicted effect of AI adoption? :)
Sai_ 3y ago
https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem Traveling Salesman is NP-Hard. Don't think it is solvable with current technology.
- jfrd 3y ago
  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!
  - Sai_ 3y ago
    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.
    - objektif 3y ago
      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.
      - pintxo 3y ago
        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.
      - Sai_ 3y ago
        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.
- domoritz 3y ago
lmpdev 3y ago
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
- tevon 3y ago
  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.
mattmcknight 3y ago
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?
- ramesh31 3y ago
  >This seems to imply most rides are scheduled pickups? Did you read the article? This is their entire business model right now.
- TheSmiddy 3y ago
  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.
cortesoft 3y ago
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.
- ramesh31 3y ago
  >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.
  - jaza 3y ago
    What is this "deterministic combinatorial problem" and "no need for inductive output" gibberish of which you speak? AI! AI! AI!

themitigating 3y ago

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

ke88y 3y ago
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".
- ComodoHacker 3y ago
  So just engineering? Isn't that predicted effect of AI adoption? :)

Sai_ 3y ago

https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem Traveling Salesman is NP-Hard. Don't think it is solvable with current technology.

jfrd 3y ago
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!
- Sai_ 3y ago
  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.
  - objektif 3y ago
    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.
    - pintxo 3y ago
      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.
    - Sai_ 3y ago
      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.
domoritz 3y ago

lmpdev 3y ago

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

tevon 3y ago
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.

mattmcknight 3y ago

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?

ramesh31 3y ago
>This seems to imply most rides are scheduled pickups? Did you read the article? This is their entire business model right now.
TheSmiddy 3y ago
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.

cortesoft 3y ago

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.

ramesh31 3y ago
>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.
- jaza 3y ago
  What is this "deterministic combinatorial problem" and "no need for inductive output" gibberish of which you speak? AI! AI! AI!