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 typenumpy.array
) andweight
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
andmin_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 algorithmsGreedyElim
Greedy Elimination ProcedureGRASP
GRASPPSOLGENT
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 ofSHIFT_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