Legacy

Using Nextmv routing app features

A how-to guide for using the different features of the Nextmv routing app

The router engine is deprecated. To read about our current vehicle routing engine documentation start reading here.

The Nextmv routing app is configurable through feature options that can be added to your input file.

The following is a list of short guides on how to use the different routing app options. The introductory example from the tutorial, where routes are created to visit seven landmarks in Kyoto using two vehicles, is used as a base for each of the below features. Unless otherwise noted, options work independently of each other so sections can be viewed in any order.

Note, you will need your Nextmv API key and the Nextmv CLI to use the Nextmv routing app. Log in to Nextmv and navigate to your account page to find your key. Keep it safe, as it alone provides unfettered access to the Nextmv API.

OptionDescription
AlternatesSpecify a set of alternate stops per vehicle of which exactly one stop will be assigned to the vehicle.
BacklogsEstablish a pre-assigned route for vehicles.
CapacitySet capacities for vehicles and quantities (demanded or offered) at stops.
Compatibility attributesRestrict stop-to-vehicle matching based on characteristics and requirements.
Duration groupsAdd times required to service a group of stops.
MeasuresDetermine the cost of routing a vehicle from one location to another.
PenaltiesSet penalities values to discourage earliness, lateness, and unassigned stops in solutions.
PrecedenceAdd pickups and deliveries or specify multiple pickups before dropoffs and vice versa.
Route limitsSet limits on the maximum route duration, route distance, or number of stops.
Solver runtime durationSet a limit on the solver runtime duration.
Stop groupsDefine which stops must be served together along the same route as part of the same group.
Time settingsDefine when certain routing events should take place for vehicles and stops with target times, hard windows, waiting times, shift start and end times, and stop duration.
Value functionDescribe the optimization objective you want to minimize, maximize, or satisfy depending on the options you add to your input file.
Vehicle costsAdd initialization costs to vehicles.

Alternates

The alternate_stops option can be used to define a set of suitable locations for a given stop for each vehicle (e.g., for a break, or for an item pick up at a grocery store), of which exactly one will be added to the vehicle's route automatically.

Alternate stops are defined with the alternate_stops attribute on root level of the input file. They have the same fields as a normal stop and adhere to the same constraints like, e.g. capacity or time windows. This can be used to introduce a break at a specific time and location (for scheduled breaks) or just location (for flexible breaks). A vehicle can reference one or more alternate stops with the alternate_stops field. The vehicle will be assigned exactly one stop from the list of alternate stops and, in addition, may be assigned normal stops.

As opposed to using backlogs and regular stops (where one stop can only be serviced by one vehicle), one alternate stop can be serviced by many different vehicles.

The aim of the example below is to define alternate stops (or breaks) for a vehicle. Note, this example also uses the capacity option for illustrative purposes.

Save the included input.json. Execute the example and you'll see from the output file that only one alternate stop was assigned to each vehicle. In this example, Nijō Castle was assigned to v1 and Kiyomizu-dera was assigned to v2.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "quantity": -1
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 },
      "quantity": -1
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 },
      "quantity": -1
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "quantity": 0
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "quantity": 0
    }
  ],
  "alternate_stops": [
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 },
      "quantity": -1
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "quantity": -1
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "alternate_stops": ["Nijō Castle", "Kiyomizu-dera"],
      "capacity": 3
    },
    {
      "id": "v2",
      "alternate_stops": ["Nijō Castle", "Kiyomizu-dera"],
      "capacity": 3
    }
  ]
}
Copy

Backlogs

The backlog options enables routes previously assigned to a vehicle (or backlog) to be assigned to the same vehicle. Backlogs are treated as flexible in the Nextmv routing app. Flexible backlogs ensure that stops in each vehicle's backlog are assigned to the same vehicle, while allowing for replanning (backlog order can change if a better route is found) and the insertion of new stops during a route in progress.

A fixed backlog in which new stops can only be appended to an assigned route must be managed outside of Nextmv, as these stops do not require optimization. In this case, be sure to set the start location and shift start time of the vehicle to the location and ETD of the last stop in the fixed backlog, and do not pass in any fixed backlog stops.

Flexible backlogs

The backlog property can be used for flexible backlogs, defined as an unordered list of stops. Each stop will be added to the vehicle's route in the cost-optimal order. Additionally, other stops from the input may be added to the vehicle's route.

Note, compatibility attributes can also be used to define backlogs. However, we recommend using backlog instead as some stops can go unassigned when using compatibility attributes for backlog.

The aim of the example below is to define backlogs for a vehicle.

Save the included input.json. Execute the example and you'll see from the output file that both stops, Arashiyama Bamboo Forest and Kinkaku-ji, which have been defined in a backlog for vehicle v1, are assigned to that vehicle.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "backlog": ["Arashiyama Bamboo Forest", "Kinkaku-ji"]
    },
    {
      "id": "v2"
    }
  ]
}
Copy

Capacity

If your vehicles need to transport something but have limited capacity, quantity and capacity are very useful attributes. capacity defines how much of a certain type of commodity/thing a vehicle can carry at maximum. It is defined on the individual vehicle (or globally in the defaults/vehicles section). The quantity defines how much a vehicle's capacity changes at a stop:

  • A negative quantity reduces the available capacity by the quantity at a stop (pickup operation),
  • A positive quantity defines how much is replenished / returned (dropoff operation).

Naturally, only include positive quantity stops if it complements a negative quantity.

Although the number of stops can be limited per vehicle by setting -1 quantities to all of them, we recommend using the route limit functionality for improved performance.

Quantities of different dimensions do not count towards the same capacity, e.g., pallets and bins can be counted directly but may both consume the same shared space. If this is needed, they can be combined in a more abstract dimension like weight or volume.

The aim of this example is to add a quantity demanded to stops and a limited capacity to vehicles.

Save the included input.json. Execute the example and you'll see from the output file that the capacity of each vehicle is not exceeded and the stops that can be assigned are done so in a fashion that minimizes the route distance.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "quantity": -1
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "quantity": -1
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 },
      "quantity": -1
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 },
      "quantity": -1
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 },
      "quantity": -1
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "quantity": -1
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "quantity": -1
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "capacity": 3
    },
    {
      "id": "v2",
      "capacity": 3
    }
  ]
}
Copy

Single capacity and quantity values

Specifying capacity and quantity as scalar values (e.g., "capacity": 50 and "quantity": 25) is supported as an alternative to the object dictionary if desired.

Compatibility attributes

The compatibility_attributes option can be added to vehicles and stops to specify characteristics of the vehicle and requirements of the stop. They determine whether a vehicle is eligible to service a stop and ultimately whether a given solution is feasible.

The compatibility attributes constraint prevents the assignment of stops to vehicles that are not eligible due to specific requirements. For example, a stop with an order that requires refrigeration will not be assigned to a vehicle that does not have refrigeration.

For each vehicle, add the relevant attributes to the compatibility_attributes array, as needed. The string must be an exact match for the relevant vehicles and stops; spelling or phrasing errors will prevent correct attribute matching.

A compatibility constraint is satisfied if one attribute is matched. In the case that multiple attribute constraints must be satisfied, concatenate them as a single string inside the array (e.g. refrigerated-oversized) for both the relevant vehicles and stops.

The aim of the example below is to define compatibility attributes for stops and vehicles.

Save the included input.json. Execute the example and you'll see from the output.json file that the stop Fushimi Inari Taisha has been assigned to v1 and the stops Arashiyama Bamboo Forest and Kinkaku-ji have been assigned to v2 due to the compatibility attributes. All other stops are cost-optimally assigned to the vehicles.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "compatibility_attributes": ["silent"]
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "compatibility_attributes": ["air-conditioned"]
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "compatibility_attributes": ["air-conditioned"]
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "compatibility_attributes": ["silent"]
    },
    {
      "id": "v2",
      "compatibility_attributes": ["air-conditioned", "storage"]
    }
  ]
}
Copy

Duration groups

The duration_groups option let you set up stop groups to which an additional duration cost (in seconds) is applied every time one or many stops in the group are approached. This can be useful if some of your stops belong to a fenced apartment complex that needs some extra time to access. In that case you can group those stops together and specify an extra time needed to enter the complex. Once in the complex, the normal stop durations per stop are applied.

Each group must consist of at least 2 stops, given by their IDs, and a duration (in seconds) that is applied every time a stop in the group is approached from a stop that does not belong to the group. Stops can only belong to one group and must be listed only once within a group.

Duration groups do not enforce group assignment. Group assignments can be enforced using the stop groups feature.

In this example, you define a service group of a few stops.

Save the included input.json. Execute the example and open the output file. The estimated arrival and departure of the stops show that for the stops Fushimi Inari Taisha and Kiyomizu-dera the service time has been applied only once for both stops, because they were approached as one group. Also, the service time was applied to Nijō Castle again, since it was approached as an isolated stop.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "start": { "lon": 135.768308, "lat": 34.972559 }
    },
    {
      "id": "v2",
      "start": { "lon": 135.763366, "lat": 34.990354 }
    }
  ],
  "duration_groups": [
    {
      "group": ["Fushimi Inari Taisha", "Kiyomizu-dera", "Nijō Castle"],
      "duration": 900
    }
  ]
}
Copy

Measures

Measures determine the cost of routing a vehicle from one location to another. These cost computations are generically referred to as "measures". Measures are used as part of the value function to make decisions in Nextmv.

Default measure

Haversine is the default measure used by the Nextmv routing app to calculate the distance between two locations.

The haversine formula provides the shortest distance between two points on the surface of a sphere and is often referred to as 'as-the-crow-flies' distance. Haversine distance is fast to compute and sufficient for finding the best routes in the run time allotted.

When using the haversine measure, vehicle speed is required to calculate duration (duration = distance / speed). If vehicle speed is not specified (as default or for individual vehicles), then an error will be returned.

No changes to the input file are required to utilize the haversine measure for distance and duration in the Nextmv routing app. If no measure is specified, haversine will be set as default.

Additional measures

Two additional measures are available as integrations:

  • Streets: This integration uses real-road networks when calculating the distance between two points.
  • HERE: This integration uses HERE's matrix routing service to make routing decisions informed by accurate street routes and real-time or projected traffic conditions.

For more information on using the streets or HERE integration to extend Nextmv measures, please contact support.

Penalties

Penalties are mechanisms for discouraging undesirable behavior in returned solutions. For example, your business operations may place value on vehicles not arriving late to stops. Or, perhaps, it's unacceptable to not service a stop by unassigning it from a route. Penalty application is usually dependent upon other input settings (e.g., target_times and hard_windows) and can be represented with different value types (e.g., a multiplier vs. arbitrary time in seconds). Penalties contribute to the overall value function of a solution.

Earliness penalties and lateness penalties

The earliness_penalty and the lateness_penalty options are costs applied to the value function when vehicles arrive at stops too early or too late. These penalties are useful for discouraging behavior such as hot food being delivered too late or ride sharing vehicles arriving too early for an airport pickup.

The penalties are multipliers applied to every second a vehicle services a stop before or after a defined target time. Target times must be defined in the input schema in order for these penalties to be applied. For example, if a vehicle services a stop 60 seconds after a target time and the lateness penalty is set to 10, 600 seconds are added to the value function.

These penalties are defined at the stops level of the input schema, either in the defaults section or on a stop-by-stop basis.

In this example, three stops have earliness and lateness penalties and the same target_time.

Save the included input.json. Execute the example and you'll see from the output file that the three stops with the same target times are prioritized in order of penalty values in an effort to minimize cost total cost.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "lateness_penalty": 100,
      "earliness_penalty": 100,
      "target_time": "2022-09-15T09:01:00-06:00"
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 },
      "lateness_penalty": 10000,
      "earliness_penalty": 10000,
      "target_time": "2022-09-15T09:01:00-06:00"
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "lateness_penalty": 10,
      "earliness_penalty": 10,
      "target_time": "2022-09-15T09:01:00-06:00"
    }
  ],
  "vehicles": [{ "id": "v1" }, { "id": "v2" }]
}
Copy

Unassigned penalties

The unassigned_penalty option represents the severity of not assigning a stop to a vehicle while still allowing for unassignment in the case that it's not possible to assign a stop (e.g., if no vehicles in a fleet have sufficient capacity or compatibility for the stop). To achieve the desired behavior of discouraging but allowing for unassignment if necessary, a sufficiently large penalty value should be used, where 'sufficiently large' can be defined as larger than the maximum cost of servicing the particular stop.

The unassigned penalty is represented by an arbitrary amount of time measured in seconds. A stop is unassigned if adding it to a vehicle's route violates a defined constraint (e.g., capacity, hard_windows, shift_start, shift_end, and compatibility_attributes).

This penalty is defined at the stops level of the input schema, either in the defaults section or on a stop-by-stop basis.

If no penalty value is defined in the input file, the unassigned penalty will be autoconfigured. Any unassigned penalties added to the input file (in the defaults section or per stop) override the autoconfigured value.

In this example, the stops' demands exceed the vehicles' capacity and penalties are provided to leave stops unassigned.

Save the included input.json. Execute the example and you'll see from the output file that there are three stops that were not assigned, as the total stop quantity exceeds the total vehicle capacity. The stops that are assigned minimize the total distance.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "quantity": -1,
      "unassigned_penalty": 10000
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "quantity": -1
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 },
      "quantity": -1,
      "unassigned_penalty": 10000
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 },
      "quantity": -1,
      "unassigned_penalty": 10000
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 },
      "quantity": -1,
      "unassigned_penalty": 10000
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "quantity": -1,
      "unassigned_penalty": 10000
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "quantity": -1,
      "unassigned_penalty": 10000
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "capacity": 2
    },
    {
      "id": "v2",
      "capacity": 2
    }
  ]
}
Copy

Precedence

The precedence constraint is used to indicate that a specific stop must be visited before a different stop. For example, a vehicle may need to pick up an order at one stop before delivering it to another stop. You can use the precedes and succeeds fields at the stops level of the input schema to work with precedence constraints as follows.

  • precedes: ensures that the pickup is visited before the dropoff. It is applied to the individual stop that must be visited before the stop id defined in the precedes field.
  • succeeds: can be used to model the precedence relation the other way around. Using the same example as above, the opposite would be specified: on the dropoff stop we define that it needs to succeed its pickup counterpart.

Both, precedes and succeeds, can be used in combination to model more complex precedence relationships.

Multiple precedence relationships can be specified for a stop by passing an unordered list of IDs in the corresponding precedes and succeeds fields.

The aim of this example is to define two precedence instructions.

Save the included input.json. Execute the example and you'll see from the output file that one vehicle serves the stop Arashiyama Bamboo Forest whereas the other services the rest of the stops. Note that in the extended route the precedence constraints are fulfilled and Fushimi Inari Taisha and Gionmachi are visited before Kiyomizu-dera.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "precedes": "Kiyomizu-dera"
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "succeeds": "Gionmachi"
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [{ "id": "v1" }, { "id": "v2" }]
}
Copy

Route limits

Route limits are useful when constraining routes for individual or all vehicles. These limits are hard constraints, hence, the limits cannot be exceeded by the routes they are applicable to.

Max stops

It may be useful to limit the number of stops in a route to a particular amount. This can simply be done with the max_stops option for one vehicle (on the vehicle itself) or globally for all vehicles (in the defaults/vehicles section). Individual vehicle settings take precedence over global settings.

The aim of this example is to limit the maximum number of stops a vehicle can make.

Save the included input.json. Execute the example and you'll see from the output file that each vehicle does not exceed the maximum number of stops.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    { "id": "v1", "max_stops": 3 },
    { "id": "v2", "max_stops": 3 }
  ]
}
Copy

Max distance

It may be useful to limit the distance a vehicle can travel. For example, if the vehicle has a limited range. This limit can be set via the max_distance option for one vehicle (on the vehicle itself) or globally for all vehicles (in the defaults/vehicles section). Individual vehicle settings take precedence over global settings. The distance is given in meters.

The aim of this example is to limit the maximum distance of a route for a vehicle.

Save the included input.json. Execute the example and you'll see from the output file that each vehicle does not exceed the maximum distance.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    { "id": "v1", "max_distance": 9000 },
    { "id": "v2", "max_distance": 9000 }
  ]
}
Copy

Max duration

It may be useful to set a hard limit on the maximum duration of a route for a vehicle. For example, if the vehicle or vehicle driver has a limited availability. This limit can be set via the the max_duration option for one vehicle (on the vehicle itself) or globally for all vehicles (in the defaults/vehicles section). Individual vehicle settings take precedence over global settings. The duration is given in seconds.

Note, there is a known accuracy issue in ETAs when combining hard_window & max_duration.

The aim of this example is to limit the maximum duration of a route for a vehicle.

Save the included input.json. Execute the example and you'll see from the output file that each vehicle does not exceed the maximum duration.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    { "id": "v1", "max_duration": 500 },
    { "id": "v2", "max_duration": 500 }
  ]
}
Copy

Solver runtime duration

Solver runtime duration defines how long a Nextmv app will look for solutions. The default runtime for the Nextmv routing app is 3 seconds. This means the app will spend up to 3 seconds looking for the best solution to the problem.

Runtime is configurable in two ways:

  • With the API, runtime maxes out at 10 minutes. You can configure it at the beginning or end of your input using the JSON snippet shown below.
  • In the Nextmv routing app demo UI runtime maxes out at 30 seconds. You can configure it via the slider.
{
  "options": {
      "solver": {
          "limits": {
              "duration": "500s"
          }
      }
  },
  ...
}
Copy

Stop groups

To assign a set of stops to the same route you have several options.

  • If you want stops to be assigned to a specific vehicle's route, use compatibility attributes. Note, stops may be left unassigned.
  • If you want stops to be assigned to a specific vehicle's route and enforce their assignment to the route, use backlogs.
  • If you want to specify the order of stops in a group, use precedence/succession.
  • If you want to group stops without specifying the vehicles to assign them to or stop order, use stop groups (below).

Stop groups are used with the stop_groups attribute which defines a list of groups. Each group must consist of at least 2 stops, given by their IDs.

In this example, you define a service group of a few stops.

Save the included input.json. Execute the example and you'll see from the output file that all stops in the group have been assigned to the same vehicle.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [{ "id": "v1" }, { "id": "v2" }],
  "stop_groups": [["Fushimi Inari Taisha", "Kiyomizu-dera", "Nijō Castle"]]
}
Copy

Time settings

Date and time formats are explicitly defined using the RFC 3339 standard, using a 24-hour clock and offset with respect to UTC (YYYY-MM-DDTHH:MM:SS-UTC). It is a profile of the ISO 8601 international standard.

Durations are defined in seconds.

Time settings define when certain routing events should take place for vehicles and stops. This can include the hours of operation for vehicles, the ideal time a vehicle should service a stop, the exact time a vehicle should service a stop, and how long it takes a vehicle to service a stop. Time settings impact the order in which stops get serviced by vehicles as well as the application of penalties. They are also used to schedule vehicle break times.

Target times

The target_time option defines a specific time a vehicle should service a stop. This time setting is useful for encouraging vehicle timeliness at stops in ride sharing or food transportation scenarios.

Target times are exact times rather than windows or ranges of time. Target times are defined per stop. They are only enforced when earliness and lateness penalties are defined.

In the penalties example, target times were provided to force an ordering of stops with the same target time based on penalty value.

Hard windows

The hard_window option is a range of time a vehicle must service a stop within. This time setting is useful for enforcing strict timeliness for vehicles servicing stops.

Hard windows are hard constraints, i.e., if a stop is assigned to a route its time window must be met. Otherwise, the stop gets unassigned. Priorities of stops with conflicting windows can be controlled by introducing unassigned penalties. Waiting at a stop for the window to open is allowed by default and can be limited by setting waiting times.

In this example, you define hard windows and max wait times for certain stops and shifts for both vehicles.

Save the included input.json. Execute the example and you'll see from the output file that given the shift availability of the vehicles, stops Fushimi Inari Taisha and Kiyomizu-dera are assigned to vehicle v1 as they must be serviced before 12 pm. Stops Arashiyama Bamboo Forest and Kinkaku-ji are assigned to vehicle v2, given that they must be visited after mid-day.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "hard_window": ["2020-10-17T10:00:00-06:00", "2020-10-17T12:00:00-06:00"],
      "stop_duration": 900,
      "max_wait": -1
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "hard_window": ["2020-10-17T10:00:00-06:00", "2020-10-17T12:00:00-06:00"],
      "stop_duration": 900,
      "max_wait": -1
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 },
      "stop_duration": 900
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "hard_window": ["2020-10-17T12:00:00-06:00", "2020-10-17T14:00:00-06:00"],
      "stop_duration": 900,
      "max_wait": -1
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 },
      "hard_window": ["2020-10-17T12:00:00-06:00", "2020-10-17T14:00:00-06:00"],
      "max_wait": -1
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "start": { "lon": 135.768308, "lat": 34.972559 },
      "shift_start": "2020-10-17T10:00:00-06:00",
      "shift_end": "2020-10-17T12:00:00-06:00"
    },
    {
      "id": "v2",
      "start": { "lon": 135.763366, "lat": 34.990354 },
      "shift_start": "2020-10-17T12:00:00-06:00",
      "shift_end": "2020-10-17T14:00:00-06:00"
    }
  ]
}
Copy

Waiting times

The max_wait option is the maximum amount of time a vehicle is allowed to wait at a stop for the time window to open.

Waiting time is a hard constraint that is defined at the stop level (default or individually). Note, if waiting time is defined, a hard window must also be defined.

The hard windows example above also uses max_wait time.

Shift start and end

The shift_start and shift_end options indicate a range of time a vehicle is available to service stops. This time setting is useful for enforcing availability of a given vehicle for a defined shift while also accounting for breaks.

Shift start and end are hard constraints. They are defined at the vehicle level (default or individually) and will influence how unassigned penalties are applied to the value function.

The hard windows example above also uses shift_start and shift_end times.

Stop duration

The stop_duration option is the estimated amount of time in seconds a vehicle needs to service a stop. For example, a vehicle might need less time to service a stop for a ride-sharing scenario than it would for loading large quantities of produce in a sourcing scenario.

They are defined at the stop level (default or individually).

In this example, you define stop durations for some stops.

Save the included input.json. Execute the example and you'll see from the output file that the route durations in the output file now not only accounts for the travel time but also the given service times.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 },
      "stop_duration": 900
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 },
      "stop_duration": 900
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 },
      "stop_duration": 900
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 },
      "stop_duration": 300
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [{ "id": "v1", "stop_duration_multiplier": 1.2 }, { "id": "v2" }]
}
Copy

Stop duration multiplier

It may be the case that some vehicles within your fleet need considerably longer time to service a stop. In order to introduce this information to the model, you can use the stop_duration_multiplier option at the vehicle level to increase or decrease the given service time for the stop.

The stop duration example above uses stop_duration_multiplier to increases the given service time for every stop by factor 1.2 for v1.

Value functions

The value function describes the optimization objective you're looking to minimize, maximize, or satisfy.The value function provides a way to numerically represent solution values and quantitatively compare them. Here, the term value function is equivalent to the term objective function and can include one or more business KPIs.

The default value function minimizes time spent on the road measured in seconds. Additional value functions are available depending on which options you add to your input file, e.g., adding a vehicle initialization cost or earliness and lateness penalties will automatically update the default value function to include ETA error.

Solution values are numerical representations of the states a solver explores as part of an optimization problem. They are defined by the value function and can consist of several components.

For the default value function of minimizing time spent on the road, the solution value equals the total time spent on the road for all vehicles plus the total values for any defined penalties and vehicle initialization costs. The solver interprets lower solution values as better than higher solution values.

The JSON output provides value details at varying levels of granularity: by vehicle, by penalty, or as a summary (see snippet below).

{
  ...
    "value_summary": {
      "value": 242799,
      "total_travel_distance": 1207599.2080259852,
      "total_travel_time": 67462.56991862402,
      "total_earliness_penalty": 51723.25995969772,
      "total_lateness_penalty": 23625.407207012177,
      "total_unassigned_penalty": 0,
      "total_vehicle_initialization_costs": 100000
    }
  ...
}
Copy

See the Nextmv routing app demo page for visualizations for helping you to understand the breakdown of contributing factors to a solution value.

Vehicle costs

Vehicle initialization costs are used to apply fixed costs for using a vehicle. This can be useful if costs that incur from using a type of vehicle (e.g. truck) are higher than another type (e.g. bike).

The initialization_cost is defined at the vehicle level of the input schema and contributes to the overall value function of a solution.

The aim of this example is to add initialization costs to vehicles. v1 has an expensive initialization cost associated with it, while v2 does not.

Save the included input.json. Execute the example and you'll see from the output file that all stops are assigned to v2 given that v1 is the most expensive vehicle to operate.

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10
    }
  },
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "initialization_cost": 100000
    },
    {
      "id": "v2",
      "initialization_cost": 0
    }
  ]
}
Copy

Page last updated

Go to on-page nav menu