Ride-sharing is very popular these days. However, because of the high complexity of the underlying optimization problem, computation time and solutions quality are very challenging aspects to address, especially on large scale dataset. Several studies proposes solutions using different approaches like heuristics and machine learning. In this study, we devise a solution of the ride-sharing problem based on the division of the area of interest (Lomé, Togo). We use k-means algorithm for space clustering of the mobility requests, and we end up with a multi-objective problem with constraints. NSGA2 genetic algorithm is used to solve this problem, with promising results.