nextmv Docs

Using HopM

Using HopM

There are a number of common, recurring patterns in decision automation. For instance, there are well studied, high performance techniques for routing drivers, assigning work, or scheduling labor.

HopM stands for "Hop models". HopM contains Nextmv's implementations of high performance models that handle common tasks. These can be used directly or as components in your own decision models similar to plugin architectures.

HopM Models

We're committed to best in class modeling components based on the latest academic and industry research. Currently, we provide components that do the following:

  • Cluster groups items based on k-means or nearest neighbor similarity
  • Pack assigns work to a resource based on constraints (capacity, compute, schedule)
  • Route dispatches drivers or items (TSP, VRP, etc)

We add new HopM models all the time. If you don't see your use case, just ask us.

HopM Structure

HopM models each have a struct defining its expected input. HopM models implement Hop's model.State interface, and can be passed directly to Hop's solver constructors. By convention, HopM models provide the following exported types and functions for constructing models:

  • Input: a struct defining required model input.
  • DefaultModel: a function that converts an Input, and any other required data, into a Hop model.
  • DefaultSolver: a function that converts an Input, and any other required data, into a Hop solver.
  • DefaultOptions: a function to configure default solver options for a model.

Additionally, for fleet routing problems, HopM models provide:

  • DefaultAssigner: a function that converts an Input, and any other required data, into a Hop assigner.

Default Solver vs Model

There are typically 3 usage patterns for HopM models:

ProblemDataUsage Pattern
StandardAdheres to Input structureInstall and run DefaultSolver directly
StandardCan be transformed into Input structureModify main, build, and run DefaultSolver
ExtensionAdheres to (or can be transformed into) Input structureInstantiate a DefaultModel, extend standard model, build, and run new solver

"Standard" here refers to the standard modeling problem represented by the HopM package. For example, a Traveling Salesperson Problem (TSP) is our standard Vehicle model that can be used stand alone (standard) or nested inside of a knapsack problem (extension).

As mentioned above, a user can install and run the DefaultSolver directly. For example, the package github.com/nextmv-io/code/hopm/route provides a default routing model for the Capacitated Vehicle Routing Problem (CVRP).

go install github.com/nextmv-io/code/hopm/cmd/route
$(go env GOPATH)/bin/route -hop.runner.input.path input.json \
-hop.runner.output.path output.json \
-hop.solver.limits.solutions 1

If the input data does not conform to the required Input format, the main method for the user model can be modified to transform input data into the required format for using the DefaultSolver directly.

package main
import (
"github.com/nextmv-io/code/hop/run/cli"
"github.com/nextmv-io/code/hopm/route/vehicle"
)
func main() {
cli.Run(vehicle.DefaultSolver)
}

The DefaultSolver configuration can be found in vehicle/default.go and shows that a cost matrix is the standard measurer for this TSP.

Modelers may, however, choose to use HopM models as components and build extensions around them rather than using the solver directly. Calling DefaultModel rather than DefaultSolver gives the modeler access to the exported components of the underlying model which allows a user to build and test models without having to dive into the individual model source.

Constraints

Our HopM models come with prebuilt, commonly used constraints as well as a constraint interface for building custom constraints unique to your business.

You can find a full list of constraints for each model in the HopM package docs.

Here is an example of a model with capacity, precedence (pickups happen before dropoffs), window (locations must be visited within cost windows), and max length (route must be less than or equal to the max) constraints for routing vehicles.

constraints = append(
constraints,
[]vehicle.Constraint{
vehicle.Capacity(capacity, capacityChange),
vehicle.Precedence(precedence),
vehicle.Window(startCost, windows, windowMeasure)
vehicle.MaxLength(routeMeasure, max, true)
},
)

Our clustering models can also have constraints. For example you may want to dictate how many points are in a cluster (cardinality) or their combined weight (capacity). Here is an example using both.

model, err := kmeans.DefaultModel(
k,
measurer,
kmeans.Cardinality(5),
kmeans.Capacity(capacity, weights),
)

Measurers

Measurers tell the model how to access the cost of an arc or connection between two locations. HopM comes with a collection of measurers (e.g. haversine and matrix) which give users flexibility in how routes are compared. Measurers also allow you to scale, override, or make cost between locations constant.

In the example below, the measurer will tell the Vehicle model that the cost between any two locations is time (haversine distance scaled by 1/speed) as a default. The override cost will be 0 if the driver is going from any location to the end of their route. This is useful for any routing model that does not specify an end location for the driver or does not return to a depot (think real time gig economy).

Check out all our measurers through the HopM package docs.

// Use speed to get drive time to/from all points and make to a driver start 0
measurer := measure.Override(
// Calculate drive time, assumes travel speed is 9m/s
measure.Scale(measure.HaversineByIndex(points), 1.0/9.0),
measure.Constant(0),
func(from, to int) bool {
return driverDomain.Contains(to)
// TODO use bin measurer for adding ETA cost to driver start
},
)

Embedded HopM Example

The following is an example for how to use HopM's Vehicle model to route a single driver from Mvrs-N-Shkrs Coffee Distributor to a set of coffee shops that ordered beans while minimizing distance traveled.

Our input for the model is pretty straightforward, with a set of locations and a single vehicle with a starting location.

{
"vehicles":
{
"vehicle_id": "Mvrs-N-Shkrs-1",
"start": [33.122746, -96.659222],
"end": [33.122746, -96.659222]
},
"requests": [
{
"location_id": "Coffee Labs Cafe",
"position": [33.004745, -96.827094]
},
{
"location_id": "The Caffeinated Cat",
"position": [33.005741, -96.86074]
},
{
"location_id": "Barks and Brew",
"position": [32.969456, -96.820915]
},
{
"location_id": "Study Loft",
"position": [32.921629, -96.695259]
},
{
"location_id": "Java the Hutt",
"position": [32.875507, -96.673973]
}
]
}

Since the value we are minimizing is the same as the HopM Vehicle model, but the input schema is different, we are going to use the DefaultModel to customize for our data.

package route
import (
"github.com/nextmv-io/code/hop/model"
"github.com/nextmv-io/code/hop/solve"
"github.com/nextmv-io/code/hopm/route/vehicle"
"github.com/mooney-corp/coffee-router/schema"
"github.com/nextmv-io/code/hopm/measure"
vehicleschema "github.com/nextmv-io/code/hopm/route/vehicle/schema"
)
// Solver constructs root state from inputs and options and returns a Minimizer.
func Solver(input schema.Input, opt solve.Options) (solve.Solver, error) {
// Extract geo points from requests to use in Vehicle.
// i.e. [location 1, location 2, ...., location n]
points := []measure.Point{}
for _, request := range input.Requests {
points = append(points, request.Position)
}
// Create an intDomain for efficient indexing points.
requests := model.Domain(model.Range(0, len(points)-1))
// Add the vehicle start and end to points
input.Vehicle.StartIndex = len(points)
points = append(points, input.Vehicle.Start)
input.Vehicle.EndIndex = input.Vehicle.StartIndex
// measure the cost between location in haversine meters
measurer := measure.HaversineByIndex(points)
// Build the Vehicle model input
vehicleInput := vehicleschema.Vehicle{
VehicleID: input.Vehicle.ID,
Locations: requests,
Start: input.Vehicle.StartIndex,
End: input.Vehicle.EndIndex,
}
// Use the default model
root, err := vehicle.DefaultModel(vehicleInput, measurer)
if err != nil {
return nil, err
}
opt.Tags["measurer"] = measurer
return solve.Minimizer(root, opt), nil
}

This is all we need to do! go build and we now have a vehicle router for our coffee business.