Skip to main content

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

Project description

Ant Colony Optimization

Develop Deploy PyPi version Python versions Downloads

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

To install the package directly from PyPi:

$ pip install aco_routing

🎈 Usage

Check out: aco_routing/example.py

Import all the dependencies.

from aco_routing.utils.graph import Graph
from aco_routing.dijkstra import Dijkstra
from aco_routing.utils.simulator import Simulator
from aco_routing.aco import 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 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}")

Simulate a real-life scenario with various episodes of stochastically updating traffic conditions in a city.

Simulator(graph).simulate(source, destination, num_episodes=100, plot=True)

📦 Contents

Graph

aco_routing.utils.graph.Graph

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

Node

aco_routing.utils.graph.Node

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

Edge

aco_routing.utils.graph.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.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.utils.ant.Ant

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

ACO

aco_routing.aco.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.

Simulator

aco_routing.utils.simulator.Simulator

  • The simulator class is used to simulate and evaluate the performance of the candidate algorithm (ACO) with a baseline Dijkstra's Algorithm.
  • It simulates a real-life city, where the traffic conditions change every episode in a conditionally stochastic manner.
  • The ants continue to find the shortest path even after the traffic conditions change.

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.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

aco_routing-1.0.5.tar.gz (11.8 kB view hashes)

Uploaded Source

Built Distribution

aco_routing-1.0.5-py3-none-any.whl (11.4 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page