There is no check that the boarded trip has not been boarded in a previous raptor iteration. The path is rejected only when the trip arrival is later added to the state of the arrival stops. This results in many extra computations that could be avoided if we could prevent it.
Lat say you search for a trip departure between 09:00 and 10:00. Then at one of the access stops A:
Iteration 09:59: At Stop A we board route X at 12:30 ...
Iteration 09:58: At Stop A we board route X at 12:30 ... (no check that this was boarded before)
:
Iteration 09:20: At Stop A we board route X at 09:25 - finally we board an earlier trip ...
Iteration 09:19: At Stop A we board route X at 09:25 - same problem
Problem
The problem is that we wast time and resources. The problem is less for round 2 and out, hence the the majority of the computations. If the same trip is reboarded in round n > 2, this new path is not the same path and we have to check if it is an optimal solution - we do that now by checking the arrival state.
Solution
There is several solutions to the problem.
One is to prohibit wait-time > (board_slack + iterationStep) for iteration 1.
Have a check on optimal trip boardings. (This is probably not worth the overhead)
Implementation
Solution no 1 is very simple to implement.
Solution no 1 should be combined with having a parameter in the interface to apply this rule also to iteration 1. This can be used to divide the search into time slices and prevent each slice of doing redundant work.
Context/Example
There is no check that the boarded trip has not been boarded in a previous raptor iteration. The path is rejected only when the trip arrival is later added to the state of the arrival stops. This results in many extra computations that could be avoided if we could prevent it.
Lat say you search for a trip departure between 09:00 and 10:00. Then at one of the access stops A:
Iteration 09:59: At Stop A we board route X at 12:30 ... Iteration 09:58: At Stop A we board route X at 12:30 ... (no check that this was boarded before) : Iteration 09:20: At Stop A we board route X at 09:25 - finally we board an earlier trip ... Iteration 09:19: At Stop A we board route X at 09:25 - same problem
Problem
The problem is that we wast time and resources. The problem is less for round 2 and out, hence the the majority of the computations. If the same trip is reboarded in round n > 2, this new path is not the same path and we have to check if it is an optimal solution - we do that now by checking the arrival state.
Solution
There is several solutions to the problem.
wait-time > (board_slack + iterationStep)for iteration 1.Implementation
Solution no 1 is very simple to implement.
Solution no 1 should be combined with having a parameter in the interface to apply this rule also to iteration 1. This can be used to divide the search into time slices and prevent each slice of doing redundant work.