Nextcheck

This feature is configurable through options, without the need for code customization and is available in both the Marketplace app and Platform. You can find a list of all available features here.

Nextcheck is a feature that can be used with apps based on our vehicle routing engine in the following scenarios:

Input check: In this scenario the submitted input file is checked. As a result Nextcheck will report which plan units can be planned and which cannot. This check can be run locally to test input files ad hoc, or it could be used as a pre-check for your input files.
Solution check: In this use case you have a solution and want to know why you have unplanned stops.

Usage

A move is a definition of a plan action for a plan unit. For each stop in the plan unit the move defines where the stop is added to an existing vehicle solution. A move is used to determine if it can be executed (aka it does not violate any constraints) and if so what the impact is on the objective.

The Nextcheck report is enabled by defining the verbosity level for Nextcheck through options. There are four levels of verbosity that you can request for your report: off, low, medium, and high.

off — Nextcheck is disabled, no report is generated. This is the default setting for Nextcheck.
low — For each plan unit we determine if there is a feasible move that improves the solution.
medium — For each plan unit we determine the best feasible move that improves the solution and report its impact on the objective. At this level we also report what vehicles have a feasible move for the plan unit.
- For each plan unit, Nextcheck determines the best feasible move that improves the solution and reports its impact on the objective. At this level, it also reports how many moves on each vehicle can be executed.
- If there is no executable move, the report will provide a list of constraints that have prevented a feasible move and the number of times that constraint was responsible for not accepting a move. Note that other constraints may have been violated as well, but as soon as Nextcheck encounters a constraint violation for a move, it stops checking for other constraint violations for that move because it is no longer necessary to do so.
high — For each plan unit, we report the same level of detail defined in medium above with the addition of a property that defines which vehicles have moves for the plan unit that will improve the solution.

To check an input file you need to make sure that none of the vehicles have any initial stops with the property fixed set to false. Once the input file complies with this requirement the check can be performed.

If you want to check a solution, you need to create an input file where your previously generated solution is added to the vehicles as initial stops.

You can see an example output here where the verbosity was set to high:

JSON

{
  "options": {
    "check": {
      "duration": 30000000000,
      "verbosity": "high"
    },
    "format": {
      "disable": {
        "progression": true
      }
    },
    "model": {
      "constraints": {
        "disable": {
          "attributes": false,
          "capacities": null,
          "capacity": false,
          "distance_limit": false,
          "groups": false,
          "maximum_duration": false,
          "maximum_stops": false,
          "maximum_wait_stop": false,
          "maximum_wait_vehicle": false,
          "mixing_items": false,
          "precedence": false,
          "start_time_windows": false,
          "vehicle_end_time": false,
          "vehicle_start_time": false
        },
        "enable": {
          "cluster": false
        }
      },
      "objectives": {
        "capacities": "",
        "cluster": 0,
        "early_arrival_penalty": 1,
        "late_arrival_penalty": 1,
        "min_stops": 1,
        "travel_duration": 0,
        "unplanned_penalty": 1,
        "vehicle_activation_penalty": 1,
        "vehicles_duration": 1
      },
      "properties": {
        "disable": {
          "duration_groups": false,
          "durations": false,
          "initial_solution": false,
          "stop_duration_multipliers": false
        }
      },
      "validate": {
        "disable": {
          "resources": false,
          "start_time": false
        },
        "enable": {
          "matrix": false,
          "matrix_asymmetry_tolerance": 20
        }
      }
    },
    "solve": {
      "duration": 10000000000,
      "iterations": 0,
      "parallel_runs": 1,
      "run_deterministically": true,
      "start_solutions": 0
    }
  },
  "solutions": [
    {
      "check": {
        "duration_maximum": 30,
        "duration_used": 0.123,
        "plan_units": [
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 536.4530622299,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 536.4530622299
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1998927.0938755402,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Fushimi Inari Taisha"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999463.5469377702,
                "delta_objective_estimate": -999463.5469377701,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Fushimi Inari Taisha"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 529.6139038839777,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 529.6139038839777
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1998940.772192232,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Kiyomizu-dera"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999470.3860961162,
                "delta_objective_estimate": -999470.386096116,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Kiyomizu-dera"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 347.02081951153525,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 347.02081951153525
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1999305.958360977,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Nijō Castle"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999652.9791804887,
                "delta_objective_estimate": -999652.9791804885,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Nijō Castle"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 412.537144030441,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 412.537144030441
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1999174.925711939,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Kyoto Imperial Palace"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999587.4628559696,
                "delta_objective_estimate": -999587.4628559696,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Kyoto Imperial Palace"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 479.1702973276746,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 479.1702973276746
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1999041.6594053446,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Gionmachi"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999520.8297026725,
                "delta_objective_estimate": -999520.8297026723,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Gionmachi"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 287.61617185337144,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 287.61617185337144
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -1999424.7676562932,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Kinkaku-ji"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -999712.3838281464,
                "delta_objective_estimate": -999712.3838281466,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Kinkaku-ji"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          },
          {
            "best_move_failed": false,
            "best_move_objective": {
              "terms": [
                {
                  "base": 0,
                  "factor": 1,
                  "name": "vehicles_duration",
                  "value": 0
                },
                {
                  "base": -1000000,
                  "factor": 1,
                  "name": "unplanned_penalty",
                  "value": -1000000
                }
              ],
              "value": -2000000,
              "vehicle": "v1"
            },
            "has_plannable_best_move": true,
            "planning_makes_objective_worse": false,
            "stops": [
              "Arashiyama Bamboo Forest"
            ],
            "vehicles_have_moves": 1,
            "vehicles_with_moves": [
              {
                "delta_objective": -1000000,
                "delta_objective_estimate": -1000000,
                "positions": [
                  {
                    "next": "v1-end",
                    "previous": "v1-start",
                    "stop": "Arashiyama Bamboo Forest"
                  }
                ],
                "vehicle_id": "v1",
                "was_plannable": true
              }
            ]
          }
        ],
        "remark": "completed",
        "solution": {
          "objective": {
            "terms": [
              {
                "base": 0,
                "factor": 1,
                "name": "vehicles_duration",
                "value": 0
              },
              {
                "base": 7000000,
                "factor": 1,
                "name": "unplanned_penalty",
                "value": 7000000
              }
            ],
            "value": 7000000
          },
          "plan_units_planned": 0,
          "plan_units_unplanned": 7,
          "stops_planned": 0,
          "vehicles_not_used": 1,
          "vehicles_used": 0
        },
        "summary": {
          "moves_failed": 0,
          "number_of_plan_units_making_objective_worse": 0,
          "plan_units_best_move_failed": 0,
          "plan_units_best_move_found": 7,
          "plan_units_checked": 7,
          "plan_units_have_no_move": 0,
          "plan_units_to_be_checked": 7
        },
        "vehicles": [
          {
            "id": "v1",
            "plan_units_have_moves": 7
          }
        ],
        "verbosity": "high"
      },
      "objective": {
        "name": "1 * vehicles_duration + 1 * unplanned_penalty",
        "objectives": [
          {
            "factor": 1,
            "name": "vehicles_duration",
            "value": 0
          },
          {
            "base": 7000000,
            "factor": 1,
            "name": "unplanned_penalty",
            "value": 7000000
          }
        ],
        "value": 7000000
      },
      "unplanned": [
        {
          "id": "Arashiyama Bamboo Forest",
          "location": {
            "lat": 35.017209,
            "lon": 135.672009
          }
        },
        {
          "id": "Fushimi Inari Taisha",
          "location": {
            "lat": 34.967146,
            "lon": 135.772695
          }
        },
        {
          "id": "Gionmachi",
          "location": {
            "lat": 35.002457,
            "lon": 135.775682
          }
        },
        {
          "id": "Kinkaku-ji",
          "location": {
            "lat": 35.039705,
            "lon": 135.728898
          }
        },
        {
          "id": "Kiyomizu-dera",
          "location": {
            "lat": 34.994857,
            "lon": 135.78506
          }
        },
        {
          "id": "Kyoto Imperial Palace",
          "location": {
            "lat": 35.025431,
            "lon": 135.762057
          }
        },
        {
          "id": "Nijō Castle",
          "location": {
            "lat": 35.014239,
            "lon": 135.748134
          }
        }
      ],
      "vehicles": [
        {
          "id": "v1",
          "route": [
            {
              "cumulative_travel_duration": 0,
              "stop": {
                "id": "v1-start",
                "location": {
                  "lat": 35.017209,
                  "lon": 135.672009
                }
              },
              "travel_duration": 0
            }
          ],
          "route_duration": 0,
          "route_travel_duration": 0
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 0,
        "max_duration": 0,
        "max_stops_in_vehicle": 0,
        "max_travel_duration": 0,
        "min_duration": 9223372036854776000,
        "min_stops_in_vehicle": 9223372036854776000,
        "min_travel_duration": 9223372036854776000,
        "unplanned_stops": 7
      },
      "duration": 0.123,
      "value": 7000000
    },
    "run": {
      "duration": 0.123,
      "iterations": 0
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}

Interpretation

The following table contains an overview of what the individual parts of the nextcheck summary are:

Field name	Description
`check.remark`	Status of the check by nextcheck. Possible values: `completed` (The check was completed), `timeout` (The check was not completed due to a timeout during the check. Try a higher duration maximum setting for nextcheck.).
`check.verbosity`	Reports the level of verbosity of nextcheck. Possible values: `off`, `low`, `medium`, `high`.
`check.duration_maxium`	The maximum duration of the check (default 30s).
`check.duration_used`	The time nextcheck used to finish the analyis (in seconds).
`check.solution`	Contains an overview of the solution.
`check.summary`	Contains a summary of nextcheck's analysis.
`check.plan_units`	Contains a list of the unplanned plan units together with a list of reasons why they were not planned.
`check.vehicles`	Contains a list of vehicles, where each vehicle is represented by its ID and the number of plan units that have a move on this vehicle (`plan_units_have_moves`).

check.solution

Field name	Description
`check.solution.stops_planned`	The number of planned stops in the solution.
`check.solution.plan_units_planned`	The number of planned plan units in the solution.
`check.solution.plan_units_unplanned`	The number of unplanned plan units in the solution.
`check.solution.vehicles_used`	The number of used vehicles in the solution.
`check.solution.vehicles_not_used`	The number of not utilized vehicles in the solution.
`check.solution.objective`	An overview of the value function, showing the individual terms with their values as well as the total value.

check.summary

Field name	Description
`check.summary.plan_units_to_be_checked`	The number of plan units that needed to be checked by nextcheck.
`check.summary.plan_units_checked`	The number of plan units that were checked by nextcheck. If this is less than `plan_units_to_be_checked` a time-out occured.
`check.summary.plan_units_best_move_found`	The number of plan units for which at least one executable move has been found. The moves do not necessarily improve the objective.
`check.summary.plan_units_have_no_move`	The number of plan units for which no executable move has been found or no move exists at all.
`check.summary.number_of_plan_units_making_objective_worse`	The number of plan units where the best executable move increases the objective value. As the solver is minimizing the objective value, it won't select such a move and therefore such a plan unit would not be assigned to a vehicle.
`check.summary.plan_units_best_move_failed`	The number of plan units for which the best move can't be planned.
`check.summary.moves_failed`	The number of checked moves that violated constraints.

check.plan_units

Field name	Description
`stops`	The stop IDs belonging to the plan unit.
`has_plannable_best_move`	Whether a plannable move was found for the plan unit and it was executed successfully. If no move was found, it's possible that the plan unit has too many restrictions from constraints or that it is too expensive.
`planning_makes_objective_worse`	Whether the best executable move of the plan unit increases the objective value. As the solver is minimizing the objective value, it won't select such a move and therefore such a plan unit would not be assigned to a vehicle.
`best_move_failed`	Whether the best move of the plan unit failed to execute.
`vehicles_have_moves`	The number of vehicles for which a move with this plan unit exists. Only displayed if verbosity is set to `medium` or `high`.
`vehicles_with_moves`	A list of vehicles, for which a move for this plan unit exists.
`best_move_objective`	The estimate of the objective of the best move if the plan unit has one.
`constraints`	Contains a list of constraints that have been violated by this plan unit. For each constraint, the number of vehicles for which the constraint fails is also given.

check.plan_units.vehicles_with_moves

Field name	Description
`vehicle_id`	The ID of the vehicle.
`delta_objective_estimate`	The estimate of the delta that would be incurred by the move on this vehicle.
`delta_objective`	The actual delta that would be incurred by the move on this vehicle. This value should be equal to `delta_objective_estimate`. If it is not, this is reason to investigate the implementation of the objective function.
`failed_constraints`	The constraints that are violated by the move on this vehicle.
`was_plannable`	Whether the move was plannable or not.
`positions`	Defines where the stop should be inserted with a move on this vehicle.

check.plan_units.vehicles_with_moves.positions

Field name	Description
`previous`	The ID of the stop after which the stop should be inserted.
`stop`	The ID of the stop that should be inserted.
`next`	The ID of the stop before the stop should be inserted.

check.plan_units.constraints

The following table gives an overview of possible constraints for which a plan unit might fail. In order to better understand some of these constraints, it is worth noting the definition of certain semantics:

arrival time at the location of a stop = end time of the previous stop + travel duration to the current stop
start time of a stop = max(arrival time at the location of the stop, earliest allowed start time of the stop)
end time of a stop = start time of the stop + duration of the stop
wait time at the location of a stop = start time of the stop - arrival time at the location of stop

Field name	Description
`late_start_penalty`	It is only possible to start a stop after the end of the allowed window for this stop.
`late_end_penalty`	The plan unit can only be planned such that it ends after its latest end.
`attributes`	There is a mismatch between the attributes of this plan unit and the attributes of the indicated vehicles.
`maximum_duration`	The plan unit can't be assigned unless the total violates breaks the maximum duration constraint. The total duration is defined as `last_stop.end - first_stop.start` of a vehicle.
`maximum_stops`	The plan unit can't be assigned without breaking the maximum stops constraint.
`maximum_travel_duration`	The plan unit can't be assigned without breaking the maximum travel duration constraint.
`maximum_stop_wait`	The plan unit can't be assigned without having a longer wait time than what is allowed by the maximum wait time constraint for the stop.
`maximum_vehicle_wait`	The plan unit can't be assigned without having a longer wait time than what is allowed by the maximum wait time constraint for the vehicle.
`no_mix`	The plan unit can't be assigned without mixing it with another plan unit, for which a no mix constraint exists.
`successor`	The plan unit can only be assigned such that it is planned after stops that disallow this plan unit as a successor.

check.vehicles

Field name	Description
`id`	The ID of the vehicle.
`plan_units_have_moves`	The number of plan units that have a move for this vehicle. Is only displayed if verbosity is set to `medium` or `high`.

A how-to guide for checking the feasibility of a problem.