Skip to content

What we Solve

Using the Flowty Optimisation Solver you can solve models like

min⁡∑k∈Kckxk+∑(V,E)∈G(∑v∈Vcvxv+∑e∈Ecexe)+∑i∈Nciyis.t. ∑k∈Kαjkxk+∑(V,E)∈G(∑v∈Vαjvxv+∑e∈Eαjexe)+∑i∈Nαjiyi=bjj∈Mxk,xv,xe≥0(V,E)∈G,v∈V,e∈ELk≤xk≤Ukk∈Kyi∈[R,Z,B]i∈N \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

min⁡∑e∈Ecexes.t. xv≥1v∈C1≤xk≤∣C∣ \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()

Add the set partitioning constraints

# 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]}, "time"
load = {"V": [D], "G": [q]}, "load"
graph = model.addGraph(edges=E, edgeCosts=C, resources=[time, load], pathSense="S")

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

timeRule = "Window", ["time"]
loadRule = "Capacity", ["load"]
subproblem = model.addSubproblem(
    graph, source=0, target=n - 1, obj=0, lb=1, ub=n - 2, domain="B", rules=[timeRule, loadRule]
)

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}")