UFES

Please use this identifier to cite or link to this item: http://repositorio.ufes.br/handle/10/6358
Title: Uma abordagem heurística para o problema de otimização de distrito postal
Authors: Fiório, Rafael Carpanedo
Keywords: serviço postal;simulated annealing (matemática);teoria dos grafos;envoltória convexa;otimização combinatória;postal district;simulated annealing (mathematics);convex hull
Issue Date: 23-Jun-2006
Publisher: Universidade Federal do Espírito Santo
Citation: FIÓRIO, Rafael Carpanedo. Uma abordagem heurística para o problema de otimização de distrito postal. 2006. 87 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Espírito Santo, Vitória, 2006.
Abstract: This study proposes a strategia solution for the optimized construction of postal districts. Postal District is a set of segments of publics areas connecteds. Given a locality composed of uncounted segments of publics areas, this study proposes an arrangement of connects subgroups of publics areas with the goal of composing a postal district. The strategy is to transform the system of public areas of a place in a graph and from this graph, to extract their respective cyclical subgraphs that are understood as atomics entities. Those atomics entities are submited by an assembly process until compose a group of postal districts. The methodology here presented divides the study in two different phases: the first one understands the process of obtaining of the cyclical subgraphs; and the second one is understood as the assembly process of postal district The process of obtaining of cyclical subgraph consists in the obtaining of the hull convex of the graph and subsequent extracting up the cyclical subgraphs tangent to edge of that. That is, in a sequential way, in other words, it is determined the first convex hull of the graph and extract up their respective tangent subgraphs; it is determined the second convex hull and extract up their subgraphs and so forth. The study of determination of the convex hull and extracting of the cyclical subgraphs is done through operations of the computational geometry. The process of construction of the postal districts is given through the clustering of the cyclicals subgraphs, using as a tool the meta- heuristic Simulated Annealing. The Chinese Postman's Problem and Capacited Chinese Postman's Problem are formulations support for the present study. The main objective of the study is to obtain, in a fast and efficient way the optimized postal district, with smaller unproductive course possible, offering agility for the process of domiciliary distribution of postal objects.
URI: http://repositorio.ufes.br/handle/10/6358
Appears in Collections:PPGI - Dissertações de mestrado

Files in This Item:
File SizeFormat 
dissertacao.pdf2.58 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.