Page 1 of 1

Best way to create a linear schedule

Posted: Fri Feb 19, 2010 7:21 pm
by jraede
My website is essentially a database of bars and restaurants, and the events happening at them (like happy hours, etc). I'm working on a new feature that will automatically create a bar crawl schedule for the user based on what kind of events/venues they want, how long they want to spend at each place, how long they're willing to travel, etc. So far, that's working great.

My one issue is, say the user wants to make 4 stops. The system does not take into account the linear aspect of the bar crawl, so it may have the first and third stops near each other, with the second stop a mile away. This, obviously, would still be within the parameters that the user specified, but it would make more sense to switch the order of the stops to follow a natural progression of travel.

So, how would you guys go about ensuring that this is the case? I have the longitude and latitude of each place stored in my database, and use a distance function in my MySQL query to only fetch events/venues that are within X distance of the previous one. From all the results returned, one is chosen at random using ORDER BY RAND() LIMIT 1. My query also includes event/venue types, and dates/times that they are open and/or happening, but the only reason why these would be applicable to my question is if I switched two stops around after the queries have all been performed, and the system would potentially tell the user to go to a place before it's open, or after it closes.

I hope all this makes sense. Just looking for some theoretical approaches to accomplishing this, because the way I'm seeing it I'd have to do multiple layers of queries to get everything just right, but I'm sure there is an easier way.

Thanks.

Re: Best way to create a linear schedule

Posted: Fri Feb 19, 2010 7:38 pm
by jraede
A friend and I were discussing this and I thought of something - I could store all of the results for each stop in a separate multi-dimensional array. That way, the times would be intact because they would be part of the initial MySQL queries. From there, I could cycle through all the possibilities and output the first one that's linear. However, this seems like it would take a long time. Thoughts?

Re: Best way to create a linear schedule

Posted: Fri Feb 19, 2010 7:48 pm
by josh
Traveling sales man problem... Or traveling drunk problem haha. NP complete. Let the user plan their own route (or at least change the one that gets generated). See google maps for an example.

Re: Best way to create a linear schedule

Posted: Sat Feb 20, 2010 12:11 pm
by jraede
I mean, that's what I'll have to do in case I can't figure this out. But it would be great if I can plan it for them. Does anyone have other ideas? Or thoughts on my double loop idea? (loop through the database to get matching events/venues with the correct times, save them in a multidimensional array for each stop, and then loop through each possible path to get the one that is most linear)

Re: Best way to create a linear schedule

Posted: Sat Feb 20, 2010 12:45 pm
by Eran
There are good heuristics to solve this problem which may not necessarily yield the optimal solution but at-least one that is pretty close (could still be the best route). The nearest neighbor is such a solution - http://en.wikipedia.org/wiki/Nearest_ne ... _algorithm
It's relatively simple to implement - start from a point and simply go to the nearest point to it that hasn't been visited yet, until all points are visited.

Re: Best way to create a linear schedule

Posted: Sat Feb 20, 2010 1:32 pm
by jraede
That's good to know, I kind of thought of something like that in my head but it's nice to see it written out and explained. I also had no idea that this TSP was so universal. Pretty interesting stuff.

So, the nearest neighbor algorithm seems pretty simple to implement, but then I run into the problem of always having the same schedule if the user chooses the same parameters and the same first stop is chosen by the system. IE, if the same parameters are passed to my query, and BarX is chosen to be the first stop at random by the system, it will always return the same schedule because the locations are static. Ideally, this system would be somewhat random, so the user could click "regenerate" and would get a different schedule, even if the system chooses the same first stop.

I think to make it a bit less static, I'm going to try the nearest neighbor algorithm in my query, but get, say, the top 5 results. Then I'll choose one at random, and repeat. Any other thoughts/ideas would be great, however.

Thanks for all the help so far.

Re: Best way to create a linear schedule

Posted: Sat Feb 20, 2010 5:42 pm
by josh
Nearest neighbor might yield a wacky route that crosses itself a LOT. Google "traveling salesman"

Nearest neighbor aims to minimize distance from the current point to the next (but by doing that it might put you 100miles away from your 3rd point).

Some of the TSP algos "look ahead" and yield a much better route.

Re: Best way to create a linear schedule

Posted: Thu Feb 25, 2010 6:56 pm
by jraede
Version 0.1 of this feature is up and running, for anyone who is interested. You can check it out here. I'm in the middle of implementing a semi random nearest neighbor algorithm, as well as a jQuery-enabled sort function to change the order of the stops. I figure this would be easier than developing some crazy algorithm to put them all in a realistic path.

Re: Best way to create a linear schedule

Posted: Fri Feb 26, 2010 1:54 am
by josh
"When do you want to go out?

How many stops do you want to make? "

Should be only 2 required options^

How do I put in my location though? I don't get it. It's sending me to "maria's kitchen" in LA cali

Re: Best way to create a linear schedule

Posted: Fri Feb 26, 2010 10:48 am
by jraede
Sorry, should have clarified. The site only serves Los Angeles for now. Also, the distance, time, and types help to narrow the results for the auto generation.

EDIT

Missed that you said "required". I agree, I'll make the other ones optional.