google / google/or-tools

Bug in Routing Solver when using amortized vehicle cost

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

Description

Hello

I'm trying to solve a simple VRP and minimize number of needed vehicles and it fails to come up with a solution when using `RoutingModel#setAmortizedCostFactorsOfAllVehicles`
Here's a simple code to reproduce:

```java
public class VrpGlobalSpan {

static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
if(solution == null) {
System.out.println("No solution");
} else {
System.out.println("There is a solution");
}
}

static class DataModel {
public final long[][] distanceMatrix = {
{0, 10, 20},
{10, 0, 20},
{20, 20, 0}
};
public final int vehicleNumber = 1;
public final int depot = 0;
}

public static void main(String[] args) {
Loader.loadNativeLibraries();
// Instantiate the data problem.
final DataModel data = new DataModel();

// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);

// routing.setFixedCostOfAllVehicles(100);
routing.setAmortizedCostFactorsOfAllVehicles(100, 1);

// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});

// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setTimeLimit(Duration.newBuilder().setSeconds(5).build())
.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_MOST_CONSTRAINED_ARC)
.build();

// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);

// Print solution on console.
printSolution(data, routing, manager, solution);
}
}
```
The problem is when I use `setFixedCostOfAllVehicles` and comment `setAmortizedCostFactorsOfAllVehicles`, a solution can be found and it uses only one vehicle.

Also when I change the `vehicleNumber` field value to 2, a solution can be found either with fixed or amortized costs.

Can any body help me with this issue.
Thank you in advance

Version: 9.2.9972
Language: Java
Routing Solver
Windows

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.