aco-routing

Ant Colony Optimization

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

➡️ Check out my Medium article for a detailed walkthrough 🚀

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

This implementation of the ACO algorithm uses the NetworkX graph environment.

🏁 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 ACO
import networkx as nx

Create a NetworkX.Graph object with nodes and edges:

G = nx.DiGraph()

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

Use ACO to find the shortest path and cost between the source and destination:

aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)

aco_path, aco_cost = aco.find_shortest_path(
    source="A",
    destination="D",
    num_ants=100,
)

Output:

ACO path: A -> H -> G -> E -> D
ACO path cost: 8.0

📦 Contents

Ant

aco_routing.Ant

• An Ant that traverses the graph.

ACO

aco_routing.ACO

• The traditional Ant Colony Optimization algorithm that spawns ants at various nodes in the graph and finds the shortest path between the specified source and destination (pseudo code).

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.