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

作者：Yan Shangyao^*; Chen Chun Ying; Lin Yu Fang

来源：IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1362-1373.

DOI：10.1109/TITS.2011.2158209

• Lagrangian relaxation
• many-to-many car pooling problem
• multiple commodity network flow problem
• network

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.

• 出版日期2011-12
• 单位中央民族大学