Abstract
This paper describes a taxi scheduling system, which aims to improve the overall efficiency of the system, both from the perspective of the drivers and the customers. This is of particular relevance to Chinese cities, where hailing a taxi on the street is by far the most common way in which taxis are requested, since the majority of taxi drivers operate independently, rather than working for a company. The mobile phone and Global Positioning System-based taxi scheduling system, which is described in this paper, aims to provide a decision support system for taxi drivers and facilitates direct information exchange between taxi drivers and passengers, while allowing drivers to remain independent. The taxi scheduling problem is considered to be a non-cooperative game between taxi drivers and a description of this problem is given. We adopt an efficient algorithm to discover a Nash equilibrium, such that each taxi driver and passenger cannot benefit from changing their assigned partner. Two computational examples are given to illustrate the effectiveness of the approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bailey W and Clark T (1987). A simulation analysis of demand and fleet size effects on taxicab service rates. Proceedings of the 19th Conference on Winter Simulation (WSC’87), ACM: New York, pp 838–844.
Cairns R and Liston-Heyes C (1996). Competition and regulation in the taxi industry. Journal of Public Economics 59 (1): 1–15.
Corbo J and Parkes D (2005). The price of selfish behavior in bilateral network formation. In: ACM Symposium on Principles of Distributed Computing, ACM: New York, pp 99–107.
Cordeau J and Laporte G (2007). The dial-a-ride problem: Models and algorithms. Annals of Operations Research 153 (1): 29–46.
Deng C, Ong H, Ang B and Goh T (1992). A modelling study of a taxi service operation. International Journal of Operations & Production Management 12 (11): 65–78.
Flores-Guri D (2003). An economic analysis of regulated taxicab markets. Review of Industrial Organization 23 (3–4): 255–266.
Flores-Guri D (2005). Local exclusive cruising regulation and efficiency in taxicab markets. Journal of Transport Economics and Policy 39 (2): 155–166.
Gale D and Shapley LS (1962). College admissions and the stability of marriage. American Mathematical Monthly 69 (1): 9–14.
Glaschenko A, Ivaschenko A, Rzevski G and Skobelev P (2009). Multi-agent real time scheduling system for taxi companies. Proc. Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, pp 29–36.
Gusfield D and Irving R (1989). The Stable Marriage Problem: Structure and Algorithms, Vol. 54. MIT Press: Cambridge, MA.
Halldorsson M et al (2003). Approximability results for stable marriage problems with ties. Theoretical Computer Science 306 (1–3): 431–447.
Irani S, Lu X and Regan A (2004). On-line algorithms for the dynamic traveling repair problem. Journal of Scheduling 7 (3): 243–258.
Ishii M, Lee P, Tezuka K and Chang Y (2013). A game theoretical analysis of port competition. Transportation Research Part E 49 (1): 92–106.
Kendall G and Li J (2013). Competitive traveling salesmen problem: A hyper-heuristic approach. Journal of Operational Research Society 64 (2): 208–216.
Lee D, Wang H and Cheu R (2003). Trip-chaining for taxi advance bookings: A strategy to reduce cost of taxi operation. Proceedings of the 83rd Annual Meeting of the Transportation Research Board, Washington DC.
Li S (2006). Multi-attribute taxi logistics optimization. MSc Thesis, Massachusetts Institute of Technology.
Liao Z (2003). Real-time taxi dispatching using global positioning systems. Communication of the ACM 46 (5): 81–83.
Luo Y and Schonfeld P (2007). A rejected-reinsertion heuristic for the static dial-a-ride problem. Transportation Research Part B: Methodological 41 (7): 736–755.
Madsen O, Ravn H and Rygaard J (1995). A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Annals of Operations Research 60 (1): 193–208.
Nash J (1951). Non-cooperative games. The Annals of Mathematics. Second Series 54 (2): 286–295.
National Bureau of Statistics of China (2006). Yearbook of China, chapter 16: Transportation & Communications.
Nkoane S (2009). Operations research modeling of the taxi transport between Polokwane and Mankweng in the Limpopo Province South Africa. MSc Thesis, University of Limpopo.
Prakash S and Kulkarin M (2003). Fleet management: A GPS-GIS integrated approach. In Proceedings of the Map India Conference, GIS Development: India.
Yang H and Yang T (2011). Equilibrium properties of taxi markets with search frictions. Transportation Research Part B: Methodological 45 (4): 696–713.
Yang H, Fung C, Wong K and Wong S (2010a). Nonlinear pricing of taxi services. Transportation Research Part A: Policy and Practice 44 (5): 337–348.
Yang H, Leung C, Wong S and Bell M (2010b). Equilibria of bilateral taxi-customer searching and meeting on networks. Transportation Research Part B: Methodological 44 (8): 1067–1083.
Acknowledgements
This work is supported by National Natural Science Foundation of China (Grant No. 71001055), Zhejiang Provincial Natural Science Foundation (Grant No. Y1100132) and ‘Qian Jiang’ Talent Initiative Program (QJD0802001).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bai, R., Li, J., Atkin, J. et al. A novel approach to independent taxi scheduling problem based on stable matching. J Oper Res Soc 65, 1501–1510 (2014). https://doi.org/10.1057/jors.2013.96
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2013.96