| dc.contributor.advisor |
Dugošija, Đorđe |
|
| dc.contributor.author |
Stanimirović, Zorica |
en_US |
| dc.contributor.other |
Kratica, Jozef |
|
| dc.date.accessioned |
2009-12-03T12:19:24Z |
|
| dc.date.available |
2009-12-03T12:19:24Z |
|
| dc.date.issued |
2007 |
|
| dc.identifier.uri |
http://hdl.handle.net/123456789/298 |
|
| dc.description.abstract |
U ovom radu opisani su različiti genetski algoritmi (GA) za rešavanje četiri
NP-teška hab lokacijska problema: problem p-hab medijane neograničenih
kapaciteta sa jednostrukim alokacijama (USApHMP), problem p-hab
medijane/centra ograničenih kapaciteta sa jednostrukim alokacijama
(CSApHMP/CSApHCP) i hab lokacijski problem ograničenih kapaciteta sa
jednostrukim alokacijama (CSAHLP). Ovi hab lokacijski problemi nalaze veliku
primenu u dizajniranju transportnih i telekomunikacijskih sistema, poštanskih i
drugih sistema isporuke, lokalnih i globalnih računarskih mreža, itd.
Za problem p-hab medijane neograničenih kapaciteta sa jednostrukim
alokacijama (USApHMP), razvijene su GA metode koje koriste dva različita
načina kodiranja i adekvatne modifikovane genetske operatore. U cilju
poboljšanja efikasnosti predloženih genetskih algoritama, primenjena je
hibridizacija oba GA koncepta sa heuristikom lokalnog pretraživanja, pa su tako
nastale hibridne HGA1 i HGA2 metode koje su veoma uspešne i pri rešavanju
problema velikih dimenzija.
Za rešavanje hab lokacijskih problema ograničenih kapaciteta CSApHMP,
CSApHCP i CSAHLP takođe su predložene razne verzije genetskih algoritama.
Primenjene su dve razičite reprezentacije rešenja i odgovarajući genetski
operatori razvijeni u skladu sa prirodom problema. Implementirani genetski
operatori čuvaju korektnost jedinki u tokom generacija GA i u smislu očuvanja
broja uspostavljenih habova i u smislu ograničenja kapaciteta habova.
Sve opisane genetske (evolutivne) metode testirane su na odgovarajućim
standardnim ORLIB instancama iz literature. Za sva četiri hab lokacijska
problema koja su razmatrana u ovom radu, predloženi (hibridni) genetski
algoritmi dostižu sve do sada poznate optimalne vrednosti na datim instancama
u zadovoljavajućem vremenu izvršavanja. U radu su data rešenja i za
probleme velikih dimenzija (n=100,200 p≤20) za koje optimalna rešenja nisu
poznata, a neki od ovih problema do sada nisu rešavani u literaturi. Dobijeni
rezultati predloženih GA metoda jasno ukazuju na značaj i potencijal genetskih
pristupa rešavanju hab i drugih lokacijskih problema. |
sr |
| dc.description.abstract |
In this paper some new genetic algorithms (GA) for solving four NP-hard hub
location problems are described: Uncapacitated Single Allocation p-hub Center
Problem (USApHCP), Capacitated Single Allocation p-hub Median/Center
Problem (CSApHMP/CSApHCP) and Capacitated Single Allocation Hub
Location Problem (CSAHLP). These hub ploblems have various applications in
designing transportation and telecommunications systems, postal and other
delivery systems, local and golobal computer area networks, etc.
For the Uncapacitated Single Allocation p-hub Center Problem (USApHCP),
two hybrid heuristic methods, named HGA1 and HGA2 are proposed. These
methods are a combination of a genetic algorithm and a generalization of the
well-known fast interchange heuristic (IH). In order to investigate the effect of
encoding on GA performance, two different encoding schemes are
implemented: binary encoding in HGA1, and integer representation in HGA2.
Modified genetic operators that keep the feasibility of individuals are designed
and implemented in both HGA1 and HGA2. The performed computational
experiments showed the effectiveness of both hybrid methods, even for solving
large-scaled problem instances
For the capacitated variants of hub location problems CSApHMP,
CSApHCP i CSAHLP, new genetic approaches are also described. In proposed
genetic algorithms, new encoding schemes are implemented with appropriate
objective functions. By using specific representation and modified genetic
operators, proposed GA approaches keep the feasibility of individuals, i.e. the
fixed number of established hubs and/or satisfying the capacity constraints on
hubs.
The numerical experiments were carried out on the standard hub data set
from the literature. For all four hub problems that were studied, the
corresponding GA method proved to be robust and efficient in solving the
problem instances with up to 200 nodes and 20 hubs. Computational
experiments demonstrate that
all proposed GA methods reach all previously known optimal solutions on tested
hub instances. The algorithm is also benchmarked on large scale hub instances
with n=100,200 nodes and p≤20 hubs that are not solved (to optimality) so far.
The presented computational results clearly indicate the usefulness of the
proposed GA approaches. |
en |
| dc.description.provenance |
Made available in DSpace on 2009-12-03T12:19:24Z (GMT). No. of bitstreams: 1
phdZoricaStanimirovic.pdf: 666693 bytes, checksum: 74fb71d1c0229d21c67a091b40357d36 (MD5) |
en |
| dc.publisher |
Belgrade |
en_US |
| dc.title |
Genetic Algorithms for solving some NP-hard hub location problems |
en_US |
| dc.title.alternative |
Genetski algoritmi za rešavanje nekih NP-teških hab lokacijskih problema |
sr |
| mf.subject.keywords |
Evolutivne metode, Hab lokacijski problemi, Genetski algoritmi,
Kombinatorna optimizacija |
sr |
| mf.subject.keywords |
Evolutionary Methods, Hub Location Problems, Genetic
Algorithms, Combinatorial Optimization |
en |
| mf.contributor.committee |
Tošić, Dušan; Dražić, Milan; |
|