Expected travel time for regularly departing trains
Here's a way you can find the optimal algorithm. Let's assume (for convenience) that all $x_i$ and $y_i$ are distinct.

First, we need to prove two theorems.

(1) If at time $t$, you would get on a train with travel time $y_i$, you would also get on any train with travel time less than $y_i$.

(2) If you would get on train $j$ at time $t_j$, you would also get on that train $j$ at any time $t \leq t_j$. 

For (1), the proof is easy. For (2), the proof is based on the observation that the longer you wait, the higher the probability that any particular train shows up. So if there's some strategy of waiting for trains other than $j$ that has better performance than getting on a train $j$ with travel time $y_j$ at time $t_j$, that same strategy is going to give travel time $\leq y_j$ for all times $t &gt; t_j$. 

Now, if train $\alpha$ is the train with minimum $y_\alpha$, then you want to get on this train any time it arrives. Furthermore, if you've waited $x_\alpha - \epsilon$ time for sufficiently small $\epsilon$, your optimal strategy is to wait for train $\alpha$. 

What we're going to do now is essentially continuous dynamic programming. If you've waited for time $t$, there are only $n$ possible optimal strategies. That is, get on any train with travel time $\leq y_i$. This optimal strategy changes at $n$ or fewer values of $t$. So, starting with time $x_\alpha$ and the strategy "wait for train $y_\alpha$", calculate the first time $t &lt; x_\alpha$ where the strategy changes. You can do this by comparing $n$ possible strategies, each of which gives an expected travel time which is a function of $t$. Keep working to the left in this fashion, until you get to time $t= 0$.