Router engine
Overview of the router engine.
The router engine (router) is a convenient, simple interface for solving various types of vehicle routing problems (VRP) and single vehicle problems (commonly known as the traveling salesman problem, TSP).
router is built on top of the two other Nextmv engines:
  • vehicle engine: routes stops that are assigned to a vehicle, and the
  • fleet engine: assigns stops to vehicles and routes them using an internal vehicle engine.
router employs a hybrid solver with two search strategies: ALNS and Decision Diagrams. Several default features are provided with router, such as measures, to make routing problems easier to solve.

Get started with router

router receives a set of stops that must be serviced by a fleet of vehicles and a list of options to configure. It returns routes for each vehicle, a list of unassigned stops (if any), and search output statistics. To learn how to use router, start with the basic tutorial. We also suggest visiting the go package docs. Once the godoc server has been launched, you can view the route package docs.

Options

The router engine is configured through a list of options. Options are used to customize your routing app. They can be passed directly to the NewRouter function or through the options method. Options are composable, meaning any number of options can be passed (or none at all).
The following is a list of short tutorials on using the different options. Unless otherwise noted, options work independently of each other, so tutorials can be viewed in any order.
  • Capacity: Set capacities for vehicles and quantities (demanded or offered) at stops.
  • Precedence: Add pickups and deliveries or specify multiple pickups before dropoffs and vice versa.
  • Services: Add times required to service stops.
  • Windows: Configure time windows for stops.
  • Attribute: Restrict stop-to-vehicle matching based on compatibility attributes.
  • LimitDurations: Set travel time limits for routes.
  • LimitDistances: Set distance limits for routes.
  • Unassigned: Use penalties to discourage but permit unassigned stops (useful when a problem is infeasible).
  • Grouper: Customize the assigner to determine which stops must be served together along the same route (part of the same group).
  • ServiceGroups: Add times required to service a group of stops.
  • Starts & Ends: Determine locations where a vehicle should start and/or end its route. This option may be used to set up depots, as in the traditional definition of a VRP.
  • Shifts: Set shifts for vehicles in which the routes have to operate. It also enables estimated time of arrival and departure in the output.
  • Backlogs: Establish a pre-assigned route for vehicles.
  • Velocities: Add velocities to vehicles to be used with the default Haversine TravelTimeMeasures.
  • InitializationCosts: Add initialization costs to vehicles.
  • Alternates: Specify a set of alternate stops per vehicle of which exactly one stop will be assigned to the vehicle.
  • Update: Personalize the value function and bookkeeping of custom data.
  • Limits: Set custom limits for routes, based on custom measures.
  • Constraint: Create a custom constraint that restricts how stops are routed for a vehicle.
  • ValueFunctionMeasures & TravelTimeMeasures: Customize the measure (cost of going from one location to another) that is optimized for each vehicle and the time measure used for keeping track of time.
  • Filter: Create a custom filter that restricts which stops are eligible to be serviced by which vehicles.
  • Output: Change the output marshalled by the engine.
  • Feasible & Optimal: Configure solver search options.
  • Minimize & Maximize: Set the solver type to be a minimizer or maximizer.
  • Selector: Customize the assigner to determine the order in which stops are selected for assignment.
  • Sorter: Customize the assigner to determine the order in which vehicles are selected for assignment.
  • Operators, Acceptor & Threads: Customize ALNS implementation.
Export as PDF
Copy link