Sort multiple trip plans

[novalis]

Having multiple trip plans is great. Next step is to sort these things based on going from the 'best' trip option to the worst. (Currently, the sorting seems random, and also non-deterministic...resubmit the same trip a few times and see if the #1 option stays the same).

So what are the qualities determining a best trip?.

1. Depart/Arrive time best matching customer's specified time.
2. Least amount of walking.
3. Fewest transfers.
4. Shortest/Fastest trip.

To make things simple, we could just sort based on one of the fields above (say depart time). But a better approach would be to examine each itinerary option on multiple fields (like transfers, shortest trip, etc...) and weight these (and other?) criteria. And use a weighting to determine the best trip, which will appear as the first option, etc...

Further, we probably want to throw out low-quality trip options. And if all our trips seem like crap maybe tweak the parameters and resubmit the trip, looking to for improvements. Further, if the planner only returns a single (transit) option, we could tweak the parameters to find the next / previous trip.

[novalis]

Hi.

I have code to order the trip alternatives by Arrive. (Attached a patch) The solution I've done is to use a TreeSet instead of a HashSet to store the alternatives, and use a Comparator to compare alternatives. If other kind of sorting is needed, we only need to change comparator.

BTW, the patch also corrects a problem about "banned" routes, banning only one at a time (not both routes if the alternative has 1 or more transbords.

--fpenarru

[novalis]

Sorry, forget about TreeSet. I use Collections.sort(). The patch should be applied to opentripplanner-routing. PathComparator added and ContractionPathServiceImpl.plan() modified.

Hope it will be useful.

Cheers.

Fran.

--fpenarru

[novalis]

What do you think of the attached patch? I think your patch misunderstood the loop on line 161 (pre-patch). The idea of that loop is that we create new set of options for each route used in the path. We avoid duplicate bans by hashing the options, which includes the hash of the set of banned routes. Your patch will only create one for the first route, as I understand it.

Also, I have returned the bus-only route, since (a) some people strongly prefer buses (especially in New York, where all buses have wheelchair lifts but only 20% of train stations do), and (b) it's what Google does. If you would like, you can make this configurable.

--novalis

[novalis]

(I applied my patch)

--novalis

[novalis]

Hi David.

I'm not sure about banning all buses every time. For example, suppose your first solution is Bus A + Bus B, and next optimal solution will be A+C. If you bann both routes, you will miss this alternative.

Anyway, I'm not sure if my solution of banning only the first route is the best. In my tests, I had better solutions, but I agree it will be some cases where it can miss some good solutions in third route alternative.

About offering always a bus solution, it's ok for me, but in my tests, there were 2 equal alternative routes, and I thought the problem was related to adding 2 identical traverse options to the queue.

--fpenarru

[novalis]

If my code is correct (and please tell me if it is not), we actually create a set of options with each route banned separately. So, if the first route is A+B, we'll create an option with A banned, and a second option with B banned. In some cases, these will end up with the same route -- if the second choice is D+E, for instance, banning A and banning B will produce the same route. Identical routes should be avoided because we check if our list contains them before re-adding them, but apparently there are some bugs in this (see #329).

--novalis