Title: Route optimisation using evolutionary approaches for on-demand pickup problem

Authors: Naoto Mukai, Toyohide Watanabe

Addresses: Department of Electrical Engineering, Faculty of Engineering, Division 1, Tokyo University of Science, Kudankita, Chiyoda-ku, Tokyo 102-0073, Japan. ' Department of Systems and Social Informatics, Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan

Abstract: The development of information technologies realises an on-demand transport (pick-up) system. In this paper, we simulate transport situations for the system based on multi-agent model to find efficient strategies. We examine four types of driver agents; random agent, greedy agent, Q-learning agent, and Genetic agent. Random agent and Greedy agents select the next pick-up points from its surround without learning and optimisation. In contrast, Q-learning agent estimates the expectation value of pick-up quantity by Q-learning, and Genetic agent optimises its travel routes by Genetic algorithm. Finally, we report our experimental results to evaluate the effect of the four strategies.

Keywords: on-demand buses; multi-agent simulation; evolutionary approach; Q-learning; genetic algorithms; multi-agent systems; MAS; agent-based systems; on-demand transport; pick-up systems; route optimisation; intelligent transport systems; ITS.

DOI: 10.1504/IJAIP.2010.029438

International Journal of Advanced Intelligence Paradigms, 2010 Vol.2 No.1, pp.19 - 32

Published online: 30 Nov 2009 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article