Davidrxyang
commented
1 week ago -
Makes sense, I will take a look at that soon. Pretty sure I already have a getDistance function in station that calculates the direct distance between two stations based on coordinates. Just to make sure, you're not suggesting our line addition algorithms add new connections right? The connections are purely theoretical?
-
we discussed previously about implementing another version of path planning that's based on Dijkstra's. We can do that, basically UCS, and simply use transfers as a path cost factor. This is great because we can also arbitrarily add more things to the past cost factor, like ticket costs for example. Eventually we certainly want to follow OOP principles and derive transfer-minimizing path planning and UCS path planning from a base path planning super class, mainly because, I envision we might want to write some sort of class that might take a pathplanning alg as a parameter (like hashmap hash function). However, for now, probably best to just implement UCS pathplanning as another function in pathplanning.java and refactor later
For the efficiency function, I think it would make sense for us to add a function that compares the efficiency of a route through the existing network with a theoretical direct (as-the-crow-flies) route for use in our line addition algorithm. The current route efficiency function depends on the route distance, but a shorter but more circuitous route shouldn't be more efficient than a longer but direct route (e.g. if the direct distance between station A and B is 5km, and B and C is 10km, it would make no sense for a 9km route between A and B to be more efficient than a 10km route between B and C)
Also, for pathplanning, would it make sense for us to consider a different pathfinding algorithm through the network, that calculates transfers as a time penalty rather than trying to minimize transfers? Since pathplanning is trying to minimize transfers, and adding a line is almost always going to add transfers, but could shorten total travel time (e.g. if a connection exists between Bethesda and Silver Spring, it would take less time overall to go from Shady Grove to Bethesda then Silver Spring, but pathplanning will take the route through the longer red line). Or maybe we can consider making a generic pathfinding class and have pathplanning extend that class, so we can implement different pathfinding algorithms (we can also mention this in our paper - implementations can choose their own pathfinding algorithm like pathplanning through the network during efficiency computation)?