What Graph would you Recommend?

My game is divided into areas that are in the same scene, but separated from each other. There is a transition time from one area to another, to allow for some asynchronous loading to take place, but because you control multiple units at the same time you can be in two areas at a time.

For instance: You have Character A and B. They are both in Area 1. You send Character B to Area 2. Area 2 loads while Character B is “In transit” to it, but during this time you can still control Character A. When the area is loaded in, and the transit time is finished, then you can now play as Character B again.

Each area is proceduraly generated and can be anywhere from 100x100 to 1000x1000, and has buildings in them with multiple floors. So I will need something that can support layers. There can be a maximum of 15 areas loaded in at any given time (as you can only control up to 15 characters). Which graph would you recommend for this scenario and why? I have the pro version so all graphs are available to me.

With the information you have given me, I would recommend a recast graph or a layered grid graph.
The drawback of the recast graph is that it will take some time to calculate, and the drawback of the layered grid graph is that it may use a lot of memory and it is slower to search on.

Thank you, I have tried both of them and the layered grid graph was able to be generated in a reasonable time (roughly 10 seconds) while the recast graph was never able to generate, as Unity locked up. So I either need to tone down the recast graph, which will probably result in less accurate results, or go with the layered grid graph.