Estimating Scalability Issues While Finding an Optimal Assignment for Carpooling

An automatic service to match commuting trips has been designed. Candidate carpoolers register their personal profile and a set of periodically recurring trips. The Global CarPooling Matching Service (GCPMS) shall advise registered candidates on how to combine their commuting trips by carpooling. Planned periodic trips correspond to nodes in a graph; the edges are labeled with the probability for negotiation success while trying to merge planned trips by carpooling. The probability values are calculated by a learning mechanism using on one hand the registered person and trip characteristics and on the other hand the negotiation feedback. The GCPMS provides advice by maximizing the expected value for negotiation success. This paper describes possible ways to determine the optimal advice and estimates computational scalability using real data for Flanders.