Graph traversal specific verticies with conditions

Question

I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm. Example:
http://i.imgur.com/15L6m.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.

A possible solution I'm working with now is:
Start with 0. Find the nearest vertex to mark in the shortest time period (I use a modified Dijkstra algorithm). Do this until I have marked all the vertices needed.
The problem is that I don't think I'm finding all the possibilities, because as I said you can also move around like the 0-1-0-1-5 combination and in the end you might end up with a shorter route.

In order to make it more clear, I have to find the shortest path so that 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.

First of all the constraints are that I will use a maximum of 20 vertices and about 50 edges at max.

Solution 1:
0
1 4 5 0 2 5 0 2 3 0 1 3

What I do is traverse the graph by visiting each neighboring vertex building something similar to a tree. I stop expanding a branch when :
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
4. I can't create another node because the edge is closed

Solution 2:

Applying @Boris Strandjev example, but I have some problems:

I have to visit nodes 1,4 and 5 at least once in their interval, visits outside the intervals are allowed but not marked. For a vertex I have {(< id1, id2id3id4>, time)}, where id1 is the ide of the current vertex, and id2-4 represent bool vals for 1,4,5 if were visited in the specified intervals, time - current time in path

Step1: 
{<0, 000>, 0} I can visit - {<1, 100>, 60} - chosen first lowest val
                          - {<4, 010>, 60}
                          - {<5, 000>, 60}
Step2:
{<1, 100>, 60} - {<0, 100>, 120} 
               - {<2, 100>, 110}   - chosen 
               - {<5, 100>, 110}    
Step3:
{<2, 100>, 110} - {<1, 100>, 160} - if I choose 1 again I will have a just go into a loop 
                - {<4, 110>, 170}   
Step4:
{<4, 110>, 170} - {<0, 110>, 230}
                - {<2, 110>, 230} 
                - {<3, 110>, 220}   - chosen

Step5:
{<3, 110>, 220} - {<4, 110>, 270} - again possible loop
                - {<5, 111>, 280} 
Step6:
{<5, 111>, 280} - I stop Path: 0-1-2-4-3-5 cost 280

Edit:

I ended up using a combination of the 2 solutions above. Everything seems to work fine.

Answer 1

I have not seen a strict restriction on the amount of vertices or edges you have in the graph, so please excuse me if my solution will not work for you. Give more strict restrictions if you need any kind of improvement.

One possible solution is to extend the definition of node. Instead of considering just the city as node in your graph, add some more attributes. Keep the edge definition implicit, generating the outgoing edges on the go, so that you spare memory.

See now:
You define a node a combination of three things: - the city the node refers to. - the time of the visit - a bitmap of the visited target nodes (so that you can tell whether you have already visited the all the targets).

Now the edges are a bit more complex - they lead you from city to city, but each edge also changes the time for the neighbouring node. Also keep on updating the target node bitmap with each step.

Here is an example:
You start in <city:=0, time:=0, bitmap:= (0 - true, 1...k - false)>
If you go trough the edge 0-4 you find yourself in node <city:=4, time:=60, bitmap:= ({0,4} - true, {1...k} / {4} - false)>

Keep on moving in such way between nodes, using Dejkstra algorithm and you will find your solution (as you extend the node definition, now even round abouts will be considered). You have found your solution whenever you find yourself in node that has in its bitmap all the bits set.

The number of nodes you will use in such solution is not so easy to calculate, but for relatively limited node number and quite restricted target city number it should work (the problem is that the number of resulting nodes is exponential in respect to target cities).

EDIT

Here goes the extended example you asked for:

Imagine you have such an input (I am using your notations):

 Vertex To1  Tc1  To2  Tc2
   1    0    40   80  120
   2    40   80   -1   -1
   3    0   400   -1   -1 
   4    30   80   120 190

 Edge To1  Tc1  Weight
 1-2   0    770  50
 1-4  30     70  30
 1-3   0    400  30
 3-4 100    200  50
 2-4   0    400  20

I will represent the vertices in the following form: <1,1100> meaning: the current vertex is 1, and the second: first and second vertex are visited already in the found path. The distance to each vertex is going to be the minimum time it takes to get to this vertex.

As you know in the process of the Dijkstra algorithm you are considering augmenting paths (meaning the best paths you found to each vertex of the front of already-reached vertices). I will dennote each augmenting path as follows: (<1,1100>, 400) meaning that the currently best time with which you can reach vertex <1,1100> is 400.

You start the algorithm with set of augmenting paths {(<1, 1000>, 0)} and distances to all vertices infinity. Now follow the next steps.

The first vertex is reached with the best augmenting path. From it the possible edges are 1-2 and 1-3 (1-4 is not available in the 0th second. they trigger two more augmenting paths: {(<2, 1100>, 50), (<3, 1010>, 30)} the distance to <1, 1000> is changed to 0.

The next step considers the best augmenting path (<3, 1010>, 30). However neighter of the outgoing edges can be used to add augmenting path: 1-3 can not be used, because the vertex 1 can not be visited at time 60. edge 3-4 can not also be used, because of the time interval. Thus the augmenting paths are now: {(<2, 1100>, 50)}.

Next step: (<2, 1100>, 50) and new augmenting paths: {(<1, 1100>, 100), (<4, 1101>, 70)}.

Next step: (<4, 1101>, 70) but it does not add new path either: vertex 2 can not be visited at time 90 and 3-4 can not be used any more. Thus the augmenting paths are {(<1, 1100>, 100)}.

Next step: (<1, 1100>, 100) which changes augmenting paths to: {(<3, 1110>, 130)}.

Next step: (<3, 1110>, 130) which changes augmenting paths to: {(<4, 1111>, 180)}.

Next step: (<4, 1111>, 180) which is the final step - we are in a state in which all target vertices are visited. So the sum-up: you can visit all the vertices in the limitations for 180 seconds.

I hope this example will help you understand my idea. You probably will need to write all considerations on sheet of paper to make sur eI do not lie with the augmenting paths.