Actas de congresos
Experimental Evaluation Of Algorithms For The Orthogonal Milling Problem With Turn Costs
Registro en:
9783642206610
Lecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 6630 LNCS, n. , p. 304 - 314, 2011.
3029743
10.1007/978-3-642-20662-7_26
2-s2.0-79955829328
Autor
De Assis I.R.
De Souza C.C.
Institución
Resumen
This paper studies the Orthogonal Milling with Turn Costs. An exact algorithm is proposed based on an Integer Programming formulation of the problem. To our knowledge, this is the first exact algorithm ever proposed for the problem. Besides, a simple heuristic is also presented and an unprecedented experimentation involving these two algorithms and an existing approximation algorithm is carried out. We report and analyze the results obtained in these tests. Our benchmark instances are made public to allow for future comparisons. © 2011 Springer-Verlag. 6630 LNCS
304 314 Arkin, E.M., Bender, M.A., Demaine, E., Fekete, S.P., Mitchell, J.S.B., Sethia, S., Optimal covering tours with turn costs (2001) Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 138-147 Demaine, E.D., Mitchell, J.S.B., O'Rourke, J., The Open Problems Project, , http://maven.smith.edu/~orourke/TOPP, page visited in January, 2011 Arkin, E., Bender, M., Demaine, E., Fekete, S., Mitchell, J., Sethia, S., Optimal covering tours with turn costs (2005) SIAM Journal on Computing, 35 (3), pp. 531-566 Clossey, J., Laporte, G., Soriano, P., Solving arc routing problems with turn penalties (2001) Journal of the Operational Research Society, 52, pp. 433-439 Benavent, E., Soler, D., The directed rural postman problem with turn penalties (1999) Transportation Science, 30 (4), pp. 408-418 Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1 (2), pp. 169-197 Ben-Arieh, D., Gutin, G., Penn, M., Yeo, A., Zverovitch, A., Transformations of generalized ATSP into ATSP (2003) Operations Research Letters, 31 (5), pp. 357-365 Bondy, J.A., Murty, U.S.R., (1976) Graph Theory with Applications, , Elsevier Science, New York Resende, M.G., Ribeiro, C.C., Greedy randomized adaptive search procedures: Advances, hybridizations, and applications (2010) Handbook of Metaheuristics. International Series in Operations Research and Management Science, 146, pp. 283-319. , Gendreau, M., Potvin, J.Y. (eds.) Springer, US Kolmogorov, V., Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009) Mathematical Programming Computation, 1 (1), pp. 43-67