JACIII Vol.14 No.5 pp. 442-452
doi: 10.20965/jaciii.2010.p0442


A Novel Taxi Dispatch System Integrating a Multi-Customer Strategy and Genetic Network Programming

QingBiao Meng, Shingo Mabu, Lu Yu, and Kotaro Hirasawa

Graduate School of Information, Production and Systems, Waseda University, Hibikino 2-7, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan

November 16, 2009
March 5, 2010
July 20, 2010
taxi, scheduling problem, dispatch system, genetic network programming, evolutionary computation
Taxi service usually benefits people by providing comfortable and flexible ride experiences. However, an inherent problem, the insufficient number of taxis at traffic peak, has baffled taxi service ever since it existed. This paper hereby proposes a Multi-Customer Taxi Dispatch System (MCTDS), where taxis are granted a right to take customers with different Origin-Destination (OD) pairs simultaneously, to shorten the total waiting time and traveling time. In addition, to mitigate the damage of detours, MCTDS is built based on Genetic Network Programming, a graph-based evolutionary algorithm that has shown excellent performances previously in some complicated applications. We also modify the structure of GNP to achieve an improvement in performance. In the simulation part, we demonstrate that MCTDS outperforms the conventional GNP and some heuristic taxi dispatch approaches.
Cite this article as:
Q. Meng, S. Mabu, L. Yu, and K. Hirasawa, “A Novel Taxi Dispatch System Integrating a Multi-Customer Strategy and Genetic Network Programming,” J. Adv. Comput. Intell. Intell. Inform., Vol.14 No.5, pp. 442-452, 2010.
Data files:
  1. [1] T. Eguchi, K. Hirasawa, J. Hu, and N. Ota, “A study of Evolutionary Multiagent Models Based on Symbiosis,” IEEE Trans. on Syst., Man and Cybernetics Part B, Vol.36, No.1, pp. 179-193, 2006.
  2. [2] S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming(GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, MIT press, Vol.15, No.3, pp. 369-398, 2007.
  3. [3] K. Hirasawa, T. Eguchi, J. Zhou, L. Yu, and S. Markon, “A Double-Deck Elevator Group Supervisory Control System using Genetic Network Programming,” IEEE Trans. on System, Man and Cybernetics, Part C, Vol.38, No.4, pp. 535-550, July 2008.
  4. [4] Y. Chen, S. Mabu, K. Shimada, and K. Hirasawa, “Real Time Updating Genetic Network Programming for Adapting to the Change of Stock Prices,” IEEJ trans. EIS, Vol.129, No.2, pp. 344-354, 2009.
  5. [5] C. Yue, S. Mabu, Y. Wang, and K. Hirasawa, “Multiple Round English Auction Agent based on Genetic Network Programming,” IEEJ trans. TEEE, 2009 (accepted).
  6. [6] M. Shrivastava, P. K. Chande, A. S. Monga, and H. Kashiwagi, “Taxi Dispatch: A Fuzzy Approach,” In Proc. of the IEEE Conf. on Intelligent Transportation System, 1997.
  7. [7] K. T. Seow, N. H. Dang, and D. H. Lee, “Towards an Automated Multiagent Taxi-Dispatch System,” In Proc. of the 3rd Annual IEEE Conf. on Automation Science and Engineering, Scottsdale, AZ, USA, Sept. 22-25, pp. 1045-1050, 2007.
  8. [8] Y. Q. Jia, “Improvement Program of Taxi Stops based on Simulated Annealing Algorithm in the Context of China,” In Proc. of the 2nd Int. Conf. on Genetic and Evolutionary Computing, 2008.
  9. [9] J. H. Lee, I. H. Shin, and G. L. Park, “Analysis of the Passenger Pick-up Pattern for Taxi Location Recommendation,” In Proc. of the 4th Int. Conf. on Networked Computing and Advanced Information Management, 2008.
  10. [10] D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
  11. [11] J. R. Koza, “Genetic Programming, on the Programming of Computers by Means of Natural Selection,” MIT Press, Cambridge, MA, 1992.
  12. [12] L. T. Wang, S. Mabu, F. M. Ye, S. Eto, X. F. Fan, and K. Hirasawa, “Genetic Network Programming with Rule Accumulation and its Application to Tile-World Problem,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.13, No.5, pp. 551-560, 2009.
  13. [13] F. M. Ye, S. Mabu, L. T. Wang, S. Eto, and K. Hirasawa, “Genetic Network Programming with Reconstructed Individuals,” SICE J. of Control, Measurement and System Integration, 2009 (accepted).
  14. [14] H. Y. Zhou, W. Wei, K. Shimada, S. Mabu, and K. Hirasawa, “Time Related Association Rules Mining with Attributes Accumulation Mechanism and its Application to Traffic Prediction,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.12, No.5, pp. 467-478, 2008.
  15. [15] M. K. Mainali, S. Mabu, S. Q. Yu, S. Eto, and K. Hirasawa, “Dynamic Optimal Route Search Algorithm for Car Navigation Systems with Preferences by Dynamic Programming,” IEEJ trans. TEEE, 2009 (accepted).

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Jun. 19, 2024