Intellectics Group: Technical Report 02-03
The Long Term Car Pooling Problem -- On the Soundness of the
Problem Formulation and Proof of NP-completeness
Klaus Varrentrapp and Thomas Stützle and Vittorio
The rising car usage deriving from growth in jobs and residential population results in air pollution, energy waste and unproductive and unpleasant consumption of people s time. Public transport cannot be the only answer to this increasing transport demand. Car pooling has emerged to be a viable possibility for reducing private car usage in congested areas. Its actual practice re-quires a suitable information system support and, most important, the capability of effectively solving the underlying combinatorial optimization problem. This paper presents a brief introduc-tion to the problem of car pooling, gives a formal definition of one variant of car pooling, the long term car pooling problem, argues on the soundness of the problem formulation, and proves the long term car pooling problem to be NP-complete.