The Minimum Road Trips Problem
The Minimum Road Trips Problem
复制标题
最少公路旅行问题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Brendan Mumey Gianforte
中科院分区：
文献类型：
--
作者：
Samuel Micka;Brendan Mumey Gianforte
道路网络可以表示为部分有向图;有向边是单向路段，无向边可以在任一方向上遍历。车辆行程只是从某个起始顶点到某个结束顶点的路径，该路径必须与所取的任何有向边的方向一致。环形检测器是一种设备，它可以计算在某个时间段内穿过边缘的车辆数量。环路检测器通常仅存在于网络中的边缘的子集上。我们感兴趣的基本问题是确定解释所有环路检测器计数测量所需的最小行程数（简单路径）。我们还考虑了一个动态版本的问题，其中时间离散化和车辆移动每个时间步长的一个边缘。在这种情况下，环路检测器为每个时间步长提供交通计数，目标再次是确定解释数据所需的最少行程数。行程现在由路径和开始时间指定。
Road networks can be represented as partially directed graphs; directed edges are one-way road segments and undirected edges can be traversed in either direction. Vehicle trips are simply paths from some starting vertex to some ending vertex that must agree with the direction of any directed edge taken. A loop detector is a device that counts the number of vehicles that cross an edge during some time period. Loop detectors are typically present on only a subset of the edges in the network. The basic problem we are interested in is to determine the minimum number of trips (simple paths) needed to explain all of the loop detector count measurements. We also consider a dynamic version of the problem in which time is discretized and vehicles move one edge per time step. In this case, the loop detectors provide traffic counts for each time step and the goal is again to determine the fewest number of trips needed to explain the data. Trips are now specified by a path and a starting time.