google / google/or-tools

AddDimensionWithVehicleTransitAndCapacity returns no solution with optional nodes when capacity requires dropping visits

Open
#5,283 0 comments 0 reactions 0 assignees View on GitHub
Help Needed Lang: .NET 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?

Google.OrTools 9.15.6755 (.NET / C#), .NET 8.0.416, macOS 26.3.1 arm64.

### Which routing solver are you using?

CP-SAT-free routing library (`Google.OrTools.ConstraintSolver`, `RoutingModel`).

### What did you do?

Built a capacity dimension two ways on an otherwise identical model, and varied only whether the instance forces visits to be dropped.

- 2 vehicles, N optional customers, one capacity dimension, `slack_max = 0`, `fix_start_cumul_to_zero = true`.
- Every customer is in its own disjunction with a strictly positive penalty (`1_000_000`).
- No pickup-and-delivery, no time dimension, no vehicle/node compatibility constraints.

The only difference between the two variants is one line:

```csharp
// A
routing.AddDimensionWithVehicleCapacity(cbA, 0, caps, true, "Load");

// B
routing.AddDimensionWithVehicleTransitAndCapacity([cbA, cbB], 0, caps, true, "Load");
```

`cbA` and `cbB` are two separate `RegisterUnaryTransitCallback` registrations. I ran B both with
**identical** callback values and with slightly different ones, to separate evaluator identity from
evaluator content.

Full standalone repro at the bottom — `dotnet new console`, add the package, `dotnet run`.

### What did you expect to see?

Both variants shed the visits that cannot fit and return a solution. Optional visits via
`AddDisjunction` and vehicle-dependent dimension transits are each documented and supported; I could
not find anything stating the combination is unsupported.

### What did you see instead?

Variant B returns no solution as soon as capacity pressure requires visits to be dropped. When
everything fits, B is fine.

```
FITS (4 customers x 10, capacity 1000) - nothing needs dropping:
single shared evaluator solved dropped=0
per-vehicle, identical values solved dropped=0
per-vehicle, 10 vs 11 solved dropped=0

OVER-SUBSCRIBED (20 customers x 10, capacity 30) - visits MUST be dropped:
single shared evaluator solved dropped=14
per-vehicle, identical values NO SOLUTION dropped=0
per-vehicle, 10 vs 11 NO SOLUTION dropped=0

CONTROL - per-vehicle evaluators, 16 of 20 nodes pinned inactive by hand:
NO SOLUTION

OVER-SUBSCRIBED, per-vehicle evaluators, across first-solution strategies:
PathCheapestArc NO SOLUTION
GlobalCheapestArc NO SOLUTION
Savings NO SOLUTION
ParallelCheapestInsertion NO SOLUTION
BestInsertion NO SOLUTION
AllUnperformed NO SOLUTION
```

Two things narrow it down:

1. **Identical callback values fail exactly like differing ones.** So it is not about what the
evaluators return — registering two evaluators is enough.
2. **The control rules out the search layer.** Taking the drop decision away from the search entirely
— `solver.Add(routing.ActiveVar(index) == 0)` on 16 of 20 customers, leaving 4 x 10 against
2 x 30 capacity, comfortably feasible — still returns no solution. So this is not a
first-solution-strategy or filter weakness that different search parameters could work around.

I have deliberately not claimed the disjunction constraint is discarded, because I have only observed
this from outside: the nodes are optional, dropping is required for feasibility, variant A drops them,
variant B returns nothing.

Every first-solution strategy I tried behaves the same (last block above). Longer time limits and
larger/smaller penalties make no difference either.

### Anything else we should know about your project / environment?

This is a fleet VRP where each vehicle class has a different usable capacity per unit of freight
(narrower truck beds fit fewer pallets abreast), which is what led to per-vehicle transit evaluators.
Real days that could not be fully served returned no plan at all rather than a partial one.

We have worked around it by keeping a single shared evaluator and moving the per-vehicle correction
onto the vehicle capacities instead, which is fine for us — filing because the failure mode is silent
(a valid model that simply returns nothing), and because if this combination is genuinely unsupported
it would be worth saying so in the docs.

Standalone repro (Program.cs)

```csharp
// dotnet new console && dotnet add package Google.OrTools --version 9.15.6755 && dotnet run
using Google.OrTools.ConstraintSolver;

const int Vehicles = 2, Depot = 0;

static (string Status, int Dropped) Solve(
int customers, long demandEach, long capacity, bool perVehicleEvaluators, bool differentValues)
{
var manager = new RoutingIndexManager(customers + 1, Vehicles, Depot);
var routing = new RoutingModel(manager);

var arc = routing.RegisterTransitCallback((from, to) =>
manager.IndexToNode(from) == manager.IndexToNode(to) ? 0 : 1);
routing.SetArcCostEvaluatorOfAllVehicles(arc);

long DemandAt(long index, long bump)
{
var node = manager.IndexToNode(index);
return node == Depot ? 0 : demandEach + bump;
}
var cbA = routing.RegisterUnaryTransitCallback(i => DemandAt(i, 0));
var cbB = routing.RegisterUnaryTransitCallback(i => DemandAt(i, differentValues ? 1 : 0));

var caps = new[] { capacity, capacity };
if (perVehicleEvaluators)
routing.AddDimensionWithVehicleTransitAndCapacity([cbA, cbB], 0, caps, true, "Load");
else
routing.AddDimensionWithVehicleCapacity(cbA, 0, caps, true, "Load");

for (var n = 1; n <= customers; n++)
routing.AddDisjunction([manager.NodeToIndex(n)], 1_000_000);

var p = operations_research_constraint_solver.DefaultRoutingSearchParameters();
p.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
p.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration { Seconds = 5 };

var sol = routing.SolveWithParameters(p);
if (sol is null) return ("NO SOLUTION", 0);

var dropped = 0;
for (var n = 1; n <= customers; n++)
{
var idx = manager.NodeToIndex(n);
if (sol.Value(routing.NextVar(idx)) == idx) dropped++;
}
return ("solved", dropped);
}

static string ForcedInactive()
{
const int customers = 20, keepActive = 4;
var manager = new RoutingIndexManager(customers + 1, Vehicles, Depot);
var routing = new RoutingModel(manager);
var arc = routing.RegisterTransitCallback((f, t) =>
manager.IndexToNode(f) == manager.IndexToNode(t) ? 0 : 1);
routing.SetArcCostEvaluatorOfAllVehicles(arc);

long Demand(long i) => manager.IndexToNode(i) == Depot ? 0 : 10L;
var cbA = routing.RegisterUnaryTransitCallback(Demand);
var cbB = routing.RegisterUnaryTransitCallback(Demand);
routing.AddDimensionWithVehicleTransitAndCapacity([cbA, cbB], 0, [30L, 30L], true, "Load");

for (var n = 1; n <= customers; n++)
routing.AddDisjunction([manager.NodeToIndex(n)], 1_000_000);

var solver = routing.solver();
for (var n = keepActive + 1; n <= customers; n++)
solver.Add(routing.ActiveVar(manager.NodeToIndex(n)) == 0);

var p = operations_research_constraint_solver.DefaultRoutingSearchParameters();
p.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
p.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration { Seconds = 5 };
return routing.SolveWithParameters(p) is null ? "NO SOLUTION" : "solved";
}

void Report(string label, (string Status, int Dropped) r) =>
Console.WriteLine($"{label,-40} {r.Status,-12} dropped={r.Dropped}");

Console.WriteLine("FITS (4 customers x 10, capacity 1000) - nothing needs dropping:");
Report(" single shared evaluator", Solve(4, 10, 1000, false, false));
Report(" per-vehicle, identical values", Solve(4, 10, 1000, true, false));
Report(" per-vehicle, 10 vs 11", Solve(4, 10, 1000, true, true));

Console.WriteLine("\nOVER-SUBSCRIBED (20 customers x 10, capacity 30) - visits MUST be dropped:");
Report(" single shared evaluator", Solve(20, 10, 30, false, false));
Report(" per-vehicle, identical values", Solve(20, 10, 30, true, false));
Report(" per-vehicle, 10 vs 11", Solve(20, 10, 30, true, true));

Console.WriteLine("\nCONTROL - per-vehicle evaluators, 16 of 20 nodes pinned inactive by hand:");
Console.WriteLine($" {ForcedInactive()}");

Console.WriteLine("\nOVER-SUBSCRIBED, per-vehicle evaluators, across first-solution strategies:");
foreach (var strat in new[]
{
FirstSolutionStrategy.Types.Value.PathCheapestArc,
FirstSolutionStrategy.Types.Value.GlobalCheapestArc,
FirstSolutionStrategy.Types.Value.Savings,
FirstSolutionStrategy.Types.Value.ParallelCheapestInsertion,
FirstSolutionStrategy.Types.Value.BestInsertion,
FirstSolutionStrategy.Types.Value.AllUnperformed,
})
Console.WriteLine($" {strat,-26} {SolveWithStrategy(strat)}");

static string SolveWithStrategy(FirstSolutionStrategy.Types.Value strat)
{
const int customers = 20;
var manager = new RoutingIndexManager(customers + 1, Vehicles, Depot);
var routing = new RoutingModel(manager);
var arc = routing.RegisterTransitCallback((f, t) =>
manager.IndexToNode(f) == manager.IndexToNode(t) ? 0 : 1);
routing.SetArcCostEvaluatorOfAllVehicles(arc);
long D(long i) => manager.IndexToNode(i) == Depot ? 0 : 10L;
var a = routing.RegisterUnaryTransitCallback(D);
var b = routing.RegisterUnaryTransitCallback(D);
routing.AddDimensionWithVehicleTransitAndCapacity([a, b], 0, [30L, 30L], true, "Load");
for (var n = 1; n <= customers; n++)
routing.AddDisjunction([manager.NodeToIndex(n)], 1_000_000);
var p = operations_research_constraint_solver.DefaultRoutingSearchParameters();
p.FirstSolutionStrategy = strat;
p.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration { Seconds = 5 };
return routing.SolveWithParameters(p) is null ? "NO SOLUTION" : "solved";
}
```

Contributor guide

Open the contributing guide

Research direction

Start with the standalone Program.cs repro and run its comparisons of AddDimensionWithVehicleCapacity versus AddDimensionWithVehicleTransitAndCapacity. Trace the RoutingModel entry point and the capacity dimension behavior when disjunctions or ActiveVar constraints remove visits. Done means the per-vehicle transit case either returns a feasible solution with dropped nodes or its unsupported behavior is documented.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.