A Model With a Heuristic Algorithm for Solving the Long-Term Many-to-Many Car Pooling Problem

Long-term car pooling is defined as the sharing of a private vehicle by more than one user who need to reach a destination following a semicommon route between the individuals´ points of origin and destination in a specific period. In this paper, we employ a network flow technique to systematically develop a long-term many-to-many car pooling model. The model is formulated as a special integer multiple-commodity network flow problem. A Lagrangian relaxation-based algorithm is also developed to solve the model. The performance of the heuristic algorithm is evaluated by carrying out a case study using real data and suitable assumptions. The test results confirm the usefulness of the model and the heuristic algorithm and that they could be useful in practice.