Abstract-I detta dokument, vi tar itu med problemet med att besvara kontinuerliga rutt planering frågor över ett vägnät, i närvaro av uppdateringar av förseningar (kostnad) uppskattningar av länkar. En enkel strategi för detta problem skulle vara att omkompilera den bästa vägen för alla frågor vid ankomsten av varje uppdatering av förseningar. Men ett sådant naivt tillvägagångssätt skakar dåligt när det finns många användare som har begärt rutter i systemet. I stället föreslår vi två nya klasser av approximativa tekniker -K-vägar och närhetsåtgärder för att avsevärt påskynda behandlingen av den uppsättning angivna rutter som anges genom kontinuerliga linjeplaneringsfrågor inför inkommande trafikfördröjningsuppdateringar. Våra tekniker arbetar genom en kombination av precomputation av troliga bra vägar och genom att undvika fullständiga omräkningar på varje delay update, istället bara skicka användaren nya rutter när förseningar förändras avsevärt. Baserat på en experimentell utvärdering med 7.000 enheter från riktiga taxibilar, fann vi att de rutter som levereras av våra tekniker ligger inom 5% av den bästa kortaste vägen och har kört gånger en storleksordning eller mindre jämfört med en naiv strategi.
Vägplaneringsreferensdokumentet syftar till att hitta den kortaste vägen i närvaro av uppdateringar av de uppskattade förseningarna.
A continuous query system for dynamic route planning
{'venue': '2011 IEEE 27th International Conference on Data Engineering', 'journal': '2011 IEEE 27th International Conference on Data Engineering', 'mag_field_of_study': ['Computer Science']}