In the theme park problem, it is important to find a coordination algorithm that effectively shortens the visiting time of an entire theme park while guaranteeing individual optimality for each visitor. In a previous study, a coordination algorithm, called statement-based cost estimate (SCE), was proposed that allows individual visitors to select plans that minimize a visitor’s visiting time while shortening the visiting time of the entire theme park. However, the improvement in visiting time was not sufficient from their experiment using SCE. We thought it necessary to relax the premise constraint “minimize individual visiting time” to further improve SCE. In this paper, we propose a framework to further reduce visiting time by considering Pareto optimality. In the proposed framework, each visitor determines several Pareto optimal plans based on the evaluation value calculated using SCE and presents them to a coordination system. Then, the coordination system searches for the entire optimal plan that minimizes the predicted value of the total visiting time of the entire theme park among the Pareto optimal plan candidates. The proposed framework guarantees visitors’ “personal optimality” in the meaning of Pareto optimality, and there is a possibility that the framework will shorten the visiting time of the entire theme park. We conducted a simulation experiment using a coordination algorithm based on the proposed framework and clarified the effectiveness of the framework.