Algorytmiczne problemy lokalizacji wezłów na grafie wynikające z modelowania ruchu

• Autorzy: Kanadys P. , Żochowski A.

Warianty tytułu

EN

Algorithmic problems of nodes selction a graph resulting from traffic modelling

• Konferencja: III Międzynarodowa Konferencja Naukowo-Techniczna Systemy Logistyczne Teoria i Praktyka (III ; 10-12.09.2008 ; Spała, Polska)
• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrujemy zadania wyboru podzbioru wierzchołków grafu według szeregu kryteriów. Kryteria te odpowiadają potrzebom grawitacyjnych modeli generowania ruchu drogowego w mieście. Niektóre z tych zadań, chociaż łatwiejsze od problemu lokalizacji, nie były dotąd rozpatrywane. Sprowadzane są one do zadań programowania mieszanego i rozwiązywane dokładnie przy użyciu CPLEX 10.0 oraz SCIP 1.0. Ponieważ dla większej wymiarowości metody dokładne zawodzą, zaproponowano prosty algorytm genetyczny i porównano z metodami dokładnymi. Obliczenia testowe przeprowadzono dla losowych grafów płaskich, wygenerowanych przez specjalnie stworzony algorytm.

EN

In the paper we consider the problem of selecting the subset of vertices in the graph according to several criteria. These criteria correspond to the needs of gravitational traffic models for the city. Some of these problems were not studied previously, even if they are easier than facility location. They are reduced to mixed programming problems and solved exactly using CPLEX 10.0, and SCIP 1.0. Since bigger cases could not be solved in this way, a simple genetic algorithm was proposed and compared to exact methods. The numerical experiments were performed on random planar graphs, generated by specialy devised algorithm.

Słowa kluczowe

PL

modelowanie ruchu; lokalizacja węzłów na grafie

EN

traffic modelling; subsets of vertices; graph problems

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2008
• Tom: nr 4
• Strony: CD--CD
• Opis fizyczny: -pełny tekst, Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Kanadys P.

autor

Żochowski A.

• Instytut Badań Systemowych Polskiej Akademii Nauk 01-447 Warszawa, ul. Newelska 6,

Bibliografia

• [1] Alkhalifah Y., Wainwright R.L.: A genetic algorithm applied to graph problems involving subsets of vertices, Congress on Evolutionary Computation CEC2004, Vol. 1, 19-23 June 2004, pp. 303 – 308.
• [2] Charikar M., Guha S.: Improved combinatorial algorithms for facility location problems, SIAM Journal on Computing, 34, 803-824 (2005).
• [3] Feige U., Langberg M.: Approximation Algorithms for Maximization Problems Arising in Graph Partitioning, Journal of Algorithms, 41, 174–211 (2001).
• [4] Korupolu M.R., Plaxton G.C., Ramajaran R.: Analysis of a local search heuristic for facility location problems, Journal of Algorithms, 37, 146 -188 (2000).
• [5] Mihelic J., Robic B.: Solving the k-center Problem Efficiently with a Dominating Set Algorithm, Journal of Computing and Information Technology, 13, 225–233 (2005).
• [6] SCIP 1.0 (Solving Constraint Integer Programs), autorzy: Achterberg T., Berthold T., Koch T., Martin A., Wolter K., Konrad-Zuse-Zentrum für Informationstechnik, Berlin.