We describe a multi-agent platform for a traveller information system, allowing travellers to find the road traffic information web service (WSs) that best fits their requirements. After studying existing proposals for discovery of semantic WS, we implemented a hybrid matching algorithm, which is described in detail here. Semantic WS profiles are annotated semantically as an OWL-S and also the traveller request is represented as a OWL-S profile. The algorithm assigns different weights and measures to each advertised WS profile parameter, depending on their relevance, type and nature. To do this we have extended Paolucci’s Algorithm and adapted it to our scenario. We have added new similarity measures, in particular, the use of the ‘sibling’ relationship, to improve the recall, allowing relevant services to be discovered by the users yet not retrieved by other algorithms. Although we have increased the similarity concept relations, we have improved the run-time using a pre-process filter step that reduces the set of potentially useful WS. This improves the scalability of the semantic matching algorithm.