Paper published: Routing with Few Collisions
News ·One sentence summary: We find the spots in time and space in a network that form bottlenecks when routing vehicles from a start to an end point.
In other words, when vehicles drive from some start to some endpoint it might be that at some point some of them collide. We try to route them in such a way that these collisions are avoided. This has applications in new navigation systems that try to minimize congestion by spreading out the use of roads. Here, collisions would mean that the routed vehicles would share road segments at the same time in their routes; and many vehicles sharing the road means that it becomes congested.
Our results show mostly hardness. The basic observation is that we can construct networks in which we can block one vehicle from using a bottleneck to the end point for an arbitrary amount of time. (Since we require vehicles to not go in circles) This means that we can require that vehicle to find a Hamilton path in a subnetwork, which is NP-hard.
I think a very interesting open question is whether we still get hardness when we look for at most a small constant number of bottlenecks and the maximum degree in our network is also a small constant. This seems to need some nontrivial insight in the temporal structure of bottlenecks.