Repository navigation
Plans are not deterministic #3580
Description
Are requests for the same parameters not meant to be deterministic? I expected deterministic results but I observe something different. Before I dive in, I thought I'd ask here.
Expected behavior
I query the same plans from the HTTP API several times and get the same itineraries as results every time.
Observed behavior
I query the same plans from the HTTP API several times and sometimes get slightly different itineraries (other leg(s) or even additional/missing itineraries) as results.
Version of OTP used (exact commit hash or JAR name)
Version: 2.0.0
Commit: a645760
Branch: v2.0.0
Build: 2020-11-27T13:02:08+0000
Data sets in use (links to GTFS and OSM PBF files)
Private :\
Command line used to start OTP
java -Xmx8G -jar /mnt/sexyssd/otp/otp-2.0.0-shaded.jar --build --serve
Request parameters
I loop over many origins and destinations, referenced by stopIds:
http://localhost:8080/otp/routers/default/plan?
fromPlace={origin}
&toPlace={destination}
&time=00%3A00
&date=05-01-2021
&mode=TRANSIT%2CWALK
&maxWalkDistance=1
&arriveBy=false
&searchWindow=86400
&numOfItineraries=99999
&keepNumOfItineraries=99999
&showIntermediateStops=true
Router config and graph build config JSON
Using default configuration.
Activity
slvlirnoff commentedon Aug 11, 2021
I've been experiencing that as well, the 'middle/end' part of the trip would change while usually keeping similar departure and arrival times. One itinerary more frequent than the other, but from time to time a different one would be selected.
I couldn't reproduce the case lately but I'd say more due to source data changes, the overall shape of the trip was 'bus' - 'train' (x1/x2) - 'bus', the 'non deterministic' part was on the last train - bus or train - destination part. Changing the arrival coordinates would stop the issue even a few dozen meters away.
flaktack commentedon Sep 9, 2021
We noticed similar issues in our deployment, which may or may not be caused by the same issue: in places where there could be multiple identical alternatives, than the trip/route in the itinerary would vary with each request.
This is caused by the alternatives having the same costs and times while planning, and so which one is stored in the
ParetoSetwhile calculating is non-deterministic. The trips depart from the same stop at the same minute and take the same amount of time to arrive at the destinationUsing the same parameters multiple options are returned:
If the
ParetoSetis modified to allow mutually dominating states even if equivalent (link), then all options are returned:The ordering of itineraries is also non-deterministic if all the values match (
transfers,departure,arrival,generalizedCost), which can also cause the ordering to change between requests:OpenTripPlanner/src/main/java/org/opentripplanner/routing/algorithm/filterchain/filters/OtpDefaultSortOrder.java
Lines 55 to 60 in 1b3d841