Due to intermittent connectivity among nodes in mobile opportunistic networks, the direct packet delivery strategy often experiences large delays. To alleviate this problem, nodes often pass a copy of their message to relay nodes, which in turn could deliver it to the destination. In this setting, we consider the problem of relay selection that minimizes the mean delivery delay. Applying ideas from a renewal theory, we derive a closed-form expression for the mean delivery delay in a heterogeneous network under any probabilistic two-hop relay selection policy. Utilizing this expression, a policy that assures the least mean delivery delay can be obtained as a solution of a linear program (the time complexity of mathcal O(n3). However, exploiting the structure of the mean delay minimization problem, we compute an optimal solution using an algorithm with linearithmic ( O(n log n)) time complexity. © 1997-2012 IEEE.