Event carpooling as an algorithm based on the Shortest Path Problem with Resource Constraints

The goal of this thesis has been to create and implement an event carpooling algorithm, as an application of the Shortest Path Problem with Resource Constraints (SPPRC). As co-founders of the start-up CovEvent, Nicolas Cognaux and myself were eager to improve the major algorithm behind our online platform. This thesis researched the relevant algorithmic literature and exposed the choices made during the development of the algorithm. The document starts with a detailed overview of the company’s context, followed by an analysis of the current system that is being used as well as a clear statement of the problem. The third section describes the algorithm as it has been designed and architectured. The following section focuses on one of the most important components of this algorithm: the Shortest Path (sub-)Problem with Resource Constraints. Eventually, the last chapter makes the link between the previous chapters by highlighting the changes made to the platform and the challenges faced during its implementation. On top of the explanations of this document, the Java code of this algorithm is available through its Bitbucket link and is described in appendix A. The product of this work is now being implemented on CovEvent’s servers. A trade-off has been found between the absolute optimality and the complexity of the algorithm. It enables to show [nearly] optimal co-riders in less than two seconds to every new rider and is expected to improve the current matching rate by more than 500%.