A model and a solution algorithm for the car pooling problem with pre-matching information

Shangyao Yan, Chun Ying Chen

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Most past car pooling studies have focused on the to-work problem (from different origins to a common destination) or the return-from-work problem (from the same origin to different destinations). Pre-matching information, including the carpool partners and the route/schedule for each previously participating vehicle, have rarely been considered. As a result, there has not yet been a suitable method/model developed for solving practical many-to-many car pooling problem with multiple vehicle and person types, as well as pre-matching information, that occur in real-world. In this study we strive to make up this lack by employing a time-space network flow technique to develop a model for this type of car pooling problem with pre-matching information (CPPPMI). The model is formulated as an integer multiple commodity network flow problem. A solution algorithm, based on Lagrangian relaxation and a heuristic for the upper bound solution, is developed to solve the model. To test how well the model and the solution algorithm may be applied to real-world, numerical tests are performed with several problem instances randomly generated based upon data reported from a past study carried out in northern Taiwan. The test results show the effectiveness of the proposed model and solution algorithm.

Original languageEnglish
Pages (from-to)512-524
Number of pages13
JournalComputers and Industrial Engineering
Issue number3
StatePublished - Oct 2011


  • Car pooling problem
  • Lagrangian relaxation
  • Multiple commodity network flow problem
  • Pre-matching information
  • Time-space network


Dive into the research topics of 'A model and a solution algorithm for the car pooling problem with pre-matching information'. Together they form a unique fingerprint.

Cite this