Custom Features

When native features (see Native Features) are not sufficient, GRID lets users describe custom behaviour through:

  • User-defined variables declared on a VehicleType or on RoutingModel, representing quantities or sets that evolve along a route.

  • Expressions built over these variables using Python operators and the free functions max(), min(), sqrt(), log(), select(), attached to nodes, edges, or the model as constraints or transitions.

The sections below describe these in order (declaring, writing, attaching, and using them in custom objectives), ending with a complete example for the Electric Capacitated Vehicle Routing Problem (ECVRP).

Declaring variables

User-defined variables are declared on a VehicleType. This choice reflects the role of vehicles as the elements that build solutions during search: a VehicleType provides the natural scope for quantities that evolve along a route while remaining shared across identical vehicles of the same type.

Three methods are available:

VehicleType.add_integer_var

Creates an integer variable with an initial value. An optional preference ("low" or "high") is a solver hint: if set, the user must guarantee that, among two partial routes ending at the same node, the route with the preferred value of the variable always leads to a better solution.

VehicleType.add_float_var

Same as the integer version but for floating-point variables.

VehicleType.add_nodes_set_var

Creates a set variable whose elements are node ids. Useful to keep track of subsets of the graph along a route (e.g. unvisited stations, served commodities, …).

The returned objects are Var (integer or float) and SetVar. They combine with Python operators to build expression trees.

Global variables can also be declared on RoutingModel through analogous add_* methods. These are not tied to any vehicle type and apply across the whole model.

Writing expressions

Expressions are built by combining variables, Python literals, and the free functions of grid. Python’s arithmetic, comparison, and logical operators are overloaded on Var and SetVar to produce expression trees with the expected semantics:

# `load`, `battery` are Var instances obtained from a VehicleType.

load - 3                    # subtraction, result is an integer expression
battery - distance * rate   # composition with literals
load >= 0                   # comparison, result is a boolean expression
(load > 0) & (battery > 0)  # logical AND, result is a boolean expression

For operations that have no equivalent Python operator, use the free functions max(), min(), sqrt(), log(), select():

grid.max([load, 0])           # element-wise max over a list
grid.sqrt(distance)           # square root
grid.select(distance_row, j)  # indexing into an array expression

Set variables additionally expose set-algebra methods: add(), remove(), contains(), is_empty(), len(). Each returns an expression usable in further operations:

unv_stations.contains(s)      # boolean: is s currently in the set
unv_stations.remove(s)        # set expression: set with s removed
unv_stations.is_empty()       # boolean: is the set empty
unv_stations.len()            # integer: cardinality of the set

Attaching expressions

An expression alone is just a tree of operations. To affect the model, it must be attached to an entity as either a constraint or a transition.

Constraints. Register a boolean precondition that must hold for the node, edge, or model to remain feasible. They are added via Node.add_constraint, Edge.add_constraint, or RoutingModel.add_constraint depending on scope. Local constraints (on nodes or edges) are checked when the entity is reached; global constraints are checked throughout the route.

Transitions. Register an update of a variable when the node or edge is included in a route, via Node.add_transition or Edge.add_transition. The signature is add_transition(var, expression): when the node or edge is traversed, var is assigned the value of expression, which may depend on the current value of var and any other variables.

Constraints and transitions on nodes apply when the vehicle visits the node; constraints and transitions on edges apply when the vehicle traverses the edge.

Custom objectives

set_objective() accepts a variables parameter in addition to metric. Passing a single Var or a list of Var instances defines a custom objective:

model.set_objective(
    variables=[cost_var_on_type_1, cost_var_on_type_2],
    aggregation="max",
)

When a list of variables is given, each variable must be associated with a distinct VehicleType, ensuring a one-to-one mapping between optimisation variables and vehicle types in the fleet. The aggregation is applied to the final values of the variables at the end of each route.

Example: ECVRP

In the Electric Capacitated Vehicle Routing Problem (ECVRP), a fleet of battery-powered vehicles based at a single depot must serve a set of customers, each with a positive demand, without exceeding the vehicle capacity. In addition to customers, the graph contains charging stations: a vehicle may visit a station to recharge its battery fully, and the same station may be visited several times. Each vehicle leaves the depot fully loaded and fully charged. Traversing an edge discharges the battery by an amount that grows with the distance travelled and with the current load, through an energy-consumption rate r + load / q (with q the capacity and r a fixed constant). The battery must never become negative along any edge. All routes start and end at the depot, and the objective is to minimise the total travel distance.

This problem cannot be expressed with native features alone, because the battery discharge along an edge depends on the current value of the load variable, a coupling that native features do not provide. It is modelled with three user-defined variables and the expressions that update and constrain them:

  • load: an integer variable tracking the remaining vehicle load, initialised to the capacity q and decreased at each customer.

  • battery: a float variable tracking the remaining charge, initialised to the maximum level b, decreased along each edge and reset to b at each charging station.

  • unv_stations: a set variable holding the stations not yet visited since the last customer, used to forbid cycles that consist only of charging stations.

import grid

# Inputs (provided externally):
# m: number of vehicles
# q: vehicle capacity
# b: maximum and initial battery level
# customers, stations: sets of customer and station node ids
# mu[i]: demand of customer i
# edges: set of edges (i, j) with distance d[i][j]
# r: fixed battery consumption rate
# min_from[i]: minimum distance from node i to any next node

model = grid.RoutingModel()

v = model.add_vehicle_type(id=0, count=m)
load = v.add_integer_var(initial_value=q)
battery = v.add_float_var(initial_value=b, preference="high")

depot = model.add_node(id=0, depot=True)
depot.add_constraint(load < q)

for i in customers:
    customer = model.add_node(id=i)
    customer.add_constraint(load - mu[i] >= 0)
    customer.add_transition(var=load, expression=load - mu[i])

for s in stations:
    station = model.add_node(id=s, optional=True, max_visits=None)
    station.add_transition(var=battery, expression=b)

for (i, j) in edges:
    edge = model.add_edge(
        node_from=model.get_node(i),
        node_to=model.get_node(j),
        distance=d[i][j],
    )
    next_battery = battery - d[i][j] * (r + load / q)
    if j not in customers:
        edge.add_constraint(next_battery >= 0)
    else:
        edge.add_transition(var=battery, expression=next_battery)
        edge.add_constraint(
            next_battery >= min_from[j] * (r + (load - mu[j]) / q)
        )

model.set_objective(metric="distance")

# Avoid station-only cycles: track unvisited stations along the route
unv_stations = v.add_nodes_set_var(initial_value=stations)
for i in customers:
    customer = model.get_node(i)
    customer.add_transition(var=unv_stations, expression=stations)
for s in stations:
    station = model.get_node(s)
    station.add_constraint(unv_stations.contains(s))
    station.add_transition(
        var=unv_stations, expression=unv_stations.remove(s)
    )

result = model.solve(solver="LNBS", time_limit=300)

Walkthrough:

  • The vehicle type v carries the two evolving quantities load and battery. load starts at the capacity q; battery starts at the maximum level b and is declared with preference="high", since a route reaching a node with more charge is never worse than one reaching it with less.

  • The depot enforces load < q as a constraint, requiring that any vehicle returning to the depot has served at least one customer. Vehicles that never leave the depot remain feasible.

  • Customer nodes update load by subtracting the customer’s demand and constrain it to remain non-negative.

  • Station nodes are optional and may be visited any number of times (max_visits=None). Visiting a station resets battery to the full level b without affecting the load.

  • Edge behaviour depends on the destination. The discharge along edge (i, j) is d[i][j] * (r + load / q), which grows with both distance and current load. Edges leading to a station or the depot only require the residual battery to stay non-negative; edges leading to a customer additionally update battery and require enough residual charge to reach at least one further node, accounting for the lower load after the customer is served.

  • The objective minimises the total travel distance via the "distance" native metric.

  • The final block adds the set variable unv_stations to forbid station-only cycles. It is reset to the full set of stations whenever a customer is visited; a station may be visited only if it is currently in the set, and is removed from the set upon visit.

The same modelling style (declare evolving quantities on the vehicle type, attach updates and preconditions to nodes and edges, and optionally register a custom objective) applies to other VRP variants beyond the scope of native features. For the technical reference of every class and function used above, see the API Reference.