Title: Multi-Agent Routing Schemes Based on Travel Risk Information in Ordinary or Emergency Situations

Name: Takanori HARA (1821038)


With the proliferation of navigation systems and smartphones, navigation services have infiltrated various aspects of our daily life. They can provide users with not only travel routes from their current locations to destinations but also travel risk information (e.g., travel time, traffic congestion, and road conditions). In this presentation, we focus on how the travel risk information affects user behavior in ordinary or emergency situations. In ordinary situations, we consider the travel congestion caused by individual selfish routing. On the other hand, as for emergency situations, we consider the travel risk of encounters with roads blocked by collapsed buildings under disaster situations (e.g., earthquakes). To tackle these issues, we address multi-agent routing schemes leveraging the travel risk information to achieve the optimal crowd guidance under ordinary and emergency situations, respectively. We first propose selfish yet optimal routing for ordinary situations, which is inspired by Nudge theory and achieves social optimum even under the rational decision making of individuals by internalizing the marginal cost into their perceiving information. Through numerical results, we show that (1) the selfish yet optimal routing exhibits almost the same performance as the optimal routing. (2) the selfish yet optimal routing decreases the individual travel time of 82% (resp. 67%) users compared with the notification of the actual travel information in case of the grid-like network (resp. local-level real road network in Nagoya city, Japan). The selfish yet optimal routing assumes that the roads in a selected route is simultaneously and constantly used by the corresponding agent, which is the same assumption of conventional congestion game. Since the roads in the selected route tends to be sequentially used by the agent, we further propose multi-commodity distributed route selection considering such time-varying road usage among agents under the ordinary situations. Through simulation results, we demonstrate that the proposed scheme can improve the actual travel time by 5.1% compared with the existing scheme while keeping the exponential convergence property. Next, focusing on the evacuation under a large-scale disaster, we further propose two kinds of schemes: 1) a geographical risk analysis based path selection scheme for the existing automatic evacuation guidance and 2) a capacitated refuge assignment scheme to achieve the speedy and reliable evacuation. Through simulation experiments using the local-level real road network in Nagoya city, Japan, we show that 1) the path selection scheme can improve the evacuation safety while keeping the evacuation speediness compared with the shortest path selection and 2) the refuge assignment scheme can improve the average route reliability by 13.6% while suppressing the increase of the average route length by 7.3% and satisfying the refuge capacity constraints, compared with the distance-based refuge assignment scheme.