# Application of shortest vertex-disjoint path with time window

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to move from one origin to its specific destination). This time window will tell us how long it will take for the object to pass a particular point on the network.

These objects should not encounter each other in any ways on the network, so it is a vertex-disjoint path problem with respect to time. For example if I have two objects A and B, and object A will pass node 1 from 10:00 a.m. to 12 p.m., during these time periods object B cannot cross this node, but any time after 12.00 and before 10 (as long as the time window of B allowed) B can pass through node 1.

I want to know if there is any application of this problem in computer science?

• I can't tell what you're asking. Isn't the vehicle routing problem part of computer science? So isn't that already an application of the vertex-disjoint paths problem in CS? And your title talks about time windows but I don't see that anywhere in the question. – David Richerby Apr 29 '15 at 7:43
• I, too, have trouble understanding what you are proposing. Mind that as soon as you do properly define your problem, it is a computer science problem. Do you mean to ask if it has been studied before? We can't answer that until you give a clearer problem description. What exactly are the inputs and outputs? (It does remind me of network flow problems.) – Raphael Apr 29 '15 at 9:01
• @DavidRicherby I edited my question, I hope it helps this time. Please let me know if you still have question. – azar Apr 29 '15 at 14:41
• @Raphael I edited my question. I want to know if there is any situation in computer science which is somehow related to this problem. For example in communication problems or parallel computing ? My major is not computer science and I am urged to find an application for this problem. – azar Apr 29 '15 at 14:42
• The search for node- resp. edge-disjoint paths has definitely been studied; you may want to search for that term. I think we even have some questions about that on this site. As for "real" applications, I don't know; that's not my area of expertise. – Raphael Apr 29 '15 at 14:52

If $G=(V,E)$ is your original graph, build $G'=(V',E')$ by making $t$ copies of each vertex in $G$, one per time slot (where there are $t$ time slots): call the copies $v_1,\dots,v_t$. Now for each vertex $v \in V$, add an edge $v_i \to v_{i+1}$ for each $i$ (this corresponds to an object staying at vertex $v$ throughout time slot $i$). Also, for each edge $(v,w) \in V$, add an edge $v_i \to w_{i+1}$ for each $i$ (this corresponds to an object moving from vertex $v$ to $w$).
Now you're looking for vertex-disjoint paths in $G'$. There are standard algorithms for finding vertex-disjoint paths in $G'$ (e.g., using network flow or other methods). If you want a collection of shortest vertex-disjoint paths, that might be possible, but you'll need to define precisely what objective function you want to minimize before we can suggest an algorithm.