Mutually Beneficial Confluent Routing

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.