A profit and a demand are associated with each arc of a set of profitable arcs of a given graph. A travel time is associated with each arc of the graph. A fleet of capacitated vehicles is given to serve the profitable arcs. A maximum duration of the route of each vehicle is also given. The profit of an arc can be collected by one vehicle only that also serves the demand of the arc. The objective of this problem, that is called the Capacitated Arc Routing Problem with Profits (CARPP), is to find a set of routes that satisfy the constraints on the duration of the route and on the capacity of the vehicle and maximize the total collected profit. We propose a branch-and-price algorithm and several heuristics. We can solve exactly instances with up to 97 profitable arcs. The best heuristics find the optimal solution on most of instances where it is available.