Detour points

This forum deals with any kind of routing computation whether it is simple A:B-routing, calculation of isochrones, simple matrix computation or nearest search.
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Detour points

Post by 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.
coverage of 7000 (!) locations around Paris. Computation time: 60 seconds.
Best regards
Bernd
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
Joost
Posts: 307
Joined: Fri Apr 25, 2014 1:46 pm

Re: Detour points

Post by 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
Joost Claessen
Senior Technical Consultant
PTV Benelux
clegroux
Posts: 8
Joined: Mon Jun 12, 2017 9:41 am

Re: Detour points

Post by 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
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Detour points

Post by 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?
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
clegroux
Posts: 8
Joined: Mon Jun 12, 2017 9:41 am

Re: Detour points

Post by 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.
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Detour points

Post by 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
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Detour points

Post by 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
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
clegroux
Posts: 8
Joined: Mon Jun 12, 2017 9:41 am

Re: Detour points

Post by 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
Attachments
open a new tour.PNG
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Detour points

Post by 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
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
Post Reply