Brasil | Actas de congresos

Experimental Evaluation Of Algorithms For The Orthogonal Milling Problem With Turn Costs

dc.creatorDe Assis I.R.
dc.creatorDe Souza C.C.
dc.date2011
dc.date2015-06-30T20:38:30Z
dc.date2015-11-26T14:52:27Z
dc.date2015-06-30T20:38:30Z
dc.date2015-11-26T14:52:27Z
dc.date.accessioned2018-03-28T22:04:31Z
dc.date.available2018-03-28T22:04:31Z
dc.identifier9783642206610
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 6630 LNCS, n. , p. 304 - 314, 2011.
dc.identifier3029743
dc.identifier10.1007/978-3-642-20662-7_26
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-79955829328&partnerID=40&md5=06ce89a64b3e9cd48d9efd81abc535c1
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/108748
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/108748
dc.identifier2-s2.0-79955829328
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1254826
dc.descriptionThis 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.
dc.description6630 LNCS
dc.description
dc.description304
dc.description314
dc.descriptionArkin, 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
dc.descriptionDemaine, E.D., Mitchell, J.S.B., O'Rourke, J., The Open Problems Project, , http://maven.smith.edu/~orourke/TOPP, page visited in January, 2011
dc.descriptionArkin, 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
dc.descriptionClossey, J., Laporte, G., Soriano, P., Solving arc routing problems with turn penalties (2001) Journal of the Operational Research Society, 52, pp. 433-439
dc.descriptionBenavent, E., Soler, D., The directed rural postman problem with turn penalties (1999) Transportation Science, 30 (4), pp. 408-418
dc.descriptionGrötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1 (2), pp. 169-197
dc.descriptionBen-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
dc.descriptionBondy, J.A., Murty, U.S.R., (1976) Graph Theory with Applications, , Elsevier Science, New York
dc.descriptionResende, 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
dc.descriptionKolmogorov, V., Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009) Mathematical Programming Computation, 1 (1), pp. 43-67
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleExperimental Evaluation Of Algorithms For The Orthogonal Milling Problem With Turn Costs
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución