Custom constraints

A constraint is a hard rule that must be satisfied by a solution. For example, you can only plan a stop on a vehicle if the vehicle has enough capacity to serve the stop's quantity. In computational terms, a constraint is a function that returns a bool value. If the function returns true, the constraint is satisfied. If the function returns false, the constraint is violated.

We offer many constraints out of the box, for example:

• Capacity
• Maximum route distance
• Maximum route duration
• Precedence

Of course, you may have your own constraints that are specific to your business needs. In this how-to guide, we will show you how to implement a custom constraint.

The nextroute Go package provides the ModelConstraint interface. To create a custom constraint, you have to implement this interface with the specific business rules you want to enforce.

Once the custom type implements the ModelConstraint interface, you pass it to the Model, by means of the AddConstraint method. You may pass as many constraints as you want.

The most important method of the ModelConstraint interface is EstimateIsViolated. This method returns true if the constraint is violated. In addition to returning the bool value, it returns a StopPositionsHint. This refers to a hint used by the solver to know if the vehicle should be skipped entirely or different stops may be planned on it.

The EstimateIsViolated method receives the following arguments:

• Move. A move in a solution. It is a potential change in the solution that can be executed, such as planning a stop on a vehicle or unplanning multiple stops from one. A move may or may not result in changing the solution, as it not always results in an improvement. We encourage you to read the package documentation for more information.
• Solution. Pretty self-explanatory: a solution to a vehicle routing problem. A solution contains all the information about how the problem is solved, such as which stops are planned on which vehicles and in which order. A solution also contains the values for the different objectives that were given. We encourage you to read the package documentation for more information.

Let's see an example of implementing a custom constraint.

Example

Let's say you want to enforce a constraint that prevents kosher food from being transported in the same vehicle as non-kosher food.

Consider the following input, where we use the custom_data field in each stop to define the type of the stop:

You can customize the main.go file that you initialized in the get started with platform tutorial. The following code snippet shows how to implement the ModelConstraint interface to enforce the constraint and how to pass it to the Model:

Please consider the following.

• The customConstraint struct implements:
  • The ModelConstraint interface because the EstimateIsViolated method is defined on that type.
  • The fmt.Stringer interface because the String method is defined on that type.
  • The ConstraintTemporal interface because the IsTemporal method is defined on that type.
• In the solver function, we pass the customConstraint to the Model by means of the AddConstraint method.
• In the EstimateIsViolated method:
  • If the vehicle is empty the constraint is feasible because there are no stops that need enforcing.
  • We get the type from the first stop present in the move's vehicle. We check if that type is the same as all the stops in the move. The stops in the move are the potential stops that may be planed on the vehicle. If there is a type mismatch, the constraint is violated, and we return true.
  • In further moves, more stops may be planned on the vehicle. Given that the constraint enforces all the stops in the vehicle to have the same type, always taking the type from the first stop is appropriate. This holds because stops will only be planned on a vehicle if all constraints in the problem are satisfied.
  • If the constraint is not violated, there is no need to give the solver a StopPositionsHint, and we can simply return false, nil.
  • If the constraint is violated, we return a SkipVehiclePositionsHint because there is no possible move for the plan unit that can be executed on this vehicle.
• The String method returns the name of the custom constraint, e.g. when the constraint is violated.
• The IsTemporal method lets the constraint check either after each initial_stop was added to the solution or after all stops have been added to the solution. The latter can be necessary if the sequence of adding stops is important for the constraint to evaluate whether the constraint was violated.

After running the code, you should get an output similar to this one:

Please note that the stops are split into two vehicles, one for each type.