ALGORITMO GENÉTICO BASEADO EM CHAVES ALEATÓRIAS PARA O ORIENTEERING PROBLEM WITH TIME WINDOWS
DOI:
https://doi.org/10.26512/ripe.v2i10.21730Keywords:
BRKGA. MultiStart. OPTW. TTDP.Abstract
The Trip Design Problem (TTDP) is a computational problem related to path planning among points of interests in a touristic area. It can be modeled as a well-known routing problem called Orienteering Problem with Time Windows (OPTW) in which a given positive profit and time interval are associated with each location. This paper approaches OPTW suggesting a comparison between two different methods to solve it: Biased Random Key Genetic Algorithm (BRKGA) and MultiStart. Both techniques use a local search with four steps, based on the lasts solutions proposed to this problem. Computational experiments were executed on traditional instances. The tests showed that the BRKGA method achieved larger or same results than MultiStart for all the 76 instances evaluated. Furthermore, were found 21 new best solutions for OPTW instances, in comparison with the current literature.
References
Arulselvan, A., Commander, C.,& Pardalos, P., 2007. A random keys based genetic algorithm for the target visitation problem.Pardalos, P., Murphey, R.,Grundel, D. & Hirsch, M., eds, Advances in Cooperative Control and Optimization, vol. 369 of Lecture Notes in Control and Information Sciences, pp. 389”“397. Springer.
Buriol, L. S.,Resende, M. G. C., Ribeiro, C. C.,&Thorup, M., 2005. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks, 46:36”“56.
Buriol, L. S.,Resende, M. G. C.,&Thorup, M., 2007. Survivable IP network design with OSPF routing. Networks, 49:51”“64.
Cura, T., 2014. An artificial bee colony algorithm approach for the team orienteering problem with time windows.Computers & Industrial Engineering, vol. 74, pp. 270”“290.
Gambardella, L. M., Montemanni, R., &Weyland, D., 2012. Coupling ant colony systems with strong local searches.European Journal of Operational Research,vol. 220, n. 3, pp. 831”“843.
Gendreau, M., Laporte, G., &Semet, F., 1998. A tabu search heuristic for the undirected selective travelling salesman problem.European Journal of Operational Research, vol. 106, n. 2-3, pp. 539”“545.
Golden, B. L., Levy, L., & Vohra, R., 1987.The orienteering problem. Naval Research Logitics, vol. 34, n. 3, pp. 307”“318.
Gonçalves, J. F., Mendes, J. J. M.,& Resende, M. G. C., 2005. A hybrid genetic algorithm for the job shop scheduling problem.European Journal of Operational Research, vol. 167, n. 1, pp. 77”“95.
Gonçalves, J. F. &Resende, M. G. C., 2004. An evolutionary algorithm for manufacturing cell formation.Computers and Industrial Engineering, vol. 47, pp. 247”“273.
Gonçalves, J. F., &Resende, M. G. C., 2009. Biased random-key genetic algorithms for combinatorial optimization. To appear in J. of Heuristics, v. 17, n. 5, pp. 487-525.
Goulart, N., Noronha, T. F., de Souza, S. R.,&Dias, L. G. S., 2011. Algoritmo Genético para o Problema de Instalação de Fibras em Redes Óticas. XLIII Simpósio Brasileiro de Pesquisa Operacional, Ubatuba.
Goulart, N., Noronha, T. F., de Souza, S. R.,& Dias, L. G. S., 2011. Biased Random-key Genetic Algorithm for Fiber Installation in Optical Network Optimization. 2011 IEEE Evolutionary Computation,New Orleans, LA, 2011, pp. 2267-2271.
Gunawan, A., Lau, H. C., &Lu, K., 2015a. An iterated local search algorithm for solving the orienteering problem with time windows.In Ochoa, G., Chicano, F., eds,Evolutionary Computation in Combinatorial Optimization, vol. 9026 of Lecture Notes in Computer Science (Springer), pp. 61”“73.
Gunawan, A., Lau, H. C., &Lu, K., 2015b. SAILS: hybrid algorithm for the team orienteering problem with time windows. In Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015). Prague, Czech Republic,pp. 276”“295.
Gunawan, A., Lau, H. C., &Lu, K., 2015c. Well-tuned ILS for extended team orienteering problem with time windows.LARC technical report series, SingaporeManagement University.
Gunawan, A., Lau, H. C., &Lu, K., 2015d. The latest best known solutions for the TeamOrienteering Problem with Time Windows (TOPTW)benchmark instances. Disponível em http://research.larc.smu.edu.sg/downloads/OPLib/Publications/SupplementTOPTW.pdf. Acesso em 15 de junho de 2016.
Gunawan, A., Lau, H. C.,&Vansteenwegen, P., 2016. Orienteering Problem: A survey of recent variants, solution approaches and applications.European Journal of Operational Research, vol. 255, n.2, pp.315”“332.
Hu, Q.,& Lim, A., 2014. An iterative three-component heuristic for the team orienteering problem with time windows.European Journal of Operational Research, vol. 232, n. 2, pp. 276”“286.
Kantor, M. G., &Rosenwein, M. B., 1992. The Orienteering Problem with Time Windows.The Journal of the Operational Research Society, vol. 43, n. 6, pp. 629”“635.
Labadie, N., Mansini, R., Melechovsk`y, J., WolflerCalvo, R., 2011. Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, vol. 17, n. 6, pp. 729”“753.
Labadie, N., Mansini, R., Melechovský, J., &WolflerCalvo, R., 2012. The team orienteering problem with time windows: an LP-based granular variable neighborhood search. European Journal of Operational Research, vol. 220, n. 1, pp. 15”“27.
Lin, S. W., Yu,& V. F., 2012. A simulated annealing heuristic for the team orienteering problem with time windows.European Journal of Operational Research, vol. 217, n. 1, pp. 94”“107.
Malve, S., &Uzsoy, R., 2007. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, v. 34, p. 3016”“3028.
Noronha, T. F.,Resende, M. G. C., &Ribeiro, C. C., 2010. A biased random-key genetic algorithm for routing and wavelength assignment.Journal of Global Optimization, vol. 50, n. 3, pp. 503-518.
Reis, R.,Ritt, M.,Buriol, L. S., &Resende, M. G. C., 2011. A biased random-key genetic algorithm for ospf and deft routing to minimize network congestion. International Transactions in Operational Research, vol. 18, pp. 401”“423.
Samanlioglu, F., Ferrell, W. G.Jr.,&Kurz, M. E., 2008. A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem. Computers & Industrial Engineering, v. 55, n. 2, p. 439”“449.
Snydera, L. V., &Daskin, M. S., 2006. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, vol. 174, pp. 38”“53.
Souffriau, W., Vansteenwegen, P., VandenBerghe, G., & Van Oudheusden, D.,2013. The multiconstraint team orienteering problem with multiple time windows.Transportation Science, vol. 47, n. 1, pp. 53”“63.
Spears, W.,de Jong, K., 1991. On the virtues of parameterized uniform crossover.Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230”“236, San Mateo.
The Orienteering Problem: Test Instances, 2011. Disponível em http://www.mech.kuleuven.be/en/cib/op. Acessado em 15 de junho de 2016.
Toso, Rodrigo F., Resende, Mauricio G. C., 2015. A C++ Application Programming Interface for Biased Random-Key Genetic Algorithms. Optimization Methods and Software, vol. 30, n. 1, pp. 81-93.
Tsiligirides, T., 1984.Heuristic methods applied to orienteering.Journal of the Operational Research Society, vol. 35, n. 9, pp. 797”“809.
Vansteenwegen, P., Souffriau, W., &Van Oudheusden, D., 2011.The Orienteering Problem: a Survey.European Journal of Operational Research, vol. 209, n. 1, pp. 1”“10.
Vansteenwegen, P., Souffriau, W., VandenBerghe, G., & Van Oudheusden, D.,2009. Iterated local search for the team orienteering problem with time windows.Computers & Operations Research, vol. 36, n. 12, pp. 3281”“3290.
Vansteenwegen, P., &Van Oudheusden, D., 2007.The mobile tourist guide: An OR opportunity.Operational Research Insight, vol. 20, n. 3, pp. 21”“27.
Downloads
Published
Issue
Section
License
Given the public access policy of the journal, the use of the published texts is free, with the obligation of recognizing the original authorship and the first publication in this journal. The authors of the published contributions are entirely and exclusively responsible for their contents.
1. The authors authorize the publication of the article in this journal.
2. The authors guarantee that the contribution is original, and take full responsibility for its content in case of impugnation by third parties.
3. The authors guarantee that the contribution is not under evaluation in another journal.
4. The authors keep the copyright and convey to the journal the right of first publication, the work being licensed under a Creative Commons Attribution License-BY.
5. The authors are allowed and stimulated to publicize and distribute their work on-line after the publication in the journal.
6. The authors of the approved works authorize the journal to distribute their content, after publication, for reproduction in content indexes, virtual libraries and similars.
7. The editors reserve the right to make adjustments to the text and to adequate the article to the editorial rules of the journal.
