# README
Nextroute
Welcome to Nextmv's Nextroute, a feature-rich Vehicle Routing Problem (VRP) solver written in pure Go. Designed with a focus on maintainability, feature-richness, and extensibility, Nextroute is built to handle real-world applications across all platforms that Go (cross)compiles to.
Our goal is not to compete on specific VRP type benchmarks, but to provide a robust and versatile tool that can adapt to a variety of routing use-cases. Whether you're optimizing the routes for a small fleet of delivery vans in a city or managing complex logistics for a global supply chain, Nextroute is equipped to help you find efficient solutions.
You can work with Nextroute in a variety of ways:
- Go package: Import the
nextroutepackage in your Go project and use the solver directly. - Python package: Use the
nextroutePython package as an interface to the Go solver.
Features
| Feature | Description |
|---|---|
| Alternate stops | Specify a set of alternate stops per vehicle for which only one should be serviced. |
| Compatibility attributes | Specify which stops are compatible with which vehicles. |
| Capacity | Set capacities for vehicles and quantities (demanded or offered) at stops. |
| Cluster constraint | Enforce the creation of clustered routes. |
| Cluster objective | Incentivize the creation of clustered routes. |
| Custom constraints | Implement custom constraints with Nextmv SDK. |
| Custom data | Add custom data that is preserved in the output. |
| Custom matrices | Use custom matrices to achieve more precise drive time. |
| Custom objectives | Implement custom objectives with Nextmv SDK. |
| Custom operators | Implement custom operators with Nextmv SDK. |
| Custom output | Create a custom output for your app. |
| Distance matrix | Specify a distance matrix in the input that provides the distance of going from location A to B. |
| Duration matrix | Specify a duration matrix in the input that provides the duration of going from location A to B. |
| Duration groups | Specify a duration that is added every time a stop in the group is approached from a stop outside of the group. |
| Early arrival time penalty | Specify a penalty that is added to the objective when arriving before a stop's target arrival time. |
| Late arrival time penalty | Specify a penalty that is added to the objective when arriving after a stop's target arrival time. |
| Map data in cloud | Calculates duration and distance matrices using a hosted OSRM map service when running on Nextmv Cloud. Note that map data is a paid feature. |
| Maximum route distance | Specify the maximum distance that a vehicle can travel. |
| Maximum route duration | Specify the maximum duration that a vehicle can travel for. |
| Maximum route stops | Specify the maximum stops that a vehicle can visit. |
| Maximum wait time | Specify the maximum time a vehicle can wait when arriving before the start time window opens at a stop. |
| Minimum route stops | Specify the minimum stops that a vehicle should visit (applying a penalty). |
| Nextcheck | Check which stops can be planned or why stops have been unplanned. |
| Precedence | Add pickups and deliveries or specify multiple pickups before deliveries and vice versa. |
| Stop duration | Specify the time it takes to service a stop. |
| Stop duration multiplier | Specify a multiplier on time it takes a vehicle to service a stop. |
| Stop groups | Specify stops that must be assigned together on the same route, with no further requirements. |
| Stop mixing | Specify properties of stops which can not be on the vehicle at the same time. |
| Time windows | Specify the time window in which a stop must start service. |
| Unplanned penalty | Specify a penalty that is added to the objective to leave a stop unplanned when all constraints cannot be fulfilled. |
| Vehicle activation penalty | Specify a penalty that is added to the objective for activating (using) a vehicle. |
| Vehicle initial stops | Specify initial stops planned on a vehicle. |
| Vehicle start/end location | Specify optional starting and ending locations for vehicles. |
| Vehicle start/end time | Specify optional starting and ending time for a vehicle. |
License
Please note that Nextroute is provided as source-available software (not open-source). For further information, please refer to the LICENSE file.
Installation
-
Go
Install the Go package with the following command:
go get github.com/nextmv-io/nextroute -
Python
Install the Python package with the following command:
pip install nextroute
Usage
For further information on how to get started, features, deployment, etc., please refer to the official documentation.
Go
A first run can be done with the following command. Stand at the root of the repository and run:
go run cmd/main.go -runner.input.path cmd/input.json -solve.duration 5s
This will run the solver for 5 seconds and output the result to the console.
In order to start a new project, please refer to the sample app in the community-apps repository. If you have Nextmv CLI installed, you can create a new project with the following command:
nextmv community clone -a go-nextroute
Python
A first run can be done by executing the following script. Stand at the root of the repository and execute it:
import json
import nextroute
with open("cmd/input.json") as f:
data = json.load(f)
input = nextroute.schema.Input.from_dict(data)
options = nextroute.Options(SOLVE_DURATION=5)
output = nextroute.solve(input, options)
print(json.dumps(output.to_dict(), indent=2))
This will run the solver for 5 seconds and output the result to the console.
In order to start a new project, please refer to the sample app in the community-apps repository. If you have Nextmv CLI installed, you can create a new project with the following command:
nextmv community clone -a python-nextroute
Local benchmarking
To run the go benchmarks locally, you can use the following command:
go test -benchmem -timeout 20m -run=^$ -count 10 -bench "^Benchmark" ./...
In order to compare changes from a PR with the latest develop version, you can
use benchstat.
# on the develop branch (or any other branch)
go test -benchmem -timeout 20m -run=^$ -count 10 -bench "^Benchmark" ./...\
| tee develop.txt
# on the new branch (or any other branch)
go test -benchmem -timeout 20m -run=^$ -count 10 -bench "^Benchmark" ./...\
| tee new.txt
# compare the two
benchstat develop.txt new.txt
Versioning
We try our best to version our software thoughtfully and only break APIs and behaviors when we have a good reason to.
- Minor (
v1.^.0) tags: new features, might be breaking. - Patch (
v1.0.^) tags: bug fixes.
# Packages
Package check contains the schema for the check configuration.
Package main allows you to run a nextroute solver from the command line.
Package common provides common functionality for the nextroute plugin.
Package factory is a package containing factory functions for creating nextroute models.
Package observers holds functionality for creating observers of what is
going on in
*/.
Package schema provides the input and output schema for.
No description provided by the author
No description provided by the author
# Functions
DefaultSolveOptionsFactory creates a new SolveOptionsFactory.
DefaultSolverFactory creates a new SolverFactory.
Format formats a solution in basic format using the map function toSolutionOutputFn to map a solution to a user specific format.
NewAttributesConstraint returns a new AttributesConstraint.
NewCluster creates a new cluster component.
NewComposedPerVehicleTypeExpression returns a new ComposedPerVehicleTypeExpression.
NewConstantDurationExpression returns a new ConstantDurationExpression.
NewConstantExpression returns an expression that always returns the same value.
NewConstSolveParameter creates a new constant solve parameter.
NewDirectedAcyclicGraph connects NewDirectedAcyclicGraph.
NewDistanceExpression returns a DistanceExpression.
NewDurationExpression returns a DurationExpression where values of the expression are interpreted as durations in units of the given duration unit.
NewEarlinessObjective returns a new EarliestObjective construct.
NewExpressionObjective is the implementation of sdk.NewExpressionObjective.
NewFromStopExpression returns a FromStopExpression.
NewFromToExpression returns a FromToExpression.
NewHaversineExpression returns a new HaversineExpression.
NewLatestArrival returns a new LatestArrival construct.
NewLatestEnd returns a new LatestEnd construct.
NewLatestStart returns a new LatestStart construct.
NewMaximum creates a new maximum construct which can be used as constraint or as objective.
NewMaximumDurationConstraint returns a new MaximumDurationConstraint.
NewMaximumStopsConstraint returns a new MaximumStopsConstraint.
NewMaximumTravelDurationConstraint returns a new MaximumTravelDurationConstraint.
NewMaximumWaitStopConstraint returns a new MaximumWaitStopConstraint.
NewMaximumWaitVehicleConstraint returns a new MaximumWaitVehicleConstraint.
NewMeasureByIndexExpression returns a new MeasureByIndexExpression.
NewMeasureByPointExpression returns a new MeasureByPointExpression.
NewMinStopsObjective returns a new MinStopsObjective.
NewModel returns a new model.
NewModelExpressionIndex returns the next unique expression index.
NewModelStatistics returns a new model statistics implementation.
NewModelStopsDistanceQueries returns a new ModelStopsDistanceQueries.
NewMoveStops creates a new move and checks if the move is allowed and if so estimates the delta score.
NewNoMixConstraint returns a new NoMixConstraint.
NewNotExecutableMove creates a new empty non-executable move.
NewOperatorExpression returns a new BinaryExpression that uses the given operator function.
NewParallelSolveEvents creates a new instance of ParallelSolveEvents.
NewParallelSolver creates a new parallel solver.
NewPreAllocatedMoveContainer creates a new PreAllocatedMoveContainer.
NewRandomSolution returns a random solution for the given model.
NewScaledDurationExpression returns a new DurationExpression scaled by the given multiplier.
NewSkeletonParallelSolver creates a new parallel solver.
NewSkeletonSolver creates a new solver for the given model.
NewSolution returns a new Solution.
NewSolutionPlanUnitCollection returns a new SolutionPlanUnitCollection.
NewSolutionStopGenerator return a solution stop iterator of a move.
NewSolveEvents creates a new instance of Solve.
NewSolveOperator returns a new solve operator.
NewSolveOperatorPlan creates a new solve operator for nextroute that plans units.
NewSolveOperatorRestart creates a new solve-operator that restarts the solver after a certain number of iterations without improvement.
NewSolveOperatorUnPlan creates a new SolveOperatorUnPlan.
NewSolveOperatorUnPlanLocation creates a new NewSolveOperatorUnPlanLocation.
NewSolveOperatorUnPlanUnits creates a new SolveOperatorUnPlanUnits.
NewSolveOperatorUnPlanVehicles creates a new SolveOperatorUnPlan.
NewSolveParameter creates a new solve parameter.
NewSolver creates a new nextroute solver using the given model and options.
NewSolverOperatorAnd creates a new solve-and-operator.
NewSolverOperatorOr creates a new solve-or-operator.
NewStopBalanceObjective returns a new StopBalanceObjective.
NewStopDurationExpression returns a new StopDurationExpression.
NewStopExpression returns a StopExpression.
NewStopPosition returns a new StopPosition.
NewStopTimeExpression returns a new StopTimeExpression.
NewSuccessorConstraint returns a new SuccessorConstraint.
NewSumExpression returns a new SumExpression.
NewSweepSolution returns a solution for the given model using the sweep heuristic.
NewTermExpression returns a new TermExpression.
NewTimeDependentDurationExpression returns a new TimeDependentDurationExpression.
NewTimeExpression returns a new TimeExpression.
NewTimeIndependentDurationExpression returns a new TimeInDependentDurationExpression.
NewTravelDurationExpression returns a new TravelDurationExpression.
NewTravelDurationObjective returns a new TravelDurationObjective.
NewUnPlannedObjective returns a new UnPlannedObjective.
NewVehiclesDurationObjective returns a new VehiclesDurationObjective.
NewVehiclesObjective returns a new VehiclesObjective.
NewVehicleStatistics returns a new vehicle statistics implementation.
NewVehicleTypeDistanceExpression returns a VehicleTypeDistanceExpression.
NewVehicleTypeDurationExpression returns a new VehicleTypeDurationExpression.
NewVehicleTypeFromToExpression returns a VehicleTypeFromToExpression.
NewVehicleTypeValueExpression returns a VehicleTypeValueExpression.
NoPositionsHint returns a new StopPositionsHint that does not skip the vehicle and does not contain a next stop.
RandomSolutionConstruction returns a random solution by populating the empty input with a random plan unit.
SequenceGeneratorChannel generates all possible sequences of solution stops for a given plan planUnit.
SkipVehiclePositionsHint returns a new StopPositionsHint that skips the vehicle.
SolutionMoveStopsGenerator generates all possible moves for a given vehicle and plan unit.
SolutionMoveStopsGeneratorChannel generates all possible moves for a given vehicle and plan unit.
SolutionMoveStopsGeneratorChannelTest is here only for testing purposes.
SolutionMoveStopsGeneratorTest is here only for testing purposes.
SweepSolutionConstruction returns a solution by planning the plan units in order of a radar sweep around the depot.
UnplanIsland un-plans planUnit and all stops (with their plan-units) that are located at the same location in the same vehicle and are within the given distance of the stops in planUnit not necessary on the same vehicle.
UnplanVehicle un-plans all stops of a vehicle that are not fixed.
Version returns the version of the nextroute module.
# Constants
AtEachSolution indicates that the constraint should be checked at each solution.
AtEachStop indicates that the constraint should be checked at each stop.
AtEachVehicle indicates that the constraint should be checked at each vehicle.
Constant is a constant cost function.
CrazyExpensive is a function that is so expensive that it should never be used.
ExponentialStop is an exponential cost function with respect to the number of stops.
ExponentialVehicle is an exponential cost function with respect to the number of vehicles.
Iterations is the key for the iterations performed.
LinearStop is a linear cost function with respect to the number of stops.
LinearVehicle is a linear cost function with respect to the number of vehicles.
Never indicates that the constraint should never be checked.
OnArrival refers to the Arrival at a stop.
OnEnd refers to the End at a stop.
OnStart refers to the Start at a stop.
QuadraticStop is a quadratic cost function with respect to the number of stops.
QuadraticVehicle is a quadratic cost function with respect to the number of vehicles.
# Variables
CheckViolations is a list of all possible values for CheckedAt.
NotExecutableMove returns a constant new empty non-executable move.
# Structs
BaseEvent1 is a base event type that can be used to implement events with one payload.
BaseEvent2 is a base event type that can be used to implement events with two payloads.
BaseEvent3 is a base event type that can be used to implement events with three payloads.
BaseEvent4 is a base event type that can be used to implement events with four payloads.
FormatOptions are the options that influence the format of the output.
IntParameterOptions are the options for an integer parameter.
MixItem is an item that is used to specify the type of mix.
ParallelSolveEvents is a struct that contains events that are fired during a solve invocation of the parallel solver.
ParallelSolveOptions holds the options for the parallel solver.
PlateauOptions define how the solver should react to plateaus, i.e., periods without significant improvement in the best solution.
PreAllocatedMoveContainer is used to reduce allocations.
ProgressionEntry is a single entry in the progression of the solver.
SolutionInfo contains solutions and error if one raised.
A SolutionStop is a stop that is planned to be visited by a vehicle.
SolutionVehicle is a vehicle in a solution.
SolveEvents is a struct that contains events that are fired during a solve invocation.
SolveOptions holds the options for the solve process.
SolverOptions are the options for the solver and it's operators.
StopPosition is the definition of the change in the solution for a specific stop.
# Interfaces
Arc is a directed connection between two nodes ([ModelStops]) that specifies that the origin stop must be planned before the destination stop on a vehicle's route.
AttributesConstraint is a constraint that limits the vehicles a plan unit can be added to.
BinaryExpression is an expression that takes two expressions as input and returns a value.
Cluster is both a constraint and an objective that limits/prefers the vehicles a plan cluster will be added to.
Complexity is the interface for constraints that have a complexity.
ComposedPerVehicleTypeExpression is an expression that uses an expression for each vehicle type.
ConstantExpression is an expression that always returns the same value.
ConstraintDataUpdater is a deprecated interface.
ConstraintReporter is the interface that can be used by a constraint if it wants to report data about the constraint for a solution stop.
ConstraintSolutionDataUpdater is the interface than can be used by a constraint if it wants to store data with each solution.
ConstraintStopDataUpdater is the interface than can be used by a constraint if it wants to store data with each stop in a solution.
ConstraintTemporal is the interface that is implemented by constraints that are temporal.
Copier is the interface that all objects that can be copied must implement.
DefaultExpression is an expression that has a default value if no other values are defined.
DirectedAcyclicGraph is a set of nodes (of type [ModelStop]) connected by arcs that does not contain cycles.
DistanceExpression is an expression that returns a distance.
DurationExpression is an expression that returns a duration.
EarlinessObjective is a construct that can be added to the model as an objective.
ExpressionObjective is an objective that uses an expression to calculate an objective.
FromStopExpression is an expression that has a value for each from stop.
FromToExpression is an expression that has a value for each combination of from and to stop.
Identifier is an interface that can be used for identifying objects.
ImmutableSolutionPlanUnitCollection is a collection of solution plan units.
InitialSolutionObserver is an observer that is used to detect the constraint that is violated by the initial solution.
InterestedInBetterSolution is an interface that can be implemented by solve-operators that are interested in being notified when a better solution is found.
InterestedInStartSolve is an interface that can be implemented by solve-operators that are interested in being notified when the solver starts solving.
LatestArrival is a construct that can be added to the model as a constraint or as an objective.
LatestEnd is a construct that can be added to the model as a constraint or as an objective.
LatestStart is a construct that can be added to the model as a constraint or as an objective.
Locker is an interface for locking a constraint.
Maximum can be used as a constraint or an objective that limits the maximum cumulative value can be assigned to a vehicle type.
MaximumDurationConstraint is a constraint that limits the duration of a vehicle.
MaximumStopsConstraint is a constraint that limits the maximum number of stops a vehicle type can have.
MaximumTravelDurationConstraint is a constraint that limits the total travel duration of a vehicle.
MaximumWaitStopConstraint is a constraint that limits the time a vehicle can wait between two stops.
MaximumWaitVehicleConstraint is a constraint that limits the accumulated time a vehicle can wait at stops on its route.
Model defines routing problem.
ModelConstraint is the interface that all constraints must implement.
ModelData is a data interface available on several model constructs.
ModelExpression is an expression that can be used in a model to define values for constraints and objectives.
ModelObjective is an objective function that can be used to optimize a solution.
ModelObjectiveSum is a sum of model objectives.
ModelObjectiveTerm is a term in a model objective sum.
ModelPlanStopsUnit is a set of stops.
ModelPlanUnit is a plan unit.
ModelPlanUnitsUnit is a set of plan units.
ModelStatistics provides statistics for a model.
ModelStop is a stop to be assigned to a vehicle.
ModelStopsDistanceQueries is an interface to query distances between stops.
ModelVehicle is a vehicle in the model.
ModelVehicleType is a vehicle type.
NoMixConstraint limits the order in which stops are assigned to a vehicle based upon the items the stops insert or remove from a vehicle.
ObjectiveDataUpdater is deprecated.
ObjectiveSolutionDataUpdater is the interface than can be used by an objective if it wants to store data with each solution.
ObjectiveStopDataUpdater is the interface than can be used by an objective if it wants to store data with each stop in a solution.
ParallelSolveInformation holds the information about the current parallel solve run.
ParallelSolver is the interface for parallel solver.
Progressioner is an interface that can be implemented by a solver to indicate that is can return the progression of the solver.
RegisteredModelExpressions is the interface that exposes the expressions that should be registered with the model.
Solution is a solution to a model.
SolutionMove is a move in a solution.
SolutionMoveStops is a move in a solution.
SolutionObserved is an interface that can be implemented to observe the solution manipulation process.
SolutionObserver is an interface that can be implemented to observe the solution manipulation process.
SolutionPlanStopsUnit is a set of stops that are planned to be visited by a vehicle.
SolutionPlanUnit is a set of stops that are planned to be visited by a vehicle.
SolutionPlanUnitCollection is a collection of solution plan units.
SolutionPlanUnitsUnit is a set of solution plan units.
SolutionStopGenerator is an iterator of solution stops.
SolutionStopViolationCheck is the interface that will be invoked on every update of a planned solution stop.
SolutionUnPlanObserver is an interface that can be implemented to observe the plan units un-planning process.
SolutionVehicleViolationCheck is the interface that will be invoked on every update of a last planned solution stop of a vehicle.
SolutionViolationCheck is the interface that will be invoked once all updates on a solution have been executed.
SolveInformation contains information about the current solve.
SolveOperator is a solve-operator.
SolveOperatorAnd is a solve-operator which executes a set of solve-operators in each iteration.
SolveOperatorOr is a solve-operator.
SolveOperatorPlan is a solve-operator that tries to plan all unplanned plan-units in each iteration.
SolveOperatorRestart is a solve operator that restarts the solver.
SolveOperatorUnPlan is a solve operator that un-plans units.
SolveOperatorUnPlanUnits is a solve-operator which un-plans all the stops of a vehicle.
SolveOperatorUnPlanVehicles is a solve-operator which un-plans all the stops of a vehicle.
SolveParameter is an interface for a parameter that can change during the solving.
Solver is the interface for the Adaptive Local Neighborhood Search algorithm (ALNS) solver.
StopDurationExpression is a ModelExpression that returns a duration per stop and allows to set the duration per stop.
StopExpression is an expression that has a value for each to stop.
StopPositionsHint is an interface that can be used to give a hint to the solver about the next stop position.
StopTimeExpression is a ModelExpression that returns a time per stop and allows to set the time per stop.
SuccessorConstraint is a constraint that disallows certain stops to be planned after other stops.
SumExpression is an expression that returns the sum of the values of the given expressions.
TermExpression is an expression that returns the product of the given factor and the value of the given expression.
TimeDependentDurationExpression is a DurationExpression that returns a value based on time on top of a base expression.
TimeExpression is a ModelExpression that returns a time.
TravelDurationExpression is an expression that returns a duration based on a distance and a speed.
TravelDurationObjective is an objective that uses the travel duration as an objective.
UnPlannedObjective is an objective that uses the un-planned stops as an objective.
VehicleFromToExpression is an expression that has a value for each combination of vehicle type, from and to stop.
VehiclesDurationObjective is an objective that uses the vehicle duration as an objective.
VehiclesObjective is an objective that uses the number of vehicles as an objective.
VehicleStatistics provides statistics for a vehicle.
VehicleTypeDistanceExpression is an expression that returns a distance per vehicle type and allows to set the duration per vehicle.
VehicleTypeDurationExpression is a ModelExpression that returns a duration per vehicle type and allows to set the duration per vehicle type.
VehicleTypeExpression is the base expression for VehicleTypeExpressions.
VehicleTypeValueExpression is a ModelExpression that returns a value per vehicle type and allows to set the value per vehicle type.
# Type aliases
Arcs is a collection of [Arc]s.
BinaryFunction is a function that takes two float64 values and returns a float64 value.
CheckedAt is the type indicating when to check a constraint when a move it's consequences are being propagated.
Cost is type to indicate the cost of a function.
Handler1 is a function that handles an event with one payload.
Handler2 is a function that handles an event with two payloads.
Handler3 is a function that handles an event with three payloads.
Handler4 is a function that handles an event with four payloads.
ModelConstraints is a slice of ModelConstraint.
ModelExpressions is a slice of ModelExpression.
ModelObjectives is a slice of model objectives.
ModelObjectiveTerms is a slice of model objective terms.
ModelPlanStopsUnits is a slice of model plan stops units .
ModelPlanUnits is a slice of plan units .
ModelPlanUnitsUnits is a slice of model plan units units .
ModelStops is a slice of stops.
ModelVehicles is a slice of ModelVehicle.
ModelVehicleTypes is a slice of vehicle types.
Move is a type alias for SolutionMoveStops.
SolutionMoves is a slice of SolutionMove.
SolutionObservers is a slice of SolutionObserver.
SolutionPlanStopsUnits is a slice of [SolutionPlanStopsUnit].
SolutionPlanUnits is a slice of [SolutionPlanUnit].
SolutionPlanUnitsUnits is a slice of [SolutionPlanUnitsUnit].
Solutions is a slice of solutions.
SolutionStops is a slice of SolutionStop.
SolutionUnPlanObservers is a slice of SolutionUnPlanObserver.
SolutionVehicles is a slice of solution vehicles.
SolveOperators is a slice of solve-operators.
SolveOptionsFactory is a factory type for creating new solve options.
SolveParameters is a slice of solve parameters.
SolverFactory is a factory type for creating new solver.
StopPositions is a slice of stop positions.
TemporalReference is a representation of OnArrival, OnEnd or OnStart as an enum.