Add specific capacity constraint on arcs for routing optimization with Or-Tools

user_19373729 0
Viewed 64

Is it possible with Or-Tools Routing to create capacity constraints on arcs?

Let me explain:

I have implemented the following example.

The problem is that during some rounds there are routes where the capacity of the truck is limited (for example a bridge where the capacity of the truck must not exceed 6 units).

Is it possible to add specific capacity constraints between two nodes i and j so that :

capacity(i) - capacity(j) <= allowed capacity between the two steps, if so how?

The constraint must be on the arc and I can't find how to do it using Java.

An example:

I have a truck loaded with 3 units at point i, it must go to point j and encounter a bridge where the maximum load allowed on the bridge is 2 units. Therefore, it cannot cross the bridge. In other words, the round must be run in another way.

Thank you very much in advance

or-tools routes optimization java
1 Answers

I share with you my solution if it can help someone else.

The following constraint must be added: the result of subtracting the load (capacity) of step j - step i must be smaller than the maximum load allowed for step ij.

With Java, we get the following code:

Capacity matrix:


long[][] maxLoad = {
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,-1,-1,-1,-1},
            };

Constraint declaration:


Solver solver = routing.solver();
RoutingDimension capacite_dim = routing.getDimensionOrDie("Capacity");

for (int i = 0; i < secteur.getMaxLoad().length; i++) {
  for (int j = 0; j < secteur.getMaxLoad()[0].length; j++) {
    //if there is a load constraint in matrix
    if (secteur.getMaxLoad()[i][j] >= 0) {
      long beforeIndex = manager.nodeToIndex(i);
      long afterIndex = manager.nodeToIndex(j);
      //add constraint
      solver.addConstraint(solver.makeLessOrEqual(solver.makeDifference(capacite_dim.cumulVar(afterIndex),capacite_dim.cumulVar(beforeIndex)),secteur.getMaxLoad()[i][j]));
    }
  }
}

The constraint ensures that the load flowing on the arc between two steps is less than the maximum allowed load for this step.

user_193737290
Related