Shortest-Path Diversification through Network Penalization: A Washington DC Area Case Study
Shortest-Path Diversification through Network Penalization: A Washington DC Area Case Study
复制标题
DOI：
10.1145/3357000.3366137
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Danhong Cheng;Olga Gkountouna;Andreas Züfle;D. Pfoser;C. Wenk
中科院分区：
文献类型：
--
作者：
Danhong Cheng;Olga Gkountouna;Andreas Züfle;D. Pfoser;C. Wenk
传统的导航系统计算空间网络中两个位置之间的定量最短或最快路线。在实践中，由所有驾驶员使用最短路径导致的问题是个体聚集在具有高中间性的路线上。为此，若干研究已经提出了用于提出替代路线的方法。在这项工作中，我们测试解决方案的交通负载平衡计算多样化的路线提出的变体的惩罚方法使用的道路网络的华盛顿DC大都市区作为一个案例研究。我们的实验评估表明，与现有的k-最短路径算法相比，以及与在每次最短路径计算时随机改变网络权重的天真基线相比，测试的基于惩罚的方法可以显着平衡空间网络的负载。
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.