aco-routing 1.0.6

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO)

Ant Colony Optimization

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO).

The Ant colony Optimization algorithm is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs (source).

📝 Table of Contents

• Getting Started
• Usage
• Contents

🏁 Getting Started

To install the package directly from PyPi:

$ pip install aco_routing

🎈 Usage

Check out: example.py

Import all the dependencies.

from aco_routing import Graph, Dijkstra, ACO

Create a Graph object.

graph = Graph()

Create Edges between Nodes (nodes are implicitly created if they don't exist).

graph.add_edge("A", "B", travel_time=2)
graph.add_edge("B", "C", travel_time=2)
graph.add_edge("A", "H", travel_time=2)
graph.add_edge("H", "G", travel_time=2)
graph.add_edge("C", "F", travel_time=1)
graph.add_edge("F", "G", travel_time=1)
graph.add_edge("G", "F", travel_time=1)
graph.add_edge("F", "C", travel_time=1)
graph.add_edge("C", "D", travel_time=10)
graph.add_edge("E", "D", travel_time=2)
graph.add_edge("G", "E", travel_time=2)

Define a source and destination as well as create objects for the Dijkstra and ACO classes.

source = "A"
destination = "D"

aco = ACO(graph)
dijkstra = Dijkstra(graph)

Find the shortest path between the source and destination as well the cost of the path using Dijkstra and ACO.

dijkstra_path, dijkstra_cost = dijkstra.find_shortest_path(source, destination)
aco_path, aco_cost = aco.find_shortest_path(source, destination)

print(f"ACO - path: {aco_path}, cost: {aco_cost}")
print(f"Dijkstra - path: {dijkstra_path}, cost: {dijkstra_cost}")

Output:

ACO - path: ['A', 'H', 'G', 'E', 'D'], cost: 8.0
Dijkstra - path: ['A', 'H', 'G', 'E', 'D'], cost: 8.0

📦 Contents

Graph

aco_routing.Graph

• A Directed Graph class which consists of Nodes and Edges.
• The evaporation_rate is initialized here.

Node

aco_routing.Node

• A Node class which represents a node in the Graph and consists of various outgoing edges.

Edge

aco_routing.Edge

• An Edge class which represents a link between 2 nodes in the Graph.
• Each Edge has 2 parameters:
  • travel_time: The amount of time it takes to traverse the edge. A high value indicates more traffic.
  • pheromones: A heuristic parameter i.e., the pheromone values deposited by the ants.

Dijkstra

aco_routing.Dijkstra

• The baseline algorithm to compare the results of the candidate algorithm with.
• The Dijkstra's algorithm (source) returns the shortest path between any 2 nodes in a graph.

Ant

aco_routing.Ant

• The Ant class representing an ant that traverses the graph.

ACO

aco_routing.ACO

• The traditional Ant Colony Optimization algorithm that spawns various ants at random nodes and tries to find the shortest path between the specified source and destination.

---

Contributing

• Post any issues and suggestions on the GitHub issues page.
• To contribute, fork the project and then create a pull request back to master.

License

This project is licensed under the MIT License - see the LICENSE file for details.