I en geografisk ruttsökning, givet sökord, är målet att hitta en effektiv rutt som 1) börjar på en given plats, 2) slutar på en given plats, och 3) reser via geografiska enheter som är relevanta för de givna villkoren. En rutt är effektiv om den inte överskrider en given avståndsgräns medan de besökta enheternas rankingpoäng, med avseende på sökorden, är maximala. Detta dokument introducerar route-search frågor, föreslår tre semantik för sådana frågor och behandlar problemet med att effektivt svara på frågor under de olika semantik. Eftersom problemet med att svara route-search frågor är en generalisering av den resande säljare problem, är det osannolikt att ha en effektiv lösning, dvs. det finns ingen polynom-tid algoritm som löser problemet (om inte P=NP). I detta arbete tänker vi därför på heuristiker för problemet. Metoder för att på ett effektivt sätt beräkna rutter presenteras. Metoderna jämförs analytiskt och experimentellt. För dessa metoder illustrerar experiment på både syntetiska och verkliga data deras effektivitet och deras effektivitet när det gäller att beräkna en rutt som uppfyller kraven i en vägsökningsfråga.
Kanza m.fl. REF har visat polynom-tid heuristik för den begränsade versionen av TPQ-problemet.
Heuristic algorithms for route-search queries over geographical data
{'venue': "GIS '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}