The car pooling problem:heuristic algorithms based on savings functions

The present research deals with car pooling as a means of making better use of existing infrastructure and as a means of reducing traffic congestion with all its associated induced effects. Car pooling schemes involve several drivers getting together to share a private vehicle simultaneously, in order to reach their destinations points according to a semi-common route rather than each driver using their own vehicle. The Car Pooling Problem belongs to the non-polynomial computational complexity family of operations problems. In the current literature there are only a few studies on this optimization problem: the research group has designed several different new automatic and heuristic data processing routines to support efficient matching in car pool schemes. These are based on savings functions and belong to two distinct macro classes of algorithms to give two different modelings of this problem. They offer average savings of more than 50% in traveled distances demonstrating the effectiveness of a trivial matching scheme for real applications.