A carregar...
Publicação
Uma heurística para um problema de localização de hubs com capacidades
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 3.76 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Num problema de localização de hubs existe um conjunto de nós, que devem efetuar trocas
de fluxo entre si. Estas trocas poder-se-iam realizar através do transporte direto entre
todos os nós, no entanto este tipo de solução não é eficiente porque requermuitas ligações.
Uma solução mais eficiente, consiste em selecionar um subconjunto de nós, para serem
hubs, tendo estes como função receber fluxo proveniente de outros nós, eventualmente
processá-lo e redireciona-lo para outros hubs, ou para o seu destino final.
A utilização deste tipo de solução permite reduzir os custos de transporte, pois envolve
um menor número de ligações diretas entre pares de nós. Adicionalmente, a circulação
de maiores quantidades de fluxo entre hubs permite a utilização de veículos de maior
capacidade, podendo usufruir-se dos benefícios das economias de escala.
Assim, num problema de localização de hubs o objetivo consiste em determinar o
subconjunto de nós, onde devem ser instalados os hubs, a afetação dos restantes nós aos
hubs e o modo de enviar o fluxo na rede, de modo a otimizar uma dada função objetivo.
Estes problemas têm sido aplicados em várias áreas, entre as quais se destacam as
áreas do transporte, das telecomunicações e da recolha e distribuição de correio.
Nesta dissertação estudou-se um problema de localização de hubs com dois tipos de
capacidades tendo-se adaptado a este novo problema uma formulação existente na literatura
para o problema clássico de localização de hubs com capacidades. Desenvolveu-se
também para o problema em estudo um algoritmo genético com chaves aleatórias enviesadas.
A formulação e o algoritmo foram testados computacionalmente num conjunto
de instâncias de teste. Com o algoritmo foi possível determinar soluções admissíveis para
todas as instâncias, enquanto que a formulação não permitiu obter soluções para algumas
instâncias de maior dimensão dentro do tempo limite estabelecido.
In a hub location problem, there is a set of nodes that must exchange flows. These exchanges could be carried out through direct transport between nodes, however this type of solution is not efficient because it requires a huge number of connections. A more efficient solution consists of selecting a subset of nodes to be hubs, with the function of receiving flow from other nodes and redirecting it to other hubs, or to its final destination. The use of this type of solution makes it possible to reduce transportation costs, as it involves a smaller number of direct connections between nodes. Additionally, the circulation of greater amounts of flow between hubs allows the use of vehicles with larger capacity, making it possible to take advantage of the benefits of scale economies. Hence, in a hub location problem, the objective is to determine the subset of nodes, that should become hubs, the assignment of the other nodes to the hubs and the routing of the flow in the network, in order to optimize an objective function, that typically consist on the minimization of the total costs. These problems have been applied in several areas, such as transportation, telecommunications and mail delivery. In this dissertation, a hub location problem with two types of capacities was studied, for which we adapted a formulation existing in the literature for the classic capacitated hub location problem. A Biased Random Key Genetic Algorithm was also developed for the problem under study. The formulation and the algorithm were computationally tested on a set of test instances. With the algorithm it was possible to determine feasible solutions for all instances, while the formulation did not allow to obtain solutions for some larger instances within the established time limit.
In a hub location problem, there is a set of nodes that must exchange flows. These exchanges could be carried out through direct transport between nodes, however this type of solution is not efficient because it requires a huge number of connections. A more efficient solution consists of selecting a subset of nodes to be hubs, with the function of receiving flow from other nodes and redirecting it to other hubs, or to its final destination. The use of this type of solution makes it possible to reduce transportation costs, as it involves a smaller number of direct connections between nodes. Additionally, the circulation of greater amounts of flow between hubs allows the use of vehicles with larger capacity, making it possible to take advantage of the benefits of scale economies. Hence, in a hub location problem, the objective is to determine the subset of nodes, that should become hubs, the assignment of the other nodes to the hubs and the routing of the flow in the network, in order to optimize an objective function, that typically consist on the minimization of the total costs. These problems have been applied in several areas, such as transportation, telecommunications and mail delivery. In this dissertation, a hub location problem with two types of capacities was studied, for which we adapted a formulation existing in the literature for the classic capacitated hub location problem. A Biased Random Key Genetic Algorithm was also developed for the problem under study. The formulation and the algorithm were computationally tested on a set of test instances. With the algorithm it was possible to determine feasible solutions for all instances, while the formulation did not allow to obtain solutions for some larger instances within the established time limit.
Descrição
Palavras-chave
Hubs localização de hubs com capacidades programação linear inteira mista heurística algoritmo genético com chaves aleatórias enviesado