NVD Solution ResponseSolution Response

Overview

The NVD solution response has an additional tier of structure over the standard IVR solution response. This is due to the problem typically being multi-objective in nature and, as a result, the initial solution is in fact a Pareto frontier (see objectives) from which the user can then select a solution instance which then closely mimics the standard IVR response (with the addition of a day assignment).

Applicable models

• NVD nvd-hap0j2y4zlm1

Endpoint

• GET: https://api.icepack.ai/vehicle-router/solve/{requestid}

Solution Response

The solution response contains two core elements. The first is a frontier which describes the Pareto frontier found by the search algorithm. The second provides the details of a solution instance from the Pareto frontier (typically), but can also support a solution instance from an evaluation. In a typical NVD solution response, either the frontier collection is populated or the solution instance details are populated.

Schema definition

message SolutionResponse {
  repeated CompactSolution frontier = 1;
  optional SolutionInstance instance = 2;
}

Fields

frontier

A list of CompactSolution objects which define the non-dominated Pareto frontier found. A non-empty list is typically returned when a solve request is issued with the Optimise type.

instance

A solution instance corresponding to a point on the Pareto frontier, or Evalute solve request.

Compact Solution

A compact solution provides all the information required by the API to recover or reconstruct a complete schedule. This structure is used to summarise the Pareto frontier in such a way as to return the critical information required by the user to make a decision on the degree of tradeoff required between competing objectives.

Schema definition

message CompactSolution {
  repeated VisitSequence visitSequence = 1;
  repeated float objectives = 2;
  repeated string objectiveNames = 3;
}

Fields

visitSequence

A visit sequence which may be assigned to a copy of the model which has been optimised to recover the solution detail. Each visit sequence fully defines a particular solution.

objectives

A list of objective values for each solution on the Pareto frontier.

objectiveNames

A list of objective names for each optimisation facet.

Notes

• NVD models typically involve two stages, the first which uncovers the Pareto frontier for a model definition, and the second call to the API which then returns the full detail of a point of interest on the Pareto frontier.
• The CompactSolution provides a measurement (in terms of objective function values) for each of the points on the frontier without providing all the detailed routing information.

Solution Instance

A solution instance is analogous to the IVR solution response but where the objective values are provided in the CompactSolution object (since this is now an array of function values).

Schema definition

message SolutionInstance {
  repeated Route routes = 1;
  repeated Infeasibility infeasibilities = 2;
}

Fields

routes

A list of routes detailing the movements and task allocations for each vehicle. The routes list will correspond in length to the vehicles provided. Routes with no tasks or jobs allocated to them have only two tasks assigned, namely the shift start and shift end task for that vehicle.

infeasibilities

It is typically desireable to schedule as many orders as possible for a given model. In certain instances, jobs may be infeasible in the context of either scheduling parameters provided, or other jobs in a particular model definition. In instances where jobs are not performed by any vehicle, the engine will evaluate such jobs once the search is complete and provide reasons for the infeasibility of unperformed jobs.

Route

The route provides the scheduled activities and evaluation values for a particular vehicle in a solution response.

Schema definition

message Route {
  required string vehicleId = 1;
  repeated Stop stops = 2;
  repeated InterStop interStops = 3;
  repeated float fixedCost = 4;
  repeated TransitRuleAttribute transitRuleAttributes = 5;
  required int32 day = 7;  // the visit day for this route.
}

Fields

vehicleId

The vehicle identifier, corresponding to the identifier of each vehicle provided in the input model.

stops

The collection of stop objects describing the standing activities of a vehicle.

interStops

The collection of interstop objects describing the movements of a vehicle between locations (i.e. transit).

fixedCost

The fixed cost applied to the vehicle if it was used.

transitRuleAttributes

A collection of transit rule attributes that were applied to this particular route.

day

The day on which this particular route is performed (zero-based).

Stop

The Stop describes a point in the route of a rep where a visit is performed. Stops are given their own unique idenfitier in the output and are referenced by the interstops.

Schema definition

message Stop {
  required int32 id = 1;
  required int32 sequence = 2;
  required string locationId = 3;
  required string visitId = 4;
  repeated StopAttribute attributes = 5;
}

Fields

id

The unique stop identifier. The stop identifier provided as output is a numeric sequence starting at zero.

sequence

The sequence of the stop within the current route. The sequence is zero-based and increasing by a single unit for each task completed.

locationId

For interface convenience, the visit identifier is returned as the location identifier at which this stop occurs.

visitId

The visit identifier which the sales rep is performing at this stop.

attributes

A list of node attributes for each dimension in the model.

Stop Attribute

The Stop attribute describes the dimensional properties at the start of performing a particular visit and at the end of the same visit. The difference between the end and start values for a node attribute will provide the marginal contribution of the node attribute to the cumulative dimension value.

Schema definition

message StopAttribute {
  required string dimId = 1;
  required float startValue = 2;
  required float endValue = 3;
  required float cost = 4;
  required float slackValue = 5;
  required float slackCost = 6;
  required float tardyValue = 7;
  required float tardyCost = 8;
}

Fields

dimId

The dimension over which this attribute is being measured.

startValue

The starting value of the attribute (in the units of the dimension).

endValue

The ending value of the attribute (in the units of the dimension).

cost

The cost of this transaction in the schedule for this particular dimension. In the context of a time dimension, this would be the cost per minute. In the context of a distance dimension, this may be the cost per km or cost per mile.

slackValue

The amount of slack on the specified dimension added to the node in order to ensure feasibility by allowing a value to be shifted up to the start of a window.

slackCost

The cost of the slack which was added to the dimension to ensure feasibility.

tardyValue

The amount of tardiness added to the specified dimension to allow for a window end which has been exceeded.

tardyCost

The cost of the tardiness added to the specified dimension to ensure feasibility.

Examples

See the IVR solution response for output samples.

InterStop

The interstop describes the movement between stops, i.e. the transit between visits that are performed in a particular schedule.

Schema definition

message InterStop {
  required int32 fromStopId = 1;
  required int32 toStopId = 2;
  repeated InterStopAttribute attributes = 3;
  repeated Geocode routeSegments = 4;
}

Fields

fromStopId

The origin stop identifier which provides the previous task that is being performed for this transit.

toStopId

The destination stop identifier which provides the next task that is being performed for this transit.

attributes

A list of edge attributes applicable to each of the dimensions in the model.

routeSegments

A list of geocodes which define the movement from the origin to the destination which correspond to a sequence through the road network which may be interpreted as a linestring. Where the source and destination stops are at the same location, two geocodes are provided at the same location so that a linestring can generally be formed in this situation.

InterStop.Attribute

An InterStop attribute is an edge attribute describing the movement between visits in a schedule. The edge attributes record the cumulative starting value and cumulative end value in the respective dimension of measurement at the relevant point in the schedule. The difference between the end value and start value will provide the marginal amount incurred on the specified dimension for this particular transaction.

Schema definition

message InterStopAttribute {
  required string dimId = 1;
  required float startValue = 2;
  required float endValue = 3;
  required float cost = 4;
}

Fields

dimId

The dimension over which this attribute is being measured.

startValue

The starting value of the attribute.

endValue

The ending value of the attribute.

cost

The cost of the units of attribute incurred on this dimension. I.e. (endValue-startValue)*(dimension cost coefficient).

TransitRuleAttribute

A transit rule attribute provides the details of each triggered transit rule for a particular route. Currently this is provided for consistency in the output parsing end-points, but no mechanism exists in the current input schema to provide transit results.

Schema definition

message TransitRuleAttribute {
  required string ruleId = 1;
  required string dimId = 2;
  required int32 fromStopId = 3;
  required int32 toStopId = 4;
  required float startValue = 5;
  required float endValue = 6;
  required float cost = 7;
}

Infeasibility

The NVD schema only supports retrieving a detailed schedule under an Evaluate solve request. In this instance, the solver evaluates specific points of infeasibility (if any) in the schedule. The Pareto frontier will consist of solutions which have an equal degree of infeasibility, i.e. if a solution is found which performs all visits within the constraints, and all other solutions found omit a non-zero number of visits, then the Pareto frontier will consist of precisely one solution.

Schema definition

message Infeasibility {
  required string taskId = 1;
  repeated Info infeasibilityInfo = 2;
}

Fields

taskId

The unique task identifier for which the infeasibility is applicable. In this context, this corresponds to a visit coupled with an iterator indicating which visit number is referenced in the schedule.

infeasibilityInfo

A list of infeasibility information objects which aggregate (for Optimise requests) common messages defining the infeasibility. Specific infeasibility messages at each task are provided for Evaluate requests.

Infeasibility Info

An infeasibility info object provides the specifics on an infeasibility detected. Where an infeasibility is related to a dimension, the dimension is provided which typically corresponds to the limits and values provided. Certain constraints are checked at a tier above the dimension in which case the dimension will be omitted. Where performing a given task is feasible, but results in infeasibility in other tasks, the constrainingTaskIds field is then populated.

Schema definition

message Info {
  required string message = 1;
  optional string dimId = 2;
  optional float limit = 3;
  optional float value = 4;
  optional int64 count = 5;
  repeated string constrainingTaskIds = 6;
}

Fields

message

A human-readable message describing the type of constraint that has been broken.

dimId

If present, the dimension on which a constraint has been broken.

limit

Depending on the context, it may pertain to a lower or upper limit on a particular dimension for this particular task.

value

The evaluation value at the point at which the constraint was broken. This value should be read with reference to the limit. I.e. if the value is below the limit, then an infeasible window start is present. If the value is higher than the limit, then a window end or capacity limit has been broken. In the case of a normal Optimise or ReOptimise request, the limit and value will represent the average limit and average value across several infeasibilities. The solver often evaluates thousands of infeasible moves which are aggregated together to provide high-level information.

count

The number of infeasible constraint evaluations that were used in the determination of the average limit and value.

constrainingTaskIds

A list of constraining tasks which are prohibiting the current task from being feasible.