grid.RoutingModel

class grid.RoutingModel(triangular_inequality=True)[source]

Bases: object

High-level model of a Vehicle Routing Problem.

A RoutingModel represents a routing problem as a directed graph of Node and Edge objects together with one or more VehicleType definitions, decision variables, constraints, and an objective. Once configured, the model is compiled to a DIDP model and solved by calling solve().

The class supports several VRP variants depending on which optional attributes are set on the nodes, edges, and vehicle types.

Parameters:

triangular_inequality (bool) – Whether the underlying distance and time data satisfy the triangular inequality.

graph

Directed graph holding Node data on vertices and Edge data on arcs.

Type:

networkx.DiGraph

vehicles

Vehicle types registered on the model, indexed by id.

Type:

dict of int to VehicleType

constraints

Global constraints registered on the model.

Type:

list of Constraint

variables

Global decision variables registered on the model.

Type:

list of Var

objective

The configured objective expression, or None until set_objective() is called.

Type:

Expr or {“total_distance”, “total_vehicles”} or None

depots

Number of nodes flagged as depots.

Type:

int

vehicles_count

Total number of vehicles across all registered types.

Type:

int

vehicle_types

Number of registered VehicleType instances.

Type:

int

shortest_distance

Precomputed shortest-distance data, set via add_shortest_distance().

Type:

optional

shortest_time

Precomputed shortest-time data, set via add_shortest_time().

Type:

optional

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> depot = model.add_node(id=0, depot=True)
>>> a = model.add_node(id=1, demand=3)
>>> b = model.add_node(id=2, demand=5)
>>> distances = {(0, 1): 4, (1, 0): 4, (0, 2): 6, (2, 0): 6, (1, 2): 3, (2, 1): 3}
>>> for (i, j), d in distances.items():
...     _ = model.add_edge(node_from=model.get_node(i), node_to=model.get_node(j), distance=d)
>>> vehicle = model.add_vehicle_type(id=0, count=2, capacity=10)
>>> model.set_objective(metric="distance")
>>> result = model.solve(solver="CABS", time_limit=10)
>>> result["Optimal"]
True
>>> result["Cost"]
13
__init__(triangular_inequality=True)[source]
Parameters:

triangular_inequality (bool)

Methods

__init__([triangular_inequality])

add_constraint(constraint)

Register a global constraint on the model.

add_edge(node_from, node_to[, distance, ...])

Add a directed edge between two nodes of the routing graph.

add_float_var(initial_value[, preference])

Create a global float decision variable on the model.

add_integer_var(initial_value[, preference])

Create a global integer decision variable on the model.

add_node(id[, demand, tw_start, tw_end, ...])

Add a node to the routing graph.

add_nodes_set_var(initial_value)

Create a global set decision variable on the model.

add_shortest_distance(shortest_distance)

Attach precomputed shortest-distance data to the model.

add_shortest_time(shortest_time)

Attach precomputed shortest-time data to the model.

add_vehicle_type(id[, count, capacity, ...])

Register a new vehicle type on the model.

get_edge(node_from, node_to)

Return the Edge connecting two nodes, if any.

get_edges()

Return all edges of the model, sorted by (node_from, node_to).

get_node(id)

Return the Node with the given id.

get_nodes()

Return all nodes of the model, sorted by id.

get_vehicle_type(id)

Return the VehicleType with the given id.

get_vehicle_types()

Return all registered vehicle types, sorted by id.

set_objective([metric, variables, ...])

Configure the objective of the model.

solve([solver, time_limit])

Compile the model to DIDP and solve it.
add_constraint(constraint)[source]

Register a global constraint on the model.

Parameters:

constraint (Expr) – Boolean expression that must hold throughout the route.

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> vehicle = model.add_vehicle_type(id=0, count=1, capacity=10)
>>> load = vehicle.add_integer_var(initial_value=10)
>>> model.add_constraint(load >= 0)
>>> len(model.constraints)
1
add_edge(node_from, node_to, distance=None, travel_time=None)[source]

Add a directed edge between two nodes of the routing graph.

Parameters:

  • node_from (Node) – Source node.

  • node_to (Node) – Destination node.

  • distance (float) – Travel distance along the edge.

  • travel_time (float) – Travel time along the edge.

Returns:

The newly created edge, also retrievable via get_edge().

Return type:

Edge

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> a = model.add_node(id=0, depot=True)
>>> b = model.add_node(id=1, demand=3)
>>> edge = model.add_edge(node_from=a, node_to=b, distance=4, travel_time=6)
>>> edge.distance
4
>>> edge.travel_time
6
add_float_var(initial_value, preference=None)[source]

Create a global float decision variable on the model.

Parameters:

  • initial_value (float) – Initial value of the variable.

  • preference (Literal['low', 'high', None]) – Solver hint indicating preferred direction.

Return type:

Var

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> level = model.add_float_var(initial_value=1.5)
>>> level.initial_value
1.5
>>> level.type
'float'
add_integer_var(initial_value, preference=None)[source]

Create a global integer decision variable on the model.

Parameters:

  • initial_value (int) – Initial value of the variable.

  • preference (Literal['low', 'high', None]) – Solver hint indicating preferred direction.

Return type:

Var

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> counter = model.add_integer_var(initial_value=0, preference="low")
>>> counter
Var_0
>>> counter.initial_value
0
add_node(id, demand=None, tw_start=None, tw_end=None, service_t=None, waiting_t=None, pickup=None, delivery=None, optional=False, max_visits=1, depot=False)[source]

Add a node to the routing graph.

Parameters:

  • id (int) – Unique identifier of the node.

  • demand (dict[str, float] | int | float) – Demand consumed when visiting the node.

  • tw_start (float) – Earliest time at which service can begin.

  • tw_end (float) – Latest time at which service can begin.

  • service_t (float) – Service time required at the node.

  • waiting_t (float) – Maximum waiting time allowed before the time window opens.

  • pickup (dict[str, float]) – Quantities picked up at the node, per commodity.

  • delivery (dict[str, float]) – Quantities delivered at the node, per commodity.

  • optional (bool) – Whether the node may be skipped.

  • max_visits (int) – Maximum number of times the node may be visited.

  • depot (bool) – Whether the node acts as a depot.

Returns:

The newly created node, also retrievable via get_node().

Return type:

Node

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> depot = model.add_node(id=0, depot=True)
>>> customer = model.add_node(id=1, demand=3, tw_start=0, tw_end=10)
>>> customer.demand
3
>>> customer.optional
False
add_nodes_set_var(initial_value)[source]

Create a global set decision variable on the model.

Parameters:

initial_value (set | list) – Initial contents of the set.

Return type:

SetVar

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> visited = model.add_nodes_set_var(initial_value={1, 2, 3})
>>> visited
SetVar_0
>>> sorted(visited.initial_value)
[1, 2, 3]
add_shortest_distance(shortest_distance)[source]

Attach precomputed shortest-distance data to the model.

Used by the converter to tighten dual bounds during solving.

Parameters:

shortest_distance – Pre-computed shortest-distance matrix where entry [i][j] is the minimum distance from node i to node j.

Return type:

None

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> matrix = [[0, 4], [4, 0]]
>>> model.add_shortest_distance(matrix)
>>> model.shortest_distance
[[0, 4], [4, 0]]
add_shortest_time(shortest_time)[source]

Attach precomputed shortest-time data to the model.

Used by the converter to tighten dual bounds during solving.

Parameters:

shortest_time – Pre-computed shortest-time matrix where entry [i][j] is the minimum travel time from node i to node j.

Return type:

None

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> matrix = [[0, 6], [6, 0]]
>>> model.add_shortest_time(matrix)
>>> model.shortest_time
[[0, 6], [6, 0]]
add_vehicle_type(id, count=1, capacity=None, start_node=None, end_node=None)[source]

Register a new vehicle type on the model.

Parameters:

  • id (int) – Unique identifier of the vehicle type.

  • count (int) – Number of vehicles of this type available.

  • capacity (dict[str, float] | int | float) – Vehicle capacity (per commodity if dict, scalar otherwise).

  • start_node (int) – Id of the start node for vehicles of this type.

  • end_node (int) – Id of the end node for vehicles of this type.

Returns:

The newly created vehicle type, also retrievable via get_vehicle_type().

Return type:

VehicleType

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> vehicle = model.add_vehicle_type(id=0, count=3, capacity=15)
>>> vehicle.count
3
>>> vehicle.capacity
15
get_edge(node_from, node_to)[source]

Return the Edge connecting two nodes, if any.

Parameters:

  • node_from (int) – Id of the source node.

  • node_to (int) – Id of the destination node.

Returns:

The edge if one exists between node_from and node_to, otherwise None.

Return type:

Edge

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> a = model.add_node(id=0, depot=True)
>>> b = model.add_node(id=1, demand=3)
>>> _ = model.add_edge(node_from=a, node_to=b, distance=4)
>>> model.get_edge(0, 1).distance
4
get_edges()[source]

Return all edges of the model, sorted by (node_from, node_to).

Return type:

list[Edge]

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> a = model.add_node(id=0, depot=True)
>>> b = model.add_node(id=1, demand=3)
>>> _ = model.add_edge(node_from=a, node_to=b, distance=4)
>>> _ = model.add_edge(node_from=b, node_to=a, distance=4)
>>> len(model.get_edges())
2
get_node(id)[source]

Return the Node with the given id.

Parameters:

id (int) – Node identifier.

Return type:

Node

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> depot = model.add_node(id=0, depot=True)
>>> model.get_node(0) is depot
True
get_nodes()[source]

Return all nodes of the model, sorted by id.

Return type:

list[Node]

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> _ = model.add_node(id=0, depot=True)
>>> _ = model.add_node(id=1, demand=3)
>>> len(model.get_nodes())
2
get_vehicle_type(id)[source]

Return the VehicleType with the given id.

Parameters:

id (int) – Vehicle type identifier.

Return type:

VehicleType

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> vehicle = model.add_vehicle_type(id=0, count=2, capacity=10)
>>> model.get_vehicle_type(0) is vehicle
True
get_vehicle_types()[source]

Return all registered vehicle types, sorted by id.

Return type:

list[VehicleType]

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> _ = model.add_vehicle_type(id=0, count=2, capacity=10)
>>> _ = model.add_vehicle_type(id=1, count=1, capacity=20)
>>> len(model.get_vehicle_types())
2
set_objective(metric=None, variables=None, aggregation='sum', maximize=False)[source]

Configure the objective of the model.

Parameters:

  • metric (Literal['distance', 'time', 'num_vehicles']) – Built-in objective metric to optimise.

  • variables (Var | list[Var]) – Decision variables whose values participate in the objective when a custom aggregation over variables is desired.

  • aggregation (Literal['max', 'sum']) – Aggregation operator used to combine per-route or per-variable contributions.

  • maximize (bool) – If True, the objective is maximised; otherwise minimised.

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> model.set_objective(metric="distance")
>>> model.metric
'distance'
solve(solver='LNBS', time_limit=None)[source]

Compile the model to DIDP and solve it.

Parameters:

  • solver (Literal['LNBS', 'CABS']) – DIDP anytime heuristic search algorithm to use.

  • time_limit (float) – Wall-clock time limit in seconds. None runs until completion or interruption.

Returns:

  • dict

  • Result of the search with the following keys

  • - ``”Optimal”`` (bool) (whether the returned solution is proven optimal.)

  • - ``”Infeasible”`` (bool) (whether the model was proven infeasible.)

  • - ``”Best Bound”`` (int or float) (best dual bound found during search.)

  • - ``”Cost”`` (int, float, or None) (cost of the best feasible solution found, or None if no feasible solution was found.)

  • - ``”Solution”`` (list or None) (best route(s) found, or None if no feasible solution was found.)

Examples

>>> import grid
>>> model = grid.RoutingModel()
>>> depot = model.add_node(id=0, depot=True)
>>> _ = model.add_node(id=1, demand=3)
>>> _ = model.add_node(id=2, demand=5)
>>> distances = {(0, 1): 4, (1, 0): 4, (0, 2): 6, (2, 0): 6, (1, 2): 3, (2, 1): 3}
>>> for (i, j), d in distances.items():
...     _ = model.add_edge(node_from=model.get_node(i), node_to=model.get_node(j), distance=d)
>>> _ = model.add_vehicle_type(id=0, count=2, capacity=10)
>>> model.set_objective(metric="distance")
>>> result = model.solve(solver="CABS", time_limit=10)
>>> result["Optimal"]
True
>>> result["Cost"]
13