Automatic selection of generating nodes in the traffic model based on k shortest paths

• Autorzy: Kanadys P. , Żochowski A.

Warianty tytułu

PL

Automatyczny dobór węzłów generujących w modeln ruchu opartym na knajkrótszych drogach

• Języki publikacji: EN

Abstrakty

EN

In the paper, we consider the problem of selecting the subset of vertices in the graph according to two criteria. These criteria correspond to the needs of gravitational trafik 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. 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 given network.

PL

W pracy badamy zadanie wyboru podzbioru węzłów grafu według dwóch kryteriów. Odpowiadają one potrzebom grawitacyjnego modelu ruchu w mieście. Niektóre z tych problemów nie były dotąd badane, chociaż są łatwiejsze od zadania lokalizacji centrów obsługowych. Zadania te są sprowadzane do problemu programowania mieszanego i rozwiązywane. Ponieważ przypadków o większych rozmiarach nie da się w ten sposób rozwiązać, zaproponowano prosty algorytm genetyczny i porównano jego wyniki z dokładnymi. Eksperymenty numeryczne przeprowadzono na zadanych sztucznie sieciach.

Słowa kluczowe

EN

traffic modelling; subsets of vertices; graph problems

PL

modelowanie ruchu; podzbiory węzłów; zadania lokalizacji

• Wydawca: Warsaw University of Technology, Faculty of Transport
• Czasopismo: Archives of Transport
• Rocznik: 2009
• Tom: Vol. 21, iss.1-2
• Strony: 65--83
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Kanadys P.

autor

Żochowski A.

• Politechnika Warszawska, Wydział Transportu, 00-662 Warszawa, ul. Koszykowa 75, doktorant

Bibliografia

• 1. Alkhalifah Y., Wainwright R.L.: A genetic algorithm applied to graph problems involving subsets of vertices. Congress on Evolutionary Computation CEC2004, 1, 19-23 June 2004, pp. 303-308, 2004.
• 2. BerindeV.: Iterative Approximation of Fixed Points. Springer 2007.
• 3. Charikar M., Guha S.: Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34, pp. 803-824, 2005.
• 4. Datka S., Suchorzewski W., Tracz M.: Inżynieria ruchu. WKiŁ, Warszawa, 1999.
• 5. Dybicz T.: Pakiet oprogramowania VISUM jako narzędzie do modelowania ruchu transportu publicznego w Warszawie. Transport publiczny w Warszawie 2005. Presentation at the Conference "Transport publiczny w Warszawie", 11 October 2005, organized by City Council.
• 6. Feige U., Langberg M.: Approximation Algorithms for Maximization Problems Arising in Graph Partitioning. Journal of Algorithms, 41, pp. 174-211,2001.
• 7. Hershberger J., Maxel M., Suri S.: Finding the Shortest Simple Paths: A New Algorithm and its Implementation. Networks, 46, No. 2, September 2005, pp. 98-109, 2005.
• 8. Korupolu M.R., Plaxton G.C., Ramajaran R.: Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37, pp. 146-188,2000.
• 9. Marcotte P., Patriksson M.: Traffic Equilibrium. Handbooks in Operations Research and Management Science, 14, Barnhart c., Laporte G. eds, North-Holland, pp. 623-713, Amsterdam, 2007.
• 10. Mihelic J., Robie B.: Solving the k-center Problem Efficiently with a Dominating Set Algorithm. Journal of Computing and Information Technology, 13, pp. 225-233, 2005.
• 11. Patriksson M.: The Traffic Assignment Problem - Models and Methods. Topies In Transportation, VSP, Utrecht, 1994 (also available as PDF, www.cs.chalmers.se/-mipat/traffic.html).
• 12. SCIP 1.0 (Solving Constraint Integer Programs). autorzy: Achterberg T., Berthold T., Koch T., Martin A., Wolter K., Konrad-Zuse-Zentrum fur Informationstechnik, Berlin.
• 13. Rutkowska D., Piliński M., Rutkowski L.: Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. PWN, Warszawa, 1999.