We address a new multi-user routing problem: mutually beneficial confluent routing (MCR). In the MCR, every user has his/her own source and destination; confluences of user routes occur so that users can mutually benefit from travelling together on the confluences. The idea of gaining benefit from travelling together is valuable in various practical applications, such as ride sharing, delivery routing, and pedestrian navigation. We formulate the MCR as a new combinatorial optimization problem on road networks to find optimum routes. As the main contributions of this paper [1], we propose exact and efficient algorithms for the MCR for the setting of two or three users. The setting is reasonable for various practical applications. We have the following two difficulties in solving the MCR: (D1) enumerating patterns of how the users meet and part in the MCR; and (D2) searching optimal meeting and parting nodes from numerous nodes. To overcome the difficulty (D1), we ascertain “confluence patterns” of the optimal solutions. Regarding (D2), we propose several efficient node pruning techniques. Experiments done on large scale road networks reveal that our algorithms are sufficiently efficient.

We investigate a new multi-user routing problem: mutually beneficial confluent routing (MCR). In the MCR, every user has his/her own source and destination; confluences of user routes occur so that users can mutually benefit from travelling together on the confluences. The idea of gaining benefit from travelling together is valuable in various practical applications, such as ride sharing, delivery routing, and pedestrian navigation. We formulate the MCR as a new combinatorial optimization problem on road networks. The MCR is more general and complex than single vehicle routing problems, ride-sharing problems, and the Steiner tree problem. We propose exact and efficient algorithms for the MCR for the setting of two or three users. The setting is reasonable for various practical applications. The key ideas of our algorithms are to use “confluence patterns” of the optimal solutions and exploit the properties of geometric graphs. Experimental results obtained on large scale road networks reveal that our algorithms are sufficiently efficient.

Walking is an easy exercise for maintaining health, although there are several environmental factors, such as road congestion or slopes, which are stressful for pedestrians, especially elders. Therefore, a pedestrian navigation system is required to recommend a less stressful route for a user by estimating such environmental factors. Towards realizing such a system, we firstly collect vital sign, spatiotemporal and environmental data from pedestrians, and secondly analyze the relation between them, and then propose models for estimating the personal stress of a pedestrian. As our vital sign data, we calculate the stress of each pedestrian from the R-R interval data obtained by a heart rate sensor. Our spatiotemporal data includes the walking speed of pedestrians and road grade calculated from GPS sensor data. We measure the degree of road congestion, as our environmental data, using a laser range finder. Our analysis reveals that the road congestion is an important factor affecting stress in walking. The proposed models based on neural networks employ the road congestion in addition to the vital sign and spatiotemporal data. Experimental results indicate that the road congestion degree is effective and the stress of pedestrians estimated by our models is similar to the real stress.

We focus on measuring relationships between pairs of objects in Wikipedia whose pages can be regarded as individual objects. Two kinds of relationships between two objects exist: in Wikipedia, an explicit relationship is represented by a single link between the two pages for the objects, and an implicit relationship is represented by a link structure containing the two pages. Some of the previously proposed methods for measuring relationships are cohesion-based methods, which underestimate objects having high degrees, although such objects could be important in constituting relationships in Wikipedia. The other methods are inadequate for measuring implicit relationships because they use only one or two of the following three important factors: distance, connectivity, and cocitation. We propose a new method using a generalized maximum flow which reflects all the three factors and does not underestimate objects having high degree. We confirm through experiments that our method can measure the strength of a relationship more appropriately than these previously proposed methods do. Another remarkable aspect of our method is mining elucidatory objects, that is, objects constituting a relationship. We explain that mining elucidatory objects would open a novel way to deeply understand a relationship.

For understanding human activity, a useful approach is to rank people according to the strength of their relations to a specified person. Similarly, rankings of objects based on such a relation are used in several fields. Several methods have been proposed for computing the strength of a relation between two objects. These methods do not present a reason why an object has a stronger relation to a specified object than another object has. Therefore, it is difficult for a user to understand a ranking obtained using these methods. On the other hand, the authors recently proposed a method for computing the strength of a relation through mining objects to elucidate the relation. We propose a ranking tool based on this method to afford a better understanding of a ranking. Our ranking tool has the following three characteristics for understanding a ranking: (1) it visualizes a relation by displaying objects that are important for elucidating the relation; (2) it classifies ranked objects into several groups, e.g., the two groups of "petroleum exporting countries'' and "petroleum consuming countries'' for ranking countries based on their respective relations to petroleum; and (3) it visualizes a reason explaining why an object has a stronger relation to a specified object than another object has. We explain novel ideas used in our ranking tool for understanding a ranking based on relations, and claim how effective the features of our tool are by presenting examples.