# What we Solve¶

Using the Flowty Optimisation Solver you can solve models like

\begin{aligned} \min{ } & \sum_{k \in K} c_k x_k + \sum_{(V,E) \in G} \Big ( \sum_{v \in V} c_v x_v + \sum_{e \in E} c_e x_e \Big ) + \sum_{i \in N} c_i y_i \\ \text{s.t. } & \sum_{k \in K} \alpha_{jk} x_k + \sum_{(V,E) \in G} \Big (\sum_{v \in V} \alpha_{jv} x_v + \sum_{e \in E} \alpha_{je} x_e \Big ) + \sum_{i \in N} \alpha_{ji} y_i = b_j & & j \in M \\ & x_k, x_v, x_e \geq 0 && (V,E) \in G, v \in V, e \in E\\ & L_k \leq x_k \leq U_k && k \in K \\ & y_i \in [\mathbb{R}, \mathbb{Z}, \mathbb{B}] && i \in N \end{aligned}

where $$N$$ is the set of general (master) variables, $$M$$ is the set of constraints, $$(g, s, t) \in K$$ is the set of subproblems with graph $$(V,E)=g \in G$$, vertices $$V$$, edges $$E$$, resource constraints $$R_g$$, and $$s,t \in V$$ is the source and target for the feasible paths for the subproblem. Paths usage may be fractional, integral, or binary.

The Flowty Optimisation Solver is a column generation based solver. It is used to solve mixed integer linear programming models formulated with (resource constrained) paths in specified graphs. The solver is well suited for solving planning & scheduling, routing, and multi-commodity flow problems. The solver is written in C++ with a Python interface.

# Install¶

Install the Flowty python packages

pip install flowty


Flowty runs with

python os platform notes
3.9, 3.10, 3.11, 3.12 Windows 10 x86_64 64-bit Python
- Linux (Ubuntu 22.04, Debian 12/Bookworm) x86_64, arm64 glibc 2.35+
- MacOS 13 (Ventura) x86_64, arm64 glibc 2.35+

# Quick Start¶

Let's solve the vehicle routing problem with time windows.

The objective is to minimize the total cost of routing vehicles from a central depot to a set of customers $$C$$. Each customer $$v \in C$$ must be visited exactly once within a specified time window $$[a_v, b_v]$$ to deliver their required demand $$d_v$$, each customer has a service time it takes to unload the vehicle, and each vehicle has a maximum capacity $$q$$ on goods to deliver. Traveling takes time. If a vehicle arrives early it is allowed to wait for the customer's time window to open.

Vehicles are identical so we only need one graph with one subproblem. Let $$g = (V,E,R)$$ be a graph of vertices $$V$$, edges $$E$$, and resources $$R$$. The depot is split into vertices indexed by 0 and $$|V|-1$$. $$R$$ consists of time and load. time has edge consumption (travel + service time) $$t_e : e \in E$$ and vertex (time window) bounds $$[a_v, b_v] : v \in V$$. load has vertex consumption (demand) $$d_v: v \in V$$ and global (vehicle capacity) bound $$[0,q]$$. We have one subproblem $$k = (g, v_0, v_{|V|-1})$$ with $$L_k=1$$ and $$U_k=|C|$$. The subproblem paths are binary.

The model can be formulated as

\begin{aligned} \min & \sum_{e \in E} c_e x_e \\ \text{s.t. } & x_v \geq 1 && v \in C \\ & 1 \leq x_k \leq |C| && \\ \end{aligned}

with domain of each path binary.

## Code¶

Find the model at examples/v2/vrptw/vrptw.py. Let's run through it.

Import libraries and data and initialize the model

Fetching data

To fetch the benchmark data using fetch_vrptw check out the examples.

# Vehicle Routing Problem with Time Windows
import flowty
import fetch_vrptw

name, n, m, E, C, D, q, T, A, B, X, Y = fetch_vrptw.fetch("C101")

model = flowty.Model()


# set partition constriants
for v in graph.vertices[1 : n - 1]:
model += v == 1


Construct the graph and it's resources. Time and capacity resources are defined as tuples with consumption and bound properties and values.

# one graph with time and demand resources, it is identical for all vehicles
time = "E", T, "V", A, B
capacity = "V", D, "G", q
graph = model.addGraph(costs=C, edges=E, resources=[time, capacity])


Add the subproblem with the graph. This is where the source, target, subproblem bounds, and path integrality is defined.

subproblem = model.addSubproblem(
graph, source=0, target=n - 1, obj=0, lb=1, ub=n - 2, domain="B"
)


Optimise and get back the result.

solution = model.getSolution()
if solution:
print(f"Cost {round(solution.cost)}")
for path in solution.paths:
print(f"Path {path.subproblem.id}: {path.x}")
for edge in path.edges:
print(f"{edge}")