Custom constraints

This feature is only available for Platform. You can find a list of all available features here.

This how-to guide assumes you already completed the get started with vehicle routing tutorial.

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:

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:

JSON

{
  "defaults": {
    "vehicles": {
      "speed": 20
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "location": { "lon": 135.772695, "lat": 34.967146 },
      "custom_data": {
        "type": "kosher"
      }
    },
    {
      "id": "Kiyomizu-dera",
      "location": { "lon": 135.78506, "lat": 34.994857 },
      "custom_data": {
        "type": "non-kosher"
      }
    },
    {
      "id": "Nijō Castle",
      "location": { "lon": 135.748134, "lat": 35.014239 },
      "custom_data": {
        "type": "kosher"
      }
    },
    {
      "id": "Kyoto Imperial Palace",
      "location": { "lon": 135.762057, "lat": 35.025431 },
      "custom_data": {
        "type": "non-kosher"
      }
    },
    {
      "id": "Gionmachi",
      "location": { "lon": 135.775682, "lat": 35.002457 },
      "custom_data": {
        "type": "kosher"
      }
    },
    {
      "id": "Kinkaku-ji",
      "location": { "lon": 135.728898, "lat": 35.039705 },
      "custom_data": {
        "type": "kosher"
      }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "location": { "lon": 135.672009, "lat": 35.017209 },
      "custom_data": {
        "type": "non-kosher"
      }
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "start_location": { "lon": 135.672009, "lat": 35.017209 }
    },
    {
      "id": "v2",
      "start_location": { "lon": 135.728898, "lat": 35.039705 }
    }
  ]
}

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:

// © 2019-present nextmv.io inc

// package main holds the implementation of the nextroute template.
package main

import (
	"context"
	"log"

	"github.com/nextmv-io/nextroute"
	"github.com/nextmv-io/nextroute/check"
	"github.com/nextmv-io/nextroute/factory"
	"github.com/nextmv-io/nextroute/schema"
	"github.com/nextmv-io/sdk/run"
	runSchema "github.com/nextmv-io/sdk/run/schema"
)

func main() {
	runner := run.CLI(solver)
	err := runner.Run(context.Background())
	if err != nil {
		log.Fatal(err)
	}
}

type options struct {
	Model  factory.Options                `json:"model,omitempty"`
	Solve  nextroute.ParallelSolveOptions `json:"solve,omitempty"`
	Format nextroute.FormatOptions        `json:"format,omitempty"`
	Check  check.Options                  `json:"check,omitempty"`
}

func solver(
	ctx context.Context,
	input schema.Input,
	options options,
) (runSchema.Output, error) {
	model, err := factory.NewModel(input, options.Model)
	if err != nil {
		return runSchema.Output{}, err
	}

	// Add a custom customConstraint.
	customConstraint := customConstraint{}
	if err := model.AddConstraint(customConstraint); err != nil {
		return runSchema.Output{}, err
	}

	solver, err := nextroute.NewParallelSolver(model)
	if err != nil {
		return runSchema.Output{}, err
	}

	solutions, err := solver.Solve(ctx, options.Solve)
	if err != nil {
		return runSchema.Output{}, err
	}
	last, err := solutions.Last()
	if err != nil {
		return runSchema.Output{}, err
	}

	output, err := check.Format(ctx, options, options.Check, solver, last)
	if err != nil {
		return runSchema.Output{}, err
	}
	output.Statistics.Result.Custom = factory.DefaultCustomResultStatistics(last)

	return output, nil
}

// customConstraint is a struct that allows to implement a custom constraint.
type customConstraint struct{}

// EstimateIsViolated returns true if the constraint is violated. If the
// constraint is violated, the solver needs a hint to determine if further
// moves should be generated for the vehicle.
func (c customConstraint) EstimateIsViolated(
	move nextroute.Move,
) (isViolated bool, stopPositionsHint nextroute.StopPositionsHint) {
	// If there are no stops planned on the vehicle, the constraint is not
	// violated.
	if move.Vehicle().IsEmpty() {
		return false, nextroute.NoPositionsHint()
	}

	// Get the type of the first stop in the vehicle that is not the vehicle's
	// starting location.
	stop := move.Vehicle().First().Next().ModelStop()
	customData := stop.Data().(schema.Stop).CustomData.(map[string]any)
	customType := customData["type"].(string)

	// Loop over all the stops that are part of the move. If the type of a stop
	// is different from the type of the first stop, the constraint is
	// violated.
	for _, stop := range move.PlanStopsUnit().ModelPlanStopsUnit().Stops() {
		customData := stop.Data().(schema.Stop).CustomData.(map[string]any)
		if customData["type"].(string) != customType {
			return true, nextroute.SkipVehiclePositionsHint()
		}
	}

	// If the constraint is not violated, the solver does not need a hint.
	return false, nextroute.NoPositionsHint()
}

// String returns the name of the constraint.
func (c customConstraint) String() string {
	return "my_custom_constraint"
}

// IsTemporal returns true if the constraint should be checked after all initial
// stops have been planned. It returns false if the constraint should be checked
// after each of the initial stops has been planned.
func (c customConstraint) IsTemporal() bool {
	return false
}

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:

JSON

{
  "options": {
    "check": {
      "duration": 30000000000,
      "verbosity": "off"
    },
    "format": {
      "disable": {
        "progression": true
      }
    },
    "model": {
      "constraints": {
        "disable": {
          "attributes": false,
          "capacities": null,
          "capacity": false,
          "distance_limit": false,
          "groups": false,
          "maximum_duration": false,
          "maximum_stops": false,
          "maximum_wait_stop": false,
          "maximum_wait_vehicle": false,
          "mixing_items": false,
          "precedence": false,
          "start_time_windows": false,
          "vehicle_end_time": false,
          "vehicle_start_time": false
        },
        "enable": {
          "cluster": false
        }
      },
      "objectives": {
        "capacities": "",
        "cluster": 0,
        "early_arrival_penalty": 1,
        "late_arrival_penalty": 1,
        "min_stops": 1,
        "stop_balance": 0,
        "travel_duration": 0,
        "unplanned_penalty": 1,
        "vehicle_activation_penalty": 1,
        "vehicles_duration": 1
      },
      "properties": {
        "disable": {
          "duration_groups": false,
          "durations": false,
          "initial_solution": false,
          "stop_duration_multipliers": false
        },
        "maximum_time_horizon": 15552000
      },
      "validate": {
        "disable": {
          "resources": false,
          "start_time": false
        },
        "enable": {
          "matrix": false,
          "matrix_asymmetry_tolerance": 20
        }
      }
    },
    "solve": {
      "duration": 10000000000,
      "iterations": 50,
      "parallel_runs": 1,
      "plateau": {
        "absolute_threshold": -1,
        "delay": 0,
        "duration": 0,
        "iterations": 0,
        "relative_threshold": 0
      },
      "run_deterministically": true,
      "start_solutions": 1
    }
  },
  "solutions": [
    {
      "objective": {
        "name": "1 * vehicles_duration + 1 * unplanned_penalty",
        "objectives": [
          {
            "base": 1692.229467672225,
            "factor": 1,
            "name": "vehicles_duration",
            "value": 1692.229467672225
          },
          {
            "factor": 1,
            "name": "unplanned_penalty",
            "value": 0
          }
        ],
        "value": 1692.229467672225
      },
      "unplanned": [],
      "vehicles": [
        {
          "id": "v1",
          "route": [
            {
              "cumulative_travel_duration": 0,
              "stop": {
                "id": "v1-start",
                "location": {
                  "lat": 35.017209,
                  "lon": 135.672009
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_distance": 5752,
              "cumulative_travel_duration": 287,
              "stop": {
                "custom_data": {
                  "type": "kosher"
                },
                "id": "Kinkaku-ji",
                "location": {
                  "lat": 35.039705,
                  "lon": 135.728898
                }
              },
              "travel_distance": 5752,
              "travel_duration": 287
            },
            {
              "cumulative_travel_distance": 9081,
              "cumulative_travel_duration": 454,
              "stop": {
                "custom_data": {
                  "type": "kosher"
                },
                "id": "Nijō Castle",
                "location": {
                  "lat": 35.014239,
                  "lon": 135.748134
                }
              },
              "travel_distance": 3329,
              "travel_duration": 166
            },
            {
              "cumulative_travel_distance": 11911,
              "cumulative_travel_duration": 595,
              "stop": {
                "custom_data": {
                  "type": "kosher"
                },
                "id": "Gionmachi",
                "location": {
                  "lat": 35.002457,
                  "lon": 135.775682
                }
              },
              "travel_distance": 2830,
              "travel_duration": 141
            },
            {
              "cumulative_travel_distance": 15846,
              "cumulative_travel_duration": 792,
              "stop": {
                "custom_data": {
                  "type": "kosher"
                },
                "id": "Fushimi Inari Taisha",
                "location": {
                  "lat": 34.967146,
                  "lon": 135.772695
                }
              },
              "travel_distance": 3935,
              "travel_duration": 196
            }
          ],
          "route_duration": 792,
          "route_travel_distance": 15846,
          "route_travel_duration": 792
        },
        {
          "id": "v2",
          "route": [
            {
              "cumulative_travel_duration": 0,
              "stop": {
                "id": "v2-start",
                "location": {
                  "lat": 35.039705,
                  "lon": 135.728898
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_distance": 5752,
              "cumulative_travel_duration": 287,
              "stop": {
                "custom_data": {
                  "type": "non-kosher"
                },
                "id": "Arashiyama Bamboo Forest",
                "location": {
                  "lat": 35.017209,
                  "lon": 135.672009
                }
              },
              "travel_distance": 5752,
              "travel_duration": 287
            },
            {
              "cumulative_travel_distance": 14002,
              "cumulative_travel_duration": 700,
              "stop": {
                "custom_data": {
                  "type": "non-kosher"
                },
                "id": "Kyoto Imperial Palace",
                "location": {
                  "lat": 35.025431,
                  "lon": 135.762057
                }
              },
              "travel_distance": 8250,
              "travel_duration": 412
            },
            {
              "cumulative_travel_distance": 17995,
              "cumulative_travel_duration": 899,
              "stop": {
                "custom_data": {
                  "type": "non-kosher"
                },
                "id": "Kiyomizu-dera",
                "location": {
                  "lat": 34.994857,
                  "lon": 135.78506
                }
              },
              "travel_distance": 3993,
              "travel_duration": 199
            }
          ],
          "route_duration": 899,
          "route_travel_distance": 17995,
          "route_travel_duration": 899
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 2,
        "max_duration": 899,
        "max_stops_in_vehicle": 4,
        "max_travel_duration": 899,
        "min_duration": 792,
        "min_stops_in_vehicle": 3,
        "min_travel_duration": 792,
        "unplanned_stops": 0
      },
      "duration": 0.123,
      "value": 1692.229467672225
    },
    "run": {
      "duration": 0.123,
      "iterations": 50
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}

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

A how-to guide for implementing custom constraints with vehicle routing.

Example

Compatibility attributes

Custom data

Contents