It is quite common in tourism industry that a tourist would love to gain the most wonderful experience from visiting multiple places in one trip. This is a service composition problem and is difficult to manage because of several reasons. We address this problem by proposing an agent-based service composition framework to allocate to the tourist an optimal composite service. We take into account a number of factors including: 1) all the places of interest must be visited; 2) the preference on visiting places must be obeyed; 3) the total price is within the budget; 4) the time constraint must be obeyed; 5) the payoffs for service providers are worthwhile and fair. We propose a bottom-up approach to allocate the optimal service composition where intelligent agents are deployed to provide flexibility and efficiency to the system. As a result, the system is more independent and every party is better off.