# Using cspy¶

Here is the guide of how to use the cspy package and the algorithms within.

## Input Requirements¶

In order to use cspy package and the algorithms within, first, one has to create a directed graph on which to apply the algorithms.

To do so, we make use of the well-known networkx package. To be able to apply resource constraints, we have the following input requirements,

Input graphs must be of type

`networkx.DiGraph`

;Input graphs must have an attribute

`n_res`

(set when initialising the graph) which determines the number of resources we are considering for the particular problem;Input graphs must have a single Source and Sink nodes with no incoming or outgoing edges respectively;

Edges in the input graph must have

`res_cost`

(of type`numpy.array`

) and`weight`

attributes.

For example the following simple network fulfills all the requirements listed above:

```
>>> from networkx import DiGraph
>>> from numpy import array
>>> G = DiGraph(directed=True, n_res=2)
>>> G.add_edge('Source', 'A', res_cost=array([1, 0]), weight=1.0)
>>> G.add_edge('A', 'B', res_cost=array([1, 0]), weight=1.0)
>>> G.add_edge('B', 'Sink', res_cost=array([1, 0]), weight=1.0)
```

The algorithms have some common inputs and requirements,

Two lists

`max_res`

and`min_res`

, with lists of the maximum and minimum resource usage to be enforced for the resulting path;

For former, the user must ensure consistency between the index in `res_cost`

and
the index in `max_res`

``min_res``, such that it corresponds to the same resource.
The latter, is due to the fact that some algorithms depend standard shortest path algorithms
(specifically `networkx.astar_path`

), hence, they get stuck.

## Algorithms¶

Have a look and choose which algorithm you’d like to use.
In order to run the algorithms create a appropriate algorithm instance, say `alg`

,
(with the appropriate inputs), call `alg.run()`

, and then access the different elements from the solution.
Attributes include `alg.path`

for a list with the nodes in the path,
`alg.total_cost`

for the accumulated cost of the path,
and `alg.consumed_resources`

for the accumulated resource usage of the path.

`BiDirectional`

: Bidirectional and monodirectional algorithms`GreedyElim`

Greedy Elimination Procedure`GRASP`

GRASP`PSOLGENT`

Particle Swarm Optimization with combined Local and Global Expanding Neighbourhood Topology (PSOLGENT)

The first algorithm `BiDirectional`

, is the only *exact* algorithm in the library.
This means that it provides an exact (optimal) solution to the resource CSP problem.
For this reason, it sometimes takes longer than the others.
The remaining algorithms are metaheuristics,
i.e. they provide fast and approximate solutions to the CSP problem.

If you are interested in custom resource extension functions, see the REFs section.

## Examples¶

The following examples are included in the examples for more in-depth usage.

vrpy: (under development) external vehicle routing framework which uses

`cspy`

to solve different variants of the vehicle routing problem using column generation.jpath : Simple example showing the necessary graph adptations and the use of custom resource extension functions. Also discussed below.

cgar: Complex example using

`cspy`

for column generation applied to the aircraft recovery problem.

Please see individual algorithm documentation for simple examples.

## Simple Example¶

For illustration of most of the things discussed above, consider the following example.

Jane is part-time postwoman working in Delft, Netherlands. However, she is assigned a small area (the Indische Buurt neighbourhood) so when planning her daily route she wants to make it as long and exciting as possible. That is, when planning her routes she has to consider the total shift time, sights visited, travel time, and delivery time. Her shift has to be at most 5 hours.

This problem can easily be modelled as a CSP problem. With the description above, the set of resources can be defined as,

```
R = ['sights', 'shift', 'travel-time', 'delivery-time']
# len(R) = 4
```

Let `G`

denote a directed graph with edges to/from all streets of the Indische Buurt
neighbourhood.
Each edge has an attribute `weight`

and an attribute `res_cost`

which is an array (specifically, a `numpy.array`

)
with length `len(R)`

.
The entries of `res_cost`

have the same order as the entries in `R`

.
The first entry of this array, corresponds to the `'sights'`

resource, i.e. how many sights there are along a specific edge. The last entry of this array, corresponds to the `'delivery-time'`

resource, i.e. time taken to deliver post along a specific edge. The remaining entries can be initialised to be 0.
Also, when defining `G`

, one has to specify the number of resources `n_res`

, which also has to be equal to `len(R)`

.

```
from networkx import DiGraph
G = DiGraph(directed=True, n_res=4) # init network with 4 resources
```

Now, using the open source package OSMnx, we can easily generate a network for Jane’s neighbourhood

```
from osmnx import graph_from_address, plot_graph
M = graph_from_address('Ceramstraat, Delft, Netherlands',
distance=1600,
network_type='walk',
simplify=False)
```

We have to transform the network for one compatible with `cspy`

,
as per the Input Requirements.
The following code will convert a city map into a directed graph,
rename the start/end nodes of Janes walk to be `Source`

and `Sink`

(names which `cspy`

uses),
and calculate the specifics of Jane’s walk (figuring out travel time, adding buildings/sights, etc).

```
from networkx import DiGraph
from jpath_preprocessing import relabel_source_sink, add_cspy_edge_attributes
# Transform M from networkx.MultiGraph to networkx.DiGraph
# This is requirement by the algorithms
G = DiGraph(M, directed=True, n_res=4)
# Relabel nodes the start/end nodes as "Source"/"Sink"
# (The post-office is in Ternatestraat and Jane's home is in Delftweg)
G = relabel_source_sink(G, {"Source": "Ternatestraat", "Sink": "Delftweg"})
# Add Jane's specific resources to the edges
# (For each edge, adds a `res_cost` attribute with an array with the resources consumed along the specific edge)
G = add_cspy_edge_attributes(G)
```

To define the custom REFs, `jane_REF`

, that controls how resources evolve throughout the path,
we require two inputs: an array of current cumulative resource values `res`

,
and the edge that is being considered for an extension of a path `edge`

(which consists of two nodes and the edge data).

```
from numpy import array
from cspy import REFCallback
WALKING_SPEED = 3
class MyCallback(REFCallback):
def __init__(self):
REFCallback.__init__(self)
# Empty attribute for later
self.G = None
def REF_fwd(self, cumul_res, tail, head, edge_res, partial_path,
cumul_cost):
new_res = list(cumul_res)
i, j = tail, head
# Monotone resource
new_res[0] += 1
# Update 'sights' resource
new_res[1] += self.G.edges[i,j]['res_cost'][1]
# Extract the 'travel-time' resource (distance/speed)
new_res[3] = - self.G.edges[i,j]['weight'] / float(WALKING_SPEED)
# # Update 'delivery-time' resource
new_res[4] = self.G.edges[i,j]['res_cost'][4]
# # Update 'shift' resource
new_res[2] += (new_res[3] + new_res[4]) # travel-time + delivery-time
return new_res
```

Hence, each resource is restricted and updated as follows:

`'sights'`

: the cumulative number of sights visited has a dummy upper bound equal to the number of edges in the graph as there is no restriction to as how many sights Jane visits. Additionally, the value of this resource in the final path, will provide us with the accumulated number of sights in the path;`'shift'`

: the cumulative shift time is updated as the travel time along the edge plus the delivery time, the upper bound of`SHIFT_DURATION`

ensures that Jane doesn’t exceed her part-time hours;`'travel-time'`

: the cumulative travel time is updated using the positive distance travelled (`-edge_data['weight']`

) over an average walking speed. Given the relationship between this resource and`'shift'`

: a maximum of the shift duration provides no restriction.`'delivery-time'`

: the cumulative delivery time is simply updated using edge data. Similarly as for the previous resource, a maximum of the shift duration provides no restriction.

Using `cspy`

, Jane can obtain a route `path`

and subject to her constraints as,

```
from cspy import Tabu, BiDirectional
n_edges = len(G.edges()) # number of edges in network
max_res = [n_edges, 5*n_edges, 5, 5, 5]
min_res = [0, 0, 0, 0, 0]
my_callback = MyCallback()
alg = BiDirectional(G,
max_res,
min_res,
REF_callback=my_callback,
direction="forward",
elementary=True)
# Pass preprocessed graph
my_callback.G = alg1.G
alg.run()
print(alg.path) # print route
```

Additionally, we can query other useful attributes as

```
alg.total_cost
alg.consumed_resources
```