nextmv Docs

Using Hop

Using Hop

Sometimes, examples help make abstract concepts a bit more concrete. Let's route a pedicab along the shortest path to pick up and drop off passengers.

Note: the following is for demonstrating how to use Hop for custom modeling. Practically, this model is easier to implement using HopM's more performant Vehicle (TSP) model. See Using HopM for more detail.

Problem Definition

Consider the following JSON. This might be something we'd see in a real implementation of a routing system. It has a single pedicab with a capacity of 2, meaning they can carry two riders at once, and a current location. Finally, there is a list of requests that have not yet been routed. These consist of pickup and drop-off location pairs, with the pickups coming first in each pair.

{
"Driver": {
"Name": "Mooney",
"Capacity": 2,
"Location": [-122.0490, 37.3806]
},
"Requests": [
[[-122.0802, 37.3937], [-122.0940, 37.3938]],
[[-122.0606, 37.3990], [-122.0660, 37.3968]],
[[-122.0589, 37.3945], [-122.0551, 37.3906]],
[[-122.0728, 37.3790], [-122.0939, 37.3800]],
[[-122.0848, 37.3820], [-122.0778, 37.3878]],
[[-122.0624, 37.3769], [-122.0772, 37.3912]],
[[-122.0514, 37.3713], [-122.0806, 37.3695]]
]
}

We refer to this structure as our "schema." Let's build a solver which takes in this input schema and creates a system state (i.e. a driver route) minimizing total distance traveled.

The schema Package

First, we need to provide a structure for reading in our input JSON. Our input is a driver and a set of requests.

// Input has a Driver and their Requests.
type Input struct {
Driver Driver
Requests []Request
}

Driver and Request are types we define.

// A Driver has a Name, Capacity, and Location.
type Driver struct {
Name string
Capacity int
Location Location
}
// Request is an array of pickup and dropoff locations.
type Request [2]Location

A Location has methods for accessing its longitude and latitude, as well as MetersTo for estimating the distance between two stops.

package schema
import (
"math"
"github.com/nextmv-io/code/hopm/measure"
)
// A Location specifies a Longitude and Latitude.
type Location [2]float64
func (l Location) lon() float64 { return l[0] }
func (l Location) lat() float64 { return l[1] }
// MetersTo approximates meters from one location to another one. This can be
// any function that approximates distance or time. This is called as needed by
// the search.
func (l Location) MetersTo(l2 Location) int {
points := []measure.Point{{l.lon(), l.lat()}, {l2.lon(), l2.lat()}}
m := measure.HaversineByIndex(points)
meters := m.Cost(0, 1)
return int(math.Round(meters))
}

We're using a HopM measurer for distance calculation in this example. We could just as easily request map distance from a map server, run a model of some kind, or look up distances in a file. Even though distance traveled is core to the optimization, Hop doesn't require us to provide it up-front. Instead, we can lazily compute distances as they are needed in the search.

The cmd Package

A runner is responsible for reading data into a structure we define, parsing runner and solver options from the environment and command line flags, and writing the solutions returned by a solver. Hop comes with pre-built model runners for different environments that make building binary artifacts trivial. The cmd package stores the main.go and data files for our command line runner (in pedicab-cli) and our test runner (in pedicab-test). Let's walk through the steps to build the pedicab-cli artifact which solves our pedicab routing problem. For details on using the test runner, please refer to test runners.

The main Function

In the code below, we pass our solver function into our command line runner. That's it!

package main
import (
"github.com/nextmv-io/templates/pedicab/dispatch"
"github.com/nextmv-io/code/hop/run/cli"
)
func main() {
cli.Run(dispatch.Solver)
}

The dispatch package

We now define all the structures and methods required to build a solver in our dispatch package.

The Solver Function

We assume we have an Input structure as defined in our schema package. The runner handles unmarshaling it for us. The Solver function constructs a root state (we'll define this in a bit) from input data and solver options and returns a Minimizer. We can use this to, you guessed it, find the shortest route.

// Solver constructs root state from inputs and options and returns a Minimizer.
func Solver(input schema.Input, opt solve.Options) (solve.Solver, error) {
root, err := root(input)
if err != nil {
return nil, err
}
return solve.Minimizer(root, opt), nil
}

The Root State

In order to define the root state, we must first introduce two new concepts (we'll dive into the code for these later): actor and system. Actors are autonomous beings in the solver that do things and consequently change state. The system is a collection of actors along with other bookkeeping data.

The system changes its state over time just like an actor. In this example, we have a single actor (driver), so our system state is essentially our actor state. We can think of the root state of the solver as the system starting point. In this example, our starting point is simply a driver "actor" and pedicab requests without any routing decisions. The driver actor's starting state is defined by the input data. We're merely taking our input data and molding it into an actor state and a system state construct so the solver can have a starting point to solve our problem.

We then test to make sure that our driver has nonzero capacity. Otherwise, they won't be able to pick anyone up. After that, we construct a "domain" which contains the index of every request and assign it to the field pickups on our system state.

pickups is a model.IntDomain, which is part of Hop's modeling interface. Our state will have two of these, one containing the index of every pickup our driver can go to from a given state, and one containing the index of every drop- off they could go to. In our root state, the driver hasn't picked up any of the requests yet, so we are allowed to append any pickup to the path, but not any drop-offs. Those will come later.

// Root returns the root state of the pedicab model.
func root(input schema.Input) (state, error) {
driver := Driver{
State: input.Driver,
}
root := state{
Driver: driver,
Requests: input.Requests,
}
if root.Driver.State.Capacity < 1 {
return state{}, errors.New("no capacity")
}
// Pedicab must go to a pickup first.
if n := len(input.Requests); n > 0 {
root.pickups = model.Domain(model.Range(0, n-1))
}
return root, nil
}

A Hop Routing Model

Now, let's build a model to route our driver. This model gets passed into our solver as methods on the root state we just created. A Hop model has to implement the model.State interface. This means it has to have a Feasible method and a Next method.

The Feasible method should return true if the system state meets our operational requirements. In this case that means every pickup and drop-off is part of the path. This will be true when the pickups and dropoffs domain values are both empty. Remember: in root we added all the pickup indices to the pickups domain, so the root state is not feasible.

// Feasible is true if all locations are in the path.
func (s state) Feasible() bool {
return s.pickups.Empty() && s.dropoffs.Empty()
}

Our Next method should create all the system states that are one hop away from a given state. For instance, calling Next on the root state creates a new state for each pickup. It adds that pickup to the end of the driver's path, adjusts the distance the driver has to travel, decrements their capacity, and updates the pickups and dropoffs domains for that state (visiting pickup n means we can no longer visit that pickup, but we can now visit its drop-off).

Let's assume we have pickup and dropoff methods on our state type that create those states for us. Then, the Next method is pretty simple. Note the use of the Iterator method on our domains. This provides an efficient way of looping over their values.

// Next appends each feasible stop to the current path.
func (s state) Next() model.Expander {
next := []model.State{}
// Pedicab must have capacity to do a pickup.
if s.Driver.State.Capacity > 0 {
for it := s.pickups.Iterator(); it.Next(); {
next = append(next, s.Pickup(it.Value()))
}
}
// Dropoffs give back capacity, so they don't need checking.
for it := s.dropoffs.Iterator(); it.Next(); {
next = append(next, s.Dropoff(it.Value()))
}
return expand.Eager(next...)
}

If all we wanted to do was find feasible routes, the Hop model piece of our code would be complete. Since we're trying to minimize route length, we have to tell Hop what the value of a state is. Let's assume that is contained in the Distance field.

// Value of the path is its distance in meters.
func (s state) Value() int {
return s.Driver.Distance
}

A Bounds method isn't required, but most of the time it's pretty useful. Since we are modeling by appending to our driver's intended path, we know that the value of subsequent states can only increase. We tell Hop this information to help it direct its search for solutions.

// Bounds on the distance from a partial path can only increase.
func (s state) Bounds() model.Bounds {
return model.Bounds{Lower: s.Value(), Upper: math.MaxInt64}
}

Driver actor

As we mentioned before, a Driver actor is an autonomous being that does things and helps us keep track of system state as the Solver finds our solution. It has pickup and dropoff methods which set the capacity of its new state. These methods also update the driver's location and distance. We keep a pointer to the previous state so we can generate a full path later. This is more efficient than copying a path slice every time we update the driver's state.

// Driver is an actor which contains the Driver state data along with
// bookkeeping features to keep track of its state while moving through hop.
type Driver struct {
State schema.Driver
Distance int
previous *Driver
}
// Pickup a request -> new driver state.
func (d Driver) pickup(loc schema.Location) Driver {
state := schema.Driver{
Name: d.State.Name,
Capacity: d.State.Capacity - 1,
Location: loc,
}
return Driver{
State: state,
Distance: d.Distance + d.State.Location.MetersTo(loc),
previous: &d,
}
}
// Dropoff a request -> new driver state.
func (d Driver) dropoff(loc schema.Location) Driver {
state := schema.Driver{
Name: d.State.Name,
Capacity: d.State.Capacity + 1,
Location: loc,
}
return Driver{
State: state,
Distance: d.Distance + d.State.Location.MetersTo(loc),
previous: &d,
}
}

We want our JSON output to contain the driver's full path, so we add a MarshalJSON method, which calls path. The path method constructs a path slice from the driver's previous state and current state.

// MarshalJSON structures nice JSON output for us.
func (d Driver) MarshalJSON() ([]byte, error) {
return json.Marshal(map[string]interface{}{
"Name": d.State.Name,
"Capacity": d.State.Capacity,
"Distance": d.Distance,
"Location": d.State.Location,
"Path": d.path(),
})
}
// Path the driver is routed to follow.
func (d Driver) path() []schema.Location {
if d.previous == nil {
return []schema.Location{d.State.Location}
}
return append(d.previous.path(), d.State.Location)
}

The System state

Now we can construct our system state. A state is just a driver actor and requests (constructed from our input data) along with domains representing the choices available to us (i.e. the pickups and drop-offs we can visit) in a given state.

type state struct {
Driver Driver
Requests []schema.Request
pickups model.IntDomain // Pickups driver can go to next
dropoffs model.IntDomain // same for Dropoffs
}

The Pickup method creates a new state by appending the pickup of a request to the driver's path and updating the pickups and dropoffs domains. We pass around the request data for convenient access.

// Pickup a request -> new state.
func (s state) Pickup(request int) state {
return state{
Driver: s.Driver.pickup(s.Requests[request][0]),
Requests: s.Requests,
pickups: s.pickups.Remove(request),
dropoffs: s.dropoffs.Add(request),
}
}

Similarly, Dropoff does the same thing for a drop-off.

// Dropoff a request -> new state.
func (s state) Dropoff(request int) state {
return state{
Driver: s.Driver.dropoff(s.Requests[request][1]),
Requests: s.Requests,
pickups: s.pickups,
dropoffs: s.dropoffs.Remove(request),
}
}

Running Models

OK, we're ready to build and run our model! First, let's compile it into an artifact.

$ go build -o pedicab-cli
$ ls -hl pedicab-cli
-rwxr-xr-x 1 ryan staff 3.5M Sep 3 11:20 pedicab-cli

Now we have a 3.5 mb binary that reads input data in JSON format, decides how to route a driver, and encodes those decisions back into a new state. It's easy to integrate with, and supports all the Hop runner and solver configuration flags.

Here's how we run it: we use the -hop.runner.output.solutions flag to tell Hop to only print out the last solution. We could also specify this with the environment variable HOP_RUNNER_OUTPUT_SOLUTIONS. You can run ./pedicab-cli -h for a complete list of flags.

cat data/input.json | ./pedicab-cli -hop.runner.output.solutions last | jq

You should see something like this:

{
"hop": {
"version": "v0.7.0"
},
"options": {
"diagram": {
"restrictor": {
"type": "github.com/nextmv-io/code/hop/solve/diagram/restrict.value"
},
"width": 10
},
"search": {
"buffer": 100,
"queuer": {
"type": "github.com/nextmv-io/code/hop/solve/queue.depth"
},
"searcher": {
"type": "github.com/nextmv-io/code/hop/solve/search.local"
}
},
"sense": "min"
},
"state": {
"Driver": {
"Capacity": 2,
"Distance": 15281,
"Location": [
-122.0551,
37.3906
],
"Name": "Mooney",
"Path": [
[
-122.049,
37.3806
],
[
-122.0514,
37.3713
],
[
-122.0624,
37.3769
],
[
-122.0806,
37.3695
],
[
-122.0728,
37.379
],
[
-122.0772,
37.3912
],
[
-122.0802,
37.3937
],
[
-122.094,
37.3938
],
[
-122.0939,
37.38
],
[
-122.0848,
37.382
],
[
-122.0778,
37.3878
],
[
-122.0606,
37.399
],
[
-122.066,
37.3968
],
[
-122.0589,
37.3945
],
[
-122.0551,
37.3906
]
]
},
"Requests": [
[
[
-122.0802,
37.3937
],
[
-122.094,
37.3938
]
],
[
[
-122.0606,
37.399
],
[
-122.066,
37.3968
]
],
[
[
-122.0589,
37.3945
],
[
-122.0551,
37.3906
]
],
[
[
-122.0728,
37.379
],
[
-122.0939,
37.38
]
],
[
[
-122.0848,
37.382
],
[
-122.0778,
37.3878
]
],
[
[
-122.0624,
37.3769
],
[
-122.0772,
37.3912
]
],
[
[
-122.0514,
37.3713
],
[
-122.0806,
37.3695
]
]
]
},
"statistics": {
"bounds": {
"lower": 0,
"upper": 15281
},
"search": {
"generated": 708016,
"filtered": 410337,
"expanded": 297679,
"reduced": 0,
"restricted": 297679,
"deferred": 708016,
"explored": 297665,
"solutions": 50
},
"time": {
"elapsed": "1.315829354s",
"start": "2021-03-02T19:18:00.185251-05:00"
},
"value": 15281
}
}

Alternatively, you can use the -hop.runner.input.path and/or -hop.runner.output.path flags if you prefer:

./pedicab-cli -hop.runner.input.path data/input.json \
-hop.runner.output.solutions last \
-hop.runner.output.path data/output.json

That's a lot of information. Let's unpack it a bit.

By default, the Hop CLI runner reads input data from standard input and writes solutions to standard output. Both input and output paths can be changed via command-line arguments, as seen in the example above. In our model, we're reading in input, creating a root system state, making decisions to update that state, then writing it out. That's what we see in the state field. Hop treats the input as the current state, and it is proposing a desired future state to us. You may have noticed that our Hop model looks a lot like a state machine. This is intentional. If we model the business rules of a system this way, then it's easier to reason about and easier to test. Our code also gets a lot cleaner and more succinct.

There are three other sections in the output. The first is called hop and just gives us the version of Hop that our model was built with.

After that comes options. This section contains important environment variables, such as the restriction diagram width, components that Hop uses to construct decision diagrams, search components and configuration, and the objective sense. If you want to compare results produced under different conditions, you can use these environment variables to define cohorts. Hop is an extensible system. Everything from the priority queue used for storing nodes for future exploration to the way states are chosen in the restriction diagram can be overridden with custom components. Hop lets us know how its behavior is changed, if at all.

Finally, we have search statistics. This section gives us bounds on the final state; information about the number of states that were deferred during search, explored, and so on; the amount of time it took to find this state; and the value of that final state.

The following map shows the optimal route of our driver. Hopefully this gives you a feel for what modeling with Hop is like and how it can be integrated into a production environment.

Optimal pedicab route