Kortaste vägberäkning är ett grundläggande problem i vägnät med tillämpning inom olika områden inom forskning och industri. Att endast återvända den kortaste vägen är dock ofta inte tillfredsställande; användarna är också intresserade av alternativa vägar som kan vara längre men som har andra fördelar, t.ex. mindre frekventa trafikstockningar. I detta dokument introducerar vi formellt k-Shortest Paths med begränsad overlap (k-SPwLO) problem försöker rekommendera k alternativa banor som är (a) så kort som möjligt och (b) tillräckligt olikartade baserat på en användarkontrollerad likhet tröskel. Vi föreslår två algoritmer som undersöker vägar från en källa s till ett mål t i ökande ordning av deras längd och gradvis konstruera resultatet som. Grundalgoritmen BSL bygger på en standardalgoritm för beräkning av k-Shortest Paths, följt av ett filtersteg. OnePass-algoritmen tar hänsyn till överlappningsbegränsningen i varje expansionssteg samtidigt som den korsar nätverket. Vi utvärderar prestandan hos båda algoritmerna på riktiga vägnät och visar att OnePass alltid överträffar BSL.
Ett annat sätt att beräkna olika alternativa rutter är att lösa k-Shortest Paths med Limited Overlap (kSPwLO) problem, som infördes av Chondrogiannis et al. Hoppa över det.
Alternative routing: k-shortest paths with limited overlap
{'venue': "GIS '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}