Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F04%3APU46995" target="_blank" >RIV/00216305:26210/04:PU46995 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing

Original language description

In this paper the Integer Maximal Multicommodity Flow Problem is discussed. Multicommodity flow problems have many specific formulations depending on the constraints defined resulting in various applications in transportation, distribution and telecommunications. Since its integer version belongs to the class of NP-hard combinatorial problems, for large scale instances, it must be solved by approximation or heuristic techniques. We present a stochastic heuristic approach based on a simulated annealing aalgorithm. All evaluations of the objective function in this algorithm are provided by an allocation procedure. Since the allocation of the edge capacities among the commodities and the corresponding combined maximal flow depend on the order in which thecommodities are selected, the neighbouring mechanism in simulated annealing is set to generate permutations of commodities. Computational results show that, for suitable parameter settings presented in the paper, this approach is able to

Czech name

Řešení problému celočíselného maximálního víceproduktového toku v síti pomocí simulovaného žíhání

Czech description

V příspěvku je studován problém celočíselného maximálního víceproduktového toku v síti. Problémy víceproduktových toků v sítích mají řadu specifických formulací v závislosti na omezujících podmínkách, které mají nejrůznější aplikace v dopravě, distribucia telekomunikacích. Protože problém v celočíselné verzi patří do třídy NP-těžkých kombinatorických problémů, musí být pro velké rozsahy vstupních dat řešen aproximativními nebo heuristickými technikami. V příspěvku prezentujeme přístup využívající stochhastickou heuristickou metodu simulované žíhání. Všechny výpočty účelové funkce se v tomto algoritmu provádí pomocí speciální alokační procedury. Protože alokace kapacit hran různých produktů a jejich odpovídající kombinovaný maximální tok závisí na pořadí, v němž jsou produkty vybírány, je mechanismus výpočtu sousedního řešení v simulovaném žíhání nastaven na generování permutací produktů. Výsledky výpočtů ukazují, že pro vhodné nastavení parametrů, uvedené v příspěvku, je tento přístup

Type

C - Chapter in a specialist book

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Book/collection name

DAAAM International Scientific Book 2004

ISBN

3-901509-38-0

Number of pages of the result

10

Pages from-to

553-562

Number of pages of the book

—

Publisher name

DAAAM International Wien

Place of publication

Wien

UT code for WoS chapter

—