Shortest-Path Diversification through Network Penalization
Dan Cheng, Olga Gkountouna, Andreas E Züfle, Dieter Pfoser, Carola Wenk · 2019
Traditional navigation systems compute the quantitatively shortest or fastest route between two locations in a spatial network. In practice, a problem resulting from all drivers using the shortest path is the congregation of individuals on routes having a high in-betweenness. To this end, several works have proposed methods for proposing alternative routes. In this work, we test solutions for traffic load-balancing by computing diversified routes proposing variants of the penalty method using the road network of the Washington DC metropolitan area as a case study. Our experimental evaluation shows that the tested Penalty-based approaches allow to significantly balance the load of a spatial network, compared to existing k-shortest path algorithms, and compared to a naive baseline that randomly changes the weights of the network at each shortest-path computation.