System, methods, and other embodiments described herein relate to improving vehicle routing for a mobility service. In one embodiment, a method includes, in response to receiving a routing request for the mobility service, determining candidate vehicles and candidate routes for the candidate vehicles to fulfill the routing request. The method includes evaluating the candidate routes using a meta-heuristic that modifies and assesses the candidate routes according to at least a fitness function defines attributes for constraining the candidate routes. The method includes providing a solution route from the candidate routes upon the solution route satisfying at least one solution condition.