What we Solve¶
Using the Flowty Optimisation Solver you can solve models like
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
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
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}")