Multimodal Itineraries Ranking using Fuzzy Logic - Naver Labs Europe


The size of the Pareto alternative set of a multicriteria multimodal shortest path problem can be exponential. Even approximation sets can remain quite large, while a user of multimodal trip planner app would like to have only a few choices but those choices must be relevant for him. Therefore, we need to process a selection of alternatives before proposing them to the users. Furthermore, since users can have different preferences over the characteristics of an itinerary, the set of alternative needs to be personalized to the user. By consequence, this study started by wondering: How can we propose a reasonable small size set of “personally good” alternatives to the corresponding user? For this aim, we need to find a way to model the users’ preferences, and then evaluate each alternative comparing to the others regarding the user’s preferences. In the existing studies, the users’ preferences are mostly modelled by some weights for each criterion, which are given by the users and that enable to aggregate all the criteria into one single objective function. We think it’s difficult to describe one person’s feeling by a crisp number and that the Fuzzy logic is better suited in this situation. In this talk, we are proposing a Fuzzy system to rank the alternatives. Our system has three phases. In the first phase, we transform the users’ preferences and the alternatives’ criteria evaluation into fuzzy sets. For example, one user’s preference on the subways can be “Like” with a descriptive membership value, the total duration of one alternative can be “Long” with its membership value. During the alternatives’ criteria transformation, we are proposing two novel methods of fuzzification according to the different types of criteria for setting the membership functions. The first method uses a parameter which is called the “tolerance” of the user for each criterion, while the second method is based on a clustering of the alternatives. In the second phase, a combination between user’s preferences and the rating of the alternatives for each criterion according to the membership functions allows to evaluate the user’s satisfaction on each criterion. The combination is realized by using a set of fuzzy rules. In the third phase, we are proposing a new defuzzification method, combining the different level of satisfactions that we calculated in the second phase into a general satisfaction of the alternative. The general satisfaction is represented by a crisp number that is our ranking parameter. In order to assess the method, we built a survey in which we asked people to rank alternatives, and we compared the surveys’ results with the results from our ranking system.

Ceci correspond à une petite biographie d'environ 200 caractéres