Release Notes

Nextmv version 0.7.0 introduces a few important changes that improve time to first feasible solution, help with memory use management, and align product releases.

This release introduces breaking changes. All Nextmv customers migrating to Hop v0.7.0 will need to make a few changes to their models to ensure smooth operations.

Updating import paths

Before downloading v0.7.0, it is important to note that we’ve combined Hop and HopM into a single GitHub repository called code. This means import paths have changed (github.com/nextmv-io/hop is now github.com/nextmv-io/code/hop) and this must be reflected in your go get command.

go get github.com/nextmv-io/code/hop
go get github.com/nextmv-io/code/hopm

You’ll need to replace the old import paths manually inside your models. Under Files, you’ll need to find, edit, and replace the old import paths with the new ones. It’s also good practice to do a go mod tidy once you’ve made the import updates.

Updating Next method for expansion limits

We’ve introduced expansion limits in version 0.7.0 to improve time to first feasible solution and better manage memory use. This enhancement has a direct impact on the Next method. If you try go build, you will see a build error that shows the Next method is expecting a model.Expander but is instead returning []model.State.

Models without HopM components

Any user with a custom model that does not embed a HopM component should update their Next method to return an Eager expander.

We'll look at our n-queens model as an example.

For v0.6.6 and before:

// Next places a queen in each available column of the most constrained row.
func (b board) Next() []model.State {
    next := []model.State{}
    if row, ok := model.IntDomains(b).Smallest(); ok {
        for it := b[row].Iterator(); it.Next(); {
            next = append(next, b.place(row, it.Value()))
        }
    }
    return next
}

For v0.7.0 with Expanders:

// Next places a queen in each available column of the most constrained row.
func (b board) Next() model.Expander {
    next := []model.State{}
    if row, ok := model.IntDomains(b).Smallest(); ok {
        for it := b[row].Iterator(); it.Next(); {
            next = append(next, b.place(row, it.Value()))
        }
    }
    return expand.Eager(next...)
}

We use an Eager expander to maintain the same state space we had before this release. We could also use Lazy to return less child states. See the overview of solvers for more details on Expanders.

Models with HopM components

Any user with an embedded Hop component should update their Next method to return a Lazy expander.

We'll look at our dispatch model as an example. When we embed a HopM component like Fleet and need to access HopM's state for value function changes, our Next method is a wrapped HopM state.

For v0.6.6 and before:

func (s state) Next() []model.State {
  next := []model.State{}
  for _, n := range s.fleetState.Next() {
    next = append(next, state{
      fleetState:        n.(fleet.State),
      outputTransformer: s.outputTransformer,
    })
  }
  return next
}

For v0.7.0 with Expanders:

func (s state) Next() model.Expander {
  expander := s.fleetState.Next()
  if expander == nil {
    return nil
  }
  return expand.Lazy(func() model.State {
    if next := expander.Expand(); next != nil {
      return state{
        fleetState:        next.(fleet.State),
        outputTransformer: s.outputTransformer,
      }
    }
    return nil
  })
}

We use an Lazy expander to limit the number of states returned by default. See the overview of solvers for more details on Expanders.

Updating CLI and ENV options

Beginning with version 0.7.0, the hop.runner.output.solutions environment variable will now default to last instead of all. This default setting tells Hop to only output the final improving solution in a Hop model. If this is the desired behavior of your model, all you need to do is remove this line of code from your command line or env. If you desire to have it return all, you will need to set the runner options accordingly.

Nextmv Cloud is the fastest way to get started with Nextmv decision stack. This post explores a few common routing problem constraints, such as capacity and speed.

Read more

Great news! Hop v0.7.1 has shipped! This release and all the features are available to you with your next go get.

A few highlights include new methods and functions in Hop fleet and vehicle model, support for new turnkey constraints for vehicle-location compatibility and max route length, an introduction to Nextmv apps to provide a faster way to get started with Nextmv. A summary of added functionality is included below.

Hop fleet extensions

Exposed new information in Hop fleet

Assigned vehicles and locations

The new Assigned() (int, model.IntDomain) function gives access to the set of locations and the vehicle those locations were assigned to in the previous call to Next(). The function can be called on a fleet state and will return an index and an IntDomain. Note, if no locations were assigned, then an empty domain will be returned by the function. Previously, accessing this information required ranging and recomputing over all vehicles. We recommend using the new Assigned function for a more efficient approach.

Vehicle state

The new Vehicle(index int) vehicle.State function gives fast access to the state of a particular vehicle. The function takes an index of a vehicle (this can be passed from Assigned) and returns the vehicle state.

Added flexible assigner framework

This version introduces a flexible assigner framework to Hop to facilitate the addition of commonly used filters or constraints. To use the new assigner framework, you will need to specify three things:

• Location selector: Takes in state and returns an IntDomain representing the next locations to be assigned to vehicles. If nil, the minimum from the domain of remaining location indices will be taken by default.
• Location grouper: Specifies for a given index location, all locations (including the index location itself) that must be assigned with the same vehicle (e.g., if a pickup is assigned to a vehicle, then the drop off must also be assigned to that vehicle). A default location grouper function is provided for convenience.
• Vehicle filter: Takes in a list of vehicles, locations, and routes for those vehicles and returns an IntDomain representing valid combinations of vehicles and locations to be assigned next. New vehicle filters are detailed below.

Added new vehicle filters

Three vehicle filters are now supported in Hop fleet and made available through the assigner framework. The following vehicle filters are available:

• Max route length filter: Prevents the assignment of locations to vehicles that will exceed a max route length (measured in time or distance between two locations).
• Capacity filter: Prevents the assignment of locations to vehicles that will exceed vehicle capacity constraints (e.g., a car with only one seat for a passenger will not be assigned to a pickup location with >1 passenger).
• Attributes filter: Prevents the assignment of locations to vehicles that are not eligible due to compatibility of vehicle and location attributes (e.g., a location with a pick up that requires refrigeration will not be assigned to a vehicle without refrigeration)

Note, because vehicle filters serve as a pre-filter they also help to improve search efficiency. We recommend customers use the built-in vehicle filters (when appropriate) for this reason.

Extended value function

Penalty cost for unassigned locations can now be included in the value function. The penalty cost will help to direct the search algorithm away from unassigned locations in solutions. Unassignment is still allowed, but can be penalized.

To add penalties for unassigned locations, specify an integer slice of UnassignedPenalities on the fleet struct. Locations can have different penalties (e.g., if there is a high priority locations that must be served, they can have higher penalties).

If no penalty is provided, the solver defaults to previous behavior (tries to assign everything, but some locations may still be unassigned).

Added access to the underlying vehicle model

A new function transform func(vehicle.State) vehicle.State has been added to CustomRouter to provide access to the underlying vehicle model. This enables constraints such as earliness and lateness to be considered as part of the vehicle model search to find improving results faster. ETAs and time windows can now be tracked when planning a vehicle route as well.

Hop vehicle model extensions

Exposed new information in Hop vehicle

Accumulated cost

The accumulated cost for each stop in a route can be accessed using vehicle.State.Cost(index int) float64. This simplifies the calculation of an ETA as part of the value function.

Vehicle state constraints

The constraints of a vehicle state can be accessed using vehicle.State.Constraints(). This new method returns the constraints of vehicle at the state it was called on.

Cost on a window constraint

Window constraints specify hard time windows that need to be met. If a vehicle arrives early, a wait time will be enforced. The new vehicle.Coster interface specifies a Cost(index int) int method implemented by the Window constraint that captures both the accumulated measure and enforced wait time.

Added max route length constraint

The vehicle max route length constraint requires a measure, max route length, and a boolean to ignore the triangular inequality as input. Most customers using their own costs (e.g., a matrix measure) will want to set ignoreTriangular to TRUE. See the package docs for additional details.

Simplified measure specifications

Previously, separate point and index interfaces were implemented for each form of measurement (e.g., HaversineByPoint, HaversineByIndex, EuclideanByPoint, EuclideanByIndex, etc.). As we add new measures, we are moving to a more scalable system where only ByPoint is specified, and ByIndex is dynamically generated.

Use the new Indexed function to generate a ByIndex measure: Indexed(m ByPoint, points []Point) ByIndex. The function takes a ByPoint measure and a slice of points as input and returns a ByIndex measure.

While switching to the new implementation of indexed measures is not required to upgrade, we strongly recommend customers do so. The change will be required in future releases.

Support for Alternate locations

This release adds support for alternate location handling. The Vehicle input schema has a new field AlternateLocations of type IntDomain. This domain specifies a set of locations one of which has to be visited by the vehicle. One usage scenario is when the vehicle should go on a break, and there are multiple break locations. The model will choose the closest (as determined by the given measure) one. Additionally we added Alternate() (index, location int), which gives access to the index in the route at which the alternate location can be found as well as the actual location that is used from the set of alternate locations.

Introducing Nextmv apps

Apps provide a faster way to get started with Nextmv and can be used off-the- shelf or customized to your needs. The first Nextmv App is now available in the apps repo on GitHub. The first application is Dispatch, a base multi-vehicle fleet routing app with no pre-specified constraints. This base app is ready to use with Hop v0.7.1 and can be easily extended to include the new functionality detailed above. Stay tuned as we continue to add new apps.

Our Dispatch app on Nextmv Cloud supports a growing list of common constraints for representing the reality of your route planning and optimization problems. This blog post provides an introduction to target times, hard time windows, timeliness penalties, and unassigned penalties in Nextmv Cloud.

Read more

Nextmv version 0.8.0 is here! This release features significant performance improvements for solving complex routing problems with the addition of ALNS and brings Dash (simulation) into the code repo in GitHub. Version 0.8.0 introduces breaking changes that will need to be addressed prior to upgrading.

Note: Cloud customers are not affected by these changes at this time and we will notify you when v0.8.0 is available for use on Nextmv Cloud.

Dash

Moved to code monorepo

Before downloading v0.8.0, it is important to note that we’ve added Dash to the code monorepo on GitHub. This means import paths have changed (github.com/nextmv-io/dash is now github.com/nextmv-io/code/dash) and this must be reflected when using the go get command.

go get github.com/nextmv-io/code/dash

Hop

Heuristic modeling with ALNS (Adaptive Large Neighborhood Search)

This version includes the addition of support for adaptive large neighborhood search (ALNS), a heuristic solver for finding more improving solutions faster. The addition of ALNS brings significant performance improvements. This can be particularly beneficial when grouping many vehicles together in a fleet and solving large-scale routing problems.

ALNS is now supported in the vehicle and fleet engines by default. No additional upgrade steps are required to use ALNS for users employing vehicle.DefaultSolver(state, opt) or fleet.DefaultSolver(state, opt). However, for users employing solve.Minimizer(outputState, opt), solve.Minimizer(outputState,opt) will need to be replaced with vehicle.Solver(root, opt) or fleet.Solver(root, opt) to use ALNS in the vehicle or fleet engine, respectively.

Default operators and parameters are provided for use with ALNS. Custom inputs are supported if required. See the package docs for additional details. Further support will be provided for ALNS in vehicle and fleet engines in future releases.

Hop API changes

A context.Context argument has been added to the following method declarations:

• model.State.Next()
• solve.Solver.All()
• solve.Solver.Last()

While this argument is now required when calling implementations of these methods, it is not required that a user do anything with it. Its purpose is to empower a user to end a run sooner in the process of diagram construction, so as to better respect a prescribed time limit.

Aditionally, diagram node generation stops after n nodes. Previously, n nodes were explored, but many more may have been generated. Upgrading and not adjusting n may result in fewer good solutions, so higher n values may be required to achieve the same results.

Hop API additions

To support hybrid optimization with ALNS, two new interfaces have been added:

• solve.Hybrid
• solve.Inferrer

The first enables the combination of different solvers and the parallelization of multiple solvers. The second can be used to share results between solvers.

Engines (formerly HopM)

We have renamed HopM to engines. This means import paths have changed (github.com/nextmv-io/code/engines) and this must be reflected in your go get command.

go get github.com/nextmv-io/code/engines

Engines API changes

As above, a context.Context argument has been added to the following method declarations:

• fleet.Router.Feasible
• fleet.Router.Optimal
• fleet.Router.WarmFeasible

This argument is required when calling implementations of these methods. See above in Hop's "API Changes" section for some additional notes on this change.

Also, service times durations []int and maximum waiting times before each window waitMax []int now need to be provided when constructing a window measure. Previously, service and waiting times were part of a measure. Now, times are provided to a measure. This enables the specification of maximum wait time, for example.

Engines API additions

When using a CustomRouter, a function must now be passed in for each phase. Two new default functions are available for use (these are used for the DefaultRouter):

• fleet.SolverFuncGenerator
• fleet.AlnsSolverFuncGenerator

New methods have been added to the fleet Engine to enable the following:

• Set a vehicle's state (fleet.State.SetVehicle)
• Set list of locations for a vehicle (vehicle.State.SetLocations)
• Set and validate routes for a vehicle (vehicle.State.SetRoute)
• Specify a custom compatibility constraint for a vehicle and a location (fleet.CustomVehicleFilter())

Enforcement of assignment

Default UnassignedPenalties behavior has changed:

• If no unassigned penalties are provided, assignment will be enforced (note, this could result in no feasible solutions being returned).
• If unassigned penalties are provided, assignment will not be enforced. Unassignment will be discouraged (more or less, based on the penalty value).

If using a penalty to prevent unassigned locations, it is advised to remove it in order to benefit from the new default behavior for the fleet engine: if no UnassignedPenalties are provided, all locations are assigned a vehicle. Note, the enforcement of assignment could result in no feasible solutions being returned. To discourage (but still allow for some) unassigned locations, we suggest to add unassigned penalties (see best practices for more on unassignment penalties).

Measures

Measures API changes

Index interfaces, such as haversineByIndex and euclideanByIndex, will be soon deprecated. ByIndex measures should now be generated with the Indexed function.

Extend

There is a new suite of modules, called extend, which use third-party dependencies such as AWS Lambda or OSRM. This may be a breaking change as these same features used to be part of dash, hop and hopm (now engines). This means import paths have changed (github.com/nextmv-io/code/hopm/measure/osrm is now github.com/nextmv-io/code/extend/measure/osrm) and this must be reflected when using the go get command.

We've introduced heuristic solving with Adaptive Large Neighborhood Search (ALNS) to Hop. This brings substantial performance improvements to Hop, especially for customers with large fleets of vehicles and complex routing problems.

Read more

This release introduces multiple solutions for runs along with an easy way for customers to evaluate the returned solutions to help configure their Dispatch app. It also includes a UI overhaul for the Nextmv Cloud Console.

New solution evaluation charts

Three new charts are now available for visualizing existing output data: Solution Value Over Time, Solution Value Composition, and Vehicle Value Composition. These visualizations were added to provide additional understanding around returned solutions and can help with app configuration.

More user-friendly interface

We improved the overall design and layout of the Nextmv Cloud Welcome and Demo pages to create a better user experience as customers get started with Nextmv, navigate and configure their Dispatch app, and explore returned solutions.

Improvements and fixes

• Updated JSON input file overview and explanation on Welcome page with more details for getting started
• Added vehicle and stop counter subtext for input files to quickly size up a particular routing problem
• Added tooltips and graphics to facilitate understanding of various aspects in the Dispatch app such as JSON input field definitions and value function composition
• Updated color scheme in map results to be higher contrast and improved highlighting to facilitate better visual parsing of routes
• Added text-based route description for each vehicle in Results tab
• Introduced a new dropdown under Results tab for visualizing each returned solution on the map

Try Nextmv Cloud Console