Unfeasible solution when using relations

[diplay]

Hello! Documentation says

A any relation is used to lock specific jobs to certain vehicle in any order

But I found a case when any relation force solver to use certain order of jobs and leads to unfeasible solution.

Example of such problem

```json { "plan": { "jobs": [ { "id": "526", "services": [ { "places": [ { "location": {"lat": 55.73217773, "lng": 37.66371536}, "duration": 3000, "times": [ ["2023-03-20T13:35:00+00:00", "2023-03-20T13:35:00+00:00"] ] } ] } ] }, { "id": "527", "services": [ { "places": [ { "location": {"lat": 55.74140549, "lng": 37.53155899}, "duration": 3000, "times": [ ["2023-03-20T14:50:00+00:00", "2023-03-20T14:50:00+00:00"] ] } ] } ] }, { "id": "529", "services": [ { "places": [ { "location": {"lat": 55.73397446, "lng": 37.58709335}, "duration": 1800, "times": [ ["2023-03-20T06:00:00+00:00", "2023-03-20T11:00:00+00:00"] ] } ] } ] } ], "relations": [ { "type": "any", "jobs": ["526", "527", "529"], "vehicleId": "43" } ] }, "fleet": { "vehicles": [ { "typeId": "vehicle_type_43", "vehicleIds": ["43"], "profile": {"matrix": "car"}, "costs": {"fixed": 22, "time": 0.004806, "distance": 0.0002}, "shifts": [ { "start": { "location": {"lat": 55.83571625,"lng": 37.50357819}, "earliest": "2023-03-19T20:00:00+00:00", "latest": "2023-03-20T19:00:00+00:00" }, "end": { "location": {"lat": 55.83571625, "lng": 37.50357819}, "latest": "2023-03-20T19:00:00+00:00" } } ], "capacity": [10000] } ], "profiles": [{"name": "car"}] } } ```

Job 529 have time window from 6:00 to 11:00 but listed in the relation after two other jobs which should be executed later.

It leads to this solution

```json { "statistic": { "cost": 89.687398, "distance": 39672, "duration": 12433, "times": { "driving": 3968, "serving": 7800, "waiting": 665, "break": 0, "commuting": 0, "parking": 0 } }, "tours": [ { "vehicleId": "43", "typeId": "vehicle_type_43", "shiftIndex": 0, "stops": [ { "location": { "lat": 55.83571625, "lng": 37.50357819 }, "time": { "arrival": "2023-03-19T20:00:00Z", "departure": "2023-03-20T13:09:32Z" }, "distance": 0, "load": [ 0 ], "activities": [ { "jobId": "departure", "type": "departure" } ] }, { "location": { "lat": 55.73217773, "lng": 37.66371536 }, "time": { "arrival": "2023-03-20T13:35:00Z", "departure": "2023-03-20T14:25:00Z" }, "distance": 15275, "load": [ 0 ], "activities": [ { "jobId": "526", "type": "service" } ] }, { "location": { "lat": 55.74140549, "lng": 37.53155899 }, "time": { "arrival": "2023-03-20T14:38:55Z", "departure": "2023-03-20T15:40:00Z" }, "distance": 23621, "load": [ 0 ], "activities": [ { "jobId": "527", "type": "service" } ] }, { "location": { "lat": 55.73397446, "lng": 37.58709335 }, "time": { "arrival": "2023-03-20T15:45:58Z", "departure": "2023-03-20T16:15:58Z" }, "distance": 27198, "load": [ 0 ], "activities": [ { "jobId": "529", "type": "service" } ] }, { "location": { "lat": 55.83571625, "lng": 37.50357819 }, "time": { "arrival": "2023-03-20T16:36:45Z", "departure": "2023-03-20T16:36:45Z" }, "distance": 39672, "load": [ 0 ], "activities": [ { "jobId": "arrival", "type": "arrival" } ] } ], "statistic": { "cost": 89.687398, "distance": 39672, "duration": 12433, "times": { "driving": 3968, "serving": 7800, "waiting": 665, "break": 0, "commuting": 0, "parking": 0 } } } ] } ```

As you can see job 529 has arrival time 2023-03-20T15:45:58Z which doesn't satisfy time window ["2023-03-20T06:00:00+00:00", "2023-03-20T11:00:00+00:00"]

Thank you for developing and supporting this project!

[reinterpretcat]

Hi,

thanks for feedback!

Actually, any relation could potentially lead to unfeasible solutions (the same is true for all relation types). This happens because at the beginning, all jobs from the relation are inserted in the order they specified in this relation in the precreated tour. Later, if solver fails to reinsert them in feasible order or this leads to solutions with worse objective value, then this initial solution will be chosen at the end.

I haven't checked your example in all details, but I guess this is what happened. As workaround:

• use skills feature instead of any relation
• return multiple solutions and pick another one (not available from command line).

[diplay]

Thank you for a good explanation!