Routing

[chw-03]

Kyler proposed using Scalable Transfer Patterns for our route planning algo. The authors tested out multiple methods for creating "convex transfer clusters" (as defined in 3.1, Definition 1). They settled on a merge-based clustering method outlined in section 3.1.2 as it gave them the best performance, described in 4.3.2 along with other experimental results. Since the authors demonstrated that one can use different clustering methods before applying Transfer Patterns, this is a proposal to find another clustering method with better time complexity and returned results.

Here are two other papers I'm looking into at the moment; I'm not sure if they apply to Transfer Patterns yet, but I just wanted to put them out here:

• Optimal clustering by merge-based branch-and-bound
• A new multi-level algorithm for balanced partition problem on large scale directed graphs

[kylerchin]

I've found some interesting papers that cite Scalable Transfer Patterns https://www.researchgate.net/publication/301269409_Scalable_Transfer_Patterns

https://www.researchgate.net/publication/333971819_Fast_Public_Transit_Routing_with_Unrestricted_Walking_through_Hub_Labeling?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uIn19

https://www.researchgate.net/publication/354949756_Extending_the_Time_Horizon_Efficient_Public_Transit_Routing_on_Arbitrary-Length_Timetables?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uIn19

[kylerchin]

There's probably more recent innovations if we just comb through research gate for long enough

[kylerchin]

https://www.researchgate.net/publication/333746018_UnLimited_TRAnsfers_for_Multi-Modal_Route_Planning_An_Efficient_Solution?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uIn19
I'll read more tonight and put a summary of interesting ideas here

[CallMeJai]

one very recent one I've been meaning to read:
https://arxiv.org/abs/2312.13146

[chw-03]

I am almost done reading through the list + supplemental papers

[chw-03]

I have read all the relevant papers!
https://docs.google.com/document/d/1Ux5PF6FcYATttIu-5qgygsF8VDdW61zCffmGrHbeO4g/edit?usp=drivesdk

[chw-03]

Update: I read more papers; there's 4 main algos I think we should consider and the basic pros/cons are listed on the first page.
@kylerchin If you can give me a list of things to prioritize (decision matrix style) I can offer more feedback!

[kylerchin]

References and Citations can be found at the bottom of this page: https://www.researchgate.net/publication/301269409_Scalable_Transfer_Patterns

[chw-03]

I looked through it all and was unable to find a faster version of Scalable Transfer Patterns. It's a derivative of the original Transfer Patterns. Many citations point to another routing method, quite a few that we're also considering, but I'm looking through the rest

[chw-03]

Was unable to find any improvements to ScTP

[chw-03]

Here's my overall take on things at this point in time: (again, full notes here)
We basically have 4 options: Scalable TP, TB-CST, CSAccel, and HypRAPTOR. I think, perhaps, use S-TP for simple cases due to its fast queries and minimal memory usage, and TB-CST for more complex queries

S-TP:

• preprocessing is ok, query is slow
• memory usage is lowest by far
• couldnt find anything about it supporting multi-model or unlimited transfers
• could only find one implementation of base TP on GH
• google uses some variety of TP; this may be why it’s so hard to find any information about it

TB-CST

• preprocessing and query are both really fast
• memory usage is above S-TP but not astronomical
• supports multimodal, unlimited transfers, and various other improvements and expansions
• found a few implementations on GH (though all base or other variants that aren’t CST)

CSAccel (also called ACSA):

• minimal preprocessing (negligible) and fast query (sometimes faster than base TB)
• suppports multimodal and unlimited transfers, faster than RAPTOR at them
• found a few implementations on GH (though all base)

HypRAPTOR:

• no preprocessing, and query speed improved base RAPTOR a bit, but base was very slow
• supports multimodal, unlimited transfers, and runs certain searches better than base TB due to faster queries but TB improvements may have mitigated it (there are no available comparisons)
• found 2 implementations on GH (one is base)

[kylerchin]

Google maps appears to restrict walking to about ~4km. Unlimited walking is not allowed.

[triphora]

It's not a set distance - it's 1hr walking time.

[kylerchin]

Ah, thank you!

…

On Sat, 2 Mar 2024 at 17:41, Emma Alexia ***@***.***> wrote: It's not a set distance - it's 1hr walking time. — Reply to this email directly, view it on GitHub <#4 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABZQTZW2HC53FPMZAHMNZQDYWJ5TBAVCNFSM6AAAAABB7ACRV2VHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DMNJUHE4TE> . You are receiving this because you were mentioned.Message ID: ***@***.***>