# Quick Start¶

Get started and solve a problem with the Flowty's network optimisation solver.

## Install¶

Clone the examples from github

```
git clone https://github.com/flowty/examples.git
```

Install the python packages

```
pip install flowty or-datasets
```

If you run on Linux make sure that your dependencies are installed.

For visualization install

```
pip install networkx matplotlib
```

## Model¶

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. Each customer must be visited exactly once within a specified time window to deliver their required demand, each customer has a service time it takes to unload the vehicle, and each vehicle has a maximum capacity of goods to deliver. If a vehicle arrives early it is allowed to wait for the customer's time window to start.

The network model can be formulated as

$\begin{aligned} \min{ } & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t. } & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & & i \in C \\ & x_{ij} = \sum_{p \in P} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big ) \lambda_p & & (i,j) \in E \\ & 1 \leq \sum_{p \in P} \lambda_p \leq |C| \\ & \lambda_p \in \mathbb{B} && p \in P \\ & x_{i,j} \in \mathbb{B} && (i,j) \in E \end{aligned}$

where $C$ is the set of customers, the depot is split in two such that the vertices are $V = \{0,|C|+1\} \cup C$, and $p \in P$ are paths in a graph $G(V,E)$ subject to time and demand constraints modeled as disposable resources. Demand with vertex consumption $d_i$ and bounds $[0,Q]$ for all $i \in V$ and time with edge consumption $t_{ij}$ for all $(i,j) \in E$ and vertex bounds $[a_i,b_i]$ for all $i \in V$.

Since the $\lambda$'s are induced from the graph relation we need only to consider the set partitioning constraints in the model

$\begin{aligned} \min{ } & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t. } & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & & i \in C \\ & x_{i,j} \in \mathbb{B} && (i,j) \in E \end{aligned}$

with the graph and resource constraints described above.

## Code¶

Find the model at `examples/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, E, C, D, q, T, A, B, X, Y = fetch_vrptw.fetch("Solomon", "R102", 25)
model = flowty.Model()
```

Add the graph and resource constraints.

```
# one graph, it is identical for all vehicles
g = model.addGraph(obj=C, edges=E, source=0, sink=n - 1, L=1, U=n - 2, type="B")
# adds resources variables to the graph.
# travel time and customer time windows
model.addResourceDisposable(
graph=g, consumptionType="E", weight=T, boundsType="V", lb=A, ub=B
)
# demand and capacity
model.addResourceDisposable(
graph=g, consumptionType="V", weight=D, boundsType="V", lb=0, ub=q
)
```

Add the set partitioning constraints

```
# set partition constriants
for i in range(1, n - 1):
model += flowty.xsum(x for x in g.vars if i == x.source) == 1
```

Add packing sets to help the algorithm. Packing sets are induced by the user and are helpful for the algorithm for path generation and branching decision.

```
# packing set
for i in range(1, n - 1):
model.addPackingSet([x for x in g.vars if i == x.source])
```

Optimise and get back the result.

```
status = model.optimize()
# get the variable values
#
if (
status == flowty.OptimizationStatus.Optimal
or status == flowty.OptimizationStatus.Feasible
):
for path in model.solutions[0].paths:
print(f"Path {path.idx}")
for var in path.vars:
print(f" {var.name}")
```

## Visualization¶

Visualize the solution

```
import math
import networkx
import matplotlib
import matplotlib.pyplot as plt
edges = [x.edge for x in g.vars if not math.isclose(x.x, 0, abs_tol=0.001)]
gx = networkx.DiGraph()
gx.add_nodes_from([i for i in range(n)])
gx.add_edges_from(edges)
pos = {i: (x[i], y[i]) for i in range(n)} # for lists of x,y coordinates
# pos = networkx.spring_layout(gx) # alternative layout
networkx.draw_networkx_nodes(gx, pos, nodelist=gx.nodes)
networkx.draw_networkx_labels(gx, pos, labels={i: i for i in gx.nodes})
networkx.draw_networkx_edges(gx, pos, nodelist=gx.edges)
# plt.show() # if gui backend is supported
plt.savefig("mygraph.png")
```

See the full example.