Concept of Neighborhood Degree and its Application to Switching Plural Optimization Methods in Scheduling
Fangyan Dong*, Kewei Chen**, and Kaoru Hirota*
*Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology G3-49, 4259 Nagatsuta, Midori-ku, Yokohama 226-8502, Japan
**The Computing, Designing and Integration Co., Ltd. 474-5 Tsukakoshi 3, Saiwai-ku, Kawasaki, Kanagawa 212-0024, Japan
A concept of neighborhood degree is proposed to evaluate the quality of solutions to scheduling problems such as vehicle routing, scheduling, and dispatching problems. It is possible to apply it to the optimization process of scheduling problems in order to switch between various optimization methods by considering convergence speed and solution quality. In the experiments on TSP benchmark data, two optimization methods, i.e., tabu search and simulated annealing, are switched effectively by observing the variation of the neighborhood degree. Directions for Practical applications are also mentioned.
-  I. Osaman, “Metastrategy Simulated Annealing and Tabu Search Algorithm for the Vehicle Routing Problem,” Annals of Operations Research, No.41, pp. 421-451, 1993.
-  F. Leclerc and J. Y. Potvin, “Genetic Algorithm for Vehicle Dispatching,” Int. Trans. Opl. Res, Vol.4, No.5/6, pp. 391-400, 1997.
-  G. Barbarosoglu and D. Ozgur, “A Tabu Search Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, No.26, pp. 255-270, 1999.
-  C. D. Tarantilis and C. T. Kiranoudis, “A Meta-Heuristic Algorithm for the Efficient Distribution of Perishable Food,” J. of food Engineering, No.50, pp. 1-9, 2001.
-  H. Igarashi, “A Vehicle Schedule Planning System Using a Simulated Annealing Method (in Japanese),” J. of the Trans. of the Institute of Electronics, Information and Communication Engineers, Japan, Vol.J78-D-II, No.5, pp. 819-826, 1995.
-  K. Chen, Y. Takama, and K. Hirota, “A Calculation Model of Hierarchical Multiplex Structure for Vehicle Routing & Scheduling Dispatching Problem with Single Depot,” Japan Society for Fuzzy Theory and Systems, Vol.13, No.2, pp. 187-198, 2001.
-  F. Dong, K. Chen, and K. Hirota, “Neighborhood-Based Formulation and Dynamic Quantitative Evaluation of Solution for Delivery Problem and it’s Application to TSP/VRP,” Vol.15. No.4, pp. 440-451, 2003 (in Japanese ).
-  F. Dong, K. Chen, Y. Takama, and K. Hirota, “An Approach of Evolutionary Computation for Vehicle Routing Problem with Single Depot,” 2nd Int. Symposium on Advanced Intelligent System, August 2001, Korea, Vol.2, No.2, pp. 339-343, 2001.
-  K. Boese, “Models for Iterative Global Optimization,” UCLA Computer Science Department, Ph.D. Thesis, 1996.