Genetic Algorithms for solving some NP-hard hub location problems
| Title: | Genetic Algorithms for solving some NP-hard hub location problems |
| Author: | Stanimirović, Zorica |
| 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. 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. |
| URI: | http://hdl.handle.net/123456789/298 |
| Date: | 2007 |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
| phdZoricaStanimirovic.pdf | 666.6Kb |
View/ |