Abstract
In this paper, the authors present a formulation of the multi-hop many-to-many Peer-to-Peer ride- matching problem, found in shared-ride applications. A many-to-many problem is one in which a rider can travel with multiple drivers, and a driver can carry multiple riders. The authors propose a pre- processing procedure to reduce the size of the problem. Furthermore, they devise a decomposition algorithm to solve the original ride-matching problem to optimality by means of solving multiple smaller problems. Finally, they demonstrate the computational efficiency of the proposed algorithm by solving randomly generated instances of the problem.