Skip to content

Custom objectives

Info

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

An objective is a soft rule that is used to evaluate the quality of a solution, by giving it a numeric value. It is also known as value function. In vehicle routing it is common to search for the solution that minimizes the total value of the objective. For example, you may want to minimize the total travel duration across all vehicles in a solution.

We offer the ModelObjectiveSum as the main objective that is optimized by the solver. It is a linear sum of multiple objectives, each with a factor that determines its weight, as given by the following expression:

model_objective_sum = factor_1 * objective_1 + factor_2 * objective_2 + ... + factor_n * objective_n

Where:

  • factor_i is the weight of the objective_i.
  • objective_i is the i-th objective and is represented by a float value.

This model_objective_sum, by default, is composed of one objective. This objective is the travel duration of all the vehicles in the solution, using a factor of 1.0. You can always override this behavior using the -model.objectives.travelduration option.

We offer many objectives that can be added to the model_objective_sum out of the box, for example:

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

The nextroute Go package provides the ModelObjective interface. To create a custom objective, you have to implement this interface with the specific business rules you want to model.

Once the custom type implements the ModelObjective interface, you pass it to the Model, by means of the Objective() method. This method returns the ModelObjectiveSum objective inteface. The interface offers the NewTerm method which you can use to add as many objective terms as you want.

The most important methods of the ModelObjective interface are EstimateDeltaValue and Value.

  • EstimateDeltaValue returns float value that represents the estimated change in the score (the objective's value) if the Move is executed on the Solution. Note that executing a move not necessarily improves the score. An improvement is represented by a negative value being returned.
  • Value returns the float value that represents the score for the given solution. Value answers the question "what is the value of this solution?", whereas EstimateDeltaValue answers the question "what would happen to the score if I were to execute this move on this solution?"

The methods make use of 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 objective.

Example

Let's say in addition to minimizing the travel duration, you want to balance the stops that are planned across vehicles. This is, you want to make the routes as even as possible as determined by the number of stops that are planned. Ideally, all vehicles have the same number of stops assigned.

Consider the following input, where we use the custom_data field in the input to define a penalty for our objective. The penalty will be used to balance out the value against the travel duration objective.

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

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 ModelObjective interface to model the balance objective 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"
    "errors"
    "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
    }

    // Check if there is custom data coming from the input.
    if input.CustomData != nil {
        // Unmarshal custom data that is part of the input into the custom
        // objective struct that we define below.
        customObjective, err := schema.ConvertCustomData[customObjective](input.CustomData)
        if err != nil {
            return runSchema.Output{}, errors.New("input.custom_data must be of type map[string]any")
        }

        // Add a custom objective. The term used is 1.0 for simplicity but it
        // can also be specified in the input.
        if _, err := model.Objective().NewTerm(1.0, &customObjective); 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
}

// customObjective is a struct that allows to pass in custom data from the
// input and implement a new custom objective.
type customObjective struct {
    // BalancePenalty is the penalty that is multiplied by the difference
    // between the maximum number of stops and the minimum number of stops.
    BalancePenalty float64 `json:"balance_penalty,omitempty"`
}

// EstimateDeltaValue estimates the cost of planning the stops into a solution
// as defined in the move. The cost may imply an improvement in the objective's
// score.
func (c *customObjective) EstimateDeltaValue(
    move nextroute.Move,
) float64 {
    solution := move.Solution()
    // Calculate the maximum and minimum number of stops for the current
    // solution.
    maxNumStops := 0
    minNumStops := solution.Model().NumberOfStops()
    secondMinNumStops := solution.Model().NumberOfStops()

    // Loop over the vehicles of the solution to set the baseline of what are
    // the current maximum and minimum number of stops across all of them.
    for _, vehicle := range solution.Vehicles() {
        stops := vehicle.NumberOfStops()
        if stops > maxNumStops {
            maxNumStops = stops
        }

        if stops < minNumStops {
            minNumStops = stops
        }

        // In case the vehicle of the move is the one holding the minimum
        // number of stops, adding stops to it will make it no longer the
        // vehicle with the minimum number of stops. In this case, we need to
        // find the second minimum number of stops.
        if vehicle.Index() != move.Vehicle().Index() {
            if stops < secondMinNumStops {
                secondMinNumStops = stops
            }
        }
    }

    // If planning stops on the move's vehicle makes it have the maximum number
    // of stops, the delta can be calculated as the difference between the new
    // number of stops and the previous maximum number of stops.
    newNumStops := move.Vehicle().NumberOfStops() + len(move.StopPositions())
    if newNumStops > maxNumStops {
        return c.BalancePenalty * float64(newNumStops-maxNumStops)
    }

    // If the move's vehicle has the minimum number of stops, the delta can be
    // calculated as the difference between the new number of stops and the
    // previous minimum number of stops.
    if newNumStops > secondMinNumStops {
        minNumStops = secondMinNumStops
        return c.BalancePenalty * float64(secondMinNumStops-minNumStops)
    }

    // If the maximum and minimum number of stops do not change, there is no
    // delta.
    return 0.0
}

// Value returns the value of the custom objective's score, calculated for a
// given solution.
func (c *customObjective) Value(solution nextroute.Solution) float64 {
    maxNumStops := 0
    minNumStops := solution.Model().NumberOfStops()

    // Loop over the vehicles of the solution to calculate the maximum and
    // minimum number of stops across all of them.
    for _, vehicle := range solution.Vehicles() {
        stops := vehicle.NumberOfStops()
        if stops > maxNumStops {
            maxNumStops = stops
        }
        if stops < minNumStops {
            minNumStops = stops
        }
    }

    // This is the value of the solution for the given objective.
    return c.BalancePenalty * float64(maxNumStops-minNumStops)
}

// String implements the fmt.Stringer interface, allowing you to print the name
// of the objective in the output in a human-readable way.
func (c *customObjective) String() string {
    return "balance_penalty"
}

Please consider the following.

  • The customObjective struct implements the ModelObjective interface because the EstimateDeltaValue and Value methods are defined on that type.
  • In the solver function, we unmarshal the custom_data defined on the input into the customObjective struct. We pass it to the Model by means of the Objective().NewTerm() method. For simplicity, a term of 1.0 is used.
  • The value of the balance objective will be calculated by looping over all the vehicles in the solution to find the maximum and minimum number of stops that are planned. The difference between the maximum and minimum, if minimized to zero, implies that all vehicles have the same number of stops assigned to them.
  • The difference between the maximum and minimum stops is multiplied by the penalty read from the custom_data to balance out the value against the travel duration. Given that the travel duration may be several hundreds or thousands of seconds (depending on the problem of course), we want the balance objective to be on the same order of magnitude so that the solver has a proper incentive to distribute stops across vehicles.
  • In the EstimateDeltaValue method:
    • We first calculate the baseline of the objective by calculating the maximum and minimum number of stops that are planned across all vehicles in the current solution.
    • In case the move's vehicle holds the minimum number of stops, executing that move will imply that the minum number of stops will not necessarily belong to that vehicle, given that it will increase the stops planned on it. For this reason, we calculate the second minimum number of stops.
    • The delta is calculated by determining how the difference between maximum and minimum changes. The increase is multiplied by the penalty. If there is no change in the difference, the delta is zero.
  • In the Value method:
    • We use the same logic to calculate the difference between the maximum and minimum number of stops and mutliply it by the penalty.
  • We implement the String() string method on the customObjective type to get a human-readable representation of the objective.

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

{
  "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,
        "distance": 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,
      "solver": {
        "plan_group_size": {
          "delta": 0,
          "delta_after_iterations": 1000000000,
          "max_value": 2,
          "min_value": 2,
          "snap_back_after_improvement": true,
          "start_value": 2,
          "zigzag": true
        },
        "unplan_units": {
          "delta": 2,
          "delta_after_iterations": 125,
          "max_value": -1,
          "min_value": 2,
          "snap_back_after_improvement": true,
          "start_value": 2,
          "zigzag": true
        },
        "unplan_weights": "Vehicle:3,Island:1,Location:293"
      },
      "start_solutions": 1
    }
  },
  "solutions": [
    {
      "objective": {
        "name": "1 * vehicles_duration + 1 * unplanned_penalty + 1 * balance_penalty",
        "objectives": [
          {
            "base": 1084.2458387952015,
            "factor": 1,
            "name": "vehicles_duration",
            "value": 1084.2458387952015
          },
          {
            "factor": 1,
            "name": "unplanned_penalty",
            "value": 0
          },
          {
            "base": 1000,
            "factor": 1,
            "name": "balance_penalty",
            "value": 1000
          }
        ],
        "value": 2084.2458387952015
      },
      "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_duration": 0,
              "stop": {
                "id": "Arashiyama Bamboo Forest",
                "location": {
                  "lat": 35.017209,
                  "lon": 135.672009
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_distance": 8250,
              "cumulative_travel_duration": 412,
              "stop": {
                "id": "Kyoto Imperial Palace",
                "location": {
                  "lat": 35.025431,
                  "lon": 135.762057
                }
              },
              "travel_distance": 8250,
              "travel_duration": 412
            },
            {
              "cumulative_travel_distance": 12243,
              "cumulative_travel_duration": 612,
              "stop": {
                "id": "Kiyomizu-dera",
                "location": {
                  "lat": 34.994857,
                  "lon": 135.78506
                }
              },
              "travel_distance": 3993,
              "travel_duration": 199
            },
            {
              "cumulative_travel_distance": 15523,
              "cumulative_travel_duration": 776,
              "stop": {
                "id": "Fushimi Inari Taisha",
                "location": {
                  "lat": 34.967146,
                  "lon": 135.772695
                }
              },
              "travel_distance": 3280,
              "travel_duration": 164
            }
          ],
          "route_duration": 776,
          "route_travel_distance": 15523,
          "route_travel_duration": 776
        },
        {
          "id": "v2",
          "route": [
            {
              "cumulative_travel_duration": 0,
              "stop": {
                "id": "v2-start",
                "location": {
                  "lat": 35.039705,
                  "lon": 135.728898
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_duration": 0,
              "stop": {
                "id": "Kinkaku-ji",
                "location": {
                  "lat": 35.039705,
                  "lon": 135.728898
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_distance": 3329,
              "cumulative_travel_duration": 166,
              "stop": {
                "id": "Nijō Castle",
                "location": {
                  "lat": 35.014239,
                  "lon": 135.748134
                }
              },
              "travel_distance": 3329,
              "travel_duration": 166
            },
            {
              "cumulative_travel_distance": 6159,
              "cumulative_travel_duration": 308,
              "stop": {
                "id": "Gionmachi",
                "location": {
                  "lat": 35.002457,
                  "lon": 135.775682
                }
              },
              "travel_distance": 2830,
              "travel_duration": 141
            }
          ],
          "route_duration": 308,
          "route_travel_distance": 6159,
          "route_travel_duration": 308
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 2,
        "max_duration": 776,
        "max_stops_in_vehicle": 4,
        "max_travel_duration": 776,
        "min_duration": 308,
        "min_stops_in_vehicle": 3,
        "min_travel_duration": 308,
        "unplanned_stops": 0
      },
      "duration": 0.123,
      "value": 2084.2458387952015
    },
    "run": {
      "duration": 0.123,
      "iterations": 50
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}

Please note that the value of the balance_penalty objective reflects that there is a difference of 1 stop between the two vehicles, given that the penalty is set to be 1000.

By comparison, this is the output of running the same problem without the balance_penalty:

{
  "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,
        "distance": 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,
      "solver": {
        "plan_group_size": {
          "delta": 0,
          "delta_after_iterations": 1000000000,
          "max_value": 2,
          "min_value": 2,
          "snap_back_after_improvement": true,
          "start_value": 2,
          "zigzag": true
        },
        "unplan_units": {
          "delta": 2,
          "delta_after_iterations": 125,
          "max_value": -1,
          "min_value": 2,
          "snap_back_after_improvement": true,
          "start_value": 2,
          "zigzag": true
        },
        "unplan_weights": "Vehicle:3,Island:1,Location:293"
      },
      "start_solutions": 1
    }
  },
  "solutions": [
    {
      "objective": {
        "name": "1 * vehicles_duration + 1 * unplanned_penalty",
        "objectives": [
          {
            "base": 909.0466359667602,
            "factor": 1,
            "name": "vehicles_duration",
            "value": 909.0466359667602
          },
          {
            "factor": 1,
            "name": "unplanned_penalty",
            "value": 0
          }
        ],
        "value": 909.0466359667602
      },
      "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_duration": 0,
              "stop": {
                "id": "Arashiyama Bamboo Forest",
                "location": {
                  "lat": 35.017209,
                  "lon": 135.672009
                }
              },
              "travel_duration": 0
            },
            {
              "cumulative_travel_distance": 5752,
              "cumulative_travel_duration": 287,
              "stop": {
                "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": {
                "id": "Nijō Castle",
                "location": {
                  "lat": 35.014239,
                  "lon": 135.748134
                }
              },
              "travel_distance": 3329,
              "travel_duration": 166
            },
            {
              "cumulative_travel_distance": 10857,
              "cumulative_travel_duration": 542,
              "stop": {
                "id": "Kyoto Imperial Palace",
                "location": {
                  "lat": 35.025431,
                  "lon": 135.762057
                }
              },
              "travel_distance": 1776,
              "travel_duration": 88
            },
            {
              "cumulative_travel_distance": 13696,
              "cumulative_travel_duration": 684,
              "stop": {
                "id": "Gionmachi",
                "location": {
                  "lat": 35.002457,
                  "lon": 135.775682
                }
              },
              "travel_distance": 2839,
              "travel_duration": 141
            },
            {
              "cumulative_travel_distance": 14897,
              "cumulative_travel_duration": 745,
              "stop": {
                "id": "Kiyomizu-dera",
                "location": {
                  "lat": 34.994857,
                  "lon": 135.78506
                }
              },
              "travel_distance": 1201,
              "travel_duration": 60
            },
            {
              "cumulative_travel_distance": 18177,
              "cumulative_travel_duration": 909,
              "stop": {
                "id": "Fushimi Inari Taisha",
                "location": {
                  "lat": 34.967146,
                  "lon": 135.772695
                }
              },
              "travel_distance": 3280,
              "travel_duration": 164
            }
          ],
          "route_duration": 909,
          "route_travel_distance": 18177,
          "route_travel_duration": 909
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 1,
        "max_duration": 0.123,
        "max_stops_in_vehicle": 7,
        "max_travel_duration": 0.123,
        "min_duration": 0.123,
        "min_stops_in_vehicle": 7,
        "min_travel_duration": 0.123,
        "unplanned_stops": 0
      },
      "duration": 0.123,
      "value": 0.123
    },
    "run": {
      "duration": 0.123,
      "iterations": 50
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}

This solution shows that the custom objective is influential enough to the solver to worsen the travel duration, by balancing out the stops.