Theory and Practice in Large Carpooling Problems

The authors address the carpooling problem as a graph-theoretic problem. If the set of drivers is known in advance, then for any car capacity, the problem is equivalent to the assignment problem in bipartite graphs. Otherwise, when it is not known in advance who will drive their vehicle and who will be a passenger, the problem is NP (Non-deterministic Polynomial-time)-hard. The authors devise and implement quick heuristics for both cases, based on graph algorithms, as well as parallel algorithms based on geometric/algebraic approach. Theycompare between the algorithms on random graphs, as well as on real, very large, data.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01536523
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jul 30 2014 3:14PM