Skip to content

Quick Start

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

Install

Install the python package

pip install flowty
conda install -c flowty flowty    

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

For visualization install

pip install networkx matplotlib
conda 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

min(i,j)Ecijxijs.t. (i,j)δ+(i)xij=1iCxij=pP(sp:s=(i,j)1)λp(i,j)E1pPλpCλpBpPxi,jB(i,j)E \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 CC is the set of customers, the depot is split in two such that the vertices are V={0,C+1}CV = \{0,|C|+1\} \cup C, and pPp \in P are paths in a graph G(V,E)G(V,E) subject to time and demand constraints modeled as disposable resources. Demand with vertex consumption did_i and bounds [0,Q][0,Q] for all iVi \in V and time with edge consumption tijt_{ij} for all (i,j)E(i,j) \in E and vertex bounds [ai,bi][a_i,b_i] for all iVi \in V.

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

min(i,j)Ecijxijs.t. (i,j)δ+(i)xij=1iCxi,jB(i,j)E \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

Import libraries and data, and initialize the model

# Vehicle Routing Problem with Time Windows

from flowty import Model, xsum
from flowty.datasets import vrp_rep

bunch = vrp_rep.fetch_vrp_rep("solomon-1987-r1", instance="R102_025")
name, n, es, c, d, Q, t, a, b, x, y = bunch["instance"]

m = Model()

Add the graph and resource constraints.

# one graph, it is identical for all vehicles
g = m.addGraph(obj=c, edges=es, source=0, sink=n - 1, L=1, U=n - 2, type="B")

# adds resources variables to the graph.
# demand and capacity
m.addResourceDisposable(
    graph=g, consumptionType="V", weight=d, boundsType="V", lb=0, ub=Q, name="d"
)

# travel time and customer tine windows
m.addResourceDisposable(
    graph=g, consumptionType="E", weight=t, boundsType="V", lb=a, ub=b, name="t"
)

Add the set partitioning constraints

# set partition constriants
for i in range(n)[1:-1]:
    m += xsum(x * 1 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(n)[1:-1]:
    m.addPackingSet([x for x in g.vars if i == x.source])

Optimize and get back the result.

status = m.optimize()
print(f"ObjectiveValue {m.objectiveValue}")

# get the variable values
for var in m.vars:
    if var.x > 0:
        print(f"{var.name} = {var.x}")

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.