Bug: Non-deterministic solution order in RaptorRouter when two solutions have the same arrival time

[munterfi]

How to reproduce this issue?

Adjust route 1 to have the same arrival time at C1 as route 2 at C in the ch.naviqore.service.gtfs.raptor.GtfsRaptorTestSchedule, then rerun the test cases in ch.naviqore.service.gtfs.raptor.routing.RoutingQueryFacadeIT:

        // Route 1 goes from A, B1, C1
        builder.addRoute("R1", "agency", "R1", "R1", RouteType.parse(1));
        builder.addTrip("T1", "R1", "always", "C1");
        builder.addStopTime("T1", "A", new ServiceDayTime(60), new ServiceDayTime(120));
        builder.addStopTime("T1", "B1", new ServiceDayTime(180), new ServiceDayTime(240));
        builder.addStopTime("T1", "C1", new ServiceDayTime(301), new ServiceDayTime(360));
        // TODO: Non-deterministic behavior; what happens when two solution are exactly the same?
        //  Change arrival time above to 300 to observe this.

        // Route 2 goes from A, B2, C
        builder.addRoute("R2", "agency", "R2", "R2", RouteType.parse(1));
        builder.addTrip("T2", "R2", "always", "C");
        builder.addStopTime("T2", "A", new ServiceDayTime(60), new ServiceDayTime(120));
        builder.addStopTime("T2", "B2", new ServiceDayTime(180), new ServiceDayTime(240));
        builder.addStopTime("T2", "C", new ServiceDayTime(300), new ServiceDayTime(360));

Expected behaviour:

If two solutions are arriving exactly at the same time, return them always in the same order. Achieve this either by sorting in the post-processing, or adjusting the algorithm in the RaptorRouter to always provide the same solution. I think the second option should be preferred, except if it introduces a large performance penalty.

TODOs:

• Introduce a separate test case in the ch.naviqore.raptor.router.RaptorRouterTest covering this issue.
• Implement fix.
• Change the routes in the GtfsRaptorTestSchedule in the service package to be identical, the tests in RoutingQueryFacadeIT should still pass.