This thesis presents two new routing problems, both with objective functions focused on
relative positioning of teams during the routing horizon. The relative positioning results in
temporal and spatial dependencies among routes and is quantified with a nonlinear dispersion
metric, designed to evaluate the instantaneous distances among teams over a time
interval. This metric allows the design of objective functions to approximate teams during
routes execution, when minimized, or disperse them, when maximized. Both approximation
and dispersion are important routing characteristics in some practical applications, and
two new optimization problems are proposed with these opposite objectives. The first one
is a variation of the Multiple Traveling Salesman Problem, and its goal is to find a set of
tours where the salesmen travel close to each other, minimizing dispersion. A Local Search
Genetic Algorithm is proposed to solve the problem. It includes specialized genetic
operators and neighborhoods. A new set of benchmark instances is proposed, adapted for
the new problem from literature instances. Computational results show that the proposed
approach provides solutions with the desired characteristics of minimal dispersion. The
second problem is a bi-objective arc routing problem in which routes must be constructed
in order to maximize collected profit and dispersion of teams. The maximization of the dispersion
metric fosters the scattering of the teams during routing procedure. Usually, profit
and dispersion objectives are conflicting, and by using a bi-objective approach the decision
maker is able to choose a trade-off between collecting profits and scattering teams. Two
solution methods are proposed, a Multi-objective Genetic Algorithm and a Multi-objective
Genetic Local Search Algorithm, both specialized in order to exploit the characteristics of
the problem. It is demonstrated, by means of computational experiments on a new set of
benchmark instances, that the proposed approach provides approximation sets with the
desired characteristics. / Esta tese apresenta dois novos problemas de roteamento, ambos com funções objetivo
voltadas para o posicionamento relativo das equipes durante o horizonte de roteamento.
O posicionamento relativo resulta em uma dependência temporal e espacial entre rotas
e é quantificado com uma métrica de dispersão não-linear, projetada para avaliar as distâncias
instantâneas entre as equipes ao longo de um intervalo de tempo. Esta métrica
permite a concepção de funções objetivo para aproximar as equipes durante a execução
das rotas, quando minimizada, ou para dispersá-las, quando maximizada. Tanto a aproximação
quanto a dispersão são características importantes de roteamento em algumas
aplicações práticas, e dois novos problemas de otimização são propostos com esses objetivos
opostos. O primeiro é uma variação do Problema de Múltiplos Caixeiros Viajantes,
e seu objetivo é encontrar um conjunto de rotas em que os caixeiros viajam próximos uns
dos outros, minimizando a dispersão. Um Algoritmo Genético com Busca Local é proposto
para resolver o problema. Ele inclui operadores genéticos e vizinhanças especializados.
Um novo conjunto de instâncias é proposto, adaptado para o novo problema de instâncias
da literatura. Resultados computacionais mostram que a abordagem proposta proporciona
soluções com as características desejadas de dispersão mínima. O segundo problema é
um problema de roteamento de arcos biobjetivo em que as rotas devem ser construídas de
modo a maximizar o lucro recolhido e o distanciamento entre as equipes. A maximização
da métrica promove a dispersão das equipes durante a execução das rotas. Normalmente,
os objetivos de lucro e dispersão são conflitantes, e com uma abordagem biobjetivo o tomador
de decisão é capaz de avaliar a troca entre a coleta de lucros e a dispersão de equipes.
Dois métodos de solução são propostos, um Algoritmo Genético Multiobjetivo e um
Algoritmo Genético Multiobjetivo com Busca Local, ambos especializados para explorar as
características do problema. É demonstrado, por meio de experimentos computacionais
sobre um novo conjunto de instâncias, que a abordagem proposta fornece conjuntos de
aproximação com as características desejadas.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsm.br:1/3700 |
| Date | 26 August 2016 |
| Creators | Dhein, Guilherme |
| Contributors | Cardoso Junior, Ghendy, Buriol, Luciana Salete, Lyra Filho, Christiano, Santos, José Vicente Canto dos, Müller, Felipe Martins |
| Publisher | Universidade Federal de Santa Maria, Programa de Pós-Graduação em Engenharia Elétrica, UFSM, BR, Engenharia Elétrica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFSM, instname:Universidade Federal de Santa Maria, instacron:UFSM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 300400000007, 400, 300, 300, 300, 300, 300, 300, eed4f55e-1a74-47ce-afc0-4daa8655d8a3, 71217d64-5f3e-4e22-b7f4-b4a2a03c6f27, 570a09aa-4e05-4999-9101-aeb1271a4104, 977c3911-6a48-4c76-af8c-72ef96ff189c, a9530854-555a-4743-831e-76d18d8b80ee, e0fdea98-55da-42d1-a36a-e2c272902d52 |
Page generated in 0.0026 seconds