Multi-agent travel planning through coalition and negotiation in an auction

In a travel scenario the travel agent often faces a situation: the users only provide their preferences on visiting destinations, while the visiting orders and the arrangements of transportations are left to the decision of the travel agent. Therefore the travel agent must find suitable (both efficient and economic) tracks for the users given their visiting destinations, different transportation services, constraints of users such as time, budget, and preferences. Although the service route map of each transportation company can be derived beforehand, the negotiable price information is often private. It is not feasible for a user or a travel planning agent to determine the total expense by simply summing up the list prices of all transportation track segments, and hence the selection of the most efficient track is also not possible. One way to find out the best route is to provide a mechanism for the transportation companies to form coalition and negotiate on the prices based on their own utilities and profit concerns. In this paper we propose a mechanism to solve the best tourist track problem. The mechanism includes a heuristic shortest path finding algorithm for a track graph and a track winner determination auction, called Z-auction, for track competition. We show how the travel planning problem can be solved through the multi-agent coalition and negotiation in the Z-auction under the multi-agent problem solving environment.