Problema de Roteamento de Veículo Suficientemente Próximo Assimétrico: Formulação e Heurística / Close-Enough Vehicle Routing Problem Asymmetric: Formulation and Heuristics
DOI:
https://doi.org/10.34117/bjdv5n12-140Keywords:
Roteamento de Veículos, Suficientemente Próximo, Heurística Geométrica.Abstract
Este trabalho propõe a versão assimétrica do Problema de Roteamento de Veículo Suficientemente Próximo, utilizado para planejamento de rotas de reconhecimento aéreo. O problema foi formulado com um modelo de programação cônica de segunda ordem e para solucioná-lo foram aplicadas técnicas de otimização heurística baseadas em uma propriedade geométrica. Também são descritos os resultados de experimentos computacionais extensivos de 240 instâncias adaptadas da literatura com até 20 pontos de observação. Destas, é possível encontrar resultados ótimos para 101 instâncias e os primeiros limites superiores para outras. Além disso, elaborou-se uma heurística baseada em clusterização, que utiliza propriedades geométricas em conjunto com o VNS. Os testes mostraram que o método proposto produz soluções de alta qualidade.
References
Arkin, E. M., & Hassin, R. (1994). Approximation algorithms for the geometric covering
salesman problem. Discrete Applied Mathematics, 55(3), 197–218.
Behdani, B., & Smith, J. C. (2014). An integer-programming-based approach to the close-
enough traveling salesman problem. INFORMS Journal on Computing, 26(3), 415–432.
Carrabs, F., Cerrone, C., Cerulli, R., & Gaudioso, M. (2017). A novel discretization scheme for
the close enough traveling salesman problem. Computers & Operations Research, 78, 163–171.
COIN-OR. (2016). Computational infrastructure for operations research project. Recuperado
em 17 de janeiro de 2018, de http://www.coin-or.org/.
Coutinho, W. P., Nascimento, R. Q. d., Pessoa, A. A., & Subramanian, A. (2016). A branch-
and-bound algorithm for the close-enough traveling salesman problem. INFORMS Journal on Computing, 28(4), 752–765.
de Berg, M., Gudmundsson, J., Katz, M. J., Levcopoulos, C., Overmars, M. H., & van der
Stappen, A. F. (2005). Tsp with neighborhoods of varying size. Journal of Algorithms, 57(1), 22–36.
Gendreau, M., Hertz, A., & Laporte, G. (1992). New insertion and postoptimization procedures
for the traveling salesman problem. Operations Research, 40(6), 1086–1094.
Gentilini, I., Margot, F., & Shimada, K. (2013). The travelling salesman problem with
neighbourhoods: Minlp solution. Optimization Methods and Software, 28(2), 364–378.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem.
Operations research, 22(2), 340–349.
Goldbarg, M. C., Goldbarg, E. F. G., & Luna, H. P. L. (2016). Otimização combinatória e
metaheurísticas: Algoritmos e apliacações. Rio de Janeiro - RJ, Brasil: Editora Elsevier.
Gulczynski, D. J., Heath, J. W., & Price, C. C. (2006). The close enough traveling salesman
problem: A discussion of several heuristics. Perspectives in Operations Research, 271–283.
LAE-UFRN. (2017). A-CEVRP - instances. Recuperado em 17 de janeiro de 2018, de
http://www.dimap.ufrn.br/lae/en/projects/ACEVRP.php.
López-Ibánez, M., Dubois-Lacoste, J., Stu¨tzle, T., & Birattari, M. (2011). The irace package:
Iterated racing for automatic algorithm configuration. IRIDIA, Universite Libre de Bruxelles, Brussels, Belgium, Tech. Rep. TR/IRIDIA/2011-004.
Mandle, J., & Goudon, J.-C. (1989, May 9). Method for determining the air speed of a
helicopter, system for carrying on this method and method for calibrating such air speed determining method and system. Google Patents. (US Patent 4,829,441).
Mennell, W., Golden, B., & Wasil, E. (2011). A steiner-zone heuristic for solving the close-
enough traveling salesman problem. In 2th INFORMS computing society conference: Operations Sesearch.
Mennell, W. K. (2009). Heuristics for solving three routing problems: Close-enough traveling
salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem (Tese de doutorado) University of Maryland, Maryland.
Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of
traveling salesman problems. Journal of the ACM (JACM), 7(4), 326–329.
Mitchell, J. S. (2007). A PTAS for TSP with neighborhoods among fat regions in the
plane. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 11-18). Society for Industrial and Applied Mathematics.
Mladenovic, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations
research, 24(11), 1097–1100.
Prins, C., Lacomme, P., & Prodhon, C. (2014). Order-first split-second methods for vehicle
routing problems: A review. Transportation Research Part C: Emerging Technologies, 40, 179–200.
Slattery, R., & Zhao, Y. (1997). Trajectory synthesis for air traffic automation. Journal of
Guidance Control and Dynamics, 20, 232–238.
Yuan, B., Orlowska, M., & Sadiq, S. (2007). On the optimal robot routing problem in wireless
sensor networks. IEEE Transactions on Knowledge and Data Engineering, 19(9), 1252– 1261.
