Many advanced traveler information systems (ATIS) provide travel solutions that are limited, by technical obstructions or by design, in terms of geographical coverage, transport services, and/or travel modes. However, using existing ATIS in an integrated manner can broaden the coverage of travel solutions, while preserving the advantages of each system. This paper presents an approach to exploit web resources such as ATIS, data sources and services to construct travel solutions. More precisely, it focuses on itinerary formulation and discovery of resources relevant to each itinerary. We propose a semantic model for describing and interlinking geographic entities in relation to web resources, creating a graph of related entities. Itinerary formulation and resource discovery are achieved via exploring the graph. To this end, we propose an adapted version of multi-agent A* algorithm.