Multi-Resolution Dijkstra Method Based on Multi-Agent Simulation and its Application to Genetic   Algorithm for Classroom Optimization

Kotaro Maekawa; Kazuhito Sawase; Hajime Nobuhara

doi:10.20965/jaciii.2014.p0113

single-jc.php

« previous

JACIII Vol.18 No.2 pp. 113-120

doi: 10.20965/jaciii.2014.p0113

(2014)

Paper:

Views over last 60 days: 1,243

Multi-Resolution Dijkstra Method Based on Multi-Agent Simulation and its Application to Genetic Algorithm for Classroom Optimization

Kotaro Maekawa, Kazuhito Sawase, and Hajime Nobuhara

Department of Intelligent Interaction Technologies, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-0033, Japan

Received:

July 14, 2013

Accepted:

December 24, 2013

Published:

March 20, 2014

Keywords:

genetic algorithm, multi-agent, dijkstra algorithm, optimization problem, university courses problem

Abstract

The combinatorial optimization problem of university classroom schedule assignments is formulated using multiagent simulation and genetic algorithms in the evaluation and optimization process. The method we propose consists of global and local multiagent planning. Conventional global planning requires setting subgoals manually, which became a bottleneck in optimization. To solve this problem, a multi-resolution Dijkstra method for selected autonomously, assuming eight classrooms as a real University of Tsukuba building and 250 agents, we confirmed the effectiveness of the proposed multi-resolution Dijkstra’s algorithm as for both global and local route selections, compared to the uniform Dijkstra’s method.

Cite this article as:

K. Maekawa, K. Sawase, and H. Nobuhara, “Multi-Resolution Dijkstra Method Based on Multi-Agent Simulation and its Application to Genetic Algorithm for Classroom Optimization,” J. Adv. Comput. Intell. Intell. Inform., Vol.18 No.2, pp. 113-120, 2014.

Data files:

References

[1] A. Sakalli et al., “Heuristic bubble algorithm for a linehaul routing problem: An extension of a vehicle routing problem with pickup and delivery,” 2013 IEEE 14th Int. Symp. on Computational Intelligence and Informatics (CINTI), pp. 435-439, 2013.
[2] T. Kondo and T. Yoshikawa, “Urban Models Minimizing Average Travel Time by Introduction of Multistage Public Transportation System and District Centers,” Papers on city planning, No.45, pp. 139-144, 2010.
[3] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II,” Lecture notes in computer science, Vol.1917, pp. 849-858, 2000.
[4] M. Tanaka et al., “The phenotype space automatic extraction method for interactive Genetic Algorithms,” J. of Japan Society for Fuzzy Theory and Intelligent Informatics, Vol.22, No.6, pp. 720-732, 2010.
[5] Y. Nishimori, H. Kanoh,and S. Nishihara, “Constraint-based Interactive Timetabling System,” J. of Information Processing, Vol.38, No.6, pp. 1094-1102, 1997.
[6] M. Kanie, R. Sawauchi, and T. Tanaka, “A Computational Experiment for a Timetable Problem to New Faculty’s Curriculum by Combinatorial Optimization,” Hirosaki University, Faculty of Science and Technology research report, Vol.1, No.2, pp. 113-125, 1999.
[7] H. Shinoda and T. Kato, “Optimization of Recitation Schedule of College by Genetic Algorithm,” Fukuoka Institute of Technology Research J.,Vol.42, No.1, pp. 19-22, 2009.
[8] T. Kimura et al., “REPRESENTATION OF CROWD IN MULTIAGENT MODEL : Development of pedestrian simulation system SimTread,” J. of Japan Architecture and Building Engineering, Vol.74, No.636, pp. 371-377, 2009.
[9] Y. Takahashi et al., “Acquisition of Competitive Behaviors in Multi-Agent System Based on a Modular Learning System,” J. of The Robotics Society of Japan, Vol.27, No.3, pp. 350-357, 2009.
[10] M. Pipattanasomporn, H. Feroze, and S. Rahman, “Multi-agent systems in a distributed smart grid: Design and implementation. In Power Systems Conference and Exposition,” PSCE’09, IEEE/PES, pp. 1-8, 2009.
[11] K. Maekawa, K. Sawase, and H. Nobuhara, “Multi-resolution Dijkstra method based on multi-agent simulation and its application to genetic algorithm for class-room optimization,” Fuzzy System Symp., Vol.28, pp. 275-279, 2012.
[12] H. Ueda, D. Ouchi, K. Takahashi, and T. Miyahara, “Comparisons of Genetic Algorithms for Timetabling Problems,” J. of the Institute of Electronics, Information and Communication Engineers D1, Vol.9, pp. 691-701, 2003.
[13] Y. Nagasaku, M. Takano, and T. Koseki, “Train Rescheduling Evaluation and Assistance System with Passengers’ Behavior Simulation based on Graph Theory,” The Institute of Electrical Engineers of Japan study group data, TER-03-23, 2003.
[14] J. Taniguchi, M. Gen, and X. Wang, “Capacitated Obstacle Facility Location Problems inSupply Chain Network using hGA,” Int. Workshop on Fuzzy Systems and Innovational Computing 2004, 2004.
[15] R. Hino and H. Tsuji, “Modeling of Schedule-Based Path Planning for Automated Vehicles Guided by Uni-Directed Rails,” Int. J. of Automation Technology, Vol.6, No.2, 2012.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] A. Sakalli et al., “Heuristic bubble algorithm for a linehaul routing problem: An extension of a vehicle routing problem with pickup and delivery,” 2013 IEEE 14th Int. Symp. on Computational Intelligence and Informatics (CINTI), pp. 435-439, 2013.

[2] [2] T. Kondo and T. Yoshikawa, “Urban Models Minimizing Average Travel Time by Introduction of Multistage Public Transportation System and District Centers,” Papers on city planning, No.45, pp. 139-144, 2010.

[3] [3] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II,” Lecture notes in computer science, Vol.1917, pp. 849-858, 2000.

[4] [4] M. Tanaka et al., “The phenotype space automatic extraction method for interactive Genetic Algorithms,” J. of Japan Society for Fuzzy Theory and Intelligent Informatics, Vol.22, No.6, pp. 720-732, 2010.

[5] [5] Y. Nishimori, H. Kanoh,and S. Nishihara, “Constraint-based Interactive Timetabling System,” J. of Information Processing, Vol.38, No.6, pp. 1094-1102, 1997.

[6] [6] M. Kanie, R. Sawauchi, and T. Tanaka, “A Computational Experiment for a Timetable Problem to New Faculty’s Curriculum by Combinatorial Optimization,” Hirosaki University, Faculty of Science and Technology research report, Vol.1, No.2, pp. 113-125, 1999.

[7] [7] H. Shinoda and T. Kato, “Optimization of Recitation Schedule of College by Genetic Algorithm,” Fukuoka Institute of Technology Research J.,Vol.42, No.1, pp. 19-22, 2009.

[8] [8] T. Kimura et al., “REPRESENTATION OF CROWD IN MULTIAGENT MODEL : Development of pedestrian simulation system SimTread,” J. of Japan Architecture and Building Engineering, Vol.74, No.636, pp. 371-377, 2009.

[9] [9] Y. Takahashi et al., “Acquisition of Competitive Behaviors in Multi-Agent System Based on a Modular Learning System,” J. of The Robotics Society of Japan, Vol.27, No.3, pp. 350-357, 2009.

[10] [10] M. Pipattanasomporn, H. Feroze, and S. Rahman, “Multi-agent systems in a distributed smart grid: Design and implementation. In Power Systems Conference and Exposition,” PSCE’09, IEEE/PES, pp. 1-8, 2009.

[11] [11] K. Maekawa, K. Sawase, and H. Nobuhara, “Multi-resolution Dijkstra method based on multi-agent simulation and its application to genetic algorithm for class-room optimization,” Fuzzy System Symp., Vol.28, pp. 275-279, 2012.

[12] [12] H. Ueda, D. Ouchi, K. Takahashi, and T. Miyahara, “Comparisons of Genetic Algorithms for Timetabling Problems,” J. of the Institute of Electronics, Information and Communication Engineers D1, Vol.9, pp. 691-701, 2003.

[13] [13] Y. Nagasaku, M. Takano, and T. Koseki, “Train Rescheduling Evaluation and Assistance System with Passengers’ Behavior Simulation based on Graph Theory,” The Institute of Electrical Engineers of Japan study group data, TER-03-23, 2003.

[14] [14] J. Taniguchi, M. Gen, and X. Wang, “Capacitated Obstacle Facility Location Problems inSupply Chain Network using hGA,” Int. Workshop on Fuzzy Systems and Innovational Computing 2004, 2004.

[15] [15] R. Hino and H. Tsuji, “Modeling of Schedule-Based Path Planning for Automated Vehicles Guided by Uni-Directed Rails,” Int. J. of Automation Technology, Vol.6, No.2, 2012.