Approaches of nearest search

Deals with generic topics such as logging, framework and so on. If you are not sure where to place your topic just put it here.
Post Reply
User avatar
Bernd Welter
Site Admin
Posts: 2548
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Approaches of nearest search

Post by Bernd Welter »

Hi there,

recently I’ve been asked for how implement nearest search with xServers? and this is why I’d like to collect some more or less simple statements around the usecase view and the server tools. Feel free to follow my texts and to provide feedback if you want. The text itself is not a 100% coverage of the topic but you could use it’s ideas to setup your approach to nearest search.
I’ll not answer everything in detail but my goal is to enable you to find the answers in yourself. Ohmmmm.
There we go – topics you should deal with…
  • Center is point versus polygon: sometimes it makes a difference whether you are looking for objects close to a given center coordinate versus along a precomputed route. For both approaches we offer proper interface methods.
    Center based (left) versus routing corridor based (right)
    Center based (left) versus routing corridor based (right)
  • What is your search horizon, your interpretation of a (maximum) distance?
    Is it simply the airline between two coordinates? Then you might implement coordinate based search functions within the database (especially with spatial databases within SQL Where and Order ;-) quite sexy and performant)
    Or do you want to consider geographic cicrumstances such as rivers, valleys and street network? Then you should have a look at the various routing based approaches.
  • PTV xServers can perform the search for you (searchForNearest) or you consume KPIs (e.g. driving distance matrix) to verify candidates on client side (calcMatrixInfo).
  • Sometimes even the driving direction is worth being treated carefully:
    looking for a restaurant in your current proximity requires to drive from the center to the coordinates while gathering the fastest pizza service is the opposite driving direction. Both mentioned methods support both directions. With calcMatrixInfo it is 1:N or N:1, with searchForNearest you can specify the driving direction by parameter.
  • Is the distance itself important (e.g. for the sorting order of a result) or is it just the computation of “who is inside”? If the later is the case you can check whether precomputed Isochrones (xRoute.calculateIsochrones) can be stored in a spatial database which supports SQL search based on geometry objects. This is a proper usecase in a callcenter where service levels (who can reach me within 60minutes based on static homebases?) are important for a quick search that can be refined afterwards (calc the matrix for each candidate).
    Isochrones. distance based isochrones usually look more like a circle while driving period based ones follow the street network (high speed on highways: longer reach into that direction).
    Isochrones. distance based isochrones usually look more like a circle while driving period based ones follow the street network (high speed on highways: longer reach into that direction).
  • Are the candidates (static) objects stored in a database? If this is the case the geodatabase search of xRoute could provide quick access to the search: the xRoute itself connects to the database in the backend and determines those objects that are candidates and validates the “hits”. Sometimes the objects could be more context driven which means the application retrieves the x,y-coordinates of objects and forwards them to the xRoute method call.
    SearchForNearest supports both approaches. But be aware that depending on the application context not all connections to the database are allowed.
    database connection: do you want to connect the xserver to the database or should the application take care of the connectivity? Sometimes you don't have a choice because the architecture defines constraints.
    database connection: do you want to connect the xserver to the database or should the application take care of the connectivity? Sometimes you don't have a choice because the architecture defines constraints.
  • Usecase: who is reachable within given horizon versus is current coordinate within reach (fencing)? What is the object info you need to check? Do you want to reduce a list of candidates (e.g. list of parkings nearby) or is it just one candidate (current GPS position of a security transport which is not allowed to leave its fence)?
  • Restrictions (time frame, skills, …)
    Are there any further restrictions to be kept in mind besides the maximum detour distance or period? For example existing visits scheduled in your calendar? Then it might be helpful to take a look at the higher level planning functions of xTour (planBasicTours and findUnscheduledOrdersForTour). Especially when it comes to timeframes and quantities these are constraints that are covered by xTour (but not by xRoute).
  • Can you use High performance routing? Can you use our high performance routing which is increasing the computation performance of distance matrices? Works fine with calcMatrixInfo.
  • After all decide which one of the following methods matches your usecase at its best:
    • database query (airline)
    • isochrones (precomputed database)
    • searchForNearest
    • planBasicTours
    • findUnscheduledOrdersForTour
Best regards
Bernd
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at Youtube
I like the smell of PTV Developer in the morning... :twisted:
Post Reply