Detour points

[clegroux]

Hello,

I would like to solve a problem and don't know if it's possible to do it easily with PTV xServer.

Here is my problem

Let's take 2 locations A et B. It takes (for example) 30 minutes to go from A to B. I'm at point A and want to go to point B but I have 2 hours (for example) to do this trip.
How can I get all the points that I can reach within these 2 hours ? That's to say, how can I get all the points X that match this condition : (travel time between A and X) + (travel time between X and B) <= 2 hours ?

Charlie

[Joost]

What order of magnitude of possible candidate points are we talking about? A few? tenfold, hundredfold? etc

[clegroux]

Oh sorry I forgot to talk about one important thing

In fact I don't want to get the points that match the condition. I would like to get the area that contains all these points (like an isochrone).

[Bernd Welter]

You want something like the blue ellipse, the geometry?

"Distance" between A and B is smaller than the available horizon, so there is a search space to be reacheable

I assume we don't have a function for this but maybe you can use some simple (A:N) + (N:B) matrix requests?

[clegroux]

Yes exactly!

You're right I could use matrix requests but I would prefer to avoid calculating a distance matrix. Using a distance matrix means divide my map into a lot of squares (for me it's the best way to get a precise area). Do you have another simple way to solve my problem ?

You assume you don't have a function for calculating such a area. Do you plan to develop such a function ?

[Bernd Welter]

To be honest: the function you'd like to have is requested once every two years
Therefore I wouldn't expect this feature to come soon . . . Sorry for that.

Getting back to the functional requirement:
What do you mean by "slicing into rectangles"?

Are you doubting in performance or in quality of results?
I'm sure e can find at least some approaches of how to solve the given operational tasks...

Best regards
Bernd

Two 30min isochrones, checking for 1 hour.
Any point outside both isochrones will not be a candidate for the given task.
Any point inside both isochrones is reacheable within 60 minutes.
Attention: doesn't guarantee anything for points inside exactly one isochrone.

[clegroux]

Arf... So let's forget the function

First I'm doubting in quality of results. Yes, in your example, any point inside both isochrones is reachable within 60 minutes but we miss a lot of points (as you said, points inside exactly one isochrone may match the condition).

The only way I see to get a maximum of points is to populate an union of isochrone intersections. Going back to your example, we have to calculate the intersection of isochrone(Karlsruhe, 5 minutes) and isochrone(Pforzheim, 55 minutes), the intersection of isochrone(Karlsruhe, 10 minutes) and isochrone(Pforzheim, 50 minutes), etc. and then populate the union of these intersections. But I'm doubting in performance if we populate this union...

Finally I wonder if it's not faster to slice my map into rectangles, to calculate the distance matrix between all the centers of these rectangles and then identifying all the rectangles that match the condition. It may be faster but not easier because slicing the map is an hard work

What do you think about that ?

[Bernd Welter]

Could you provide an image how you'd like to slice the map?
I don't get the point

How about using xTour.findUnscheduledOrdersForTour?

http://xserver.ptvgroup.com/fileadmin/f ... s%7C_____8

[Bernd Welter]

And you can still calculate an airline ellipse to filter the candidates C for a later validation.
The (A:C)+(C:B) routings should then be performant enough...

[clegroux]

Here is a map example

Yeah good idea! I could first define the area with two isochrones and then calculate the "squared" ellipsochrone with (A:N) + (N:B) matrix requests.

I would like to ask you others questions about the distance matrix :

• 1- My map will be sliced into (approximatively) 6000 squares. How long will it take with xDima to calculate this matrix?
  2- According to your experience, could it be possible to define the "squared" ellipsochrone with (A:N) + (N:B) matrix requests with a 6000x6000 distance matrix?

Thanks a lot for all your posts Bernd

[Bernd Welter]

The computatio of a 6000x6000 matrix can be done within less than 1 minute (my local example took 45 secs), but my stomach tells me we are on a wrong path.

Let's get several steps back:
Imagine you could wish a blackbox function where you provide a given input and describe the required output.
From a functional usecase point of view (forget each method of xServers for a moment):
how would the signature of the function look like?

I think I might provide a better solution for the original task then...

coverage of 7000 (!) locations around Paris. Computation time: 60 seconds.

Best regards
Bernd

[Joost]

You do not need to calculate a full 6000 by 6000 dima. You only need to calculate 2 by 6000. I suggest you do this with 2 calculateMatricInfo calls from xRoute. If you use high performance routing this should be done quick. I don't have exact numbers unfortunately but probably around a few seconds per call.

Be aware though: for such big calls it can be that the framework will hit it's maximum memory usage. I'm not expecting it with your numbers but I would recommend for you to stress test your solution before deploying it into a production environment. If it does you can always increase the maximum memory if needed. See:

http://xserver.ptvgroup.com/fileadmin/f ... n%7C_____2

[clegroux]

Okay!

I would like a function which takes three arguments :

• - the startpoint location (A)
  - the endpoint location (B)
  - the time I have to go from startpoint to endpoint (T)

As a result, I would like to get a polygon which ensures that every point N in it verifies (A:N) + (N:B) < T where (X:Y) represents the time to go from X to Y

[Bernd Welter]

That's the point.
The polygon itself is useless.
What do you need it for in a later step?
You want to determine as quick as possible for a given customer whether you can add him to such a tour?

[clegroux]

Yes and no...

In fact I have a lot of vehicles tours on several days (from a date D to D+14). Some are full, some not. For a new given customer :

• 1- I want to know quickly what vehicles can visit this customer
  2- If no vehicle can visit this customer, I want to know at what date I should open a new tour to visit this customer. And here is the point, I don't want to open a new tour on day X if this new tour's area intersects too much tours areas (on day X). For a given day, I finally want to cover my map as much as possible.

[Bernd Welter]

So all the existing tours start at A and end at B?
But I assume they server other locations as well.

How about using findToursForOrder which will give you a quick feedback about

• Which one of the tours can be extended with less than NN kilometer detour?
• What is the impact on these tours?

If no tour is returned you could decide to create a new tour.

Best regards
Bernd

PS: I recommend to get in touch 1:1 with your technical counterpart at PTV.
Who's that? Maybe I can moderate?

[Bernd Welter]

Another approach mentioned by DEV (Thanks, Ralf!) is as follows:

• Determine a set of potential C's
• Use searchForNearest(Sink=A, Candidates=C's, direction = forward, horizon=2h) : returns Candidates A:C's
• Use searchForNearest(Sink=B, Candidates=C's, direction = backward, horizon=2h) : returns Candidates C's:B
• Filter those candidates C's where (A:C) + (C:B) > 2 hours...

But: be aware that the performance of searchForNearest scales superlinear with the horizon!

Best regards,
Bernd

[clegroux]

Hi Bernd,

Sorry for this late response...

Here is an example

I have two tours on day D and on day D+1. I have a new customer to visit and I may visit it on day D or on day D+1. This customer can't be visited by vehicle 1 or vehicle 2 so I have to open a new tour.

Is it more efficient to open a new tour on day D or on day D+1?

Here this answer is day D+1 because the new tour will cover 80% of the area defined by tour 1 and tour 2 on day D. On day D+1, it will only cover 20% of this area.

The approach mentioned by Ralf is a good idea but it requires to determine the set of potential customers and the only way I see to do that is by slicing my map...

Regards,
Charlie

[Bernd Welter]

Ah, I see. But that's a different target then.
If you want to optimize reachability and coverage you might take a look at this feature of xCluster:
http://xserver.ptvgroup.com/forum/viewt ... f=10&t=482
Not exactly what you are looking for within this thread but related to "how to cover a broad area?".

Best regards
Bernd