RoutingBlocks

https://routingblocks.readthedocs.io/en/latest/
Admin
RoutingBlocks is a C++ library for solving vehicle routing problems with metaheuristic algorithms,...
Tokens:54,111
Snippets:513
Trust Score:9.6
Update:4 months ago
Show doc for...
Tokens:
Raw
### Install and Run Sphinx Autobuild

Source: https://routingblocks.readthedocs.io/en/latest/development.html

Install sphinx-autobuild for live-reloading documentation and then run it.

```bash
pip install sphinx-autobuild
sphinx-autobuild docs/source docs/build/html

```

--------------------------------

### Install Development Dependencies

Source: https://routingblocks.readthedocs.io/en/latest/development.html

Install testing and optional documentation dependencies using pip.

```bash
pip install .[test]
pip install .[docs]

```

--------------------------------

### Instance Builder Usage Example

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Illustrates how to use the InstanceBuilder to create routing problem instances. This example defines custom data classes for vertices and arcs and shows the basic setup for instance construction.

```python
from routingblocks import InstanceBuilder, Vertex, Arc

class MyVertexData:
    pass

class MyArcData:
    pass

```

--------------------------------

### Install RoutingBlocks using pip

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Install the latest stable version of the RoutingBlocks library from PyPI.

```bash
pip install routingblocks

```

--------------------------------

### Install Development Version of RoutingBlocks

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Install the bleeding-edge development version directly from the GitHub repository.

```bash
pip install git+https://github.com/tumBAIS/RoutingBlocks

```

--------------------------------

### Local Search Optimization Example

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

This snippet demonstrates setting up and running a local search algorithm. It defines operators, initializes a local search instance, and iterates to find the best solution.

```python
pivoting_rule = rb.BestImprovementPivotingRule()
local_search = rb.LocalSearch(instance, evaluation, None, pivoting_rule)
# Create a set of allowed arcs
arc_set = rb.ArcSet(instance.number_of_vertices)

# Create a set of operators that will be used later when calling the local search
operators = [
    rb.operators.SwapOperator_0_1(instance, arc_set),
    rb.operators.SwapOperator_1_1(instance, arc_set),
    rb.operators.InsertStationOperator(instance),
    rb.operators.RemoveStationOperator(instance),
]

best_solution = create_random_solution(evaluation, instance)
current_solution = copy.copy(best_solution)
for i in range(10):
    # Search the neighborhood of the current solution. This modifies the solution in-place.
    local_search.optimize(current_solution, operators)
    if current_solution.cost < best_solution.cost:
        best_solution = current_solution
        print(f"New best solution found: {best_solution.cost} ({best_solution.feasible})")

    # Perturb the current solution
    current_solution = perturb(current_solution, len(current_solution) // 2)

print("Best solution:")
print(solution)
```

--------------------------------

### prepare_search(_solution : Solution_)

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Called before the search for improving moves is started. This method can be used to initialize search-related data structures.

```APIDOC
## prepare_search(_solution : Solution_)

### Description
Called before the search for improving moves is started.

### Parameters
#### Path Parameters
- **solution** (Solution) - Required - 
```

--------------------------------

### Iterating and Accessing Routes in a Solution

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Demonstrates how to iterate through routes in a Solution object, access a specific route by index, get the total number of routes, and delete a route.

```python
solution = Solution(evaluation, instance, 5)

for route in solution:
    print(route)

print(solution[0])

print(len(solution))

del solution[0]
```

--------------------------------

### ALNS Solver Iteration Example

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

This snippet demonstrates a typical iteration within an ALNS solver loop. It shows how to create a random initial solution, perturb it, perform local search, and update the best solution found. It also illustrates how to collect scores for operators and adapt operator weights.

```python
best_solution = create_random_solution(evaluation, instance)
for i in range(1, number_of_iterations+1):
    current_solution = copy.copy(best_solution)
    # Perturb the current solution
    number_of_vertices_to_remove = int(random.uniform(min_vertex_removal_factor, max_vertex_removal_factor) * sum(
        len(route) - 2 for route in current_solution))
    picked_operators = alns.generate(evaluation, current_solution, number_of_vertices_to_remove)

    # Search the neighborhood of the current solution. This modifies the solution in-place.
    local_search.optimize(current_solution, operators)

    if current_solution.cost < best_solution.cost:
        best_solution = current_solution
        print(f"New best solution found: {best_solution.cost} ({best_solution.feasible})")
        # Update the ALNS solver with the performance of the operators used in the last iteration
        # We assign a score of '4' to the operators that were used to improve the solution
        alns.collect_score(*picked_operators, 4)
    else:
        # Update the ALNS solver with the performance of the operators used in the last iteration
        # We assign a score of '0' to the operators that were not used to improve the solution
        alns.collect_score(*picked_operators, 0)

    # Calculate new operator weights based on the last period
    if i % 20 == 0:
        alns.adapt_operator_weights()

return best_solution
```

--------------------------------

### ALNS Solver Setup with Custom Evaluation

Source: https://routingblocks.readthedocs.io/en/latest/custom_problem_settings.html

This snippet shows how to initialize the ALNS solver with a custom CVRPEvaluation instance. It sets the vehicle storage capacity and optionally adjusts the load penalty.

```python
evaluation = CVRPEvaluation(vehicle_storage_capacity)
evaluation.load_penalty = 1000.0
```

--------------------------------

### prepare_search

Source: https://routingblocks.readthedocs.io/en/latest/localsearch.html

Called before the search for improving moves is started. This method can be used to initialize any necessary state before the search begins.

```APIDOC
## prepare_search

### Description
Called before the search for improving moves is started.

### Parameters
#### Parameters
- **solution** (Solution) - Required - The solution to be improved.

### Return type
None
```

--------------------------------

### cost

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets the total cost of the solution, i.e., the sum of costs of all routes.

```APIDOC
## cost

### Description
Gets the total cost of the solution, i.e., the sum of costs of all routes.

### Returns
The total cost of the solution.

### Return type
float
```

--------------------------------

### Implement Custom Best Improvement with Blinks Pivoting Rule

Source: https://routingblocks.readthedocs.io/en/latest/localsearch.html

This example shows how to implement a custom pivoting rule that selects the best improving move found, with a probability of 'blinking' (continuing the search even after finding a good move). It overrides the select_move and continue_search methods of the base PivotingRule class.

```python
class BestImprovementWithBlinksPivotingRule(routingblocks.PivotingRule):
    def __init__(self, blink_probability: float, randgen: routingblocks.Random):
        routingblocks.PivotingRule.__init__(self)
        self._blink_probability = blink_probability
        self._randgen = randgen
        self._best_move = None
        self._best_delta_cost = -1e-2

    def continue_search(self, found_improving_move: routingblocks.Move, delta_cost: float,
                        solution: routingblocks.Solution) -> bool:
        if delta_cost < self._best_delta_cost:
            self._best_move = found_improving_move
            self._best_delta_cost = delta_cost
            # If we do not blink, we can stop the search. Otherwise we continue.
            # This ensures that we always return the best found move, even if only one is found and that one is blinked.
            if self._randgen.uniform(0.0, 1.0) >= self._blink_probability:
                return False
        return True

    def select_move(self, solution: routingblocks.Solution) -> Optional[routingblocks.Move]:
        move = self._best_move
        self._best_move = None
        self._best_delta_cost = -1e-2
        return move

```

--------------------------------

### insertion_points

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets all possible insertion points in the solution. That is, for each route r, positions [0, len(r) - 2].

```APIDOC
## insertion_points

### Description
Gets all possible insertion points in the solution. That is, for each route r, positions [0, len(r) - 2].

### Returns
A list of NodeLocation objects representing the insertion points in the solution.

### Return type
List[NodeLocation]
```

--------------------------------

### InstanceBuilder.set_depot

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Sets the depot for the instance. This method is used to define the starting point or central hub of the routing problem.

```APIDOC
## set_depot(str_id, vertex_data)

### Description
Sets the depot for the instance.

### Parameters
* **str_id** (str) - The string identifier for the depot.
* **vertex_data** - Additional data associated with the depot vertex.
```

--------------------------------

### cost_components

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets the cost components of the solution, i.e., the sum of costs components of all routes.

```APIDOC
## cost_components

### Description
Gets the cost components of the solution, i.e., the sum of costs components of all routes.

### Returns
A list of cost components for the solution.

### Return type
List[float]
```

--------------------------------

### _property _insertion_points

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets all possible insertion points in the solution. That is, for each route r, positions [0, len(r) - 2]. Returns a list of NodeLocation objects.

```APIDOC
## _property _insertion_points

### Description
Gets all possible insertion points in the solution. That is, for each route r, positions [0, len(r) - 2].

### Returns
A list of NodeLocation objects representing the insertion points in the solution.

### Return type
List[NodeLocation]
```

--------------------------------

### Build Documentation

Source: https://routingblocks.readthedocs.io/en/latest/development.html

Navigate to the docs directory and build HTML documentation using make.

```bash
cd docs
make html

```

--------------------------------

### Initialize Instance and Evaluation

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Parse instance data, create an instance object, and initialize the evaluation object with vehicle capacities and penalty factors. This sets up the problem for optimization.

```python
def solve(instance_path: Path):
    vertices, arcs, params = parse_instance(instance_path)
    instance = create_instance(vertices, arcs)
    vehicle_storage_capacity = params['C']
    # Vehicle battery capacity in units of time:
    # battery capacity * inverse refueling rate = battery capacity / refueling rate
    vehicle_battery_capacity_time = params['Q'] * params['g']

    evaluation = rb.adptw.Evaluation(vehicle_battery_capacity_time, vehicle_storage_capacity)
    # Set the penalty factors used to penalize violations of the time window,
    # the
    # vehicle capacity, and the charge constraints
    evaluation.overload_penalty_factor = 100.
    evaluation.resource_penalty_factor = 100.
    evaluation.time_shift_penalty_factor = 100.
```

--------------------------------

### DestroyOperator.name

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets the name of this operator.

```APIDOC
## DestroyOperator.name

### Description
Get the name of this operator.

### Method
APIDOC

### Endpoint
DestroyOperator.name

### Parameters
None

### Request Example
```json
{}
```

### Response
#### Success Response (200)
- **return value** (str) - The name of the operator.

#### Response Example
```json
{
  "return_value": "operator_name"
}
```
```

--------------------------------

### AdaptiveLargeNeighborhood.repair_operators

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets an iterator over all registered repair operators.

```APIDOC
## AdaptiveLargeNeighborhood.repair_operators

### Description
Get an iterator over all registered repair operators.

### Method
APIDOC

### Endpoint
AdaptiveLargeNeighborhood.repair_operators

### Parameters
None

### Request Example
```json
{}
```

### Response
#### Success Response (200)
- **return value** (Iterator) - An iterator over the registered repair operators.

#### Response Example
```json
{
  "return_value": "Iterator"
}
```
```

--------------------------------

### AdaptiveLargeNeighborhood.destroy_operators

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets an iterator over all registered destroy operators.

```APIDOC
## AdaptiveLargeNeighborhood.destroy_operators

### Description
Get an iterator over all registered destroy operators.

### Method
APIDOC

### Endpoint
AdaptiveLargeNeighborhood.destroy_operators

### Parameters
None

### Request Example
```json
{}
```

### Response
#### Success Response (200)
- **return value** (Iterator) - An iterator over the registered destroy operators.

#### Response Example
```json
{
  "return_value": "Iterator"
}
```
```

--------------------------------

### Solution Constructor (with routes)

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Creates a new Solution object initialized with a provided list of routes. This constructor is useful when you have pre-defined routes to form the initial solution.

```APIDOC
## Solution Constructor (with routes)

### Description
Creates a new Solution object with the specified list of routes.

### Parameters
* **evaluation** (_Evaluation_) – The evaluation object for cost and feasibility calculations.
* **instance** (_Instance_) – The Instance object representing the problem instance.
* **routes** (_List_[Route]_) – The list of routes to include in the solution.
```

--------------------------------

### Solution Constructor (with number of routes)

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Creates a new Solution object with a specified number of empty routes. This is useful for initializing an empty solution structure that will be populated later.

```APIDOC
## Solution Constructor (with number of routes)

### Description
Creates a new Solution object with the specified number of empty routes.

### Parameters
* **evaluation** (_Evaluation_) – The evaluation object for cost and feasibility calculations.
* **instance** (_Instance_) – The Instance object representing the problem instance.
* **number_of_routes** (_int_) – The number of empty routes the solution should contain.
```

--------------------------------

### number_of_non_depot_nodes

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets the number of non-depot nodes in the solution.

```APIDOC
## number_of_non_depot_nodes

### Description
Gets the number of non-depot nodes in the solution.

### Returns
The number of non-depot nodes in the solution.

### Return type
int
```

--------------------------------

### number_of_insertion_points

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets the number of insertion points in the solution.

```APIDOC
## number_of_insertion_points

### Description
Gets the number of insertion points in the solution.

### Returns
The number of insertion points in the solution.

### Return type
int
```

--------------------------------

### AdaptiveLargeNeighborhood.__init__

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Initializes the ALNS solver with a random number generator and a smoothing factor for adaptive weights.

```APIDOC
## AdaptiveLargeNeighborhood.__init__

### Description
Initializes the ALNS solver. Initially, all operators are assigned equal weights of 1. The weights are then adapted based on the performance of the operators in the last period.

### Method
APIDOC

### Endpoint
AdaptiveLargeNeighborhood.__init__

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **randgen** (Random) - Random number generator.
- **smoothing_factor** (float) - Smoothing factor for the adaptive weights. Determines the importance of the historical performance of the operators.

### Request Example
```json
{
  "randgen": "Random",
  "smoothing_factor": 0.5
}
```

### Response
#### Success Response (200)
None

#### Response Example
None
```

--------------------------------

### _property _number_of_non_depot_nodes

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets the number of non-depot nodes in the solution. Returns an integer.

```APIDOC
## _property _number_of_non_depot_nodes

### Description
Gets the number of non-depot nodes in the solution.

### Returns
The number of non-depot nodes in the solution.

### Return type
int
```

--------------------------------

### _property _number_of_insertion_points

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets the number of insertion points in the solution. Returns an integer.

```APIDOC
## _property _number_of_insertion_points

### Description
Gets the number of insertion points in the solution.

### Returns
The number of insertion points in the solution.

### Return type
int
```

--------------------------------

### Building a Vehicle Routing Instance

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

This snippet demonstrates how to use the InstanceBuilder to construct a vehicle routing problem instance. It shows adding a depot, customers, and stations, and then defining arcs between them.

```python
builder = InstanceBuilder()
builder.fleet_size = 3

builder.add_depot("D", MyVertexData())

builder.add_customer("C1", MyVertexData())
builder.add_customer("C2", MyVertexData())

builder.add_station("S1", MyVertexData())

for i, j in product(["D", "S1", "C1", "C2"], ["D", "S1", "C1", "C2"]):
    builder.add_arc(i, j, MyArcData())

instance = builder.build()
```

--------------------------------

### Solution Class Initialization

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Creates a new Solution object with the specified list of routes. The Solution class represents a solution to a VRP problem and maintains a list of Route objects.

```APIDOC
## Solution Class Initialization

### Description
Creates a new Solution object with the specified list of routes. The Solution class represents a solution to a VRP problem and maintains a list of Route objects.

### Parameters

*   **evaluation** (_Evaluation_) – The evaluation object for cost and feasibility calculations.
*   **instance** (_Instance_) – The Instance object representing the problem instance.
*   **routes** (_List_[_Route_]_) – The list of routes to include in the solution.
```

--------------------------------

### non_depot_nodes

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Gets the non-depot nodes in the solution. Useful for removing nodes from the solution.

```APIDOC
## non_depot_nodes

### Description
Gets the non-depot nodes in the solution. Useful for removing nodes from the solution.

### Returns
A list of NodeLocation objects representing the non-depot nodes in the solution.

### Return type
List[NodeLocation]
```

--------------------------------

### copy

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Creates a copy of the solution. This copies routes and nodes.

```APIDOC
## copy()

### Description
Creates a copy of the solution. This copies routes and nodes.

### Returns
A copy of the solution.

### Return type
Solution
```

--------------------------------

### exchange_segment

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Exchanges segments between two routes based on their indices and specified start and end positions within those segments.

```APIDOC
## exchange_segment

### Description
Exchanges segments between two routes using their indices.

### Parameters
* **first_route_index** (_int_) – The index of the first route in the exchange operation.
* **first_route_begin_position** (_int_) – The start position of the segment in the first route.
* **first_route_end_position** (_int_) – The end position of the segment in the first route.
* **second_route_index** (_int_) – The index of the second route in the exchange operation.
* **second_route_begin_position** (_int_) – The start position of the segment in the second route.
* **second_route_end_position** (_int_) – The end position of the segment in the second route.
```

--------------------------------

### InstanceBuilder.add_customer

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Adds a customer to the instance. Each customer represents a destination that needs to be visited.

```APIDOC
## add_customer(str_id, vertex_data)

### Description
Adds a customer to the instance.

### Parameters
* **str_id** (str) - The string identifier for the customer.
* **vertex_data** - Additional data associated with the customer vertex.
```

--------------------------------

### apply(_instance : Instance_, _solution : Solution_)

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Applies the move to the solution. This method modifies the solution based on the defined move.

```APIDOC
## apply(_instance : Instance_, _solution : Solution_)

### Description
Applies the move to the solution.

### Parameters
#### Path Parameters
- **instance** (Instance) - Required - The instance.
- **solution** (Solution) - Required - The solution to be improved.

### Returns
None
```

--------------------------------

### _property _non_depot_nodes

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Gets the non-depot nodes in the solution. Useful for removing nodes from the solution. Returns a list of NodeLocation objects.

```APIDOC
## _property _non_depot_nodes

### Description
Gets the non-depot nodes in the solution. Useful for removing nodes from the solution.

### Returns
A list of NodeLocation objects representing the non-depot nodes in the solution.

### Return type
List[NodeLocation]
```

--------------------------------

### Configure Local Search Solver in RoutingBlocks

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Sets up a local search solver using the best-improvement pivoting rule and initializes an arc set for the instance.

```python
# Create a best-improvement pivoting rule
pivoting_rule = rb.BestImprovementPivotingRule()
# Configure the local search - use the best-improvement pivoting rule
local_search = rb.LocalSearch(instance, evaluation, None, pivoting_rule)
# Create a set of allowed arcs
arc_set = rb.ArcSet(instance.number_of_vertices)
```

--------------------------------

### RepairOperator

Source: https://routingblocks.readthedocs.io/en/latest/metaheuristic_components.html

Abstract base class for repair operators. Provides methods to apply the operator, check applicability, and get the operator's name.

```APIDOC
## RepairOperator

### Description
Abstract base class for repair operators.

### Methods
#### apply
Applies this operator to the given solution. The solution is modified in-place.

Parameters:
* **evaluation** (Evaluation) - The evaluation function to use.
* **solution** (Solution) - The solution to apply the operator to.
* **removed_vertex_ids** (List[VertexID]) - The IDs of the vertices that should be inserted into the solution.

Return type:
None

#### can_apply_to
Check if this operator can be applied to the given solution.

Parameters:
* **solution** (Solution) - The solution to check.

Return type:
bool

#### name
Get the name of this operator.

Return type:
str
```

--------------------------------

### prepare

Source: https://routingblocks.readthedocs.io/en/latest/exact_facility_placement.html

Prepares the propagator for algorithm execution on a given route.

```APIDOC
## prepare(_route_vertex_ids : List[VertexID]_)

### Description
Prepare the propagator before running the algorithm on the route represented by the given vertex IDs.

### Parameters
* **route_vertex_ids** (_List_ _[__VertexID_ _]_) – The vertex IDs of the route.

### Return type
None
```

--------------------------------

### DestroyOperator

Source: https://routingblocks.readthedocs.io/en/latest/metaheuristic_components.html

Abstract base class for destroy operators. Provides methods to apply the operator, check applicability, and get the operator's name.

```APIDOC
## DestroyOperator

### Description
Abstract base class for destroy operators.

### Methods
#### apply
Applies this operator to the given solution. The solution is modified in-place.

Parameters:
* **evaluation** (Evaluation) - The evaluation function to use.
* **solution** (Solution) - The solution to apply the operator to.
* **number_of_vertices_to_remove** (int) - The number of vertices to remove from the solution.

Returns:
A list containing the IDs of the vertices that were removed from the solution.

Return type:
List[VertexID]

#### can_apply_to
Check if this operator can be applied to the given solution.

Parameters:
* **solution** (Solution) - The solution to check.

Return type:
bool

#### name
Get the name of this operator.

Return type:
str
```

--------------------------------

### Create a Random Solution for RoutingBlocks

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Generates a random initial solution by shuffling customers and splitting them into routes. Uses helper functions to create Route and Solution objects.

```python
def create_random_solution(evaluation: rb.Evaluation, instance: rb.Instance):
    customer_vertex_ids = [x.vertex_id for x in instance.customers]
    random.shuffle(customer_vertex_ids)

    # Draw a sequence of positions where to split
    number_of_splits = random.randint(1, len(customer_vertex_ids) // 2)
    split_positions = [0, *sorted(random.sample(range(1, len(customer_vertex_ids) - 1), number_of_splits)),
                       len(customer_vertex_ids)]
    # Create routes according to the split positions. Each route is a list of customer vertex ids.
    routes = [[customer_vertex_ids[route_start_index:route_end_index]] for route_start_index, route_end_index in
              zip(split_positions, split_positions[1:])]
    # Create RoutingBlocks Route objects
    routes = [rb.create_route(evaluation, instance, route) for route in routes]
    # Create RoutingBlocks Solution object
    return rb.Solution(evaluation, instance, routes)
```

--------------------------------

### Adding and Modifying Routes in a Solution

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Shows how to add a route to a Solution and how route modifications (like inserting a vertex) affect the original route object, not the one stored in the solution.

```python
solution = Solution(evaluation, instance, 0)
route = create_route(evaluation, instance, [D, C1, D])
solution.add_route(route)

route.insert_vertex_after(1, C2)
print(route) # [D, C1, C2, D]
print(solution.routes[0]) # [D, C1, D]
```

--------------------------------

### Route Class

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Represents a sequence of vertex visits (Nodes) starting and ending at the depot. It ensures consistency between the forward and backward labels of the nodes in the sequence.

```APIDOC
## Route Class

### Description
Routes represent a sequence of visits to vertices, represented by Node objects. A route starts and ends at the depot. The route class ensures that the information stored in each node’s label is consistent with the forward and backward sequences.

### Example
Route [D, a, b, c, d, e, D], where capital D represents a visit to the depot. Then the route class ensures that the forward labels stored on node ‘c’ represent the sequence [D, a, b, c], that is, are calculated by propagating the forward label at D across arcs (D, a), (a, b), (b, c). Similarly, the backward labels stored on node ‘c’ represent the sequence [c, d, e, D].

Routes behave like lists of nodes, that is, they can e.g. be indexed and iterated over.

### Parameters
* **evaluation** (_Evaluation_) – The evaluation object used for route calculations.
* **instance** (_Instance_) – The instance containing the problem data.
```

--------------------------------

### Create CVRP Instance with InstanceBuilder

Source: https://routingblocks.readthedocs.io/en/latest/custom_problem_settings.html

This function demonstrates how to use the InstanceBuilder to construct a CVRP problem instance. It involves creating custom data objects for vertices and arcs and registering them with the builder.

```python
def create_instance(serialized_vertices, serialized_arcs) -> rb.Instance:
    instance_builder = rb.utility.InstanceBuilder()
    # Create and register the vertices
    for vertex in serialized_vertices:
        # Create problem-specific data held by vertices
        vertex_data = CVRPVertexData(vertex['demand'])
        # Register the vertex depending on it's type
        if vertex['Type'] == 'd':
            instance_builder.set_depot(vertex['StringID'], vertex_data)
        elif vertex['Type'] == 'c':
            instance_builder.add_customer(vertex['StringID'], vertex_data)
        else:
            instance_builder.add_station(vertex['StringID'], vertex_data)

    # Create and register the arcs
    for (i, j), arc in serialized_arcs.items():
        # Create problem-specific data held by arcs
        arc_data = CVRPArcData(arc['distance'])
        instance_builder.add_arc(i, j, arc_data)

    # Create instance
    return instance_builder.build()
```

--------------------------------

### Run Tests

Source: https://routingblocks.readthedocs.io/en/latest/development.html

Navigate to the test directory and run pytest tests.

```bash
cd test
pytest tests

```

--------------------------------

### Implement ALNS Solver

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

This snippet shows how to set up and configure an Adaptive Large Neighborhood Search (ALNS) solver in RoutingBlocks. It includes initializing the evaluation, local search, and registering various destroy and repair operators.

```python
def alns(instance: rb.Instance, vehicle_storage_capacity: float, vehicle_battery_capacity_time: float,
         number_of_iterations: int = 100, min_vertex_removal_factor: float = 0.2,
         max_vertex_removal_factor: float = 0.4):
    evaluation = rb.adptw.Evaluation(vehicle_battery_capacity_time, vehicle_storage_capacity)
    # Set the penalty factors used to penalize violations of the time window,
    # the
    # vehicle capacity, and the charge constraints
    evaluation.overload_penalty_factor = 100.
    evaluation.resource_penalty_factor = 100.
    evaluation.time_shift_penalty_factor = 100.

    pivoting_rule = rb.BestImprovementPivotingRule()
    local_search = rb.LocalSearch(instance, evaluation, None, pivoting_rule)
    # Create a set of allowed arcs
    arc_set = rb.ArcSet(instance.number_of_vertices)

    # Create a set of operators that will be used later when calling the local search
    operators = [
        rb.operators.SwapOperator_0_1(instance, arc_set),
        rb.operators.SwapOperator_1_1(instance, arc_set),
        rb.operators.InsertStationOperator(instance),
        rb.operators.RemoveStationOperator(instance),
    ]
    #############################################################################################
    # End of the code that is identical to the ILS algorithm
    #############################################################################################

    # Create a random engine and seed it with the current time
    randgen = rb.Random(time.time_ns())
    # Create an ALNS solver.
    # Smoothing factor determines the weight of historic performance when selecting an operator.
    smoothing_factor = 0.4
    alns = rb.AdaptiveLargeNeighborhood(randgen, smoothing_factor)

    # Register some operators with the ALNS solver
    alns.add_repair_operator(rb.operators.RandomInsertionOperator(randgen))
    alns.add_repair_operator(rb.operators.BestInsertionOperator(instance,
                                                                rb.operators.blink_selector_factory(
                                                                    blink_probability=0.1, randgen=randgen)))
    alns.add_destroy_operator(rb.operators.RandomRemovalOperator(randgen))
    alns.add_destroy_operator(rb.operators.WorstRemovalOperator(instance,
                                                                rb.operators.blink_selector_factory(
                                                                    blink_probability=0.1, randgen=randgen)))

```

--------------------------------

### Move.apply

Source: https://routingblocks.readthedocs.io/en/latest/localsearch.html

Applies the move to the given instance and solution. This method modifies the solution based on the move's logic.

```APIDOC
## Move.apply

### Description
Applies the move to the solution.

### Parameters
#### Parameters
- **instance** (Instance) - Required - The instance.
- **solution** (Solution) - Required - The solution to be improved.

### Return type
None
```

--------------------------------

### InstanceBuilder Initialization

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Initializes a new InstanceBuilder object. Custom factory functions can be provided for creating vertex and arc objects.

```APIDOC
## InstanceBuilder()

### Description
Initializes a new InstanceBuilder object.

### Parameters
* **create_vertex** (Optional[vertex_factory]) - A factory function for creating vertex objects. Defaults to the constructor of the Vertex class.
* **create_arc** (Optional[arc_factory]) - A factory function for creating arc objects. Defaults to the constructor of the Arc class.
```

--------------------------------

### routes

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Returns an iterator over the routes in the solution.

```APIDOC
## routes

### Description
Returns an iterator over the routes in the solution.

### Returns
An iterator over the routes.

### Return type
Iterator
```

--------------------------------

### cheaper_than

Source: https://routingblocks.readthedocs.io/en/latest/exact_facility_placement.html

Checks if one label is cheaper than another based on cost.

```APIDOC
## cheaper_than(_label : Any_, _other_label : Any_)

### Description
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

Source: https://routingblocks.readthedocs.io/en/latest/exact_facility_placement.html

Creates the initial label for the dynamic programming algorithm, representing the state at the source node.

```APIDOC
## create_root_label()

### Description
Creates the initial label for the dynamic programming algorithm. Represents the state at the source node, i.e. the depot node.

### Returns
The initial label.

### Return type
Any
```

--------------------------------

### Instance._number_of_customers

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Retrieves the number of customers in the instance. This is a property and does not take parameters.

```APIDOC
## Instance._number_of_customers

### Description
Retrieves the number of customers.

### Method
Property access

### Parameters
None

### Request Example
None

### Response
#### Success Response
- **number_of_customers** (int) - The number of customers.

#### Response Example
None
```

--------------------------------

### __len__

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Returns the number of routes in the solution.

```APIDOC
## __len__()

### Description
Returns the number of routes in the solution.

### Returns
The number of routes in the solution.

### Return type
int
```

--------------------------------

### routingblocks.utility.InstanceBuilder

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

A class for building an instance of a vehicle routing problem. It allows adding vertices and arcs, and then constructing the instance.

```APIDOC
## routingblocks.utility.InstanceBuilder

### Description
A class for building an instance of a vehicle routing problem. The builder provides methods to add vertices (depot, customers, and stations) and arcs with their associated data. Once all the necessary data has been added, the builder can create an instance of the problem.

### Parameters
* **create_vertex** (_Optional_[vertex_factory]_) – A factory function for creating vertex objects. Defaults to the constructor of the Vertex class.
* **create_arc** (_Optional_[arc_factory]_) – A factory function for creating arc objects. Defaults to the constructor of the Arc class.
```

--------------------------------

### copy

Source: https://routingblocks.readthedocs.io/en/latest/solution.html

Creates a deep copy of the route.

```APIDOC
## copy

### Description
Creates a deep copy of the route. This includes copying Node objects and labels, but not the underlying Vertex and Instance objects.

### Method
`copy()`

### Returns
- **Route** - A deep copy of the route.
```

--------------------------------

### InstanceBuilder.build

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Constructs and returns an Instance object based on the vertices and arcs that have been added to the builder. It utilizes the specified vertex and arc factories during construction.

```APIDOC
## build()

### Description
Constructs an Instance object based on the vertices and arcs added to the InstanceBuilder. Uses vertex_factory and arc_factory to create the vertices and arcs.

### Returns
* **Instance** - A new Instance object.

### Raises
* **ValueError** - If the InstanceBuilder does not have a depot or at least one customer.
* **ValueError** - If not all arcs are defined between vertices.
```

--------------------------------

### InsertionCache get_best_insertions_for_vertex() Method

Source: https://routingblocks.readthedocs.io/en/latest/auxilliary.html

Retrieves a list of the best possible insertion moves for a given vertex. This method is crucial for exploring insertion options.

```python
get_best_insertions_for_vertex(_vertex_id : VertexID_)
```

--------------------------------

### routingblocks.niftw.FacilityPlacementOptimizer.optimize

Source: https://routingblocks.readthedocs.io/en/latest/niftw.html

Optimizes a given route by inserting visits to replenishment facilities at optimal locations.

```APIDOC
## routingblocks.niftw.FacilityPlacementOptimizer.optimize

### Description
Optimizes the route by inserting visits to replenishment facilities at optimal locations.

### Parameters
* **route_vertex_ids** (List[VertexID]) - The vertex ids of the route to optimize.

### Returns
The optimized route as a list of vertex ids.
```

--------------------------------

### _property _routes

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Returns an iterator over the routes in the solution.

```APIDOC
## _property _routes

### Description
Returns an iterator over the routes in the solution.

### Returns
An iterator over the routes.

### Return type
Iterator
```

--------------------------------

### create_niftw_vertex

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Creates a vertex for a NIFTW (New Insertion First Time Window) problem setting. Note that the 'data' member is not accessible from Python after creation.

```APIDOC
## routingblocks.create_niftw_vertex

### Description
Creates a vertex for an NIFTW problem setting. Stores the provided data directly as a native C++ object. Warning: The data member of the created vertex is not accessible from python.

### Method
routingblocks.create_niftw_vertex

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
None

### Response
#### Success Response
- **vertex** (Vertex) - The created vertex object.

#### Response Example
None
```

--------------------------------

### routingblocks.Evaluation.create_forward_label

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Creates and initializes a forward label for a given vertex. This corresponds to `INIT` in Vidal _et al._ [VCGP14].

```APIDOC
## routingblocks.Evaluation.create_forward_label

### Description
Creates and initializes a forward label for the given vertex. Corresponds to `INIT` in Vidal _et al._ [VCGP14].

### Method
create_forward_label

### Parameters
#### Path Parameters
- **vertex** (Vertex) - Required - The vertex representing singleton route [vertex].

### Returns
- **AnyBackwardLabel** - The initialized backward label.
```

--------------------------------

### generate

Source: https://routingblocks.readthedocs.io/en/latest/metaheuristic_components.html

Generates a new solution by applying a destroy and repair operator selected based on operator weights. Modifies the solution in-place and returns the operators used.

```APIDOC
## generate

### Description
Generate a new solution by applying a destroy and repair operator selected based the on the operator weights. Modifies the solution in-place.

### Parameters
* **evaluation** (_Evaluation_) – The evaluation function to use.
* **solution** (_Solution_) – The solution to generate a new solution from.
* **number_of_vertices_to_remove** (_int_) – The number of vertices to remove from the solution.

### Returns
A tuple containing the destroy and repair operator used to generate the solution.

### Return type
Tuple[DestroyOperator, RepairOperator]
```

--------------------------------

### Instance._number_of_stations

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Retrieves the number of stations in the instance. This is a property and does not take parameters.

```APIDOC
## Instance._number_of_stations

### Description
Retrieves the number of stations.

### Method
Property access

### Parameters
None

### Request Example
None

### Response
#### Success Response
- **number_of_stations** (int) - The number of stations.

#### Response Example
None
```

--------------------------------

### FacilityPlacementOptimizer Pseudocode

Source: https://routingblocks.readthedocs.io/en/latest/exact_facility_placement.html

This pseudocode outlines how the FacilityPlacementOptimizer accesses the propagator interface. Lines using the propagator interface are highlighted.

```python
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)
```

--------------------------------

### order_before

Source: https://routingblocks.readthedocs.io/en/latest/exact_facility_placement.html

Determines if one label should be ordered before another, crucial for dominance checks.

```APIDOC
## order_before(_label : Any_, _other_label : Any_)

### Description
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
```

--------------------------------

### Create RoutingBlocks Instance

Source: https://routingblocks.readthedocs.io/en/latest/getting_started.html

Creates a RoutingBlocks Instance object using the InstanceBuilder, which requires vertex and arc factory functions. This is used to construct the problem instance from parsed data.

```python
import routingblocks as rb

def create_instance(serialized_vertices, serialized_arcs) -> rb.Instance:
    instance_builder = rb.utility.InstanceBuilder(create_vertex=rb.adptw.create_adptw_vertex,
                                                  create_arc=rb.adptw.create_adptw_arc)
    # Create and register the vertices
    for vertex in serialized_vertices:
        # Create problem-specific data held by vertices
        vertex_data = rb.adptw.VertexData(vertex['x'], vertex['y'], vertex['demand'], vertex['ReadyTime'],
                                               vertex['DueDate'],
                                               vertex['ServiceTime'])
        # Register the vertex dependinx for x in self._move_selector(related_vertices)g on it's type
        if vertex['Type'] == 'd':
            instance_builder.set_depot(vertex['StringID'], vertex_data)
        elif vertex['Type'] == 'c':
            instance_builder.add_customer(vertex['StringID'], vertex_data)
        else:
            instance_builder.add_station(vertex['StringID'], vertex_data)

    # Create and register the arcs
    for (i, j), arc in serialized_arcs.items():
        # Create problem-specific data held by arcs
        arc_data = rb.adptw.ArcData(arc['distance'], arc['consumption'], arc['travel_time'])
        instance_builder.add_arc(i, j, arc_data)

    # Create instance
    return instance_builder.build()

```

--------------------------------

### NIFTWFacilityPlacementOptimizer.optimize

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Optimizes a given route by inserting visits to replenishment facilities at their optimal locations. This method is specific to NIFTW problems.

```APIDOC
## optimize

### Description
Optimizes the route by inserting visits to replenishment facilities at optimal locations. :param route_vertex_ids: The vertex ids of the route to optimize. :return: The optimized route as a list of vertex ids.

### Parameters
* **route_vertex_ids** (List[VertexID]) - 

### Return type
List[VertexID]
```

--------------------------------

### Propagator.cheaper_than

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Checks whether one label is cheaper than another label based on cost.

```APIDOC
## Propagator.cheaper_than

### Description
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
```

--------------------------------

### InstanceBuilder.add_station

Source: https://routingblocks.readthedocs.io/en/latest/instance.html

Adds a station to the instance. Stations can represent points like charging stations or service points.

```APIDOC
## add_station(str_id, vertex_data)

### Description
Adds a station to the instance.

### Parameters
* **str_id** (str) - The string identifier for the station.
* **vertex_data** - Additional data associated with the station vertex.
```

--------------------------------

### _routingblocks.operators.BestInsertionOperator.apply

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Applies the BestInsertionOperator to a solution to insert vertices. This is the core method for applying the operator.

```APIDOC
## _routingblocks.operators.BestInsertionOperator.apply

### Description
Applies the operator to insert vertices into the solution.

### Method
Direct method call.

### Parameters
#### Path Parameters
- **evaluation** (_routingblocks.Evaluation_) - Required - The evaluation context.
- **_solution** (_routingblocks.Solution_) - Required - The solution to modify.
- **number_of_inserted_vertices** (_int_) - Required - The number of vertices to insert.

### Return Type
List[int] - A list of inserted vertex indices.
```

--------------------------------

### ADPTWFacilityPlacementOptimizer

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

An ADPTW-specific algorithm for optimizing routes by inserting visits to replenishment facilities at optimal locations.

```APIDOC
## Class: ADPTWFacilityPlacementOptimizer

### Description
ADPTW-specific detour insertion algorithm. Inserts visits to replenishment facilities at optimal locations into a route.

### Parameters
* **instance** (Instance) - The instance.
* **resource_capacity_time** (float) - The vehicle’s resource capacity expressed in units of time, that is, the time it takes to fully replenish the resource of an empty vehicle.

## Method: optimize

### Description
Optimizes the route by inserting visits to replenishment facilities at optimal locations.

### Parameters
* **route_vertex_ids** (List[VertexID]) - The vertex ids of the route to optimize.

### Returns
The optimized route as a list of vertex ids.
```

--------------------------------

### Create Route

Source: https://routingblocks.readthedocs.io/en/latest/full_api.html

Creates a new route object with a specified evaluation, instance, and a list of vertex IDs.

```python
routingblocks.create_route(evaluation, instance, [D, C1, C2, C3, D])
```
Tokens:
Raw