2
$\begingroup$

Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm. Example:
https://i.stack.imgur.com/4sVRf.png

The idea is that each vertex is a city, and each edge is a road.
The weight of an edge represents the time needed to traverse the specified edge.
The conditions are:

  1. Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.
  2. Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.
  3. The starting point is always vertex 0

For my example I have:
Vertices that must be visited and their time window (values with -1 are not taken into consideration): 

Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1 
  5    170  450  -1   -1

Edges are open in the following time window (values with -1 are not taken into consideration):

Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1 
0-4  0    210  230  770
0-5  0    260  -1   -1 
1-2  0    160  230  770
1-5  40   770  -1   -1 
2-4  80   500  -1   -1 
3-4  60   770  -1   -1 
3-5  0    770  -1   -1

So the basic idea is to start with vertex 0 and find the shortest route to traverse vertices 1, 4 and 5 taking in consideration the specified time.
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.

I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices.
For example:
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5 I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60. So is there a way to solve this using dijkstra or other path finding algorithms ?

Thanks in advance for any help!

Edit

My solution for now is something like this

         0    
  1      4      5
0 2 5  0 2 3  0 1 3

Basically I try all possibilities. The conditions for stopping in expanding a branch are:
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4
2. I find a road that contains all the vertices to mark
3. I find a road that takes longer than another complete road

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ so if I understand you correctly, you have a graph with edge and vertex windows, and edge weights. Your goal is to visit each of a specified set of target vertices at least once for each time window that it's open using a path of minimum weight ? What happens if the windows for a vertex overlap ? Then would one visit cover both occurrences, or should we assume that no windows overlap. Also, is the "vistor" allowed to stand still, or must it constantly be moving ? $\endgroup$
    – Suresh Venkat
    Sep 17, 2012 at 19:45
  • $\begingroup$ There is no problem if the windows overlap. Also the time passes only when you pass an edge. For example if you are in 2 and you need to use 2-4 but it is closed you can do 2-1-2 then you may use 2-4 if it becomes available. It doesn't how many vertices you use you can do even something like 0-1-5-1-4-0-4-3-5-1-5-1-0-4, so any combination as long as it takes the shortest possible time. $\endgroup$
    – hDan
    Sep 18, 2012 at 5:16

1 Answer 1

Reset to default
6
$\begingroup$

It is NP-hard to decide whether your problem is soluble. That's bad news from a theoretical point of view, but in practice it is possible that a heuristic algorithm will fare quite well. Also, you're (possibly) dealing with the "promise" variant of the problem, that is, you assume that a solution exists, and want to find it.

To see that the problem is NP-hard, we reduce Hamiltonian cycle to it. All the edges are always open, and they always have unit weight. The windows for each non-zero vertex are $[1,n-1]$ and $[n+1,2n-1]$; for vertex zero they are $\{0\}$ and $\{n\}$. These constraints are satisfiable only via a Hamiltonian cycle, and the converse is also true.

Improve this answer
$\endgroup$
6
  • $\begingroup$ OK so using a computational approach how can you solve this problem ? $\endgroup$
    – hDan
    Sep 18, 2012 at 5:29
  • $\begingroup$ That's your question. $\endgroup$
    – Yuval Filmus
    Sep 18, 2012 at 13:30
  • $\begingroup$ What I mean if there is a better solution than the one I am currently using. $\endgroup$
    – hDan
    Sep 19, 2012 at 6:09
  • $\begingroup$ I don't understand the reduction. Is the set of vertices $\{0,1,\ldots,n\}$? Are the windows for $1$ supposed to be empty? If a vertex has two windows then it will be visited twice, which makes the path non-hamiltonian. What am I missing? $\endgroup$
    – Radu GRIGore
    Sep 21, 2012 at 10:29
  • 1
    $\begingroup$ The set of vertices is $\{0,1,\ldots,n-1\}$. The windows for $0$ are singletons. The first $n$ edges of the path will form a Hamiltonian cycle. $\endgroup$
    – Yuval Filmus
    Sep 21, 2012 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.