Detail publikace

Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing

ŠEDA, M.

Originální název

Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing

Typ

kapitola v knize

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova v angličtině

Multicommodity network flow, integer programming, NP-hard problems, stochastic heuristics, simulated annealing, neighbourhood operation

Autoři

ŠEDA, M.

Rok RIV

2004

Vydáno

1. 10. 2004

Nakladatel

DAAAM International Wien

Místo

Wien

ISBN

3-901509-38-0

Kniha

Katalinic, B. (ed.): DAAAM International Scientific Book 2004

Edice

DAAAM International Scientific Book 2004

ISSN

1726-9687

Periodikum

DAAAM International Scientific Book

Stát

Rakouská republika

Strany od

553

Strany do

562

Strany počet

10

BibTex

@inbook{BUT55521,
  author="Miloš {Šeda}",
  title="Solving the Integer Maximal Multicommodity Flow Problem Using Simulated Annealing",
  booktitle="Katalinic, B. (ed.): DAAAM International Scientific Book 2004",
  year="2004",
  publisher="DAAAM International Wien",
  address="Wien",
  series="DAAAM International Scientific Book 2004",
  pages="10",
  isbn="3-901509-38-0"
}