looking for a design strategy - road trip planner

['makerphile]

What would be a good database design strategy for something like a road trip planner? One starts with data in a LEG OF TRIP table whose fields are: START LOCATION, FINISH LOCATION, DISTANCE BETWEEN START AND FINISH. When a user inputs an overall start location, an overall finish location, a minimum and maximum number of trip legs, and a minimum and maximum distance of travel, the database would display a list of possible acceptable itineraries connecting the overall start and finish locations, perhaps sorted based on some user-specified parameters such as by number of trip legs. Let us suppose that the number of trip legs and combinations thereof are too large to simply make a table of all possible itineraries between all possible combinations of start and finish locations. Thanks for any suggestions, I'm at a loss.

Edited October 29, 2008 by Guest

[Fitch]

This sounds similar to the Travelling salesman problem which is fairly easy to describe, but notoriously difficult to solve.

['makerphile]

I hope more tractable. This is like an airline flight search, where the number of stops/changes and overall cost and/or time of travel can sharply limit the itineraries considered. It's not yet an optimization problem (though one could sort by overall distance, etc.) and doesn't require traveling a path through all locations. Hope that shrinks the problem enough to make a difference.

Edited November 6, 2008 by Guest

[comment]

Just thinking out loud:

Find all legs whose origin is the given origin. If any one of these has the given destination, then you're done. If not, go to all legs whose origin is one of destinations of the current found set. If one or more of these has the given destination, stop. Else continue until you find the given destination or exceed the limit.

Another way could be to calculate all possible destinations of a leg's origin, using a cascading calculation in a recursive relationship. Then you could simply (albeit slowly) do a find in this field. However, sorting/filtering records based on a criteria that is NOT an attribute of a record is very problematic.

['makerphile]

Thanks for your thoughts. I had been hoping for something like a portal to an itineraries table that would show ALL the acceptable routes between specified termini (e.g. each field representing a node on the route). Your first approach suggests to me a script that systematically works its way through all the possible routes branching out from the origin until limits are met or exceeded and further branching is thus cut off. Doing this kind of thing in C is easy, using "for" loops. Would scripting be the right approach here? I admit I have not done scripting with much ambition.

The second suggestion sounds appealing. For other projects I've tried something that I take to be a cascading calculation in a recursive relationship and it didn't work (I got question marks where I was expecting other data). Maybe I don't understand what is a cascading calculation in a recursive relationship or how to set them up properly. What would that involve? Is there a convenient sample database I could look at?

[Vaughan]

I ended up spending a couple of hours reading up on the traveling salesman problem... let me know where to send the invoice, Fitch.

This is another one of those apparently "simple" problems that end up being awfully complicated to solve. It's not a matter of working out how to do it in FMP or any other technology, it's because the problem becomes too big to calculate.

If the best mathematical minds on the planet spend years working on a problem like this, and decide that it's "hard" then I doubt that a couple of "for" loops are going to lead to a breakthrough.

Custom functions in FMP are limited to 10,000 recursions, that may be the cause of the ?s.

[comment]

I am not at all convinced that this falls in the category of the traveling salesman problem. There are no constraints here regarding interim stops - the only requirements are the overall origin and destination points. This seems much more like the problem of the shortest path:

http://en.wikipedia.org/wiki/Shortest_path_problem

[comment]

I had been hoping for something like a portal to an itineraries table

What itineraries table? There is no itineraries table, according to your description. For each given pair of origin and destination, the system needs to start from scratch, looking for possible combinations of legs that lead from origin to destination. Only then can the comparison begin.

You could create records for the "candidate itineraries" (if the process is scripted) and view them in a portal. But you cannot use fields to represent the legs of the journey, because the number of legs is not known beforehand.

You can see an example of a cascading calculation here:

http://fmforums.com/forum/showtopic.php?tid/198869/

However, if all the points on your web are somehow interconnected, then the calculation will return a very similar result for all of them - only the order of listing will be different.

[Fitch]

Shortest path does seem like a more apt problem type, Michael. I started playing around with your "thinking out loud" idea and it seems workable to me.

@makerphile, attached is a file that you might get started with. It needs work but you can at least get the idea of how the script might go. I pasted Michael's idea into the comments of the script to use as a framework. It's often helpful to build a script up from comments that describe the logic.

shortestPath.fp7.zip