Question concerning synchronization constraints and join function

[uncreativename42]

Hi there,
I currently try to use cspy (using Python only) for a sub problem of a vehicle routing problem with time windows and synchronization constraints.
I want to ensure that two visits which have a synchronization relationship cannot be part of the same route in the sub problem.
I managed to model this relationship in the forward as well as in the backward REF referencing partial_path and setting new_res to 1 (max_res = 0) if two synchronization visits are put into the same route, but I am not sure if it is possible to use the bidirectional algorithm, since I fail to find a way to prevent two feasible partial paths being joined into an unfeasible route by the join function. (I know there are some issues using bidirectional search when faced with time windows in the vrpy example, but at the moment I seem to have made it work for my problem, so I could use bidirectional otherwise.
Is there a way to prevent joining into an unfeasible route when faced with my problem?

[torressa]

Hi @uncreativename42!
Does Synchronization = pick up and delivery?
If so, you have to make updates at the labelling level (C++).
I've had a go at this, see this issue Kuifje02/vrpy#15.
I have not tried to work on the bidirectional version, to be honest, as the authors of the paper, also linked in the discussion said:

"A prototype implementation of a bidirectional search that used a more restrictive dominance condition criterion for the backward extension gave disappointing results."

But it's definitely worth revisiting. If you managed to get it working when joining you need to check the partial paths of both labels to ensure that

1. the pdp pair is only one of them
2. or pickup in forward and delivery in backward (forming the correct pair).