A comparison of two routing methods shows that speed and memory pull in different directions.
Finding a bus route sounds like a solved problem. You know where you are, you know where you want to go, and you want the shortest combination of lines in between. It turns out there is more than one way to compute that answer.
Dijkstra is the classic choice. It expands outward from the starting point until it reaches the destination. Routing software has relied on it for decades because it is reliable and its results are predictable.
Ant colony optimization takes a different path entirely. It borrows the behaviour of real ants, which find short routes by laying down pheromone trails that later ants follow. In software, simulated ants explore a graph repeatedly and the best paths accumulate artificial pheromone.
The study asked a specific question: can ant colony optimization produce recommendations as good as Dijkstra when both get the same resources? The team ran Dijkstra first to establish the best route, then let the ant based method try to match it.
The ant based approach was more efficient in execution time and in the number of pathways it traversed. The trade-off was memory. The findings suggest that ant colony optimization may need a larger memory budget to deliver the outcomes the researchers were looking for.
The honest reading is that neither method wins outright. Dijkstra gives a predictable answer with a modest footprint. Ant colony optimization can move faster across a large search space, but it asks for more memory to get there. Which one fits depends on the device and the shape of the network.
Abdul Jabbar and Aryo Pinandito (2023). Recommending Public Transit Route: Ant-Colony Optimization or Dijkstra? 2023 International Conference on Modeling and E-Information Research, Artificial Learning and Digital Applications.
DOI10.1109/ICMERALDA60125.2023.10458207 (opens in a new tab)
