Possible number of combinations for return travel routes

Question

My math is bad, real bad. So bad I'm struggling to even phrase this question, but here goes.

The situation is train travel and you have four arrays to work with.

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

So let's say you're only interested in one way routes and you need to figure out how many combinations of route there are. That would be (i think)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

But how would I go about figuring out how many combinations there are if I want a return trip?

UPDATE::

or would this work?

possible_routes = ((leaving_stations x arriving_stations) x leaving_dates) x (leaving_dates x returning_dates)

Answer 1

I'm not sure if i understand correctly, but this seems like a typical graph-routing theory problem. You can look at Minimum Path or A* algorithms.

Answer 2

first, A-A routes are wrong things, so:

possible_routes = 
(
  leaving_stations x arriving_stations - 
  (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates

intersection operation is elements that belongs to both arrays

second, when you want 2 way routes, the combinations are:

possible_2way_routes = 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x 
leaving_dates x 
(return_dates that later than leaving dates+route time)

'leaving_dates x (return_dates that later than leaving dates+route time)' are strange thing, so it may be easier to cumpute high estimation - number, that not less than possible_2way_routes in any case. the highest count will be when all returning_dates later than leaving_dates, so:

possible_2way_routes <= 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates x return_dates

oh, I've remembered how to calculate 'return_dates that later than leaving dates+route time'. it's:

for each element of leaving_dates {
sum=sum+return_dates that later than ith leaving date+route time}

there is still problem of 'route time', though...

Answer 3

Well, the answer is it's not totally clear from your array names.

Assuming we have the 4 arrays:

• Leaving Dates
• Return Dates
• Leaving Stations
• Arriving Stations

Then we can do a bit of explaining here. Let's use the notation |x| to represent the cardinality (number of elements) of array [x], so that |Leaving Dates| is the total number of dates that you could leave on.

Then |Leaving Dates| * |Leaving Stations| * |Arriving Stations| would translate to, pick a date to leave on, then pick a station to leave from, then pick a station to arrive at, and do that in all possible ways. So this would seem to be what you're asking for for one-way trips.

Now, practically, I'm going to assume that this is a real world problem, so that let's say we picked to leave from Southampton to Yorkshire on June 20, on the return trip all we are allowed to choose at this point should be the return date (meaning I'm assuming you want to return home).

So the total number of ways that we can plan a round trip would be first plan a one-way trip as above, and then pick a return date, which would be |Leaving Dates| * |Leaving Stations| * |Arriving Stations| * |Return Date|. The first 3 terms pick the one-way trip as above, and the last term picks a return date from all the possible dates. Of course, if we had the option to return to another station other than the one that we left from, then the equation would be (|Leaving Dates| * |Leaving Stations| * |Arriving Stations|) * (|Return Date| * |Leaving Stations|), or if we could even leave from a different Arrival Station than the one that we first arrived at it would become (|Leaving Dates| * |Leaving Stations| * |Arriving Stations|) * (|Return Date| * |Arriving Stations| * |Leaving Stations|).