TY - JOUR

T1 - Solution methods for the taxi pooling problem

AU - Yan, Shangyao

AU - Chen, Chun Ying

AU - Wu, Chuan Che

N1 - Funding Information:
Acknowledgements This research was supported by grant NSC-98-2221-E-008-076-MY3 from the National Science Council of Taiwan. We thank the unnamed taxi company for providing the test data and their valuable opinions. We would also like to thank the two anonymous referees for their helpful comments and suggestions on the presentation of the paper.

PY - 2012/5

Y1 - 2012/5

N2 - In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.

AB - In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.

KW - Lagrangian relaxation

KW - Mathematical programming

KW - Multiple commodity network flow problem

KW - Multiple origins/destinations

KW - Taxi pooling

UR - http://www.scopus.com/inward/record.url?scp=84859264856&partnerID=8YFLogxK

U2 - 10.1007/s11116-011-9354-9

DO - 10.1007/s11116-011-9354-9

M3 - 期刊論文

AN - SCOPUS:84859264856

SN - 0049-4488

VL - 39

SP - 723

EP - 748

JO - Transportation

JF - Transportation

IS - 3

ER -