Usually I talk about pretty current stuffs, let’s talk future now. And the future is needed to be talked now. Because after some days in this young app industry simple rss readers won’t be considered a quality app anymore. If you look around, Windows Phone in Bangladesh has walked a pretty silent but significant path. And I’m quiet happy that I walked a little too.

I hope the one who is reading this do know Bus Map Dhaka for Windows Phone. If you dont know, the following is the link: http://www.windowsphone.com/en-bd/store/app/bus-map-dhaka/3795f088-028a-4958-bea6-a2d0eb243bd

Now, let’s start talking how this was made. When I started doing this, the first thing that came into my mind is the actual scenario of Dhaka, if you really expect a local bus to come in the very right time exactly every day,  I guess you have optimism as your profession. So, along with finding the best route and other basic operations, I had to believe someday I would face the challenge which will “actually” solve the problem.

Traffic jams are usually one of the common phenomena here, very common as in like brushing your teeth everyday. If it’s not there, you get surprised. But it’s not the only thing that can keep you getting on the right bus. There’s bad road situations, there’s bus shortage, possibly anything that you can’t predict or manage.

I thought big big plans, like putting devices on buses and tracking down each one of them. But think once, just once. When nobody is even curious about putting proper fitness checks on a bus, maintaining  a device would be a overkill for them, and of course will lead my dream service to perish.

What I had it mind was a pretty simple one. If you ever heard of Ant Colony Optimization, I believe in case of Dhaka, it would come to a greater use . Because the shortest path is not always the “right path”.

If you want to know about ant colony optimization algorithm do a wiki read here:
http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Ant_Colony_System

I wanted to follow the traditional Ant Colony Optimization trait here. Let’s put a small city like Dhaka with us like below:

Pretty simple for Dhaka, eh? 😀 Let’s keep it simple for understanding. You will see Node D is kind of the hub of the city, much like our motijheel, mohakhali or other big bus junctions, right? Now, in this city there can be a number of buses, right? Essentially a Bus Route is nothing but a number of these nodes ordered by bus stops.

Let’s make some bus routes, shall we?
1. A-C-E

2. C-D-E-B-A

3. D-E-C-A

For simplicity lets assume all these bus goes and comes back in the same order. Now, I know what you guys are thinking, if I put “distance metrics” on these paths, it’s easy to find a suitable bus route. Like, if you want to take A trip from A to D you can chose bus number 2 or 3. Question is which one should you pick? What if there is more traffic jam in B-E junction and less in C-E? These data changes over time, even in fraction of ten minutes.  You can’t possibly decide every time.

Here ant colony comes so handy. The very basics of Ant Colony Optimization is based on how ants find best paths. In the natural world, ants  wander randomly and after finding food return to their colony while they continuously lay down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food. So, the fact is who knows the best path right now, the bus that just has gone to that path a few minutes ago. Just like the ant. The only deficit we have here is pheromone trail left by ants. Now, remember what we have in hand. We cant put too much on a local bus as they wont take care of it properly.

But what about known bus counters? If we manage to find only time-stamps of a bus arriving at a bus-stoppage somehow, we don’t need to know which one came, just spotting one on a counter, much like spotting an ant on a node.   And based on the frequency of that timestamp, you can actually verify the frequency of buses coming down there. If the adjacent roads are not doing well with traffic jams, you are bound to have a lesser frequency and if it’s smooth sailing you will have a solid frequency. Even if that sounds awkward we can even track ticket sales, although that would be far off, still a usable heuristic metric to understand whether people are actually getting up on a bus or not.

Now, based on that. We want to go to D from A.

We have two bus routes, 2 and 3. Now which to pick? All we have to do is check the pheromone/our very own heuristic cost metric trails and the route that currently has a more favorable reinforcement/feedback. No matter what comes in the road, traffic jams or stuff, within minutes, these would be updated. And as the buses are continuously traveling, the metric will always be updated. And further more, you can even predict a possible next bus time from this too. Or predict a best possible route to go from one place to another on a car. I know, for Dhaka, it might be a bit long shot, still…worth a try.

So, if you believe every bus is a ant running on a direction (although these are defined rather than random). Actually that makes us one step closer to goal. Because logically ant colony optimization finds a best path. As our possible paths are already defined, we don’t have to go through the first state.

There should be usually two steps of ant colony optimization:
1. Edge selection
2. Pheromone Update

As our paths are already defined, edge selection is basically finding eligible bus routes to go from one place to another, it could be a multiple bus journey but I will write about that later.

procedure BMD_Heuristic
    while(not_termination)
       TraverseRoutes()
       RouteActions()
       UpdateMetrics()
    end while
  end procedure

Let me know what you guys think of it and how can you help NerdCats take it to the next level. See ya!