Wikipedia:Reference desk/Archives/Computing/2016 June 15

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 15

route optimization combining Google Maps and Uber

For my project that I hope to use as a portfolio as part of my admissions to a boot camp, I am trying to write an app that include a route optimization feature that's always been on my wishlist. Now, right now I'm working on the more boring aspects of basic app development, but at my heart I'm trying to decide if my algorithm is possible at all.

Concept: As a resident of New York City, I often note there are many parts of desired trips where the subway for that route is much faster and efficient then a car along the route, especially for express trains (the A, D, E, F, Q, 4, 5 etc.) However, transfer times and hailing times for the Uber have to be factored in as well. Thus we could have two types of commuters: customers who mainly want to save time, but will trade a little time for money, as well as customers who want to save money, but willing to trade a little money for more time saved. It is also possible to save both, assuming transfer times work out, and this app should detect that. (Surges and UberPool can be dealt with at a later stage of development.)

• Imagine customer A, who sets a budget of $20 for her trip (has an Unlimited Ride metro card), and but also wishes to maintain gains on time. However, customer A wants to stay below $20 (a little over is okay, this tolerance could be entered) and is willing to take as much public transit as possible in order for her Uber ride to cost roughly $20. She's coming from bars in the Village and doesn't want to spend 2.5 hours using late night (low-frequency) subway service getting home to Flushing, Queens, but doesn't want to spend a fortune either.

• Imagine customer B, who sets a time budget of 45 minutes for his trip, and would rather not spend that much on an Uber ride especially if the Uber ride is going to take him through really traffic-jammed areas of the city, but will spend money on a ride to ensure that his ride stays under 45 minutes. (He's going to an important meeting.)

• Another optimization feature would be to set a "time for money" or "money for time" conversion rate, i.e. "I am willing to spend $5 to save 15 minutes" or "I am willing to spend up to 20 minutes more to save $25

So my questions are: is such an optimization practical to implement? Is this an NP complete problem? (It sounds a little like the Knapsack problem.) I spoke to a CS major on the Megabus who didn't seem convinced it could be implemented easily. Would Uber be really mad if I was using their API frequently to try to estimate times for trips at various branch points of calculation without actually hailing a ride? To me it seems possible at least for an NYC implementation given that a) there a fixed amount of subway stops in NYC b) there are natural chokepoints in and out of the city (bridges, tunnels) c) the app could have a "common sense" feature that could be turned on so it would ignore jammed areas or lines reporting construction or delays, and also focus on expressways and express train routes as branch points for optimization. Yanping Nora Soong (talk) 12:03, 15 June 2016 (UTC)

It is not an NP complete problem to get *A* solution that meets your criteria. It is an NP complete problem to get the absolute optimal solution. Another way to word it: Can I find a path through a weighted network that is below a cutoff? Once I find one, I'm done. So, I use a greedy algorithm to brute force it. I know that I will likely miss complicated paths that are the absolute best, but I will get one that works. 199.15.144.250 (talk) 15:05, 15 June 2016 (UTC)

Updating the previous comment... If you can represent all options as a weighted graph, you can use Dijkstra's algorithm to quickly find an optimal solution. So, the trick is in the representation of the problem. If it is represented as "how do I pack all these options into a confined space", it is much harder to solve. If it is represented as "I have a network of locations with a weight to get from one to another and I want the shortest/cheapest/quickest route from one location to another", it is easy to solve. 199.15.144.250 (talk) 17:11, 15 June 2016 (UTC)

"Would Uber be really mad...?" MAYBE. I wouldn't like that, but I also don't like Uber, so maybe they'll like it. My point is we can't answer this. I can point you to their TOS for the API: [1], but interpreting that for your specific use case would constitute legal advice. Maybe call them if you want clarification. Seems to me you'd be aggregating Uber data with the competing subway, but maybe not. SemanticMantis (talk) 14:00, 16 June 2016 (UTC)

Tweeting @UberDevelopers may be a good idea. (((The Quixotic Potato))) (talk) 16:43, 16 June 2016 (UTC)

Yanping Nora Soong, will you be publishing that app for download? I loved that 'time to money' idea.--Aryan ( है?) 06:07, 20 June 2016 (UTC)