solver returns an invalid solution for the vrptw with breaks

[pmateusz]

A solution found by the constraint programming solver violates breaks of vehicles. The breaks are fixed and performed. A repro is included.

It is possible to define an instance of the Vehicle Routing Problem with Time Windows and Breaks for which the solver will report an invalid solution. Furthermore, the solver fails to recognize that the returned solution is invalid. A more appropriate action would be either dropping more visits or returning a nullptr solution.

Repro example is available in the fork: https://github.com/pmateusz/or-tools/commit/ff78b5c27d7db3a5b8c6ef1791ca3df35b55fd93

Example output

./cvrptw_with_breaks_repro
E0205 17:14:37.660873 11997 cvrptw_with_breaks_repro.cc:390] The time [13:00:00, 13:45:00] allocated for the visit (0 [12:15:00, 13:15:00] 00:45:00) overlaps with the break [13:00:00, 16:00:00] of vehicle (0)
E0205 17:14:37.661190 11997 cvrptw_with_breaks_repro.cc:390] The time [19:30:00, 19:45:00] allocated for the visit (8 [19:30:00, 20:30:00] 00:15:00) overlaps with the break [19:30:00, 20:00:00] of vehicle (17)
E0205 17:14:37.661250 11997 cvrptw_with_breaks_repro.cc:390] The time [19:00:00, 19:30:00] allocated for the visit (9 [19:00:00, 20:00:00] 00:30:00) overlaps with the break [19:00:00, 19:30:00] of vehicle (18)

Could you confirm the bug? Are you aware of any workarounds for the problem reported?

[pmateusz]

Finally I didn't use the break feature from the routing library and implemented a custom constraint.

You may consider reviewing how the breaks are implemented currently. For example the logic for symmetry breaking does not work as expected, because the code is unreachable:

or-tools/ortools/constraint_solver/routing.cc

Line 4958 in d3bd654

if (last != nullptr) {

[furnon]

Thanks for reporting. We will investingate the issue.

…

On Mon, Feb 19, 2018 at 2:07 PM, pmateusz ***@***.***> wrote: Finally I didn't use the break feature from the routing library and implemented a custom constraint. You may consider reviewing how the breaks are implemented currently. For example the logic for symmetry breaking does not work as expected, because the code is unreachable: https://github.com/google/or-tools/blob/ d3bd654/ortools/constraint_ solver/routing.cc#L4958 — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#569 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKjyUhoj8B5XcizyWgnbMApj2bc9Ayo6ks5tWXIrgaJpZM4R52vA> .