Custom operators

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.

The nextroute search engine utilizes a sequence of search operators to progressively improve a solution. These operators typically operate on plan units. A plan unit is a unit of stops which must be planned together (e.g. stop groups or stops with pickup / delivery precedence).

The default search engine has two search operators, the unplan operator and the plan operator, and the engine will loop over these two operators until a stop criterium is met. The stop criterium can be a maximum number of iterations or a maximum duration. After the execution of an operator, the search engine will check if the working solution has a better score than the best solution, if so the working solution will be stored as best solution.

It is possible for a user to configure their own search engine by providing it one or more operators configured for their needs. The following search operators are available in nextroute:

Operator	Description	Nextmv Routing App	Platform
SolveOperatorUnPlan	Selects a subset of planned plan units and removes them from the solution.	✅	✅
SolveOperatorPlan	Attempts to plan all the unplanned plan units in the working solution.	✅	✅
SolveOperatorRestart	Swaps out the working solution for the best solution found for certain criteria (e.g. not having found a better solution for a number of iterations).		✅
SolveOperatorUnplanUnits	Randomly selects a planned plan unit. For each stop in the plan unit, unplan it as well as all of its neighboring plan units.		✅
SolveOperatorUnplanVehicles	Randomly selects one or more vehicles and unplans all the plan units on them. Also includes an option to configure a radius for unplanning neighboring plan units.		✅
SolveOperatorUnplanLocations	Randomly selects locations and removes all plan units from these locations.		✅
SolveOperatorAnd	A collection of operators that must be executed in sequence.		✅
SolveOperatorOr	A collection of operators where either one or the other are executed with a weighted probability.		✅

You may choose instead to construct your own custom operators which are specific to your business needs. For example, you may want to prioritize finding assignments for certain kinds of stops first (perhaps they were already committed to or perhaps they are higher value customers). A custom operator gives you more control over how nextroute explores the search space, which can be helpful in guiding the search to better solutions when given a limited amount of time to solve. In this how-to guide, we will show you how to implement a custom operator.

The nextroute Go package provides the SolveOperator interface which you will need to implement in order to create a custom operator.

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

Example

In this example we create two new search operators.

An operator which will unplan planned plan units randomly.
An operator which plans unplanned plan units.

For demonstration purposes we will keep these operators extremely simple.

First, let's add the custom unplan operator. We want the custom operator to select a random planned plan unit and unplan it. For this we need to implement the SolveOperator interface and, most importantly, the Execute interface.

		return runSchema.Output{}, err
	}
	return output, nil
}

type customUnplanImpl struct {
	nextroute.SolveOperator
}

// NewCustomUnPlanSearchOperator creates a new custom unplan search operator.
func NewCustomUnPlanSearchOperator() nextroute.SolveOperator {
	return &customUnplanImpl{
		nextroute.NewSolveOperator(
			1.0,
			true,
			nextroute.SolveParameters{},
		),
	}
}

func (d *customUnplanImpl) Execute(
	_ context.Context,
	runTimeInformation nextroute.SolveInformation,
) error {
	workSolution := runTimeInformation.
		Solver().
		WorkSolution()

	if workSolution.PlannedPlanUnits().Size() == 0 {
		return nil
	}

	randomPlannedPlanUnit := workSolution.PlannedPlanUnits().RandomElement()

	_, err := randomPlannedPlanUnit.UnPlan()

	if err != nil {

From the above example, you can see the Execute method tells the solver how the operator should manipulate the working solution, in this case by randomly unplanning a planned plan unit.

Now, let's add the custom plan operator. We want the custom operator to select a random unplanned plan unit and plan it at the best location in the existing solution until we have tried to plan all unplanned plan units. Again, we need to implement the SolveOperator interface for this.

	}

	return nil
}

type customPlanImpl struct {
	nextroute.SolveOperator
}

// NewCustomPlanSearchOperator creates a new custom plan search operator.
func NewCustomPlanSearchOperator() nextroute.SolveOperator {
	return &customPlanImpl{
		SolveOperator: nextroute.NewSolveOperator(
			1.0,
			true,
			nextroute.SolveParameters{},
		),
	}
}

func (d *customPlanImpl) Execute(
	ctx context.Context,
	runTimeInformation nextroute.SolveInformation,
) error {
	workSolution := runTimeInformation.
		Solver().
		WorkSolution()

	unPlannedPlannedPlanUnits := workSolution.
		UnPlannedPlanUnits().
		SolutionPlanUnits()

	unPlannedPlannedPlanUnits = common.Shuffle(
		workSolution.Random(),
		unPlannedPlannedPlanUnits,
	)

	for _, unPlannedPlannedPlanUnit := range unPlannedPlannedPlanUnits {
		select {
		case <-ctx.Done():
		default:
			bestMove := workSolution.BestMove(
				ctx,
				unPlannedPlannedPlanUnit,
			)
			if bestMove.IsExecutable() {
				_, err := bestMove.Execute(ctx)
				if err != nil {
					return err
				}
			}

Once you've implemented your custom operators, you must construct a solver function which uses the defined solve operators. The parallel search uses multiple solvers in parallel. It does so for a certain amount of time or iterations after which it collects the best of the best solution and restarts the solvers with the best solution as start solution. One loop of parallel solvers is refered to as a cycle. You will need to construct a parallel solver function which creates solvers in parallel according to your solver function:

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

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 main() {
	runner := run.CLI(solver)
	err := runner.Run(context.Background())
	if err != nil {
		log.Fatal(err)
	}
}

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
	}
	solver, err := nextroute.NewSkeletonSolver(model)
	if err != nil {
		return runSchema.Output{}, err
	}
	solver.AddSolveOperators(
		NewCustomUnPlanSearchOperator(),
		NewCustomPlanSearchOperator(),
	)

	parallelSolver, err := nextroute.NewSkeletonParallelSolver(model)
	if err != nil {
		return runSchema.Output{}, err
	}
	parallelSolver.SetSolverFactory(
		func(
			_ nextroute.ParallelSolveInformation,
			_ nextroute.Solution,
		) (nextroute.Solver, error) {
			solver, err := nextroute.NewSkeletonSolver(model)
			if err != nil {
				return nil, err
			}
			solver.AddSolveOperators(
				NewCustomUnPlanSearchOperator(),
				NewCustomPlanSearchOperator(),
			)
			return solver, nil
		},
	)

	parallelSolver.SetSolveOptionsFactory(
		func(
			_ nextroute.ParallelSolveInformation,
		) (nextroute.SolveOptions, error) {
			return nextroute.SolveOptions{
				Iterations: 1000,
				Duration:   10 * time.Minute,
			}, nil
		},
	)

	solutions, err := parallelSolver.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)

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

Example

Custom objectives

Custom output

Contents