Dijkstra’s algorithm on jeepney routes
can a greedy algorithm assist commuters?
Inspired by foreign nationals (mostly indian med students) who struggle to communicate with our local jeepney drivers or the concept of double-triple ride, I went on a quest to build a jeepney route optimizer.
Step 1: Plot Jeepney Routes
According to the summary report of Davao City Transport Roadmap, Davao has around 116 routes within the city. 116 routes are way too much effort, so I’ll stick with five routes I often use (Buhangin & Sasa via JP Laurel, Bunawan via Buhangin, Obrero, and Route 4).
Step 2: Combine Converging lines
In analyzing our rough plot, we see multiple routes stack on top of each other. By combining these lines, we can reduce the vertices of our jeepney route network.
Step 3: Apply Dijkstra!
Now you have a network of jeepney routes, simply search for Dijkstra algorithm packages/code snippet in your favorite language. Convert the created network as a graph, then specify a source and destination vertex.
As long as you understand the concept, using packages is a brilliant, noble, and valiant move. Here’s one I used.
Although we can get the shortest path between 2 known vertices, passengers, on the contrary, could be anywhere on the map. What if we try to locate the nearest route to a passenger’s origin & destination, and then insert a new vertex in the network?
Apply Perpendicular Distance Formula
In essence, jeepney routes are a collection of line segments while passengers, just like a point, could be anywhere on the map. Hence, we could apply this formula to check which route is the closest to a passenger.
The beauty of jeepney routes is that they are technically an infinite sequence of vertices; you can ride and depart anywhere. Besides, the concept of a bus stop isn’t applicable on jeepneys; simply knock on the roof, shout lugar lang ya, and the jeepney will immediately stop for you.
Result
With the concepts discussed now combined, we now have a jeepney route optimizer 🎉
Try applying this theory to your local jeepney routes; or even boat, UV express, triciboat, and bus routes. Is it still viable in other modes of transportation?
Conclusion
This greedy algorithm could recognize the shortest routes given a proper graph; however, it isn’t economical sometimes. There are instances where one jeepney is enough to transport us. But, since we want the shortest path, we get a path that requires riding a combination of jeepneys.
User sets Gaisano Mall as the origin and AdDU Jacinto as the destination. The shortest path is through JP Laurel Ave. (Acacia) and then turn to Jacinto St., but this requires riding 2 jeepneys.
The practical way (or what I’ll do) is to just ride an Obrero jeepney. Because this route travels a slightly longer distance (~200 meters) before it reaches ADDU Jacinto, the algorithm doesn’t recognize this as the shortest route.
in the end, it’s the commuter’s choice
Do they want to get there faster, thus paying more?
or spend less and enjoy the journey 🀄
