Given a set of geographically dispersed vehicles, the first-mile ride-sharing problem seeks optimal routes to transport customers to a common destination (e.g., a transit station) via shared trips. In this article, we address the trade off between operating costs and service rates. The resulting multi-objective optimization problem is of a combinatorial nature. To obtain Pareto solutions we propose an evolutionary algorithm based on efficient non-dominated solution sorting. Extensive tests based on real-life data illustrate that the algorithm is able to find high-quality non-dominated fronts.