module documentation
Solve traveling salesman problems with bound and branch
Implements a variant of the bound and branch algorithm to solve a cluster-based variant of an assymetric traveling salesman problem. This determines the optimal order of components to create the cutting path. The clusters are introduced because ordered list of points comprising a component path can be navigated either forward or backward, but not both.
| Function | bnb |
Undocumented |
| Function | calculate |
Undocumented |
| Function | create |
Create matrix of distances between nodes |
| Function | generate |
Create brothers (clusters) to track which nodes represent the same component |
| Function | plot |
Undocumented |
| Function | tsp |
Find solution to a clustered, assymetric traveling salesman problem with bound and branch |
Create matrix of distances between nodes
| Parameters | |
numint | Number of nodes in the problem. Equal to twice the number of components |
brothers:dictionary | Map of node clusters |
nodes:list | List of all component objects in the scene |
| Returns | |
list | Cost to travel between two nodes |
Create brothers (clusters) to track which nodes represent the same component
| Parameters | |
numint | Number of nodes in the problem. Equal to twice the number of components" |
| Returns | |
dictionary | Map of node clusters |
Find solution to a clustered, assymetric traveling salesman problem with bound and branch
| Parameters | |
matrix:list | Matrix of edge costs between nodes |
brothers:dictionary | Maps which nodes belong to which clusters |
| Returns | |
tuple |
|