In recent years the cavity method, or message-passing algorithm, has been successfully exploited by statistical physicists to solve combinatorial optimization problems such as the K-satisfability (K-SAT). In this talk we introduce this method and outline how it is applied to solve routing problems on communication or traffic networks. In this context the typical situation is where many users want to communicate at the same time over a given network. One then wants to optimize the overall routing by minimizing communication path length and the traffic overlap either at nodes or at edges given a set of constraints. We will show how the cavity method provides the algorithmic tools to tackle these types of optimization problems efficiently.