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

QingBiao Meng; Shingo Mabu; Lu Yu; Kotaro Hirasawa

doi:10.20965/jaciii.2010.p0442

single-jc.php

« previous

JACIII Vol.14 No.5 pp. 442-452

doi: 10.20965/jaciii.2010.p0442

(2010)

Paper:

Views over last 60 days: 912

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

Received:

November 16, 2009

Accepted:

March 5, 2010

Published:

July 20, 2010

Keywords:

taxi, scheduling problem, dispatch system, genetic network programming, evolutionary computation

Abstract

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:

References

[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] 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] 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] 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] 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] 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] 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] 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] 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] D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
[11] J. R. Koza, “Genetic Programming, on the Programming of Computers by Means of Natural Selection,” MIT Press, Cambridge, MA, 1992.
[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] 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] 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] 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 article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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).