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=None, 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 | None) – Global span cost coefficient (load balancing). Defaults to 100 normally, but to 0 when vehicle_fixed_cost is set (so span cost doesn’t distort fleet-sizing); pass a value to override.

  • 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). Nodes may be given as matrix column names or positional integers.

  • 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. Nodes may be names or positional integers.

  • 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). Nodes may be names or positional integers. 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). The terminal leg of each vehicle (arrival back at the depot) is flagged with isReturn=True; metadata["vehicles_used"] counts vehicles that serve at least one non-depot stop, and metadata["dropped"] lists unserved optional visits.

Return type:

SolveResult

Example

Filter out depot rows to get just the served stops in visit order:

result = ortidy.solve_routing(matrix, vehicles=3)
depot = "0"  # the starting_point label
stops = result.frame.query("departure != @depot and not isReturn")
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