In this paper we consider a scenario of travelling between different cities using a partial autonomous car. In our scenario, various platoons travel along preset paths. The goal is to find a path between two vertices that is shorter than a given value and the overlap with the paths of the platoons is maximized. We formulate two versions of the Platooning Problem using graphs. In this versions, we aim to maximize either the time spent as member of a platoon or the percentage of the total time spent as member of a platoon. We prove that the two versions are not solvable in polynomial time, so we propose three polynomial time approximation algorithms, one for the first version and two for the second version.