An optimization model and a solution algorithm for the many-to-many car pooling problem

Shangyao Yan, Chun Ying Chen

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


Car pooling is one method that can be easily instituted and can help to resolve a variety of problems that continue to plague urban areas, ranging from energy demands and traffic congestion to environmental pollution. Although car pooling is becoming more common, in practice, participant matching results are still being obtained by an inefficient manual approach, which may possibly result in an inferior solution. In the past, when car pooling studies have been done the problem has been treated as either a to-work problem (from different origins to the same destination) or return-from-work problem (from the same origin to different destinations). However, in this study we employ a time-space network flow technique to develop a model for the many-to-many car pooling problem with multiple vehicle types and person types. The model is formulated as an integer multiple commodity network flow problem. Since real problem sizes can be huge, it could be difficult to find optimal solutions within a reasonable period of time. Therefore, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model. To test how well the model and the solution algorithm can be applied to real world, we randomly generated several examples based upon data reported from a past study carried out in northern Taiwan, on which we performed numerical tests. The test results show the effectiveness of the proposed model and solution algorithm.

Original languageEnglish
Pages (from-to)37-71
Number of pages35
JournalAnnals of Operations Research
Issue number1
StatePublished - Nov 2011


  • Car pooling
  • Lagrangian relaxation
  • Many-to-many
  • Multiple commodity network flow problem
  • Time-space network


Dive into the research topics of 'An optimization model and a solution algorithm for the many-to-many car pooling problem'. Together they form a unique fingerprint.

Cite this