routing(.Net): Span upper bounds causing broken depot time windows

[AdamLithgow]

What version of OR-Tools and what language are you using?
Version: v9.11
Language: C#

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Windows 11 Enterprise version 10.0.26100 Build 26100

What did you do?
Steps to reproduce the behavior:

1. Open the linked demo solution
2. Run all unit tests in the test project (SolverTests)

What did you expect to see
All 3 tests should pass

What did you see instead?
For one of the tests, the solve is marked as successful, and the start and end depots of the route are set to occur outside the hard time windows specified by approx. 5 hours. This is only occurring for a specific set of circumstances, which was brought on by attempting to cap the duration of the routes.

Adding SetSpanUpperBoundForVehicle on all vehicles caused slack to not properly factor into the solve, resulting in hours of excess wait time (vehicle leaving depot hours early to wait at an order location). Adding SetSpanCostCoeffieicntForAllVehicles causes the slack to be correctly factored into the solve, but results in the time windows being thrown off for empty routes.

Also, in one of my callbacks I have a ternary evaluation. If I change it to always return the true condition, I get 0 unassigned orders, and the time windows for the depots are correct. If I change it to always return the false condition, I get ROUTING_INFEASIBLE. However, if I let the ternary evaluate, I get ROUTING_SUCCESS with an empty route and broken time windows on the depots, but only if SetSpanUpperBoundForVehicle and/or SetSpanCostCoeffieicntForAllVehicles is set. If neither of those are present, I get ROUTING_SUCCESS with an empty route, but correct start and end depot time windows.

Make sure you include information that can help us debug (full error message, model Proto).

Anything else we should know about your project / environment
The code in Solver.cs has been commented with TODOs pertaining to the relevant lines of code and what happens with each.

https://github.com/AdamLithgow/OrToolsBugDemo