Exact replenishment facility placement

RoutingBlocks provides an implementation of the exact replenishment facility placement algorithm described in Schiffer and Walther [SW18]. The algorithm models the problem as a resource-constrained shortest path problem (CSP) on an auxilliary graph, solved for each route in the solution independently. The auxilliary graph comprises a vertex for each customer node in the route, and allows detours to replenishment facilities by inserting copies of each facility between two consecutive customer vertices (See Figure 1). We refer to Schiffer and Walther [SW18] for a comprehensive description of this procedure.

_images/auxilliary_graph.png

Figure 1: Auxilliary graph for a route with three customers. The dashed lines indicate potential detours to the replenishment facilities.

RoutingBlock’s implementation of this algorithm that takes care of label mangement, dominance-based path pruning, graph building, and other boilerplate tasks while providing an interface to abstract problem-specific functionality, i.e., label repre- sentation, resource extension functions, and dominance (cf. routingblocks.Propagator). The design of this interface bases on the abstractions introduced in Irnich [Irn08].

Customizing this algorithm to a specific problem instance is analogous to implementing a custom evaluation class. Specifically, this requires implementing the routingblocks.Propagator interface and providing a custom label class. The solver (routingblocks.FacilityPlacementOptimizer) can be configured to use a custom propagator by passing it in the constructor.

Warning

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

The pseudocode listed below outlines how the FacilityPlacementOptimizer accesses the propagator interface:

Pseudocode for the FacilityPlacementOptimizer, lines using the propagator interface are highlighted.
 1def extract_label():
 2    # Find the vertex with the cheapest label in the node queue
 3    vertex_with_cheapest_label = find_vertex_with_cheapest_label(node_queue)
 4    cheapest_label = extract_cheapest_label(vertex_with_cheapest_label)
 5    for each label settled at vertex_with_cheapest_label:
 6        # Check if the label is dominated
 7        if propagator.dominates(settled_label, cheapest_label):
 8            break
 9        if propagator.order_before(cheapest_label, settled_label):
10            # If the cheapest label is ordered before the settled label, the cheapest label cannot be dominated anymore
11            # as all later settled labels will also be ordered before cheapest label
12            return cheapest_label, vertex_with_cheapest_label
13
14    # Restart the search
15    extract_label()
16
17
18def optimize(route: List[VertexID]) -> List[VertexID]:
19    # Prepare the propagator
20    propagator.prepare(route)
21    # Build the auxiliary graph from the input route, removing any existing stations
22    build_auxiliary_graph(route)
23    # Create the root label and add it to the first bucket
24    root_label = propagator.create_root_label()
25    add_unsetted_label(root_label, depot)
26    # Enqueue the first vertex (depot) in the _node_queue
27    enqueue(depot)
28    while node_queue is not empty:
29        # Extract the next cheapest label and its corresponding origin vertex from all unsettled label
30        label, origin = extract_label()
31        # Check if the extracted label is a final label (feasible solution) using
32        if propagator.is_final_label(label):
33            return propagator.extract_path(label)
34        # Propagate the extracted label to all adjacent vertices in the graph
35        for each vertex adjacent to origin:
36            label_at_adjacent_vertex = propagator.propagate(label, origin, vertex, get_arc(origin, vertex))
37            if label_at_adjacent_vertex is not None:
38                # Add the candidate label to the corresponding bucket in _buckets
39                add_unsetted_label(label_at_adjacent_vertex, vertex)
40                enqueue(vertex)
41        # Place the label in the set of settled labels
42        settle(label, origin, propagator.order_before)
class routingblocks.FacilityPlacementOptimizer(instance: Instance, propagator: Propagator)

Algorithm that inserts visits to replenishment facilities at optimal locations into a route.

Parameters:

  • instance (Instance) – The instance.

  • propagator (Propagator) – The propagator to use.

optimize(route_vertex_ids: List[VertexID])

Inserts visits to replenishment facilities at optimal locations into the route represented by the given vertex IDs.

Parameters:

route_vertex_ids (List[VertexID]) – The vertex IDs of the route.

Returns:

The vertex IDs of the optimized route.

Return type:

List[VertexID]

class routingblocks.Propagator

The Propagator class implements problem-specific ordering, dominance, and propagation functions. It’s design bases on the concepts introduced in Irnich [Irn08]. 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 instead.

cheaper_than(label: Any, other_label: Any)

Checks whether the label is cheaper than the other label, i.e., has lower cost.

Parameters:

  • label (Any) – The (potentially) cheaper label.

  • other_label (Any) – The (potentially) more expensive label.

Returns:

True if the label is cheaper than the other label, False otherwise.

Return type:

bool

create_root_label()

Creates the initial label for the dynamic programming algorithm. Represents the state at the source node, i.e. the depot node. :return: The initial label.

Return type:

Any

dominates(label: Any, other_label: Any)

Checks whether the label dominates the other label.

Parameters:

  • label (Any) – The (potentially) dominating label.

  • other_label (Any) – The (potentially) dominated label.

Returns:

Return type:

bool

extract_path(label: Any)

Extracts the path represented by label, converting it to a list of vertex IDs.

Parameters:

label (Any) – The label that represents the path.

Returns:

The list of vertex IDs visited on the path.

Return type:

List[VertexID]

is_final_label(label: Any)

Checks whether the label is the final label, i.e. whether it represents a depot-depot path. :param label: The label to check. :return: True if the label is final, False otherwise.

Parameters:

label (Any) –

Return type:

bool

order_before(label: Any, other_label: Any)

Whether the label should be ordered before the other label. This is used to determine the order in which labels are stored in the set of settled labels, which is important for dominance checks: the checks considers only labels that would be ordered before the label being checked.

Parameters:

  • label (Any) – The (potentially) earlier label.

  • other_label (Any) – The (potentially) later label.

Returns:

True if the label should be ordered before the other label, False otherwise.

Return type:

bool

prepare(route_vertex_ids: List[VertexID])

Prepare the propagator before running the algorithm on the route represented by the given vertex IDs. :param route_vertex_ids: The vertex IDs of the route.

Parameters:

route_vertex_ids (List[VertexID]) –

Return type:

None

propagate(label: Any, origin_vertex: Vertex, target_vertex: Vertex, arc: Arc)

Propagates the label to the target vertex, using the given arc. This creates a new label that represents the state at the target vertex. Return None if the resulting path would be infeasible.

Parameters:

  • label (Any) – The label to propagate.

  • origin_vertex (Vertex) – The origin vertex of the arc.

  • target_vertex (Vertex) – The target vertex of the arc.

  • arc (Arc) – The arc to propagate the label along.

Returns:

The propagated label, or None if the resulting path would be infeasible.

Return type:

Optional[Any]