google / google/or-tools

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

Open
#4,573 0 comments 0 reactions 1 assignee Claimed by @Mizux View on GitHub
Bug Lang: .NET OS: Windows Solver: Routing
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**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

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.