search

Davidrxyang / raines-2024-line-addition-problem

MIT License
1 stars 0 forks source link

implement LAA version 2 #99

Closed henrydeng2002 closed 3 months ago

henrydeng2002 commented 3 months ago

algorithm now functions and generates line candidates. However, there are some areas of improvement to be made:

  1. Efficiency generation is too slow and needs optimization. One idea could be to have subset paths track which superset paths pass through it, so when the subset path is changed, it can directly modify the superset paths. This eliminates the need to go through every station pair in updateefficiencyanddemand. However, doing so does lose a little bit of accuracy, as new connections can mean that previous paths that do not go through those two stations now can go through. I think this change is worth a try though

  2. Line joining needs to be optimized. Currently, the algorithm generates a new line even if the terminal stations of two lines are only one station apart (e.g. it generates [spring hill -> shady grove], [twinbrook -> glenmont] instead of [spring hill -> twinbrook, twinbrook -> glenmont]). This is not great as too many line candidates will be generated. Potential fix: when checking if an existing line candidate contains the station pair, consider checking the adjacent stations of the station pair instead of just the station pair (e.g. when the efficiency [spring hill -> shady grove] is picked, instead of just checking if shady grove is a part of an existing line candidate, check if shady grove, rockville, twinbrook are a part of an existing line)

  3. additional demand coefficient is currently a constant, but I think it would make more sense to have it be based on the length of the potential connection. Could make it = (distance of path if new connection is made) / (distance of direct connection). I think this makes more sense because the shorter the new path, the more desirable the new connection is.

I can take a look at 2 and 3 and you do 1 if that works. I think these are the main issues for now but we might find new things while we run it more.

henrydeng2002 commented 3 months ago

also reminder to update the paper draft as we change

Davidrxyang commented 3 months ago

nice

henrydeng2002 commented 3 months ago

I also changed least transfers to astar in the algorithm, since i think thats the pathplanning algorithm that makes more sense (more transfers can be more efficient like on the red line)

Davidrxyang commented 3 months ago

I also changed least transfers to astar in the algorithm, since i think thats the pathplanning algorithm that makes more sense (more transfers can be more efficient like on the red line)

If we are using a bfs based path finder we will have to go back and fix the bug where the path "hops" between lines, since routeEfficiency takes into account nTransfers via complexity, and nTransfers is currently exaggerated because of this bug