HEURISTICS FOR THE NETWORK DESIGN PROBLEM WITH DISCRETE COST FUNCTIONS / HEURÍSTICAS PARA O PROJETO DE REDES COM FUNÇÕES DE CUSTO DISCRETAS
AUTOR(ES)
DANIEL ALOISE
DATA DE PUBLICAÇÃO
2005
RESUMO
Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.
ASSUNTO(S)
network flows funcoes de custo discretas fluxos em redes otimizacao combinatoria heuristica multicommodity flows redes multifluxos combinatorial optimization discrete cost functions heuristics
