3
$\begingroup$

I have reduced a problem I'm working on to something resembling a graph theory problem, and my limited intuition tells me that it's not so esoteric that only I could have ever considered it. I'm looking to see if someone knows of any related work. Here's the problem:

Given a roadway map (directed graph) and a set of sensor activations that reports how many vehicles were on each edge at a given time, generate as many sets of routes (i.e. source edge, sink edge, and start-time) that would explain the given sensor activations as possible.

Here is a trivial approach: Create a source and sink for each edge, and generate/consume as much traffic is needed to satisfy the count at that edge for that time-slice.

The trivial case is useless to me, as I'm trying to study the dependencies across multiple intersections and multiple time-slices. What I need is a likely explanation, where the routes resemble the kind of routes that actual drivers would choose, and where the distribution of trip lengths also makes sense.

If I could generate all such explanations, or at least a great number of them, I could then treat picking the "likely" one as a separate problem.

Is there an algorithm that might be applicable here?

Improve this question
$\endgroup$
5
  • $\begingroup$ how do you know that the sensor reports are consistent with each other?, or is this an abstract road map? $\endgroup$
    – JMP
    Commented Oct 12, 2015 at 21:27
  • $\begingroup$ They were gathered from inductive loops at the intersections, so presumably each sensor report does correspond with an actual vehicle's passage. I hope to handle the general case, however--so the ideal algorithm, given inconsistent sensor reports, would give only trivial explanations for the sensor activity. $\endgroup$
    – MatrixManAtYrService
    Commented Oct 12, 2015 at 21:36
  • $\begingroup$ this could be related to 'Recovery of Information from Partial Systems' - take a page of text, remove k% of the letters - can the original document be recovered? $\endgroup$
    – JMP
    Commented Oct 13, 2015 at 11:11
  • $\begingroup$ So you want to solve the variant, where it is known how many vehicles are on street segment between two crossings at a fixed time? That problem could be solved approximately with a linear system of equations; the minor problem is to model that. I could provide some ideas how to do that. $\endgroup$
    – Manfred Weis
    Commented Oct 17, 2015 at 16:54
  • $\begingroup$ @ManfredWeis I would be quite interested in those ideas, thank you. $\endgroup$
    – MatrixManAtYrService
    Commented Oct 17, 2015 at 23:24

2 Answers 2

Reset to default
1
$\begingroup$

At the very lowest level of modelling, one has to make some assumptions about the chosen paths, e.g. that they are the optimal ones connecting a pair of nodes. With that assumption, one obtains for each path a set of edges that defines the path; now in turn, one obtains for each edge a set of paths that contains that edge and the restriction, that the sum of flows through those paths must not be greater than the flow through the edge.

For taking time-slices into account, either the edge-lengths or the driving speeds on that edge have to be adjusted to yield a transition time that equals an integral multiple of the time-slice's thickness.
Now the system of equations is obtained from combinations of all shortest paths and their start-times that reach the start-node of an edge at a time, that guarantees that the edge is reached within the current time-slice.

Already from that model it will be possible to check, whether a unique solution exists (which I doubt) or whether additional knowledge needs to be incorporated into the model. Such knowledge could be a characterization nodes, e.g. into homes and companies along with their working hours. It is a plausible assumption, that an employee drives to a workplace once every weekday and also drives home only once per weekday; furthermore she must start early enough to reach the workplace before the start of the working hours and can only leave after their end.

So, put in a nutshell, without incorporating statistical data about a community, it will not be possible to retrieve path-data from flow-data.

Some useful techniques could be vertex-splitting to model waiting times (such as work hours) and to model typical time-periods such as a weekday; that would yield the restriction that oppositely directed flows between every pair of nodes must be equal, when summed over the time-period. From an algorithmic point, time-staged flows or flows with gains and losses might be useful to know.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was heading towards something like what you mentioned in your first paragraph, but I like the way you framed it much better. I like where you're going with the opposite-direction flow symmetry, but the simulation I'm trying to build only needs to capture five or ten minutes in order to be useful as a control (I plan to compare it to the same simulation, but have the traffic lights behave differently, in order to assess the value of the change). I'll be sure to check out vertex-splitting. Thanks for the reply. $\endgroup$
    – MatrixManAtYrService
    Commented Oct 21, 2015 at 18:34
1
$\begingroup$

One possibility is to use the maximum entropy distribution that satisfies your edge volume constraints. Specifically, you let $A$ be an $n \times N$ matrix, where $n$ is the number of edges in your network and $N$ is the number of paths between all pairs, and then let $x$ be a vector in $\mathbb{R}^N$ where $x_j$ is the amount of people using path $j$. You have $a_{ij}=1$ if edge $i$ belongs to path $j$ and $0$ otherwise. Your edge volume constraints then just require that $Ax=b$ and $x\geq0$, where $b$ is the vector of sensor data. Then, you maximize the function $-\sum_{j} x_j \log x_j$ over all $x$. This objective function comes from information theory because it asks for the set of flows where the amount of added "information" is as small as possible, as can be read about here:

https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm currently taking this down the path of brute force, despite the fact that I expect it to become intractable (as route enumeration often does, e.g. traveling salesman). I hope to be able to place restrictions at each recursion that keeps the set of results small. I hadn't thought to keep track of entropy, but it seems like it might help me narrow things down at each step. Thanks for your response! $\endgroup$
    – MatrixManAtYrService
    Commented Oct 21, 2015 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .