Cross Entropy Method for Solving Generalized Orienteering Problem

DOI: 10.4236/ib.2010.24044   PDF   HTML     5,048 Downloads   8,619 Views   Citations


Optimization technique has been growing rapidly throughout the years. It is caused by the growing complexity of problems that require a relatively long time to solve using exact optimization approach. One of complex problems that is hard to solve using the exact method is Generalized Orienteering Problem (GOP), a combinatorial problem including NP-hard problem. Recently, there has been plenty of heuristic method development to solve this problem. This research is an implementation of cross entropy (CE) method in real case of GOP. CE is an optimization technique that relatively new, using two main procedures; generating sample solution and parameter updating to produce better sample for next iteration. At this research, GOP problem that occurs at finding optimal route consist of 27 cities in eastern China is investigated. Results indicate that CE method give better performance than those of Artificial Neural Network (ANN) and Harmony Search (HS).

Share and Cite:

B. Santosa and N. Hardiansyah, "Cross Entropy Method for Solving Generalized Orienteering Problem," iBusiness, Vol. 2 No. 4, 2010, pp. 342-347. doi: 10.4236/ib.2010.24044.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Z. Sevkli, and F. dan E. Sevilgen, “Variable Neigh- borhood Search for the Orienteering Problem,” A. Levi et al., Eds., ISCIS, Springer-Verlag, Berlin, Heidelberg, 2006, pp. 134-143.
[2] Q. Wang, X. Sun, B. L. Golden and J. Jia, “Using Artificial Neural Networks to Solve the Orienteering Problem,” Annals of Operations Research, Vol. 61, No. 1, 1995, pp. 111-120.
[3] Tasgetiren and M. Fatih, “A Genetic Algorithm with an Adaptive Penalty Function for Orienteering Problem,” Journal of Economic and Social Research, Vol. 4, No. 2, 2000, pp. 1-26.
[4] G. Z. Woo, T. C. Li, D. Park and J. Yong, “Harmony Search for Generalized Orienteering Problem: Best Touring in China,” L. Wang, K. Chen and Y. S. Ong, Eds., Springer-Verlag, Berlin Heidelberg, 2005, pp. 741- 750.
[5] Z. Sevkli and F. dan E. Sevilgen, “Particle Swarm Optimization for the Orienteering Problem,” Proceedings of International Symposium on Innovation in Intelligent Systems and Applications, Istanbul, 2007, pp. 185-190.
[6] R. Rubinstein and D. Kroese, “The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization,” Monte-Carlo Simulation, and Machine-Learning, Springer-Verlag, Berlin, Heidelberg, 2004.
[7] H. Zhou, J. Wang and Y. Qiu, “Application of the Cross Entropy Method to the Credit Risk Assessment in an Early Warning System,” International Symposiums on Information Processing, 2008.
[8] R. Y. Rubinstein, “Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-Event Estimation,” Methodology and Computing in Applied Probability, Vol. 7, No. 1, 2005, pp. 5-50.
[9] D. Magee, “A Sequential Scheduling Approach to Combining Multiple Object Classifiers Using Cross-Entropy,” T. Windeatt and F. Roli, Eds., Springer-Verlag, Berlin, Heidelberg, 2003, pp. 135-145.
[10] D. P. Kroese and K.-P. Hui, “Applications of the Cross- Entropy Method in Reliability,” Computational Intelligence in Reliability Engineering, Vol. 40, 2007, pp. 37- 82.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.