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
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.
-  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.
-  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.
-  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.
-  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.
-  C. Yue, S. Mabu, Y. Wang, and K. Hirasawa, “Multiple Round English Auction Agent based on Genetic Network Programming,” IEEJ trans. TEEE, 2009 (accepted).
-  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.
-  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.
-  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.
-  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.
-  D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
-  J. R. Koza, “Genetic Programming, on the Programming of Computers by Means of Natural Selection,” MIT Press, Cambridge, MA, 1992.
-  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.
-  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).
-  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.
-  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).