Column Generation Algorithms
Mostrando 1-11 de 11 artigos, teses e dissertações.
-
1. COLUMN GENERATION BASED ALGORITHMS FOR THE CAPACITATED MULTI-LAYER NETWORK DESIGN WITH UNSPLITTABLE DEMANDS
ABSTRACT We investigate a variant of the Multi-Layer Network Design problem where minimum cost capacities have to be installed upon a virtual layer in such a way that (i) a set of traffic demands can be routed AND (ii) each capacity (subband) is assigned a route in the physical layer. The traffic demands cannot be splitted along several paths (nor even sever
Pesqui. Oper.. Publicado em: 2017-09
-
2. COST-EFFECTIVE BANDWIDTH PROVISIONING IN MICROWAVE WIRELESS NETWORKS UNDER UNRELIABLE CHANNEL CONDITIONS
ABSTRACT Cost-effective planning and dimensioning of backhaul microwave networks under unreliable channel conditions remains a relatively underexplored area in the literature. In particular, bandwidth assignment requires special attention as the transport capacity of microwave links is prone to variations due to, e.g., weather conditions. In this paper, we f
Pesqui. Oper.. Publicado em: 2017-09
-
3. MODELS AND ALGORITHMS TO THE TEAM ORIENTEERING PROBLEM / MODELOS E ALGORITMOS PARA O TEAM ORIENTEERING PROBLEM
O Team Orienteering Problem é um problema de roteamento de veículos sobre um grafo com durações associadas aos arcos e prêmios atribuídos à visitação de cada vértice. Neste problema, considera-se que as visitas são realizadas por uma frota com um número fixo de veículos idênticos e que existe uma duração total máxima para as rotas serem fina
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 12/09/2011
-
4. Heurísticas e algoritmo exato para o problema de roteamento de veículos com coleta e entrega simultâneas
This work adresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery, where routes must be devised to fulfil the pickup and delivery requests of a set of customers. Each customer must be served by only one route, the load it receives isbrought from a central depot, to where the picked-up load is also taken. The capacity of the used vehicles m
Publicado em: 2010
-
5. Algoritmos para problemas de corte e empacotamento / Algorithms for cutting and packing problems
Several versions of Cutting and Packing problems are considered NP-hard and, if we consider that P ¿ NP, we do not have any exact polynomial algorithm for solve them. Practical applications arises for such problems and include: resources allocation for computers; cut of steel, wood, glass, aluminum, etc.; packing of objects; and, loading objects into contai
Publicado em: 2010
-
6. Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade / Column generation heuristics for capacitated lotsizing problem
The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation,
Publicado em: 2009
-
7. O metodo de geração de colunas aplicado a problemas de otimização em grafos / Column generation technique applied to graph optimization problems
In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem
Publicado em: 2009
-
8. Algoritmos para problemas de empacotamento / Algorithms for packing problems
In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We
Publicado em: 2006
-
9. AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM / UM ALGORITMO DE GERAÇÃO DE COLUNAS E CORTES PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS
The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80
Publicado em: 2004
-
10. MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES / MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS
This dissertation tackles the Generalized Assignment Problem (PAG), models and algorithms are studied and proposed. This work was motivated by a real world application: the Truck Loading Problem (PCC). Research was done on approximated (metaheuristics) and exact algorithm for solving the PAG. The approximated algorithms proposed were based on a recent idea f
Publicado em: 2003
-
11. Problemas de escalonamento no transporte coletivo : programação por restrições e outras tecnicas
This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the problem is usualIy divided in two distinct subproblems, namely: crew sched
Publicado em: 2000