Today's street traffic is still largely inefficient. Overburdened roads lead to congestions, accidents and unnecessary pollution. The increasing interconnection of traffic participants into the Internet of Vehicles (IoV) has tremendous potential for improving this issue. Cooperative route planning, for example, is a concept for optimizing vehicular routing on a global scale by gathering data about planned routes from interconnected vehicles. As in other IoV applications, the benefits of such a system come at the cost of an increased privacy risk for participating users. Published routes include both the current and the planned future locations of drivers and passengers - all highly sensitive pieces of information. In the scope of this paper, we demonstrate how cooperative route planning can be realized with strong privacy guarantees without significant cuts in utility or cost. According to our knowledge, this is the first work to consider this issue. We propose a scheme by which vehicles can publish their intent to pass at specific waypoints at approximate times in an anonymous fashion. While providing complete unlinkability of published intentions to individual users, our scheme is protected against abuse, with misbehaving (i.e., lying) users quickly losing their right to participate.