An Application of Binary Cuckoo Search Algorithm to Orienteering Problem

Giovano Alberto, Alfian Tan

Abstract


This research applies the cuckoo search metaheuristics model to find solutions to the Orienteering Problem (OP). The OP formulation is useful to model a situation in which someone wants to determine an optimal city route that is subject to a specified time constraint. OP can be categorized into NP Hard Problem which takes a very long time to analytically find the optimal solution as the number of entities involved increases. Therefore, metaheuristics often become an option to deal with this situation. A cuckoo search model based algorithm is developed in this research. An adjustment for discrete combinatorial problem is performed by adopting an idea of binary cuckoo search method. In addition, three types of local search methods are considered to improve the searching performance. This algorithm can eventually find better solutions for some of the 18 cases than two other benchmarked algorithms. Furthermore, experiment on model parameters shows that the worse nest fraction (P_alpha) affects the quality of solutions obtained.

Keywords


Cuckoo Search; Orienteering Problem; NP-Hard Problem; Discrete Optimization

Full Text:

PDF

References


P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden, “The orienteering problem: A survey,” European Journal of Operational Research, vol. 209, no. 1, pp. 1–10, 2011.

G. Laporte, M. Desrochers, and Y. Nobert, “Two exact algorithms for the distance-constrained vehicle routing problem,” Networks, vol. 14, no. 1, pp. 161–172, 1984.

S. Kataoka and S. Morito, “An algorithm for single constraint maximum collection problem,” Journal of the Operations Research Society of Japan, vol. 31, no. 4, pp. 515–531, 1988.

E. Arkin, J. Mitchell, and G. Narasimhan, “Resource-constrained geometric network optimization,” in Proceedings of the fourteenth annual symposium on Computational geometry, 1998, pp. 307–316.

B. Golden, L. Levy, and R. Vohra, “The orienteering problem,” Naval Research Logistics (NRL), vol. 34, no. 3, pp. 307–318, 1987.

D. Gavalas, C. Konstantopoulos, K. Mastakas, and G. Pantziou, “A survey on algorithmic approaches for solving tourist trip design problems,” Journal of Heuristics, vol. 20, no. 3, pp. 291–328, 2014.

S. Desale, A. Rasool, S. Andhale, and P. Rane, “Heuristic and metaheuristic algorithms and their relevance to the real world: a survey,” Int. J. Comput. Eng. Res. Trends, vol. 351, no. 5, pp. 2349–7084, 2015.

K. Bhattacharjee and S. Sarmah, “A binary cuckoo search algorithm for knapsack problems,” in International Conference on Industrial Engineering and Operations Management (IEOM), 2015, pp. 1–5.

D. Gupta, “Solving tsp using various meta-heuristic algorithms,” International Journal of Recent Contributions from Engineering, Science & IT (iJES), vol. 1, no. 2, pp. 22–26, 2013.

X.-S. Yang and S. Deb, “Cuckoo search: recent advances and applications,” Neural Computing and Applications, vol. 24, no. 1, pp. 169–174, 2014.

Y.-C. Liang and A. Smith, “An ant colony approach to the orienteering problem,” Journal of the Chinese Institute of Industrial Engineers, vol. 23, no. 5, pp. 403–414, 2006.

R. Pramudi, “Penerapan modified firefly algorithm pada orienteering problem,” Skripsi Jurusan Teknik Industri Universitas Katolik Parahyangan, 2018.

X.-S. Yang and S. Deb, “Cuckoo search via l´evy flights,” in World congress on nature & biologically inspired computing (NaBIC), 2009, pp. 210–214.

X.-S. Yang and S. Deb, “Engineering optimisation by cuckoo search,” International Journal of Mathematical Modelling and Numerical Optimisation, vol. 1, no. 4, pp. 330–343, 2010.

A. Gherboudj, A. Layeb, and S. Chikhi, “Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm,” International Journal of Bio-Inspired Computation, vol. 4, no. 4, pp. 229–236, 2012.

T. Tsiligirides, “Heuristic methods applied to orienteering,” Journal of the Operational Research Society, vol. 35, no. 9, pp. 797–809, 1984.




DOI: http://dx.doi.org/10.12962/j24775401.v7i2.8663

Refbacks

  • There are currently no refbacks.



View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.