Publication detail
Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing
ŠEDA, M.
Czech title
Řešení problému celočíselného maximálního víceproduktového toku v síti pomocí simulovaného žíhání
English title
Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing
Type
book chapter
Language
en
Original abstract
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 algorithm. 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 the commodities 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 find the optimal solution almost in all cases or at least a solution very close to optimum when the test is executed several times. Furthermore, the proposed algorithm is stable because even the average results gained from all the executions are close to optimum.
Czech abstract
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ě, distribuci a 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í stochastickou 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 schopen najít optimální řešení téměř ve všech případech anebo alespoň řešení blízké optimu, pokud je výpočet spuštěn několikrát. Navíc navržený algoritmus je stabilní, protože průměrné výsledky získané ze všech výpočtů jsou rovněž blízké optimu.
English abstract
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 algorithm. 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 the commodities 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 find the optimal solution almost in all cases or at least a solution very close to optimum when the test is executed several times. Furthermore, the proposed algorithm is stable because even the average results gained from all the executions are close to optimum.
Keywords in English
Multicommodity network flow, integer programming, NP-hard problems, stochastic heuristics, simulated annealing, neighbourhood operation
RIV year
2004
Released
01.10.2004
Publisher
DAAAM International Wien
Location
Wien
ISBN
3-901509-38-0
ISSN
1726-9687
Book
Katalinic, B. (ed.): DAAAM International Scientific Book 2004
Journal
DAAAM International Scientific Book
Pages count
10
BIBTEX
@inbook{BUT55521,
author="Miloš {Šeda},
title="Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing",
journal="DAAAM International Scientific Book",
booktitle="Katalinic, B. (ed.): DAAAM International Scientific Book 2004",
year="2004",
month="October",
publisher="DAAAM International Wien",
address="Wien",
isbn="3-901509-38-0",
issn="1726-9687"
}