We’ve found a route optimization request with an in_sequence relation that appears to be ignored. The request was originally a multi-vehicle route but I’ve distilled it down to a minimal reproducible case. There is a service wnkleFg6kbWmkaDIkN0C that should be last service in the route, but it ends up being first. It has its group set to “low” and there is a relation with groups “high”, “medium” and “low”. It seems to work as expected when there is at least one service that isn’t pre-assigned using allowed_vehicles.
In the full example there are services with 3 different groups “high”, “medium” and “low”. It seems like this happens because there is a “high” service in all of the services, but there aren’t any “high” services that can be assigned to the route that wnkleFg6kbWmkaDIkN0C is in, so it seems to be ignoring the relation completely.
In the minimal example there are only 2 vehicles but there are no “high” services at all. It returns the same result even though I’d expect it to throw an error about there not being any “high” services when that is specified in the relation. It seems to only throw the error when there is a single vehicle.
request_full.json (73.7 KB)
request_min.json (6.7 KB)
We have now been able to reproduce this. If all services are assigned to some vehicles, we turn the problem into n sub-problems (n = number of vehicles), because the problems are usually independent and much faster to solve. For these sub-problems, we only apply the relations if the sub-problem contains the same groups as the parent problem. So the first bug here is that there is no “high” service, but this is implicitly expected via the relation. I will now throw an error here. Do you agree with this?
The next problem that arises from this decomposition is that even if there is a “high” service, the subproblem can only contain a subset of the defined groups. For example: There are 2 subproblems. All “high” services end up in problem 1 and all “medium” and “low” services in problem 2. Here I have the following suggestion: Problem 1 does not need a group relation. For problem 2 I try to keep as much of the original group relation as possible, i.e. in this case there is an “in_sequence” relation with “medium” and “low” groups (in the order as specified in the original relation). Does that make sense to you?
So the first bug here is that there is no “high” service, but this is implicitly expected via the relation. I will now throw an error here. Do you agree with this?
Yes this makes sense to me. If there are no “high” services in the problem at all, then I agree it makes sense to throw the error. It’s only included in the relation in the min example I sent over to demonstrate the second issue.
For problem 2 I try to keep as much of the original group relation as possible, i.e. in this case there is an “in_sequence” relation with “medium” and “low” groups (in the order as specified in the original relation). Does that make sense to you?
Yeah this makes sense to me too. Thanks for looking into it.
This should be fixed now.
Thanks a lot for your detailed description (plus min example). Great!