Network flow & routing¶

Network flow¶

ortidy.flow.flow.max_flow(edges, source, sink, *, tail_column='from', head_column='to', capacity_column='capacity', flow_column='flow')[source]¶

Maximum flow from source to sink over a capacitated edge list.

Returns the edges (same backend) with a flow column; objective is the maximum flow value.

Parameters:

edges (Any)
source (Any)
sink (Any)
tail_column (str)
head_column (str)
capacity_column (str)
flow_column (str)

Return type:

SolveResult

ortidy.flow.flow.min_cost_flow(edges, supplies, *, tail_column='from', head_column='to', capacity_column='capacity', cost_column='cost', node_column='node', supply_column='supply', flow_column='flow')[source]¶

Minimum-cost flow over a capacitated, costed edge list with node supplies.

supplies is a frame of (node, supply) (positive = source, negative = sink). Returns the edges (same backend) with a flow column; objective is the minimum total cost.

Parameters:

edges (Any)
supplies (Any)
tail_column (str)
head_column (str)
capacity_column (str)
cost_column (str)
node_column (str)
supply_column (str)
flow_column (str)

Return type:

SolveResult

ortidy.flow.flow.shortest_path(edges, source, sink, *, tail_column='from', head_column='to', weight_column='weight', flow_column='onPath')[source]¶

Shortest path from source to sink, solved as a unit min-cost flow.

Returns the edges (same backend) with a boolean-ish onPath column (1 on the chosen path); objective is the path length.

Parameters:

edges (Any)
source (Any)
sink (Any)
tail_column (str)
head_column (str)
weight_column (str)
flow_column (str)

Return type:

SolveResult

Transportation¶

ortidy.transportation.transportation.transportation(edges, supply, demand, *, source='source', sink='sink', cost='cost', quantity_column='quantity')[source]¶

Solve a (balanced) transportation problem from a tidy edge list.

Parameters:

edges (Any) – One row per allowed (source, sink) lane with its unit cost.
supply (Mapping[Any, float] | Any) – Per-source supply, as a {source: qty} mapping or a two-column (source, qty) frame.
demand (Mapping[Any, float] | Any) – Per-sink demand, as a {sink: qty} mapping or a two-column (sink, qty) frame.
source (str) – Column names within edges.
sink (str) – Column names within edges.
cost (str) – Column names within edges.
quantity_column (str) – Name of the added shipped-quantity column.

Returns:

SolveResult whose frame is the edge frame (same backend) plus a quantity column; objective is the total shipping cost. Total supply must equal total demand (raises ValueError otherwise).

Return type:

SolveResult

Routing¶

ortidy.routing.routing.solve_routing(df, vehicles=1, *, locations=None, starting_point=0, max_distance=3000, span_cost_coefficient=100, time_limit=1.0, vehicle_id_column='vehicleId', capacity_column='capacity', demand_column='demand', pickups_deliveries=None, pickup_column='pickup', delivery_column='delivery', time_windows=None, node_column='node', open_column='open', close_column='close', service_time=0, time_horizon=100000, penalties=None, vehicle_fixed_cost=None)[source]¶

Solve a vehicle-routing problem over a distance matrix.

Parameters:

df (Any) – A square distance matrix (a row/column per location).
vehicles (int | Any) – Number of vehicles, or a frame with a vehicle-id column (and an optional capacity column for the capacitated variant).
locations (Any) – Optional frame with a demand column (capacitated routing).
starting_point (str | int) – Depot node — a column name or positional node index.
max_distance (int) – Per-vehicle max travel distance (distance dimension).
span_cost_coefficient (int) – Global span cost coefficient (load balancing).
time_limit (float) – Solver wall-clock limit in seconds.
vehicle_id_column (str) – Vehicle-id column in the vehicles frame.
capacity_column (str) – Vehicle-capacity column in the vehicles frame.
demand_column (str) – Demand column in the locations frame.
pickups_deliveries (Any) – Optional frame of (pickup, delivery) node pairs; each pair is served by one vehicle, pickup before delivery (VRP-PD).
pickup_column (str) – Pickup-node column within pickups_deliveries.
delivery_column (str) – Delivery-node column within pickups_deliveries.
time_windows (Any) – Optional frame of (node, open, close) arrival windows (VRPTW); travel time is taken from the distance matrix plus service_time per stop.
node_column (str) – Node column within time_windows.
open_column (str) – Window-open column within time_windows.
close_column (str) – Window-close column within time_windows.
service_time (int) – Per-node service time added to travel time (VRPTW).
time_horizon (int) – Upper bound on the time dimension (VRPTW).
penalties (Any) – Optional (node, penalty) frame or {node: penalty} mapping making those visits optional — a node may be dropped at its penalty cost (prize-collecting routing). Dropped nodes appear in metadata["dropped"].
vehicle_fixed_cost (int | None) – Optional fixed cost charged per vehicle that is actually used, so the solver minimizes the number of vehicles (fleet sizing).

Returns:

SolveResult whose frame (same backend as df) is an edge list of trips with route features, plus status and objective (total distance).

Return type:

SolveResult

ortidy.routing.distance.distance_matrix(locations, *, method='euclidean', x='x', y='y', lat='lat', lon='lon', id_column=None)[source]¶

Build an N×N distance matrix from a locations frame.

Parameters:

locations (Any) – Frame of locations.
method (str) – "euclidean" (uses x/y) or "haversine" (uses lat/lon, great-circle distance in kilometres).
x (str) – X-coordinate column for the euclidean method.
y (str) – Y-coordinate column for the euclidean method.
lat (str) – Latitude column for the haversine method.
lon (str) – Longitude column for the haversine method.
id_column (str | None) – Optional column whose values label the matrix rows/columns. Defaults to positional labels "0"…"N-1".

Returns:

A square distance matrix as a native frame (same backend as locations), with one column per location labelled by id_column (or position).

Return type:

Any