Search in a partial ordering defined by tuples of numbers
I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

global: visited, front

function proceed(arrival)
    visited := array of bool for each node initialized to false 
    for each x &amp;isin; front
        proceed(arrival, x)
    return front

function proceed(arrival, node):
    if(visited[node]): return
    visited[node] := true
    if(node.departure &gt; arrival):
       remove node from front
       for each node x:
           append x to the end of front

function calculate_outgoing:
    outgoing := array of lists for each arrival at A, each list contains feasible and relevant A-&gt;B connections for that arrival.
    front   := [(-&amp;infin;, -&amp;infin;)]
    for each arrival at A in increasing order:
        outgoing[arrival] := proceed(arrival)
    return outgoing


Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.