Network virtualization has become one of the most prominent solutions that can efficiently deal with the dramatic increase of data demand in mobile networks. In order to allow multiple virtual networks to coexist in the same substrate network, the need for development of efficient virtual network embedding algorithms and techniques is imperative. The main purpose of this paper is to provide an optimization framework for virtual network embedding that minimizes the end-to-end delay. The proposed scheme takes also into account the actual user mobility effect in order to allow efficient mapping for mobile networks. In addition, it provides service differentiation allowing delay sensitive services to use the formed virtual networks with the minimum possible delay in comparison to elastic services. The performance of the proposed algorithm is evaluated and compared to existing optimal shortest path virtual network embedding algorithms. The numerical results reveal that the proposed algorithm converges to an optimal solution and its performance can achieve significant improvement in comparison to shortest path optimization algorithms.