Evaluation

The evaluation class implements problem-specific cost and move evaluation functions. It’s design bases on the concepts introduced in Vidal et al. [VCGP14].

Note that this class is an interface: it’s not meant to be instantiated or used directly. Please use the concrete implementations of this interface and helper functions instead. See e.g. ADPTW or NIFTW for examples of concrete implementations.

Warning

We recommend implementing a custom Evaluation class by extending the native RoutingBlocks library instead of providing a python implementation for code used beyond prototyping. See native extensions for an example.

class routingblocks.PyConcatenationBasedEvaluation

The evaluation class implements problem-specific cost and move evaluation functions. It’s design bases on the concepts introduced in Vidal et al. [VCGP14]. Note that this class is an interface: it’s not meant to be instantiated or used directly. Please use the concrete implementations of this interface and helper functions instead.

concatenate(fwd: AnyForwardLabel, bwd: AnyBackwardLabel, vertex: Vertex)

Specialization of the general evaluation member of PyEvaluation for cases where two route subsequences can be concatenated efficiently. Classes who extend this class do not need to implement PyEvaluation.evaluate.

The concatenation function works as follows: Assume that we have two route subsequences [v_1, ..., v_n] and [v_{n+1}, ..., v_m]. The specialized evaluation function first propagates v_n to v_{n+1}, and the calls concatenate(fwd_{n+1}, bwd_{n+1}, v_{n+1}) where fwd_{n+1} is the forward label of v_{n+1} and bwd_{n+1} is the backward label of v_{n+1}.

If the specialized evaluation function is called with several route sub-sequences [..., v_n], [v_n+1, ... v_{n+m}], [v_{n+m+1}, ...] then the first sequence is extended to v_{n+m} and the operation reduces to the first case: concatenate(fwd_{n+m+1}, bwd_{n+m+1}, v_{n+m+1}) where fwd_{n+m+1} is the forward label of v_{n+m+1} and bwd_{n+m+1} is the backward label of v_{n+m+1}.

Parameters:

fwd (AnyForwardLabel) – The forward label representing the route sub-sequence [v_1, ..., v_n, v_{n+1}]
bwd (AnyBackwardLabel) – The backward label representing the route sub-sequence [v_{n+1}, ..., v_m]
vertex (Vertex) – The vertex v_{n+1}

Returns:

The cost of the route [v_1, ..., v_n, v_{n+1}, ..., v_m]

Return type:

float

compute_cost(label: AnyForwardLabel)

Computes the cost of a given label.

Parameters:: label (AnyForwardLabel) – The label
Returns:: The cost of the label
Return type:: float

evaluate(instance: Instance, segments: List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]])

Evaluates the cost of the route given by concatenating the passed route sub-sequences. Each sub-sequences is guaranteed to have valid forward and backward labels.

Corresponds to EVALN in Vidal et al. [VCGP14].

Parameters:

instance (Instance) – The instance
segments (List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]]) – A list of route sub-sequences, each given as a list of tuples of (vertex, forward label, backward label)

Returns:

The cost of the route

Return type:

float

create_backward_label(vertex: Vertex)

Creates and initializes a backward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:: vertex (Vertex) – The vertex representing singleton route [vertex]
Returns:: The initialized backward label
Return type:: AnyBackwardLabel

create_forward_label(vertex: Vertex)

Creates and initializes a forward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:: vertex (Vertex) – The vertex representing singleton route [vertex]
Returns:: The initialized backward label
Return type:: AnyBackwardLabel

get_cost_components(label: AnyForwardLabel)

Returns the cost components of a given label.

Parameters:: label (AnyForwardLabel) – The label
Returns:: The cost components of the label
Return type:: List[float]

is_feasible(label: AnyForwardLabel)

Checks whether a given label is feasible.

Parameters:: label (AnyForwardLabel) – The label
Returns:: True if the label is feasible, False otherwise
Return type:: bool

propagate_forward(pred_label: AnyForwardLabel, pred_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the forward label of pred_vertex to the vertex.

Corresponds to FORW([..., pred_vertex]⊕[vertex]) in Vidal et al. [VCGP14].

Parameters:

pred_label (AnyForwardLabel) – The forward label of the predecessor vertex
pred_vertex (Vertex) – The predecessor vertex
vertex (Vertex) – The vertex
arc (Arc) – The arc connecting pred_vertex and vertex

Returns:

The propagated forward label

Return type:

AnyForwardLabel

propagate_backward(succ_label: AnyBackwardLabel, succ_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the backward label of succ_vertex to the vertex.

Corresponds to BACK([vertex]⊕[succ_vertex, ...]) in Vidal et al. [VCGP14].

Parameters:

succ_label (AnyBackwardLabel) – The backward label of the successor vertex
succ_vertex (Vertex) – The successor vertex
vertex (Vertex) – The vertex
arc (Arc) – The arc connecting succ_vertex to vertex. Note that this corresponds to the reverse arc of the forward direction.

Returns:

The propagated backward label

Return type:

AnyBackwardLabel

class routingblocks.PyEvaluation

The PyEvaluation class implements the evaluation interface in pure Python. It’s meant to be used as a base class for custom python-based evaluation classes.

compute_cost(label: AnyForwardLabel)

Computes the cost of a given label.

Parameters:: label (AnyForwardLabel) – The label
Returns:: The cost of the label
Return type:: float

evaluate(instance: Instance, segments: List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]])

Evaluates the cost of the route given by concatenating the passed route sub-sequences. Each sub-sequences is guaranteed to have valid forward and backward labels.

Corresponds to EVALN in Vidal et al. [VCGP14].

Parameters:

instance (Instance) – The instance
segments (List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]]) – A list of route sub-sequences, each given as a list of tuples of (vertex, forward label, backward label)

Returns:

The cost of the route

Return type:

float

create_backward_label(vertex: Vertex)

Creates and initializes a backward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:: vertex (Vertex) – The vertex representing singleton route [vertex]
Returns:: The initialized backward label
Return type:: AnyBackwardLabel

create_forward_label(vertex: Vertex)

Creates and initializes a forward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:: vertex (Vertex) – The vertex representing singleton route [vertex]
Returns:: The initialized backward label
Return type:: AnyBackwardLabel

get_cost_components(label: AnyForwardLabel)

Returns the cost components of a given label.

Parameters:: label (AnyForwardLabel) – The label
Returns:: The cost components of the label
Return type:: List[float]

is_feasible(label: AnyForwardLabel)

Checks whether a given label is feasible.

Parameters:: label (AnyForwardLabel) – The label
Returns:: True if the label is feasible, False otherwise
Return type:: bool

propagate_forward(pred_label: AnyForwardLabel, pred_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the forward label of pred_vertex to the vertex.

Corresponds to FORW([..., pred_vertex]⊕[vertex]) in Vidal et al. [VCGP14].

Parameters:

pred_label (AnyForwardLabel) – The forward label of the predecessor vertex
pred_vertex (Vertex) – The predecessor vertex
vertex (Vertex) – The vertex
arc (Arc) – The arc connecting pred_vertex and vertex

Returns:

The propagated forward label

Return type:

AnyForwardLabel

propagate_backward(succ_label: AnyBackwardLabel, succ_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the backward label of succ_vertex to the vertex.

Corresponds to BACK([vertex]⊕[succ_vertex, ...]) in Vidal et al. [VCGP14].

Parameters:

succ_label (AnyBackwardLabel) – The backward label of the successor vertex
succ_vertex (Vertex) – The successor vertex
vertex (Vertex) – The vertex
arc (Arc) – The arc connecting succ_vertex to vertex. Note that this corresponds to the reverse arc of the forward direction.

Returns:

The propagated backward label

Return type:

AnyBackwardLabel

evaluate_insertion(evaluation: Evaluation, instance: Instance, route: Route, after_position: int, vertex_id: VertexID) → float

Evaluates inserting a vertex into a route after the specified position.

Parameters:

evaluation (Evaluation) – The evaluation function
instance (Instance) – The instance
route (Route) – The route
after_position (int) – The position after which the vertex is inserted
vertex_id (VertexID) – The id of the vertex to insert

Returns:

The cost of the route with the vertex inserted

Return type:

float

evaluate_insertion(evaluation: Evaluation, instance: Instance, route: Route, after_position: int, vertex: Vertex) → float

Evaluates inserting a vertex into a route after the specified position.

Parameters:

evaluation (Evaluation) – The evaluation function
instance (Instance) – The instance
route (Route) – The route
after_position (int) – The position after which the vertex is inserted
vertex (Vertex) – The vertex to insert

Returns:

The cost of the route with the vertex inserted

Return type:

float

evaluate_insertion(evaluation: Evaluation, instance: Instance, route: Route, after_position: int, node: Node) → float

Evaluates inserting a node into a route after the specified position.

Parameters:

evaluation (Evaluation) – The evaluation function
instance (Instance) – The instance
route (Route) – The route
after_position (int) – The position after which the vertex is inserted
node (Node) – The node to insert

Returns:

The cost of the route with the vertex inserted

Return type:

float

routingblocks.evaluate_splice(evaluation: Evaluation, instance: Instance, route: Route, forward_segment_end_pos: int, backward_segment_begin_pos: int)

Evaluates splicing two sub-sequences of a route together. The first sub-seuence ends (non-inclusive) at forward_segment_end_pos and the second sub-sequence starts (including) at backward_segment_begin_pos.

Example: Let route = [D, C1, C2, C3, C4, C5, C6, D] and forward_segment_end_pos = 2 and backward_segment_begin_pos = 5. Then the sub-sequences are [D, C1] and [C5, C6, D]. The splice operation thus evaluates the cost of the route [D, C1, C5, C6, D].

Parameters:

evaluation (Evaluation) – The evaluation function
instance (Instance) – The instance
route (Route) – The route
forward_segment_end_pos (int) – The end position of the first sub-sequence (non-inclusive)
backward_segment_begin_pos (int) – The start position of the second sub-sequence

Returns:

The cost of the spliced route

Return type:

float